Bounding Synchronization Overhead for Parallel Iteration
ORSA Journal on Computing · 1991 · Volume 3 · Issue 4
Abstract
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 E R ( m ) ( t )≤E X , 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 (1) ( 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 E R ( 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.
Keywords
probability, renewal processes: bounds on expected excess, extreme order statistics, probability, stochastic model applications: parallel loops, synchronization delay, production/scheduling, sequencing, stochastic, multimachine: on-line expected makespan
Enable JavaScript for citation tools and additional paper interactions.