Low-contention depth-first scheduling of parallel computations with synchronization variables

In this paper, we present a randomized, online, space-efficient algorithm for the general class of programs with synchronization variables (such programs are produced by parallel programming languages, like, e.g., Cool, ID, Sisal, Mul-T, OLDEN and Jade). The algorithm achieves good locality and low scheduling overheads for this general class of computations, by combining work-stealing and depth-first scheduling. More specifically, given a computation with work $T_1$, depth $T_\infty$ and $\sigma$ synchronizations that its execution requires space $S_1$ on a single-processor computer, our algorithm achieves expected space complexity at most $S_1 + O(PT_\infty \log (PT_\infty))$ and runs in an expected number of $O(T_1/P + \sigma \log (PT_\infty)/P + T_\infty \log (PT_\infty))$ timesteps on a shared-memory, parallel machine with $P$ processors. Moreover, for any $\varepsilon > 0$, the space complexity of our algorithm is at most $S_1 + O(P(T_\infty + \ln (1/\varepsilon)) \log (P(T_\infty + \ln(P(T_\infty + \ln (1/\varepsilon))/\varepsilon))))$ with probability at least $1-\varepsilon$. Thus, even for values of $\varepsilon$ as small as $e^{-T_\infty}$, the space complexity of our algorithm is at most $S_1 + O(PT_\infty \log(PT_\infty))$, with probability at least $1-e^{-T_\infty}$. The algorithm achieves good locality and low scheduling overheads by automatically increasing the granularity of the work scheduled on each processor. Our results combine and extend previous algorithms and analysis techniques (published by Blelloch et. al [6] and by Narlikar [26]). Our algorithm not only exhibits the same good space complexity for the general class of programs with synchronization variables as its deterministic analog presented in [6], but it also achieves good locality and low scheduling overhead as the algorithm presented in [26], which however performs well only for the more restricted class of nested parallel computations