What is the impact of synchronisation overhead on parallel speedup? [closed]

When implementing a parallel version of an algorithm, what is the impact of synchronization delays on speedup efficiency? Does this depend on the platform used?

Is coarse-grained parallelism better than fine-grained parallelism in certain situations?

• 1) You question is way too broad. 2) Note that "speedup" and "efficiency" are typically used to describe different things. E.g. a brute-force search for TSP can be (embarassingly) parallelised for maximum speedup but is not efficient. 3) Should this be on Computational Science? – Raphael Aug 6 '13 at 9:12
• "3) Should this be on Computational Science?" Yes. "2) Note that "speedup" and "efficiency" are typically used to describe different things. E.g. a brute-force search for TSP can be (embarassingly) parallelised for maximum speedup but is not efficient." Effectively, maybe we could use the term "efficient speedup", meaning a speedup greater than one... – user7060 Aug 6 '13 at 9:39
• You can use the words in whichever way you want, just be aware that they will probably mean different things in literature. (Speedup > 1 is a low bar indeed.) Do you want me to migrate to Computational Science? – Raphael Aug 6 '13 at 10:11
• I don't understand, this location is not correct ? Synchronisation aspects seems Ok for this forum... – user7060 Aug 6 '13 at 12:32
• You want specific answers for select languages and platforms -- that's not our game. If you have a general question (I tried to make your post one) it's fine here, although then I'm tempted to judge "too broad" here. So you should find a specific question (maybe a concrete algorithm you want to parallelise) that can be answered independently of language and machine (but depending on models, obviously, say "shared memory" or the like). – Raphael Aug 6 '13 at 13:47

For current multicore CPUs with support for SMT (Simultaneous Multi Threading), coarse-grained parallelism is strictly required, independently of the parallel technology used (pthreads, OpenMP, MPI). You need to feed each thread or process with enough work, otherwise the cost of thread creation/management and synchronization (for Pthreads and OpenMP) or the cost of communication and synchronization (for MPI processes) will be much higher than the work done per thread/process.

For GPUs, since these are actually SIMD units, i.e., data parallel machines, you need to feed them with data according to a fine-grained data decomposition (again, this is independent from the actual technology used, such as CUDA or OpenCL). In this case, thread management is lower (because it is done in hardware, not in software), but in general synchronization must be avoided, as much as possible. If you can not restructure your code so as to avoid synchronization you are going to experience bad performances on GPUS. Both NVIDIA and AMD recommend to avoid synchronization and to use GPUs for very simple data parallel tasks. Moreover, you need to copy the data to be processed from the host to the GPU and back once results are computed, and this will also incur a performance penalty, depending on the size of your data processed by the GPU device.

There is no general answer to this question. There certainly are situations where coarse-grain parallelism is better than fine-grain parallelism.

It is important to note that the efficiency of an algorithm depends not only on the problem but also on the environment. You usually want to break down your work in pieces of sensible size and let the environment (e. g. the JVM) determine the optimal number of parallel executions. Do benchmarks on different setups and with different parameters to your algorithm and you will see if your assumptions are right. There really is no substitute for testing here.

Edit: I must admit I never did anything serious with CUDA nor with OpenCL. I guess similar rules apply but I will be happy if you correct me.

• In fact. what do you think about the parallelization of the evaluation of the following expression $13 \times 15 \times 17 \times 19$ ? It seems that two threads can compute at the same time $195=13 \times 15$ and $323=17 \times 19$, then at a second step one thread can compute $195 \times 323$. So in two steps we can compute the result, whereas in the sequential version we need 3 steps. If we implement the parallel version with pthread and compare the performance in comparison to the sequential version, we will obtain a speedup below $1$. – user7060 Aug 5 '13 at 13:11
• Assuming your last sentence was a question I think the answer is no. Creating threads is a very expensive operation which will not pay-off for such fine-grainded parallelisation. If you use a thread pool it would certainly be executed in one thread. – Paul Aug 5 '13 at 13:21
• If your referring to Amdahl's law you should not forget to include all thread/process management operations into the total number of operations. You will see that the amount of work that can be parallelised (your computation) is insignificantly low. – Paul Aug 5 '13 at 13:25
• We may even suppose that the threads are already created and measure the run time. Why do you say that if we use a thread pool it would certainly be executed with one thread ? I don't understand that, that should be two as often as one thread... – user7060 Aug 5 '13 at 14:28
• I fear I mixed that up a bit. If you use a thread pool you give it a number of jobs and the jobs will be executed by one or more threads, but they will always be executed as a whole. So the question whether your calculation is executed on one or multiple threads is easily answered. It will execute on one, unless you split it up into multiple separate jobs. What I originally intended to say was that your calculation is way too small for thread-parallelisation to be effective. Sorry for mixing this up with thread pools. – Paul Aug 5 '13 at 15:02