A Simple Improvement of the Work-stealing Scheduling Algorithm

Work-stealing is 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.