Algorithms and analyses: piggy-backed time-stepped simulation with ‘super-stepping’

ABSTRACT

We propose an optimization technique for reducing global synchronizations in traditional time-stepped simulations. Time-stepped simulations are known to be efficient when events are frequent or dense. However, when events are less frequent (when compared to the size of time-steps) the performance of time-stepped simulations drop noticeably. This paper aims at improving the performance of traditional time-stepped simulations during low frequency periods and maintaining its efficiency during high frequency periods. We focus on interactive simulations which have tight real-time interactive constraints. The proposed optimization is achieved by informing the host about future events. This information is ‘piggybacked’ on the ready messages sent by the participating Processing Elements (PE) to the host. We maintain simulation efficiency by switching between the proposed technique and the traditional technique depending on the observed event density. To achieve this switching we introduce a concept called ‘super-stepping’. A probabilistic method is used to optimize ‘super-step’ size.

REFERENCES

• 1: Ayani, R. 1989. A parallel simulation scheme based on distance between objects, Proceedings of the SCS Multiconference on distributed simulations. Volume 21, Pages 113--118.
• 2: Banks, J., Carson II, J. S., and Nelson, B. L. 1996. Discrete-Event System Simulation, Second Edition, Prentice Hall.
• 3: Buxton, J. N., and Laski J. G. 1962. Control and Simulation Language, Computer Journal, Volume 5(3), 1962.
• 4: Wentong Cai , Emmanuelle Letertre , Stephen J. Turner, Dag consistent parallel simulation: a predictable and robust conservative algorithm, Proceedings of the eleventh workshop on Parallel and distributed simulation, p.178-181, June 10-13, 1997, Lockenhaus, Austria
• 5: 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]
• 6: Phillip M. Dickens , Paul F. Reynolds, Jr., A performance model for parallel simulation, Proceedings of the 23rd conference on Winter simulation, p.618-626, December 08-11, 1991, Phoenix, Arizona, United States
• 7: Stephen G. Eick , Albert G. Greenberg , Boris D. Lubachevsky , Alan Weiss, Synchronous relaxation for parallel simulations with applications to circuit-switched networks, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.3 n.4, p.287-314, Oct. 1993 [doi>10.1145/159737.159744]
• 8: Fujimoto, R. M. 1989. Performance Measurements of Distributed Simulation Strategies, Transactions of the Society for Computer Simulation, Volume 6, Pages 89--132.
• 9: Gan, B. P., Low, Y. H., Cai, W., Turner, S. J., Jain, S., Hsu, W. J., and Huang, S. Y. 2001. The Development of Conservative Superstep Protocols for Shared Memory Multiprocessor Systems, Parallel and Distributed Computing Practices, Volume 4(1), pp. 1--17.
• 10: Groselj B., and Tropper C. 1988. The Time-of-Next-Event Algorithm, Proceedings of the SCS Multiconference on Distributed Simulation, pp. 25--29, Society for Computer Simulation.
• 11: David M. Nicol, The cost of conservative synchronization in parallel discrete event simulations, Journal of the ACM (JACM), v.40 n.2, p.304-333, April 1993 [doi>10.1145/151261.151266]
• 12: Lubachevsky, B. D. 1988. Bounded Lag Distributed Discrete Event Simulation, Proceedings of the SCS Multi-conference on Distributed Simulation, Pages 183--191, Society for Computer Simulation.
• 13: Lubachevsky, B. D. 1989. Scalability of the bounded lag distributed discrete event simulation, In Distributed Simulation, Volume 21(2), pp. 100--107.
• 14: Page, E. H. 1997. Zero Lookahead in a Distributed Time-Stepped Simulation, Simulation Digest, Volume 26(2), pp. 4--13.