high performance computing on graphics processing units: hgpu.org

Algorithms that aim to simultaneously run on a heterogeneous collection of devices on a commodity platform have been in recent research focus. On such platforms, individual devices can have very differing architectures, clock rates, and execution models. Hence, one of the fundamental challenges in designing and implementing such algorithms is to identify load balancing mechanisms that aim to apportion the right amount of work for each device. The state-of-the-art in load balancing of heterogeneous algorithms has several drawbacks. Static solutions that partition the work irrespective of the input instance cannot lead to well-balanced load. On the other hand, analytical methods to identify the right work partition are available for only a few workloads or special cases of a few workloads. In this paper, we propose a light-weight, low overhead, and completely dynamic framework that addresses the load balancing problem of heterogeneous algorithms. Our framework will be applicable for workloads which have a few simple characteristics such as having a collection of largely independent tasks that are easily describable. To show the efficacy of our framework, we consider two different heterogeneous computing platforms, and three different workloads: spmm, LBM, and ray casting. For each of the above workloads, we demonstrate that using our framework, we can identify the proportion of work to be allotted to each device up to ±8% on average. Further, solutions using our framework require no more than 5% additional time on average compared to best possible load assignment obtained via empirical search.