Simultaneous Multi-Level Divisible Load Balancing for Heterogeneous Desktop Systems

In this paper, we propose an algorithm for efficient divisible load balancing across all processing devices available in a heterogeneous desktop system. The proposed algorithm allows to achieve simultaneous load balancing at different execution levels, namely between execution subdomains defined with several processing devices, and between devices in each subdomain. Moreover, the algorithm builds partial performance models for each execution subdomain, using the minimal set of approximation points determined during the algorithm run, while converging towards the optimal multi level load distributions. The proposed approach was experimentally evaluated in a real desktop system with a quad core CPU and two GPUs, for matrix multiplication. Experimental results show the ability of the algorithm to provide significant performance improvements with very low scheduling overhead when compared to similar scheduling approaches.