Back to BMAC Page
Title: Steady state scheduling for heterogeneous platforms
Speaker:
Yves Robert, Ecole Normale Supérieure de Lyon, France
In this talk, we consider static scheduling techniques for
heterogeneous systems, such as clusters and grids. But instead of
dealing with heuristics aimed at minimizing the total execution
time, we target steady-state scheduling techniques. The motivation
is as follows: in many situations, an absolute minimization of the
total execution time is not really required; deriving
asymptotically optimal schedules is more than enough to ensure an
efficient use of the architectural resources. The idea is to relax
the problem: (i) neglect the initialization and clean-up phases,
and concentrate on steady-state operation; (ii) derive an optimal
steady-state scheduling (e.g., using linear programming); and
(iii) prove the asymptotic optimality of the associated schedule.
We first illustrate the approach with an example due to Bertsimas
and Gamarnik, the packet routing problem. Given a non-oriented
graph modeling the target architectural platform, consider a set
of same-size packets to be routed through the network. Each packet
is characterized by a source node (where it initially resides) and
a destination node (where it must be located in the end). The
objective is to design an efficient algorithm to route all the
packets.
Next, we move to the problem of allocating a large number of
independent, equal-sized tasks to a heterogeneous computing
platform. Again, we use a non-oriented graph to model the
platform; resources can have different speeds of computation and
communication. We assume that one specific node (the master),
initially holds (or generates the data for) a large collection of
independent, identical tasks. The question for the master is to
decide which tasks to execute itself, and how many tasks (i.e.
task files) to forward to each of its neighbors. Due to
heterogeneity, the neighbors may receive different amounts of work
(maybe none for some of them). Each neighbor faces in turn the
same dilemma: determine how many tasks to execute, and how many to
delegate to other processors. We show that finding the optimal
steady state (for each processor, compute the fraction of time
spent computing and the fraction of time spent communicating with
each neighbor) can be solved using a linear programming approach,
and thus in polynomial time. This result holds for a quite general
framework, allowing for cycles and multiple paths in the
interconnection graph, and allowing for several masters.
Back to BMAC Page