Bandwidth-aware Resource Allocation for Computing Independent Tasks in Heterogeneous Computing Systems

B. Hong and V.K. Prasanna (USA)


Resource Allocation, Heterogeneous Computing System, Throughput, Linear Programming


In this paper, we consider the resource allocation prob lem for computing a large set of equal-sized independent tasks on heterogeneous computing systems. This problem represents the computation paradigm for a wide range of applications such as SETI@home and Monte Carlo simu lations. Compute nodes in the system are heterogeneous and may communicate with each other at different speeds. We model such a system as a graph, which is capable of representing an arbitrary network topology. Our study fo cuses on the maximization of the steady state throughput of such systems. We show that, unlike the surprisingly diffi cult makespan minimization problem, the throughput max imization problem can be solved through a linear program ming formulation. We also show that different operation scenarios of the compute nodes have intrinsic similarities. Our approach shows improved performance compared with the master/worker computation paradigm which assumes a tree-structured system topology.

Important Links:

Go Back