Computing Publications

Publications Home » Efficient Parallelization of the ...

Efficient Parallelization of the Method of Moments for Queueing Networks Using Multi-Modular Algebra

Michalis Makaronidis, Giuliano Casale

Conference or Workshop Paper
5th International ICST Conference on Performance Evaluation Methodologies and Tools (ValueTools 2011)
May, 2011

The solution of service performance models based on closed queueing networks often relies on the Mean Value Analysis (MVA) algorithm, which is unable to solve exactly large models with multiple service classes and hundreds or thousands of users. The Method of Moments (MoM) algorithm has been introduced and addressed this problem, by relying on the exact solution of large linear systems with rational coeffcients. In this paper, we focus on the design, analysis and implementation of a parallel solver for MoM linear systems. Parallelization is introduced using residue number systems and recombining the results by the Chinese Remainder Theorem. A comprehensive test set representative of modern applications is used for experimental evaluation. The overall result proves the enhanced performance of both the MoM algorithm over established ones, namely Convolution and RECAL, and of the parallel solver over the serial one.

PDF of full publication (476 kilobytes)
(need help viewing PDF files?)
BibTEX file for the publication
Conditions for downloading publications from this site. built & maintained by Ashok Argent-Katwala.