Adaptive protocols for parallel discrete event simulation

ABSTRACT

This paper reviews issues concerning the design of adaptive protocols for parallel discrete event simulation (PDES). The need for adaptive protocols are motivated in the background of the synchronization problem that has driven much of the research in this field. Traditional conservative and optimistic protocols and their hybrid variants are also discussed. Adaptive synchronization protocols are reviewed with special reference to their characteristics regarding the aspects of the simulation state that influence the adaptive decisions and the control parameters used. Finally, adaptive load management and scheduling strategies and their relationship to the synchronization protocol are discussed.

REFERENCES

• 1: Ahmed, H., R. RSnngren, and R. Ayani 1994. Impact of event scheduling on performance of Time Warp parallel simulations. In Proceedings of the 27th Annual Hawaii Intl. Conf. on System Sciences.
• 2: Arvind, K. and C. Smart 1992. Hierarchical parallel discrete event simulation in composite ELSA. In 6th Workshop on Parallel and Distributed Simulation, pp. 147-158.
• 3: Ball, D. and S. Hoyt 1990. The adaptive Time- Warp concurrency control algorithm. Proceedings of the SCS Multiconference on Distributed Simulation 22 (1), 174-177.
• 4: Burdorf, C. and J. Marti 1993. Load balancing strategies for Time Warp on multi-user workstaions. The Computer Journal 36 (2), 168-176.
• 5: Chandy, K. M. and j. Misra 1979. Distributed simulation: A case study in design and verification of distributed programs. IEEE Transactions on Software Engineering SE-5(5), 440-452.
• 6: Samir R. Das, Estimating the cost of throttled execution in time warp, Proceedings of the tenth workshop on Parallel and distributed simulation, p.186-189, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 7: Samir R. Das , Richard M. Fujimoto, A performance study of the cancelback protocol for Time Warp, ACM SIGSIM Simulation Digest, v.23 n.1, p.135-142, July 1993
• 8: Samir R. Das , Richard M. Fujimoto, An adaptive memory management protocol for Time Warp parallel simulation, Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.201-210, May 16-20, 1994, Nashville, Tennessee, United States
• 9: Dickens, P. M. and P. F. Reynolds, Jr. 1990. SRADS with local rollback. Proceedings of the SCS Multiconference on Distributed Simulation 22(1), 161-164.
• 10: Ferscha, A. 1995a. Parallel and distributed simuation of discrete event systems. In A. Y. H. Zomaya (Ed.), Parallel and Distributed Computing Handbook, Chapter 35. McGraw-Hill.
• 11: Alois Ferscha, Probabilistic adaptive direct optimism control in Time Warp, Proceedings of the ninth workshop on Parallel and distributed simulation, p.120-129, June 13-16, 1995, Lake Placid, New York, United States
• 12: Ferscha, A. and G. Chiola 1994. Self adaptive logical processes: The probabilistic distributed simulation protocol. In Proceedings of the 27th Annual Simulation Symposium, pp. 78-88.
• 13: A. Ferscha , J. Luthi, Estimating rollback overhead for optimism control in Time Warp, Proceedings of the 28th Annual Simulation Symposium, p.2, April 25-28, 1995
• 14: Josef Fleischmann , Philip A. Wilsey, Comparative analysis of periodic state saving techniques in time warp simulators, Proceedings of the ninth workshop on Parallel and distributed simulation, p.50-58, June 13-16, 1995, Lake Placid, New York, United States
• 15: Fujimoto, R. M. 1989. Performance measurements of distributed simulation strategies. Transactzons of the Society for Computer Simulation 6(2), 89-132.
• 16: 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]
• 17: Richard M. Fujimoto, Parallel and distributed discrete event simulation: algorithms and applications, Proceedings of the 25th conference on Winter simulation, p.106-114, December 12-15, 1993, Los Angeles, California, United States [doi>10.1145/256563.256596]
• 18: Fujimoto, R. M. 1993b. Parallel discrete event simulation: Will the field survive? ORSA Journal of Computzng 5 (3), 213-230.
• 19: D. W. Glazer , C. Tropper, On Process Migration and Load Balancing in Time Warp, IEEE Transactions on Parallel and Distributed Systems, v.4 n.3, p.318-327, March 1993 [doi>10.1109/71.210814]
• 20: Hamnes, D. O. and A. Tripathi 1994a. Evaluation of a local adaptive protocol for distributed discrete event simulation. In Proceedings of the 199~ Internatzonal Conference on Parallel Processing, pp. III:127-134.
• 21: Donald O. Hamnes , Anand Tripathi, Investigations in adaptive distributed simulation, Proceedings of the eighth workshop on Parallel and distributed simulation, p.20-23, July 06-08, 1994, Edinburgh, Scotland, United Kingdom
• 22: David R. Jefferson, Virtual time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.3, p.404-425, July 1985 [doi>10.1145/3916.3988]
• 23: David Jefferson, Virtual time II: storage management in conservative and optimistic systems, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.75-89, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93403]
• 24: Lin, Y.-B. and E. D. Lazowska 1990. Optimality considerations of "Time Warp" parallel simulation. Proceedings of the SCS Multiconference on Distributed Simulation 22 (1), 29-34.
• 25: Lipton, R. J. and D. W. Mizell 1990. Time Warp vs. Chandy-Misra: A worst-case comparison. Proceedings of the SCS Multiconference on Distributed Simulation 22(1), 137-143.
• 26: B. D. Lubachevsky, Efficient distributed event-driven simulations of multiple-loop networks, Communications of the ACM, v.32 n.1, p.111-123, Jan. 1989 [doi>10.1145/63238.63247]
• 27: B. Lubachevsky , A. Shwartz , A. Weiss, Rollback sometimes works...if filtered, Proceedings of the 21st conference on Winter simulation, p.630-639, December 04-06, 1989, Washington, D.C., United States [doi>10.1145/76738.76819]
• 28: Boris Lubachevsky , Adam Schwartz , Alan Weiss, An analysis of rollback-based simulation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.1 n.2, p.154-193, April 1991 [doi>10.1145/116890.116912]
• 29: Vijay Madisetti , Jean Walrand , David Messerschmitt, Wolf: a rollback algorithm for optimistic distributed simulation systems, Proceedings of the 20th conference on Winter simulation, p.296-305, December 12-14, 1988, San Diego, California, United States [doi>10.1145/318123.318205]
• 30: Vijay K. Madisetti , David A. Hardaker , Richard M. Fujimoto, The MIMDIX environment for parallel simulation, Journal of Parallel and Distributed Computing, v.18 n.4, p.473-483, Aug. 1993 [doi>10.1006/jpdc.1993.1078]
• 31: Mehl, H. 1991. Speedup of conservative distributed discrete-event simulation methods by speculative computing. Proceedings of the Multiconference on Advances in Parallel and Distributed Simulation 23(1), 163-166.
• 32: 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]
• 33: Nicol, D. M. and R. M. Fujimoto 1994. Parallel simulation today. Annals of Operations Research 53, 249-286.
• 34: Palaniswamy, A. C. and P. A. Wilsey 1993. Adaptive bounded time windows in an optimistically synchronized simulator. In Great Lakes VLSI Conference, pp. 114-118.
• 35: Avinash C. Palaniswamy , Philip A. Wilsey, Scheduling time warp processes using adaptive control techniques, Proceedings of the 26th conference on Winter simulation, p.731-738, December 11-14, 1994, Orlando, Florida, United States
• 36: Atul Prakash , Rajalakshmi Subramanian, Filter: an algorithm for reducing cascaded rollbacks in optimistic distributed simulations, Proceedings of the 24th annual symposium on Simulation, p.123-132, April 1991, New Orleans, Louisiana, United States
• 37: Hassan Rajaei , Rassul Ayani , Lars-Erik Thorelli, The local Time Warp approach to parallel simulation, Proceedings of the seventh workshop on Parallel and distributed simulation, p.119-126, May 16-19, 1993, San Diego, California, United States
• 38: Peter L. Reiher , David Jefferson, Dynamic load management in the time warp operating system, Transactions of the Society for Computer Simulation International, v.7 n.2, p.91-120, Jun. 1990
• 39: P. L. Reiher , F. Wieland , D. Jefferson, Limitation of optimism in the time warp operating system, Proceedings of the 21st conference on Winter simulation, p.765-770, December 04-06, 1989, Washington, D.C., United States [doi>10.1145/76738.76834]
• 40: Paul F. Reynolds, Jr., A spectrum of options for parallel simulation, Proceedings of the 20th conference on Winter simulation, p.325-332, December 12-14, 1988, San Diego, California, United States [doi>10.1145/318123.318209]
• 41: Paul F. Reynolds, Jr. , Carmen M. Pancerella , Sudhir Srinivasan, Design and performance analysis of hardware support for parallel simulations, Journal of Parallel and Distributed Computing, v.18 n.4, p.435-453, Aug. 1993 [doi>10.1006/jpdc.1993.1076]
• 42: Sokol, L. M., D. P. Briscoe, and A. P. Wieland 1988. MTW: a strategy for scheduling discrete simulation events for concurrent execution. Proceedings of the SCS Multiconference on Distributed Simulation 19(3), 34-42.
• 43: Sudhir Srinivasan , Paul F. Reynolds, Jr., NPSI adaptive synchronization algorithms for PDES, Proceedings of the 27th conference on Winter simulation, p.658-665, December 03-06, 1995, Arlington, Virginia, United States [doi>10.1145/224401.224705]
• 44: Sudhir Srinivasan , Paul F. Reynolds, Jr., Elastic time, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.8 n.2, p.103-139, April 1998 [doi>10.1145/280265.280267]
• 45: Steinman, J. 1992a. SPEEDES: A multiplesynchronization environment for parallel discrete event simulation. International Journal of Computer Simulation 2(3), 251-286.
• 46: Steinman, J. 1992b. SPEEDES: A unified approach to parallel simulation. In 6th Workshop on Parallel and Distributed Simulation, pp. 75-84.
• 47: Jeff S. Steinman, Breathing Time Warp, Proceedings of the seventh workshop on Parallel and distributed simulation, p.109-118, May 16-19, 1993, San Diego, California, United States
• 48: Turner, S. J. and M. Q. Xu 1992. Per!~ormance evaluation of the bounded Time Warp algorithm. Proceedings of the SCS Multiconference on Parallel and Distributed Simulation 24(3), 117-126.