Workload Aware Algorithms for Heterogeneous Platforms

Kishore Kothapalli, Sivaramakrishna Indarapu, Shashank Sharma, Dip Sankar Banerjee, Rohit Nigam
Center for Security, Theory, and Algorithmic Research, International Institute of Information Technology, Hyderabad, India
International Institute of Information Technology, 2013


   title={Workload Aware Algorithms for Heterogeneous Platforms},

   author={Kothapalli, Kishore and Indarapu, Sivaramakrishna and Sharma, Shashank and Banerjee, Dip Sankar and Nigam, Rohit},



Download Download (PDF)   View View   Source Source   



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.
Rating: 0.5/5. From 1 vote.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: