Bandwidth-Centric Allocation of Independent Tasks on Heterogeneous Platforms

In this paper, we consider the problem of allocating a large number of independent, equal-sized tasks to a heterogenerous "grid" computing platform. Such problems arise in collaborative computing efforts like SETI@home. We use a tree to model a grid, where resources can have different speeds of computation and communication, as well as different overlap capabilities. We define a base model, and show how to determine the maximum steady-state throughput of a node in the base model, assuming we already know the throughput of the subtrees rooted at the node's children. Thus, a bottom-up traversal of the tree determines the rate at which tasks can be processed in the full tree. The best allocation is {\em bandwidth-centric}: if enough bandwidth is available, then all nodes are kept busy; if bandwidth is limited, then tasks should be allocated only to the children which have sufficiently small communication times, regardless of their computation power. We then show how nodes with other capabilities -- ones that allow more or less overlapping of computation and communication than the base model -- can be transformed to equivalent nodes in the base model. We also show how to handle a more general communication model. Finally, we present simulation results of several demand-driven task allocatio- n policies that show that our bandwidth-centric method obtains better results than allocating tasks to all processors on a first-come, first serve basis