Mor Harchol-Balter
Computer Science Dept.
Carnegie Mellon Univ.

TITLE:
Dimensionality Reduction Technique for Scheduling in Multiserver Systems,
Including Cycle Stealing, Priority Queueing, and Threshold Policies

ABSTRACT:

We consider common scheduling policies for multiserver systems
including cycle stealing policies, priority queueing, task assignment
policies, and threshold policies.  Even these simple policies are
already very difficult to analyze because their underlying Markov
chain structure grows infinitely in more than one dimension.  The
dimensionality of the Markov chain is typically equal to the number of
servers or the number of job classes.

We introduce a new analysis technique which we call Recursive
Dimensionality Reduction (RDR) which allows us to reduce an
n-dimensionally inifinite Markov chain to a 1-dimensionally infinite
Markov chain, that can then be solved via numerical methods.  This
technique enables the first near-exact analysis of many fundamental
multiserver system problems.

The talk will focus on the new insights obtained by analyzing these
policies and proposals for improved policies.  We will consider
questions such as: When does cycle stealing pay, and how do different
cycle stealing methods compare?  How does the multiserver priority
queue compare with the single server priority queue, and what is the
effect of variability in service demand?  Under threshold-based load
sharing, where a ``donor'' machine helps a ``beneficiary'' machine
based on some threshold on the number of jobs, who should control this
threshold: the donor or the beneficiary, and how many thresholds does
one need?

This work will appear in the QUESTA and  Performance Evaluation journals
2006.

JOINT WORK WITH:  Adam Wierman, Taka Osogami, Alan Scheller-Wolf