Bounding Synchronization Overhead for Parallel Iteration

Suppose m stochastically identical iterative processes are run in parallel. Each iteration of the process runs for a random time X, distributed identically and independently for each iteration. At the end of each iteration, each process checks a shared variable to see whether some global event has occurred; if it has, the process terminates and instantly joins a rendezvous with the other processes that have detected the event. The synchronization overhead is the time R_(m)(t) needed to complete the rendezvous, measured from the time t of occurrence of the event (t is assumed to be independent of the m processes). It is not true (for general X) that ER_(m)(t)≤EX, because t will more probably occur during a long iteration than a short one, and because R_(m)(t) is an extreme value of a sample of size m. In renewal theory the random variable R₍₁₎(t) is called the excess at t, and R_(m)(t) will be the extreme of m i.i.d. excesses. While exact expressions for ER_(m)(t) are impossible to obtain in practice, we give useful upper bounds. The bounds get tighter depending on information known about the underlying distribution of X. Results include: (1) a general bound valid for any X having finite third moment, (2) a better bound valid if X is dominated by an exponential in stochastic variability ordering, (3) an even better bound if X has bounded mean residual life, and (4) a bound valid when X has decreasing failure rate. The results are applied to searching a table in parallel and to on-line makespan scheduling.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.