The data locality of work stealing

This paper studies the data locality of the work-stealing scheduling algorithm on hardware-controlled shared-memory machines, where movement of data to and from the cache is solely controlled by the hardware. We present lower and upper bounds on the number of cache misses when using work stealing, and introduce a locality-guided work-stealing algorithm and its experimental validation. As a lower bound, we show that a work-stealing application that exhibits good data locality on a uniprocessor may exhibit poor data locality on a multiprocessor. In particular, we show a family of multithreaded computations ¢ ¡ whose members perform £¥¤§¦© ¨ operations (work) and incur a constant number of cache misses on a uniprocessor, while even on two processors the total number of cache misses soars to ��¤§¦© ¨. On the other hand, we show a tight upper bound on the number of cache misses that nested-parallel computations, a large, important class of computations, incur due to multiprocessing. In particular, for nested-parallel computations, we show that on processors a multiprocessor execution incurs ��¤����� � �� � ¨ an expected more misses than the uniprocessor � execution. Here is the execution time 1 of an instruction incurring a cache miss, � is the steal time, � is the size of cache, and ��� is the number of nodes on the longest chain of dependen-cies. Based on this we give strong execution time bounds for nested-parallel computations using work stealing. For the second part of our results, we present a locality-guided work stealing algorithm that improves the data locality of multithreaded computations by allowing a thread to have an affinity for a processor. Our initial experiments on iterative data-parallel applications show that the algorithm matches the performance of static-partitioning under traditional work loads but improves the performance up to ���� � over static partitioning under multiprogrammed work loads. Furthermore, the locality-guided work stealing improves the performance of work-stealing up to ���� �.