TY - JOUR

T1 - A Study of Achievable Speedup in Distributed Simulation via NULL Messages

AU - Kumar, Devendra

AU - Harous, Saad

N1 - Funding Information:
The first author is thankful to Prof. K. M. Chandy and Prof. J. Misra for several fruitful discussions on distributed simulation, including their idea of simulating the distributed simulator. The first author is also thankful to them for their financial support under the Air Forcc Grant AFOSR 81-0205 during which he developed part of the simulation software. We are especially thankful to them and to R. Bagrodia for the use of their May system. We appreciate several helpful comments by three anonymous referees and by Dr. D. DeGroot (editor) on an earlier draft of this paper.
Funding Information:
Unfortunately, only a few performance studies of these schemes are available, e.g., [4]-[6], [15]-[ 171. These studies have provided useful data, and have shown some positive and some negative performance results for a few combinations of the distributed simulation scheme, the system to be simulated, and the available distributed system on which the simulation is to be carried out. Unfortunately, several obvious questions have remained unanswered. For example, what is the relationship hetwcen the amount of overhead and the performance of a distributed simulation scheme. Understanding this relationship is important since this can provide useful information as to whether there is much hope in trying to improve the performance by trying to find variations of a scheme that aim at reducing the amount of overhead. For example, suppose the distributed simulation of a particular system using the scheme [2] has low performance. Would it be useful to define and study variations of the scheme that would tend to reduce the number of NULL messages? A related question is how much speedup one can expect in an ideal variation of a distributed simulation scheme that would somehow totally eliminate the effect of overhead messages. Can we expect a reasonable performance in Manuscript received January 20, 1992. This work was supported by the National Science Foundation under Award CCR-9 110347 and in part by Air Force Grant AFOSR 81-0205. D. Kumar is with the Department of Computer Enginecring and Science, Case Western Reserve University, Cleveland, OH 441 Oh. S. Harous is with the Department of Mathematics and Computing, Sultan Qahoos University, Oman. IEEE Log Number 92058% such a simulation‘? Also, what kind of ideal speedup can be expected if one is considering possibilities across all the well known schemes [2], [3], 191, 1141 and their simple variations.

PY - 1993/3

Y1 - 1993/3

N2 - Performance study of modern computer and communication systems critically depends on our ability to simulate them with reasonable speed, since these systems are often mathematically intractable. Simulation on a uniprocessor is often unacceptably slow. A promising alternative is distributed simulation, i.e., simulating the system on a distributed system of processors that communicate with each other via messages. Several distributed simulation schemes have been proposed in the literature; but their performance is not well understood. In this paper, we report the results of an experimental study on distributed simulation of three open queueing networks. The distributed simulation scheme considered here is a simple variation of the scheme given by Chandy and Misra using NULL messages. This work presents a new approach to study the relationship between the overhead and performance of a distributed simulator, and illustrates the approach by studying these three example networks. Moreover, this study defines and measures two measures of “ideal” speedup of distributed simulation over sequential simulation. These values of ideal speedup are much less than simply the number of processors, and hence provide a more realistic value for the ideal speedup.

AB - Performance study of modern computer and communication systems critically depends on our ability to simulate them with reasonable speed, since these systems are often mathematically intractable. Simulation on a uniprocessor is often unacceptably slow. A promising alternative is distributed simulation, i.e., simulating the system on a distributed system of processors that communicate with each other via messages. Several distributed simulation schemes have been proposed in the literature; but their performance is not well understood. In this paper, we report the results of an experimental study on distributed simulation of three open queueing networks. The distributed simulation scheme considered here is a simple variation of the scheme given by Chandy and Misra using NULL messages. This work presents a new approach to study the relationship between the overhead and performance of a distributed simulator, and illustrates the approach by studying these three example networks. Moreover, this study defines and measures two measures of “ideal” speedup of distributed simulation over sequential simulation. These values of ideal speedup are much less than simply the number of processors, and hence provide a more realistic value for the ideal speedup.

KW - Deadlocks

KW - Sequential simulation

KW - distributed simulation

KW - distributed systems

KW - performance evaluation

KW - queueing networks

UR - http://www.scopus.com/inward/record.url?scp=84939027826&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84939027826&partnerID=8YFLogxK

U2 - 10.1109/71.210817

DO - 10.1109/71.210817

M3 - Article

AN - SCOPUS:84939027826

VL - 4

SP - 347

EP - 354

JO - IEEE Transactions on Parallel and Distributed Systems

JF - IEEE Transactions on Parallel and Distributed Systems

SN - 1045-9219

IS - 3

ER -