ALCOMFT-TR-01-77

Panagiota Fatourou
Low-Contention Depth-First Scheduling of Parallel Computations with Write-Once Synchronization Variables
MPI. Work package 2. May 2001.

Abstract: We present an efficient, randomized, online, scheduling algorithm for a large class of programs with write-once synchronization variables. The algorithm combines the work-stealing paradigm with the depth-first scheduling technique, resulting in high space efficiency and good time complexity. By automatically increasing the granularity of the work scheduled on each processor, our algorithm achieves good locality, low contention and low scheduling overhead, improving upon a previous depth-first scheduling algorithm [BGMN:97] published in SPAA'97. Moreover, it is provably efficient for the general class of multithreaded computations with write-once synchronization variables (as studied in [BGMN:97]), improving upon algorithm DFDeques (published in SPAA'99 [N:99]), which is only for the more restricted class of nested parallel computations.

More specifically, consider such a computation with work T₁, depth T_\infty and \sigma synchronizations, and suppose that space S₁ suffices to execute the computation on a single-processor computer. Then, on a P-processor shared-memory parallel machine, the expected space complexity of our algorithm is at most S₁ + O(PT_\infty log (PT_\infty)), and its expected time complexity is O(T₁/P + \sigma log (PT_\infty)/P + T_\infty log (PT_\infty)). Moreover, for any epsilon > 0, the space complexity of our algorithm is S₁ + O(P(T_\infty + \ln (1/epsilon)) log (P(T_\infty + \ln(P(T_\infty + \ln (1/epsilon))/epsilon)))) with probability at least 1-epsilon. Thus, even for values of epsilon as small as e^-T_\infty, the space complexity of our algorithm is at most S₁ + O(PT_\infty log(PT_\infty)) with probability at least 1-e^-T_\infty. These bounds include all time and space costs for both the computation and the scheduler.

Postscript file: ALCOMFT-TR-01-77.ps.gz (109 kb).