AuthorsZ. Vrba, P. Halvorsen and C. Griwodz
TitleA Simple Improvement of the Work-Stealing Scheduling Algorithm
AfilliationCommunication Systems, Communication Systems
StatusPublished
Publication TypeProceedings, refereed
Year of Publication2010
Conference NameProceedings of the International Conference on Complex, Intelligent and Software Intensive Systems (CISIS) - International Workshop on Multi-Core Computing Systems (MuCoCoS), Krakow, Poland, February 2010
Pagination925-930
PublisherN/A
ISBN Number978-1-4244-5917-9
Abstract

Work-stealing is the todays algorithm of choice for dynamic load-balancing of irregular parallel applications on multiprocessor systems. We have evaluated the algorithm's efficiency on a variety of workloads, including scatter-gather workloads, which occur in common algorithms such as MapReduce. We have discovered that work-stealing scheduling suffers serious scalability problems with fine-grained parallelism because of contention over run-queues. We therefore propose a simple modification to the work-stealing algorithm that significantly improves its performance on scatter-gather workloads, without any negative impact on other types of workloads.

DOI10.1109/CISIS.2010.67
Citation KeySimula.ND.409