Estimating Mean Completion Times 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 independent random variables X 1 ; : : : ; Xn . As a measure of performance we consider the normalized job completion time S = maxfX i g= P n i=1 X i . We consider a simple approximation to the expected value of S, valid asymptotically whenever the X i 's are bounded, and assess its accuracy as a function of n both theoretically and experimentally. The approximation is easy to compute and involves only the first two moments of X i . 1 Introduction In this paper we study a simple performance metric for parallel programs. We are interested in so-called fork-join programs, of the following type. A job splits into n processes that run independently, then wait for the last one to complete. As a measure of performance we consider the ratio S := maxfT i g D ; (1) where T i is the time taken by process i, an..