No. 64 (00182, 194)

Family name : Bityukov
Given name : Serge
Affiliation : Skobeltsyn Institute of Nuclear Physics, Moscow State
University
Abbreviation : SINP MSU
E-mail address : serge@shade.msu.ru
Title : On application of queueing theory to development of optimal GRID 
schedulers
Authors : Serge S. Bityukov
Abstract : 
Application of methods of Queueing theory to
studying the scheduling algorithms in distributed
GRID systems makes it possible to develop
a sound model of functioning of such systems, and
to propose a solution for the problem of optimal
scheduling. In this model, it is possible
to formulate, which scheduling algorithms are
"effective" and "optimal", and completely solve
the problem of scheduling for a particular class
of scenarios. However, the class of scenarios is
rich enough to allow an arbitrarily good
approximation for the general scenario.

From the perspective of a scheduling algorithm, it
is possible to limit the number of parameters
sufficient to describe the state of a GRID system
in a particular moment of time to cumulative
complexity of the tasks already dispatched to each
node. Each task to be dispatched has a vector of
associated complexities for each node, and the
decisions scheduler makes are based on this
information. Arrival of tasks is modeled with a
Poisson flow of fixed intensity.

We consider a scheduler "effective", if there
exists a stationary distribution of GRID state
under its control. While the class of effective
schedulers is rather large, the condition of
efficiency under high load makes it possible to
drop most of them and to formulate the problem as
the one of optimization. By approximating the
structure of flow of tasks with discrete
distributions, we make it possible to
reduce the problem, and to solve it as the one of
finite-dimensional optimization with linear
programming technique. The "optimal" algorithm
is obtained from the solution of the optimization
problem.

While the general case can theoretically only be
handled by approximations in this model, the
real-world scheduling algorithms will likely
not possess full information about distribution of
task complexities, and they will always operate
with finite histories. Thus, the approximate
solutions are likely to be justified.

Numerical modeling conducted by the author shows
that significant performance gain over trivial
scheduling algorithms can be achieved by the ones
"optimal" in terms of the model considered.