Cooperative Scheduling of Parallel Tasks with General Synchronization Patterns

Abstract. In this paper, we address the problem of scheduling parallel tasks with general synchronization patterns using a cooperative runtime. Current implementations for task-parallel programming models provide efficient support for fork-join parallelism, but are unable to efficiently support more general synchronization patterns such as locks, futures, barriers and phasers. We propose a novel approach to addressing this challenge based on cooperative scheduling with one-shot delimited con-tinuations (OSDeConts) and event-driven controls (EDCs). The use of OSDeConts enables the runtime to suspend a task at any point (thereby enabling the task’s worker to switch to another task) whereas other run-times may have forced the task’s worker to be blocked. The use of EDCs ensures that identification of suspended tasks that are ready to be re-sumed can be performed efficiently. Furthermore, our approach is more efficient than schedulers that spawn additional worker threads to com-pensate for blocked worker threads. We have implemented our cooperative runtime in Habanero-Java (HJ), an explicitly parallel language with a large variety of synchronization patterns. The OSDeCont and EDC primitives are used to implement a wide range of synchronization constructs, including those where a task may trigger the enablement of multiple suspended tasks (as in futures, barriers and phasers). In contrast, current task-parallel runtimes and schedulers for the fork-join model (including schedulers for the Cilk lan-guage) focus on the case where only one continuation is enabled by an event (typically, the termination of the last child/descendant task in a join scope). Our experimental results show that the HJ cooperative runtime delivers significant improvements in performance and memory utilization on various benchmarks using future and phaser constructs, relative to a thread-blocking runtime system while using the same un-derlying work-stealing task scheduler