NPSI adaptive synchronization algorithms for PDES

ABSTRACT

Adaptive approaches to synchronization in parallel discrete event simulations hold significant potential for performance improvement. We contend that an adaptive approach based on low cost near-perfect system state information is the most likely to yield a consistently efficient synchronization algorithm. We suggest a framework by which NPSI (near-perfect state information) adaptive protocols could be designed and describe the first such protocol-elastic time algorithm. We present performance results which show that NPSI protocols are very promising. In particular, they have the capacity to outperform time warp consistently in both time and space.

REFERENCES

• 1: Ball, D. and S. Hoyt. 1990. The adaptive Time-Warp concurrency control algorithm. Proceedings of the SCS Multiconference on Distributed Simulation, 174-177.
• 2: Steven Bellenot, Performance of a riskfree Time Warp operating system, Proceedings of the seventh workshop on Parallel and distributed simulation, p.155-158, May 16-19, 1993, San Diego, California, United States
• 3: 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
• 4: Phillip Mathew Dickens, Analysis of the aggressive global windowing algorithm, University of Virginia, Charlottesville, VA, 1993
• 5: Dickens, P.M. and P.F. Reynolds, Jr. 1990. SRADS with local rollback. Proceedings of the 1990 SCS Multiconference on Distributed Simulation, 161-164.
• 6: Domenico Ferrari , Songnian Zhou, An Empirical Investigation of Load Indices for Load Balancing, University of California at Berkeley, Berkeley, CA, 1987
• 7: Alois Ferscha , Satish K. Tripathi, Parallel and distributed simulation of discrete event systems, University of Maryland at College Park, College Park, MD, 1994
• 8: 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]
• 9: Richard Fujimoto , David Nicol, State of the art in parallel simulation, Proceedings of the 24th conference on Winter simulation, p.246-254, December 13-16, 1992, Arlington, Virginia, United States [doi>10.1145/167293.167344]
• 10: R. L. Gimarco, Distributed simulation using hierarchical rollback, Proceedings of the 21st conference on Winter simulation, p.621-629, December 04-06, 1989, Washington, D.C., United States [doi>10.1145/76738.76818]
• 11: Hamnes, D.O. and A. Tripathi. 1994. Evaluation of a local adaptive protocol for distributed discrete event simulation. Proceedings of the 1994 International Conference on Parallel Processing, Vol. III, 127-134.
• 12: 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]
• 13: Lin. Y-B. 1992. Memory management algorithms for optimistic parallel simulation. Proceedings of the 6th Workshop on Parallel and Distributed Simulation, 43- 52.
• 14: 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]
• 15: Madisetti, V.K. 1993. Randomized algorithms for selfsynchronization. Private communication.
• 16: Madisetti, V.K., D.A. Hardaker, and R.M. Fujimoto. 1992. The MIMDIX operating system for parallel simulation. Proceedings of the 6th Workshop on Parallel and Distributed Simulation, 65-74.
• 17: 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]
• 18: Jeff McAffer, A unified distributed simulation system, Proceedings of the 22nd conference on Winter simulation, p.415-422, December 09-12, 1990, New Orleans, Louisiana, United States
• 19: Mehl, H. 199f. Speed-up of conservative distributed discrete event simulation methods by speculative computing. Proceedings of the 5th Workshop on Parallel and Distributed Simulation, 163-166.
• 20: David M. Nicol, Performance bounds on parallel self-initiating discrete-event simulations, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.1 n.1, p.24-50, Jan. 1991 [doi>10.1145/102810.102812]
• 21: David M. Nicol , Paul F. Reynolds, Jr., Optimal Dynamic Remapping of Data Parallel Computations, IEEE Transactions on Computers, v.39 n.2, p.206-219, February 1990 [doi>10.1109/12.45206]
• 22: Palaniswamy, A.C. and P.A. Wilsey. 1993. Adaptive bounded time window in an optimistically synchronized simulator. Proceedings of the 3rd Great Lakes Symposium on VLSI, 114-118.
• 23: 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
• 24: 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
• 25: K. Ramamritham , J. A. Stankovic , W. Zhao, Distributed Scheduling of Tasks with Deadlines and Resource Requirements, IEEE Transactions on Computers, v.38 n.8, p.1110-1123, August 1989 [doi>10.1109/12.30866]
• 26: 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]
• 27: 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]
• 28: Paul F. Reynolds, Jr. , Carmen M. Pancerella , Sudhir Srinivasan, Making parallel simulations go fast, Proceedings of the 24th conference on Winter simulation, p.646-656, December 13-16, 1992, Arlington, Virginia, United States [doi>10.1145/167293.167658]
• 29: Sokol, L.M., D.P. Briscoe, and A.P. Wieland 1988. MTW: a strategy for scheduling discrete events fgr concurrent execution. Proceedings of the SCS Multiconference on Distributed Simulation, 34-42.
• 30: Sudhir Srinivasan , Paul F. Reynolds, Jr., Non-interfering GVT computation via asynchronous global reductions, Proceedings of the 25th conference on Winter simulation, p.740-749, December 12-15, 1993, Los Angeles, California, United States [doi>10.1145/256563.256834]
• 31: Paul F. Reynolds, Jr., NPSI adaptive synchronization algorithms for PDES, University of Virginia, Charlottesville, VA, 1994
• 32: Jeff S. Steinman, Interactive SPEEDES, Proceedings of the 24th annual symposium on Simulation, p.149-158, April 1991, New Orleans, Louisiana, United States
• 33: 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
• 34: Turner, S.J. and M.Q. Xu. 1992. Performance evaluation of the Bounded Time Warp algorithm. Proceedings of the 6th Workshop on Parallel and Distributed Simulation, 117-126.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Synchronization

General Terms:
Algorithms, Design, Performance, Theory