
Analysis of
Cycle Stealing We have been working on
modeling and analysis of systems with cycle
stealing, where two independent processors serve their own workload,
but one of the processors (donor) can help the other processor with
its jobs during times when the donor processor is idle. We have
studied this problem under various settings: preemptive or
nonpreemptive, immediate dispatch or central queue, with or without
threshold constraint, and with or without switching cost. With
elaborate modeling, we successfully applied the matrix analytic method
to these problems. Analysis was validated via simulation. Results of
the analysis illuminate several interesting principles with respect to
the general benefits of cycle stealing and the design of cycle
stealing policies. Papers on this research was presented at the
SIGMETRICS 2003, ICDCS 2003, and SPAA 2003
[ICDCS03,SIGMETRICS03,SPAA03]. 


Approximating
general distributions by PH distributions A fundamental
question came up
through the study of cycle stealing
systems. Which distributions can be wellrepresented by an nphase
PH distribution in the sense that the first three moments are
matched, and how can we find the minimal PT distribution
that wellrepresents a given distribution?
We
formally characterized the set of distributions G which are
wellrepresented by an nphase PH distribution, in the
sense
that the Coxian distribution matches the first three moments of G.
We also proposed an algorithm for mapping a general
distribution G to a phase type (PH) distribution so that the PH
distribution matches the first three moments of G.
Since
efficiency
of the algorithm is of primary importance, we first defined a
particular subset of the PH distributions, which we refer to as EC
distributions. The class of EC distributions has very few free
parameters, which narrows down the search space, making the algorithm
efficient  In fact we provided a closedform solution for the
parameters of the EC distribution. Our solution is general in that it
applies to any distribution whose first three moments can be matched
by a PH distribution. Also, our resulting EC distribution requires a
nearly minimal number of phases, always within one of the minimal
number of phases required by any PH distribution. Papers on this
research were presented at Performance TOOLS 2003 [TOOLS03a,TOOLS03b]. 
