AuthorsZ. Vrba, P. Halvorsen and C. Griwodz
TitleA Simple Improvement of the Work-Stealing Scheduling Algorithm
AfilliationCommunication Systems, Communication Systems
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
ISBN Number978-1-4244-5917-9

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.

Citation KeySimula.ND.409