Journal of Applied Mathematics and Stochastic Analysis
Volume 11 (1998), Issue 3, Pages 397-409
doi:10.1155/S1048953398000331
Performance limitations of parallel simulations
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.
Abstract
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.