On the Effects of Synchronization in Parallel Computing
Dan Cristian Marinescu, John R. Rice · Purdue e-Pubs (Purdue University System) · 1988
We present a non-deterministic model of parallel computation that includes the effects of communication costs, computation control costs and synchronization effects.Synchronization may be the most important effect in many important applications.Our model is particularly suited for coarse grain parallelism, as in Same Program Multiple Data (SPMD) computations.Using this model we derive exact expressions for synchronization costs, where the parallel tasks have execution times that are unifonnly or exponentially distributed.We show that efficient massive parallelism is possible with the unifonn distribution, but the synchronization costs for exponentially distributed execution times lead to a logarithmically decayiog efficiency.