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. Many parallel languages allow for dynamic fine-grained parallelism and leave the task of mapping the parallelism onto processors to the implementation. Such languages include both data-parallel languages such as HPF [24] There has been a large body of work on how to schedule computations so as to minimize running time. This work dates back at least to the results by Graham [21]. More recently, in addition to time, there has been significant concern about space. This concern has been motivated in part by the high memory usage of many implementations of languages with dynamic parallelism, and by the fact that parallel computations are often "memory limited. A poor schedule can require exponentially more space than a good schedule [1 1]. Early solutions to the space problem considered various heuristics to reduce the number of active threads [10, 23, 34, 16, 26]. More recent work has considered provable bounds on space usage. The idea is to relate the space required by the parallel execution to the space SI required by the sequential execution. Burton [11] first showed that for a certain class of computations the space required by a parallel implementation on p processors can be bound by p~SI (s1 space per processor). Blumofe and Leiserson [8, 9] then showed that this space bound can be maintained while also achieving good time bounds. They showed that a fully strict computation that executes a total of w operations (work) and has a critical path length (depth) of d can be implemented to run in O(w/p + d) time, which is within a constant factor of optimal. These results were used to bound the time and space used by the Cilk programming language [7]. Blelloch, Gibbons and Matias [4] showed that for nested computations, the time bounds 'can be maintained while bounding the space by SI + O(pd), which for sufficient parallelism is just an additive factor over the sequential space. This was used to bound the space of the NESL programming language [5]. Narlikar and Blelloch [30] showed that this same bound can be achieved in a non-preemptive manner (threads are only moved from a processor when synchronizing, forking or allocating memory) and gave experimental results showing the effectiveness of the technique. All this work, however, has been limited to computations in which threads can only synchronize with their sibling or ancestor threads. Although this is a reasonably general class, it does not include languages based on futures [23, 27, 12, 14, 13], languages based on lenient or speculative evaluation [1, 32], or languages with general user-specified synchronization constraints [33]. In this DaDer we show how to extend the results to suD-. . port synchronization based on write-once synchronization variables. A write-once synchronization variable is a variable (memory location ) that can be written by one thread and read by any number of other threads. If it is read before 12
Blelloch et al. REF present the write-once synchronization variable, which is a variable (memory location) that can be written by one thread and read by any number of other threads.
Space-efficient scheduling of parallelism with synchronization variables
SPAA '97
Computer Science