Centralized  versus distributed schedulers for multiple bag-of-task
applications

Yves Robert, ENS Lyon

Multiple applications that execute concurrently on heterogeneous
platforms compete for CPU and network resources. In this talk we
consider the problem of scheduling applications to ensure fair
and efficient execution on a distributed network of processors. We limit
our study to the case where
communication is restricted to a tree embedded in the network, and the
applications consist of a large number of independent tasks that
originate at the tree's root. The tasks of a given application all have
the same computation and communication requirements, but these
requirements can vary for different applications. Each application is
given a weight that quantifies its relative value. The goal of
scheduling is to maximize throughput while executing tasks from each
application in the same ratio as their weights. We can find the optimal
asymptotic rates by solving a linear program that expresses all
necessary problem constraints, and we show how to construct a periodic
schedule.  For single-level trees, the solution is characterized by
processing tasks with larger communication-to-computation ratios at
children with larger bandwidths. For multi-level trees, this approach
requires global knowledge of all application and platform parameters.
For large-scale platforms, such global coordination by a centralized
scheduler may be unrealistic.  Thus, we also investigate decentralized
schedulers that use only local information at each participating
resource. We assess their performance via simulation, and compare to a
centralized solution obtained via linear
programming. The best of our decentralized heuristics achieves the same
performance on about two-thirds of our test cases, but is far worse in a
few cases.  While our results are based on simplistic assumptions and do
not explore all parameters (such as buffer size), they provide insight
into the important question of fairly and optimally co-scheduling
heterogeneous applications on heterogeneous grids.

This is joint work with  O. Beaumont, L. Carter, J. Ferrante,
A. Legrand, and  L. Marchal.

Short biography:
Yves Robert received the PhD degree from Institut National
Polytechnique de Grenoble in 1986. He is currently a full professor
in the Computer Science Laboratory LIP at ENS Lyon. He is the author
of four books, 95 papers published in international journals, and
115 papers published in international conferences. His main research
interests are scheduling techniques and parallel algorithms for
clusters and grids. He is a senior member of IEEE and the IEEE
Computer Society, and serves as an associate editor of IEEE
Transactions on Parallel and Distributed Systems