On analyzing events to estimate the possible speedup of parallel discrete event simulation

ABSTRACT

We describe in this paper a new event based approach for estimating the possible speed up in parallel discrete event simulation which is similar to Berry and Jefferson's method. This method calculates a critical path through a graph developed from a trace of a simulation and from constraints on the order of processing of event instances that ensure correctness of the simulation. Different ways of classifying event instances to determine required constraints are presented. A software system that uses this approach is described and examples are presented.

REFERENCES

• 1: Berry, O., and Jefferson, D. (1985). "Critical Path Analysis of Distributed Simulation", Distributed Simulation, 1985 (Paul Reynolds, ed.), Simulation Series, 15, 2, 57--60, Society for Computer Simulation.
• 2: Berry, O. (1986). Ph.D. Thesis, Department of Computer Science, University of Southern California.
• 3: Chacko, J. and Sargent, R. G. (1989). BUBBLES, The Event Graph Simulator. Simulation Research Group, 441 Link Hall, Syracuse University, Syracuse, NY 13244.
• 4: Cota, B. A. and Sargent, R. G. (1989). "An Algorithm for Parallel Discrete Event Simulation Using Common Memory", Proceedings of 22nd Annual Simulation Symposium, (A. H. Raton, ed.), 23--31, March 1989, Tampa, FL.
• 5: Even, S. (1979). Graph Algorithms. Computer Science Press, Potomac, MD.
• 6: Franta, W. R. (1977). The Process View of Simulation. North-Holland, New York.
• 7: Jefferson, D. (1985). "Virtual Time", ACM TOPLAS, 7, 3, July 1985, 404--425.
• 8: Misra, J. (1986). "Distributed Discrete-Event Simulation", ACM Computer Surveys, 18, 1, 39--65.
• 9: Sargent, R. G. (1988). "Event Graph Modelling for Simulation with an Application to Flexible Manufacturing Systems", Management Science, 34, 10, 1231--51.
• 10: Schruben, L. (1983). "Simulation Modeling with Event Graphs", Communications of the ACM, 26, 957--963.
• 11: Wagner, D. B. and Lazowska, E. D. (1989). "Parallel Simulation of Queueing Networks: Limitations and Potentials," Proceedings of the International Conference on Measurement and Modeling of Computer Systems, 146--155, May 1989, Berkeley, CA.
• 12: Zeigler, B. P. (1976). Theory of Modelling and Simulation. John Wiley and Sons, New York.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  G. Mathematics of Computing
  G.m MISCELLANEOUS
      Subjects: Queueing theory**

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.1 Simulation Theory
          Subjects: Types of simulation (continuous and discrete)*

General Terms:
Algorithms, Design, Experimentation, Performance