| Abstract |
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.
First 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. However, 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. 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.
Then we move to a more realistic platform model that captures some of the
fundamental network properties of grid platforms. We formulate the
steady-state multi-application scheduling problem as a 0/1 linear program.
This scheduling problem is NP-complete and we propose several heuristics
that we
evaluate and compare via extensive simulation experiments. Our main
finding is that
some of our heuristics can achieve performance close to the optimal and we
quantify the trade-offs between achieved performance and heuristic
complexity.
|
