A two-list synchronization procedure for discrete event simulation
- 1 December 1981
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 24 (12), 825-829
- https://doi.org/10.1145/358800.358805
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.Keywords
This publication has 5 references indexed in Scilit:
- Analysis of the Time Indexed List Procedure for Synchronization of Discrete Event SimulationsManagement Science, 1978
- An efficient data structure for the simulation event setCommunications of the ACM, 1977
- Heaps applied to event driven mechanismsCommunications of the ACM, 1976
- Improved event-scanning mechanisms for discrete event simulationCommunications of the ACM, 1975
- A comparison of simulation event list algorithmsCommunications of the ACM, 1975