SC Conference - Activity Details

Work-stealing and Work-sharing Schedulers for Terminally Strict Parallel Computations

Rajkishore Barik  (Rice University)
Yi Guo  (Rice University)
Raghavan Raman  (Rice University)
Vivek Sarkar  (Rice University)
Posters Session
Tuesday,  05:15PM - 07:00PM
Room Rotunda Lobby
Multiple programming models are emerging to address an increased need for dynamic task parallelism in applications for multicore processors and shared-memory computing. Examples include OpenMP 3.0, Java Concurrency Utilities, Microsoft Task Parallel Library, Cilk, X10, Chapel, and Fortress. Scheduling algorithms based on work stealing, as embodied in Cilk's implementation of dynamic spawn-sync parallelism, are gaining in popularity but also have inherent limitations. In this paper, we address the problem of efficient and scalable implementation of X10's terminally strict async-finish task parallelism, which is more general than Cilk's fully strict spawn-sync parallelism. We introduce a new work-stealing scheduler for async-finish task parallelism, and compare it with a work-sharing scheduler that we previously implemented for X10. Performance results on three different multicore SMP platforms show significant improvements due to our new work-stealing algorithm for terminally strict computations. They also shed insight on scenarios in which work-stealing outperforms work-sharing, and vice versa.
   IEEE Computer Society  /  ACM     2 0   Y E A R S   -   U N L E A S H I N G   T H E   P O W E R   O F   H P C