Space-efficient scheduling of parallelism with synchronization variables
Guy E. Blelloch, Phillip B. Gibbons, Girija J. Narlikar, Yossi Matias · 1997
Recent work on scheduling algorithms has resulted in provable bounds on the space taken by parallel computations in relation to the space taken by sequential computations.The results for online versions of these algorithms, however, have been limited to computations in which threads can only synchronize with ancestor or sibling threads.Such computations do not include Ianguages with futures or user-specified synchronize ation const mints.Here we extend the results to languages with synchronization variables.Such languages include languages with futures, such as Multilisp and Cool, as well as other languages such as ID.The main result is an ordine scheduling algorithm which, given a computation with w work (total operations), u synchronizations, a'depth (critical path) and SI sequential space, WiIl run in O(w/P + a log@i)/p + d log(pd)) time and SI + O(pd Iog(pd)) space, on a p-processor CRCW PRAM with a fetch-and-add primitive.This includes all time and space costs for both the computation and the scheduler.The scheduler is non-preemptive in the sense that it will only move a thread if the thread suspends on a synchronization, forks a new thread, or exceeds a threshold when allocating space.For the special case where the computation is a planar graph with left-to-right synchronization edges, the scheduling algorithm can be implemented in 0( w/P+~log p) time and SI + O(pd log p) space.These are the first nontrivial space bounds described for such languages.