A performance evaluation methodology for parallel simulation protocols

ABSTRACT

Most experimental studies of the performance of parallel simulation protocols use speedup or number of events processed per unit time as the performance metric. Although helpful in evaluating the usefulness of parallel simulation for a given simulation model, these metrics tell us little about the efficiency of the simulation protocol used. In this paper, we describe an Ideal Simulation Protocol (ISP), based on the concept of critical path, which experimentally computes the best possible execution time for a simulation model on a given parallel architecture. Since ISP computes the bound by actually executing the model on the given parallel architecture, it is much more realistic than that computed by a uniprocessor critical path analysis. The paper illustrates, using parameterized synthetic benchmarks, how an ISP-based performance evaluation can lead to much better insights into the performance of parallel simulation protocols than what would be gained from speedup graphs alone.

REFERENCES

• 1: Anurag Kumar , Rajeev Shorey, Stability of event synchronisation in distributed discrete event simulation, Proceedings of the eighth workshop on Parallel and distributed simulation, p.65-72, July 06-08, 1994, Edinburgh, Scotland, United Kingdom
• 2: R. L. Bagrodia , Wen-Toh Liao, Maisie: A Language for the Design of Efficient Discrete-Event Simulations, IEEE Transactions on Software Engineering, v.20 n.4, p.225-238, April 1994 [doi>10.1109/32.277572]
• 3: O. Berry and D. Jefferson. Critical path analysis of distributed simulation. In Proceedings of 1985 SCS Multzconference on Distmbuted Simulatzon, pages 57-60, January 1985.
• 4: K. M. Chandy , J. Misra, Asynchronous distributed simulation via a sequence of parallel computations, Communications of the ACM, v.24 n.4, p.198-206, April 1981 [doi>10.1145/358598.358613]
• 5: K.M. Chandy and R. Sherman. The conditional event approach to distributed simulation. In Distributed Simulation Conference, Miami, 1989.
• 6: D. Conklin, J. Cleary, and B. Unger. The sharks world: A study in distributed simulation. In 1990 Simulation Multiconference: Distributed Simulation, San Diego, California, January 1990.
• 7: Richard M. Fujimoto, Parallel discrete event simulation, Communications of the ACM, v.33 n.10, p.30-53, Oct. 1990 [doi>10.1145/84537.84545]
• 8: R. M. Fujimoto. Performance measurements of distributed simulation strategies. Technical Report Tech. Rep. UUCS-87-026a, University of Utah, Salt Lake City, 1987.
• 9: David Jefferson , Peter Reiher, Supercritical speedup, Proceedings of the 24th annual symposium on Simulation, p.159-168, April 1991, New Orleans, Louisiana, United States
• 10: Vikas Jha , Rajive L. Bagrodia, Transparent implementation of conservative algorithms in parallel simulation languages, Proceedings of the 25th conference on Winter simulation, p.677-686, December 12-15, 1993, Los Angeles, California, United States [doi>10.1145/256563.256814]
• 11: Yi-Bing Lin , Edward D. Lazowska, Understanding the limits of optimistic and conservative parallel simulation, 1990
• 12: D.B. Wagner and E.D. Lazoska. Parallel simulation of queueing networks: Limitations and potentials. Technical report 88-09-05, Dept. of Computer Science, University of Washington, Seattle 98195, September 1988.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Parallel

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures

General Terms:
Measurement, Performance, Theory

Keywords:
Parallel and Distributed Simulation, Critical Path, Experimental Performance Evaluation, Null Message Protocol