Shams Imam, Cooperative Scheduling of Parallel Tasks in the Presence of Synchronization Patterns

In this talk, I 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 futures, barriers and phasers. I present our novel approach to addressing this challenge based on Cooperative Scheduling with one-shot delimited continuations and event-driven controls. The use of delimited continuations enables the runtime to suspend a task at any point where other runtimes may have forced the task to block. The use of event-driven controls ensures that identification of suspended tasks that are ready to be resumed can be performed efficiently, unlike for example polling-based approaches. Furthermore, our approach is more efficient than schedulers that spawn additional worker threads to compensate for blocked worker threads. Our experimental results for our implementation on various benchmarks show that the cooperative runtime delivers significant improvements in performance and memory utilization relative to a thread-blocking runtime system while using the same underlying work-stealing task scheduler.