The Price of Synchrony

Loops that synchronize parallel processors at the end of each iteration are compared with loops that do not synchronize their iterations. In the presence of data dependencies, loop synchronization cannot always be removed---the purpose here is to estimate the additional costs incurred when synchronization is necessary. Suppose there are n parallel processors each executing k iterations. Under the assumption that each iteration of the loop body runs for a time controlled by an independent identically distributed random variable X with mean µ and variance s 2 , it is shown here that the ratio of the expected time taken with synchronized loops to the expected time taken with unsynchronized loops is asymptotically µ EX (n) + e(n) ############# (n , k ® ) (*) where EX (n) is the expected maximum of n independent random variables with with the distribution of X, and e(n) is the (deterministic) time to fork n processes. Since EX (n) grows with n in a way that can be estimated for many par..