Hierarchical Work Stealing on Manycore Clusters
Seung-Jai Min, Costin Iancu, Katherine Yelick · 2011
Partitioned Global Address Space languages like UPC offer a convenient way of expressing large shared data structures, especially for irregular structures that require asynchronous random access. But the static SPMD parallelism model of UPC does not support divide and conquer parallelism or other forms of dynamic parallelism. We introduce a dynamic tasking library for UPC that provides a simple and effective way of adding task parallelism to SPMD programs. The task library, called HotSLAW, provides a high-level API that abstracts concurrent task management details and performs dynamic load balancing. To achieve scalability, we propose a topology-aware hierarchical work stealing strategy that exploits locality in distributed-memory clusters. Our approach, named HotSLAW, extends state of the art techniques in shared- and distributed-memory implementations with two mechanisms: Hierarchical Victim Selection (HVS) finds the nearest victim thread to preserve locality and Hierarchical Chunk Selection (HCS) dynamically determines the amount of work to steal based on the locality of the victim thread. We evaluate the performance of our runtime on shared- and distributed-memory systems using irregular applications. On shared memory, HotSLAW provides performance comparable or better than hand tuned OpenMP implementations. On distributed memory systems, the combination of Hierarchical Victim Selection and Hierarchical Chunk Selection provides better performance than state of the art approaches using a random victim selection with a StealHalf strategy for the workload considered. 1.