Research Article
Efficient Parallelization of the Method of Moments for Queueing Networks Using Multi-Modular Algebra
@INPROCEEDINGS{10.4108/icst.valuetools.2011.245725, author={Michail Makaronidis and Giuliano Casale}, title={Efficient Parallelization of the Method of Moments for Queueing Networks Using Multi-Modular Algebra}, proceedings={5th International ICST Conference on Performance Evaluation Methodologies and Tools}, publisher={ICST}, proceedings_a={VALUETOOLS}, year={2012}, month={6}, keywords={Performance Model Queueing Network Parallel Solution}, doi={10.4108/icst.valuetools.2011.245725} }- Michail Makaronidis
Giuliano Casale
Year: 2012
Efficient Parallelization of the Method of Moments for Queueing Networks Using Multi-Modular Algebra
VALUETOOLS
ICST
DOI: 10.4108/icst.valuetools.2011.245725
Abstract
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 coefficients. 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.