ESTIMATING COMPLETION-TIME RATIOS OF A FORK-JOIN BARRIER SYNCHRONIZATION

In simulation studies of parallel processors, it is useful to consider the following abstraction of a parallel program. A job is partitioned into n processes, whose running times are proportional to i.i.d. rand om variables X(1),..., X(n). As a measure of performance we consider t he normalized job completion time S = max{X(i)}/Sigma(i=1)(n) X(i). We consider a simple approximation to the expected value of S, valid asy mptotically whenever the X(i)'s are bounded, and assess its accuracy a s a function of n both theoretically and experimentally. The approxima tion is easy to compute and involves only the mean, variance, and maxi mum of X(i). We also give asymptotic series for the mean and standard deviation of S when the X(i) have a uniform distribution. In this case , the standard deviation is asympotically negligible compared to the m ean.