On Dynamic Load Balancing on Graphics Processors

To get maximum performance on the many-core graphics processorsit is important to have an even balance of the workload so thatall processing units contribute equally to the task at hand.This can be hard to achieve when the cost of a task is notknown beforehand and when new sub-tasks are created dynamicallyduring execution. With the recent advent of scatter operationsand atomic hardware primitives it is now possible to bring someof the more elaborate dynamic load balancing schemes from theconventional SMP systems domain to the graphics processordomain.We have compared four different dynamic load balancing methodsto see which one is most suited to the highly parallel world ofgraphics processors. Three of these methods were lock-free andone was lock-based. We evaluated them on the task of creatingan octree partitioning of a set of particles. The experimentsshowed that synchronization can be very expensive and that newmethods that take more advantage of the graphics processorsfeatures and capabilities might be required. They also showedthat lock-free methods achieves better performance thanblocking and that they can be made to scale with increasednumbers of processing units