CSE 292: Faculty Research Seminar
Winter 2002

16 January 2001

Jeanne Ferrante
UC San Diego

Bandwidth-centric scheduling of independent tasks on a heterogeneous grid

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 define a base model, and show how to determine the maximum steady-state throughput in the model.

The best allocation is 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 preliminary simulation results of several demand-driven task allocation policies that show that our bandwidth-centric method obtains better results than allocating tasks to all processors on a first-come, first serve basis.

(Joint work with Olivier Beaumont, Larry Carter, Arnaud Legrand and Yves Robert, while on sabbatical spring, 2000 at Ecole Normale Superieure de Lyon)

We'll also briefly discuss current work and future plans (with Barbara Kreaseck and Henri Casanova and the AppLeS group).

Questions and comments to Keith Marzullo. Last edited 15 January 2002.