Journal of Applied Mathematics and Stochastic Analysis
Volume 11 (1998), Issue 3, Pages 397-409

Performance limitations of parallel simulations

Liang Chen1 and Richard F. Serfozo2

1Lucent Technologies, Wireless Networks Group, 67 Whippany Road, Room 14D-270, Whippany 07981, NJ, USA
2Georgia Institute of Technology, School of Industrial and Systems Engineering, Atlanta 30332, GA, USA

Received 1 November 1997; Revised 1 February 1998

Copyright © 1998 Liang Chen and Richard F. Serfozo. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


This study shows how the performance of a parallel simulation may be affected by the structure of the system being simulated. We consider a wide class of “linearly synchronous” simulations consisting of asynchronous and synchronous parallel simulations (or other distributed-processing systems), with conservative or optimistic protocols, in which the differences in the virtual times of the logical processes being simulated in real time t are of the order o(t) as t tends to infinity. Using a random time transformation idea, we show how a simulation's processing rate in real time is related to the throughput rates in virtual time of the system being simulated. This relation is the basis for establishing upper bounds on simulation processing rates. The bounds for the rates are tight and are close to the actual rates as numerical experiments indicate. We use the bounds to determine the maximum number of processors that a simulation can effectively use. The bounds also give insight into efficient assignment of processors to the logical processes in a simulation.