A two-list synchronization procedure for discrete event simulation

ABSTRACT

The traditional mechanism for maintaining a list of pending events in a discrete event simulation is the simple linked list. However, in large scale simulations this list often becomes cumbersome to maintain since the number of pending events may become quite large. As a result, the execution time required by the simple linked list is often a significant portion of total simulation time. Several papers have been published suggesting improved synchronization procedures. The most efficient procedures reported are the time-indexed procedure and the two-level procedure. Both methodologies are much more efficient than simple linked lists; however, neither has been adopted by a general purpose simulation language. Further, both procedures require external parameter definition, which is a major handicap to their adoption by a general purpose language. This paper introduces a new sychronization procedure, the two-list procedure, which is much faster than simple linked lists for large pending event files. This procedure was designed for implementation in Fortran, and properly implemented it is transparent to the user. Thus it is ideal for adoption by general purpose simulation languages.

REFERENCES

• 1: Electric Power Institute, Texas A&M University, Large-scale system effectiveness analysis. Final report on Contract F.D.-77-S-01- S 104 to the U.S. Department of Energy.
• 2: Engelbrecht-Wiggans, R., and Maxwell, W. L. Analysis of the time indexed list procedure for synchronization of discrete event simulations. Manage. Sci. 24, 13 (Sept. 1978), 1417-1427.
• 3: W. R. Franta , Kurt Maly, An efficient data structure for the simulation event set, Communications of the ACM, v.20 n.8, p.596-602, Aug. 1977 [doi>10.1145/359763.359801]
• 4: Gaston H. Gonnet, Heaps applied to event driven mechanisms, Communications of the ACM, v.19 n.7, p.417-418, July 1976 [doi>10.1145/360248.360261]
• 5: Markowitz, H. M., Karr, H. W., and Hadsner, B. SIMSCRIPT: A Simulation Programming Language. Prentice-Hall, Englewood Cliffs, N.J., 1963.
• 6: Pritsker, A. A. B. The GA SP-I V Simulation Language. Wiley,New York, 1974.
• 7: Thomas J. Schriber, Simulation Using GPSS, Krieger Publishing Co., Inc., Melbourne, FL, 1990
• 8: Jean G. Vaucher , Pierre Duval, A comparison of simulation event list algorithms, Communications of the ACM, v.18 n.4, p.223-230, April 1975 [doi>10.1145/360715.360758]
• 9: F. Paul Wyman, Improved event-scanning mechanisms for discrete event simulation, Communications of the ACM, v.18 n.6, p.350-353, June 1975 [doi>10.1145/360825.360873]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Documentation, Management

Keywords:
discrete event simulation, event synchronization, linked lists and chains, simulation file structures