Dynamic Load Balancing using Work-Stealing

In this chapter, we present a methodology for efficient load balancing of computational problems thatcan be easily decomposed into multiple tasks, but where it is hard to predict the computation cost ofeach task, and where new tasks are created dynamically during runtime. We present this methodologyand its exploitation and feasibility in the context of graphics processors. Work-stealing allows an idlecore to acquire tasks from a core that is overloaded, causing the total work to be distributed evenlyamong cores, while minimizing the communication costs, as tasks are only redistributed when required.This will often lead to higher throughput than using static partitioning