Dynamic Load Balancing on Single- and Multi-GPU Systems

The computational power provided by many-core graph-ics processing units (GPUs) has been exploited in many applications. The programming techniques currently em-ployed on these GPUs are not sufficient to address prob-lems exhibiting irregular, and unbalanced workload. The problem is exacerbated when trying to effectively exploit multiple GPUs concurrently, which are commonly avail-able in many modern systems. In this paper, we propose a task-based dynamic load-balancing solution for single-and multi-GPU systems. The solution allows load balanc-ing at a finer granularity than what is supported in cur-rent GPU programming APIs, such as NVIDIA’s CUDA. We evaluate our approach using both micro-benchmarks and a molecular dynamics application that exhibits signif-icant load imbalance. Experimental results with a single-GPU configuration show that our fine-grained task so-lution can utilize the hardware more efficiently than the CUDA scheduler for unbalanced workload. On multi-GPU systems, our solution achieves near-linear speedup, load balance, and significant performance improvement over techniques based on standard CUDA APIs.