Yi-Bing Lin, Edward D. Lazowska* and Shu-Yuen Hwang+
2D297, 445 South Street
Morristown, NJ 07962-1910, USA
* Department of Computer Science and Engineering
University of Washington
Seattle, WA 98195, USA
+ Department of Computer Science and Information Engineering
National Chiao-Tung University
Hsinchu, Taiwan, R.O.C.
Performance studies of parallel simulation are complest because a large number of parameters need to be considered. Basically, there are two categories of paramenters: logical parameters, which represent the logical structure of the simulation application, and architecture parameters or hardware parameters, which represent the architecture of the machine that performs the simulation. Logical parameters include the set of events, their timestamps, and the relationships among these events. Architecture parameters include the event execution times and the message sending delays. The interactions between these two sets of paramenters are difficult to analyze.
Fortunately, several inportant metrics for parallel simulation are determined entirely by logical parameters. These metrics can be investigated without considering architecture parameters. In this paper, we show that two important metrics of Chandy-Misra simulation, the number of deadlocks and the number of null messages, are independent of architecture parameters. These results can be used to test the correctness of a Chandy-Misra simulator. Also, based on these results, certain output metric analysis of a Chandy-Misra simulation are simplified.
Keywords: chandy-misra protocol, conservative parallel simulation, deadlock, deadlock avoidance, deadlock detection, discrete event simulation, null message
Received January 28, 1991; revised October 28, 1991.
Communicated by Ferng-Ching Lin.