411k compressed postscript / 380k pdf
Abstract:
The running time and memory requirement of a parallel program with dynamic, lightweight threads depends heavily on the underlying thread scheduler. In this paper, we present a simple, asynchronous, space-efficient scheduling algorithm for shared memory machines that combines the low scheduling overheads and good locality of work stealing with the low space requirements of depth-first schedulers. For a nested-parallel program with depth D and serial space requirement S1, we show that the expected space requirement is S1 + O(K . p . D) on p processors. Here, K is a user-adjustable runtime parameter, which provides a trade-off between running time and space requirement. Our algorithm achieves good locality and low scheduling overheads by automatically increasing the granularity of the work scheduled on each processor.
We have implemented the new scheduling algorithm in the context of a native, user-level implementation of Posix standard threads or Pthreads, and evaluated its performance using a set of C-based benchmarks that have dynamic or irregular parallelism. We compare the performance of our scheduler with that of two previous schedulers: the thread library's original scheduler (which uses a FIFO queue), and a provably space-efficient depth-first scheduler. At a fine thread granularity, our scheduler outperforms both these previous schedulers, but requires marginally more memory than the depth-first scheduler.
We also present simulation results on synthetic benchmarks to compare our
scheduler with space-efficient versions of both a work-stealing scheduler
and a depth-first scheduler.
The results indicate that unlike these previous approaches,
the new algorithm covers a range of scheduling granularities and space
requirements, and allows the user to trade the space requirement of a program
with the scheduling granularity.
@techreport{NarlikarTR99,
author = "Girija J. Narlikar",
title = "Scheduling Threads for Low Space Requirement and Good Locality",
institution = "Computer Science Department, Carnegie Mellon University",
number = "CMU-CS-99-121",
year = 1999,
month = "May"
}