Speculative parallel simulation with an adaptive throttle scheme

ABSTRACT

Excessive rollback recoveries due to overoptimistic event execution in Time Warp simulators often degrade their runtime performance. This paper presents a two-sided throttling scheme to dynamically adjust the event execution speed of Time Warp simulators. The proposed throttle is based on a new concept called global progress window, which allows the individual simulation process to be positioned on a global time scale, thereby to accelerate or suspend their event execution. As each simulation process can be throttled to a steady state, excessive rollback recoveries due to causality errors can be avoided. To quantify the effect of rollbacks and for purpose of comparing different Time Warp implementations, we propose two new measures called RPE (number of Rollback events Per committed Event), and E (relative Effectiveness in reducing rollback overhead). Our implementation results show that the proposed throttle effectively regulates the proceeding of each simulation process, resulting in a significant reduction in rollback thrashing and elapsed time.

REFERENCES

• 1: D. Ball and S. Hoyt, "The Adaptire Time-IVarp Con. currency Control Algorithm," Proc. of the SCS Multiconference on Distributed Simulationt pp. 174-177, 1990.
• 2: 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
• 3: 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
• 4: A. Ferscha, "Parallel and Distributed Simulation of Discrete Event Systems," in Handbook of Parallel and Distributed Computing, McGraw-Hill, 1995.
• 5: 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
• 6: A. Gafni, "Rollback Mechanisms for Optimistic Distributed Simulation Systems," Proc. of the SCS Multiconference on Distributed Simulation, Vol. 19(3), pp. 61-67, 1988.
• 7: Al Geist , Adam Beguelin , Jack Dongarra , Weicheng Jiang , Robert Manchek , Vaidy Sunderam, PVM: Parallel virtual machine: a users' guide and tutorial for networked parallel computing, MIT Press, Cambridge, MA, 1995
• 8: Stewart V. Hoover , Ronald F. Perry, Simulation: a problem-solving approach, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 9: 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]
• 10: 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]
• 11: Yi-Bing Lin , Bruno R. Preiss, Optimal memory management for time warp parallel simulation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.1 n.4, p.283-307, Oct. 1991 [doi>10.1145/130611.130612]
• 12: 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]
• 13: Jayadev Misra, Distributed discrete-event simulation, ACM Computing Surveys (CSUR), v.18 n.1, p.39-65, March 1986 [doi>10.1145/6462.6485]
• 14: 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]
• 15: Peter L. Reiher and David Jefferson, "Virtual Time Based Dynamic Load Management in the Time Warp Operating System," Proc. of the ACM/IEEE/SCS Workshop on Parallel and Distributed Simulation (PADS), pp. 103-111, 1990.
• 16: Rolf Schlagenhaft , Martin Ruhwandl , Christian Sporrer , Herbert Bauer, Dynamic load balancing of a multi-cluster simulator on a network of workstations, Proceedings of the ninth workshop on Parallel and distributed simulation, p.175-180, June 13-16, 1995, Lake Placid, New York, United States
• 17: J. S. Steinman, "SPEEDES: A Multiple Synchronization Environment for Parallel Discrete-Event Simulation," International Journal in Computer Simulation, Vol. 2, pp. 251-286, 1992.
• 18: 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
• 19: Y. M. Teo, S. C. Toy and S. T. Kong, "Structured Parallel Simulation o} Discrete-Event Systems," Proc. of Sixth Parallel Computing Workshop, Kawasaki, JAPAN, pp. 2-A-1 to 2-A-10, Nov. 12-13, 1996.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Parallel

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Experimentation, Measurement