The performance analysis of multiserver systems is notoriously hard, especially when the system involves resource sharing or prioritization. We provide two new analytical tools for the performance analysis of multiserver systems: moment matching algorithms and dimensionality reduction of Markov chains (DR).

Moment matching algorithms allow us to approximate a general distribution with a phase type (PH) distribution. Our moment matching algorithms improve upon existing ones with respect to the computational efficiency (we provide closed form solutions) as well as the quality and generality of the solution (the first three moments of almost any nonnegative distribution are matched). Approximating job size and interarrival time distributions by PH distributions enables modeling a multiserver system by a Markov chain, so that the performance of the system is given by analyzing the Markov chain. However, when the multiserver system involves resource sharing or prioritization, the Markov chain often has a multidimensionall y infinite state space, which makes the analysis computationally hard.

DR allows us to closely approximate a multidimensionally infinite Markov chain with a Markov chain on a one-dimensionally infinite state space, which can be analyzed efficiently. We validate the accuracy of DR against simulation. Further, we formally define two classes of multidimensionally infinite Markov chains, called recursive foreground-background processes and generalized foreground-background processes (RFB/GFB processes), and analyze the RFB/GFB process via DR. The definition of the RFB/GFB process enables one to easily identify whether a given multiserver system can be analyzed via DR, and our analysis of the RFB/GFB process enables the immediate analysis of a multiserver system by simply modeling it as an RFB/GFB process.

These new analytical tools enable us to analyze the performance of many multiserver systems with resource sharing or prioritization for the first time. For example, we study the benefit and penalty of cycle stealing, the effectiveness of prioritization and threshold-based resource allocation policies for multiserver systems, and the impact of job size variability and irregularity of arrival processes on the response time in multiserver systems. Our analysis results in lessons on the design of good resource allocation policies for multiserver systems.

252 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu