Dynamic Load Balancing on Graphics Processors

Daniel Cederman, Philippas Tsigas

To get maximum performance on the many-core graphics processors it is important to have an even balance of the workload so that all processing units contribute equally to the task at hand. This can be hard to achieve when the cost of a task is not known beforehand and when new sub-tasks are created dynamically during execution. With the recent advent of scatter operations and atomic hardware primitives it is now possible to bring some of the more elaborate dynamic load balancing schemes from the conventional SMP systems domain to the graphics processor domain.

We have compared four different dynamic load balancing methods to see which one is most suited to the highly parallel world of graphics processors. Three of these methods were lock-free and one was lock-based. We evaluated them on the task of creating an octree partitioning of a set of particles and playing a game of four-in-a-row. The experiments showed that synchronization can be very expensive and that new methods that take more advantage of the graphics processors features and capabilities might be required. They also showed that lock-free methods achieves better performance than blocking and that they can be made to scale with increased numbers of processing units.

Download

The source code for the benchmarks is released under a BSD license, see source for details. It contains Visual Studio project files and is known to work with Visual Studio 2008, CUDA 3.0 and a sm_13 capable graphics processor.

Version 1.0 - Released 2011-02-16

Presentation

Papers

[1] Daniel Cederman and Philippas Tsigas, On Dynamic Load Balancing on Graphics Processors, in the Proceedings of the 11th Graphics Hardware (GH 2008), 2008. [pdf]

[2] Daniel Cederman and Philippas Tsigas, On Sorting and Load Balancing on GPUs, in the ACM SIGARCH Computer Architecture News, Vol. 36, No. 5, pages: 11-18, ACM press 2009. [doi]

[3] Daniel Cederman and Philippas Tsigas, Dynamic Load Balancing using Work-Stealing in GPU Computing Gems Vol. 2 (to appear).