On the Benefits of Work Stealing in Shared-Memory Multiprocessors
Load balancing is one of the key techniques exploited to improve the performance of parallel programs. However, load balancing is a difficult task for the programmer. Work stealing is an architectural mechanism that provides improved performance by instantaneously balancing the load among processors in a multiprocessor system. In this work, the authors develop a queueing model of a shared-memory multiprocessor system in order to show that work stealing can ease the burden of the programmer by eliminating the need to manually load balance.