|Authors||Z. Vrba, P. Halvorsen and C. Griwodz|
|Title||A Simple Improvement of the Work-Stealing Scheduling Algorithm|
|Afilliation||Communication Systems, Communication Systems|
|Publication Type||Proceedings, refereed|
|Year of Publication||2010|
|Conference Name||Proceedings of the International Conference on Complex, Intelligent and Software Intensive Systems (CISIS) - International Workshop on Multi-Core Computing Systems (MuCoCoS), Krakow, Poland, February 2010|
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.