Effects of the checkpoint interval on time and space in time warp

ABSTRACT

Optimistically synchronized parallel discrete-event simulation is based on the use of communicating sequential processes. Optimistic synchronization means that the processes proceed under the assumption that a synchronized execution schedule is fortuitous. Periodic checkpointing of the state of a process allows the process to roll back to an earlier state when synchronization errors are detected. This article examines the effects of varying the checkpoint interval on the execution time and memory space needed to perform a parallel simulation.The empirical results presented in this article were obtained from the simulation of closed stochastic queuing networks with several different topologies. Various intraprocessor process-scheduling algorithms and both lazy and aggressive cancellation strategies are considered. The empirical results are compared with analytical formulae predicting time-optimal checkpoint intervals. Two modes of operation, throttling and thrashing, have been noted and their effect examined. As the checkpoint interval is increased from one, there is a throttling effect among processes on the same processor, which improves performance. When the checkpoint interval is made too large, there is a thrashing effect caused by interaction between processes on different processors. It is shown that the time-optimal and space-optimal checkpoint intervals are not the same. Furthermore, a checkpoint interval that is too small affects space adversely more than time, whereas, a checkpoint interval that is too large affects time adversely more than space.

REFERENCES

• 1: BELLENOT, S. 1992. State skipping performance with the Time Warp Operating System. In Proceedings of the 1992 Workshop on Parallel and Distrzbuted Simulation (Newport Beach, Calif., Jan. 1992), M. Abrams and P. F. Reynolds Jr., Eds. IEEE, New York, 53-61.
• 2: Christopher Burdorf , Jed Marti, Non-preemptive time warp scheduling algorithms, ACM SIGOPS Operating Systems Review, v.24 n.2, p.7-18, April 1990 [doi>10.1145/382258.382787]
• 3: CHANDY, K. M. AND MISRA, J. 1979. Distributed simulation: A case study in design and verification of distributed programs. IEEE Trans. Softw. Eng. 5, 5 (Sept.), 440 452.
• 4: CHANDY, K. M., BROWNE, J. C., DtSSLY, C. W., AND UHR~G, W. R. 1975. Analytic models for rollback and recovery strategies in data base systems. IEEE Trans. Softw. Eng. 1, i (Mar.), 100-110.
• 5: Richard M. Fujimoto, Optimistic approaches to parallel discrete event simulation, Transactions of the Society for Computer Simulation International, v.7 n.2, p.153-191, Jun. 1990
• 6: FUJIMOTO, R.M. 1988. Lookahead in parallel discrete event simulation. In Proceedings of the 1988 Irternatlona{ Conference on Parallel Processing (St Charles, Ill, Aug. 1988). Vol. III, Pennsylvania State Umversity, University Park, 34-41
• 7: GAFNI, A. 1985 Space management and cancellation mechanisms for Time Warp. Tech. Rep. TR-85-341, Univ. of Southern California, Los Angeles, Calif.
• 8: Erol Gelenbe, On the Optimum Checkpoint Interval, Journal of the ACM (JACM), v.26 n.2, p.259-270, April 1979 [doi>10.1145/322123.322131]
• 9: Vincenzo Grassi , Lorenzo Donatiello , Salvatore Tucci, On the Optimal Checkpointing of Critical Tasks and Transaction-Oriented Systems, IEEE Transactions on Software Engineering, v.18 n.1, p.72-77, January 1992 [doi>10.1109/32.120317]
• 10: D. Jefferson , B. Beckman , F. Wieland , L. Blume , M. Diloreto, Time warp operating system, Proceedings of the eleventh ACM Symposium on Operating systems principles, p.77-93, November 08-11, 1987, Austin, Texas, United States
• 11: 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]
• 12: LIN, Y.-B. AND L^ZOWSKA, E.D. 1990a. Processor scheduling for Time Warp parallel simulation. Tech. Rep. 90-03-03, Dept. of Computer Science and Engineering, University of Washington, Seattle.
• 13: L~N, Y.-B. AND LAZOWS~, E D. 1990b. Reducing the state saving overhead for Time Warp parallel simulation. Tech. Rep. 90-02-03, Dept. of Computer Science and Engineering, Umverslty of Washington, Seattle
• 14: Yi-Bing Lin , Bruno R. Preiss , Wayne M. Loucks , Edward D. Lazowska, Selecting the checkpoint interval in time warp simulation, Proceedings of the seventh workshop on Parallel and distributed simulation, p.3-10, May 16-19, 1993, San Diego, California, United States
• 15: LOUCKS, W. M. AND PREISS, B. R 1990. The role of knowledge m distributed smmlation. In Proceedtngs of SCS Multlconference on Dlstrzbuted Sirnulatwn (San Diego, Calif., Jan. 1990). SCS, San Diego, Calif., 9 16.
• 16: N. Manjikian , W. M. Loucks, Using split event sets to form and schedule event combinations in discrete event simulation, Proceedings of the 25th annual symposium on Simulation, p.184-191, April 1992, Orlando, Florida, United States
• 17: Jayadev Misra, Distributed discrete-event simulation, ACM Computing Surveys (CSUR), v.18 n.1, p.39-65, March 1986 [doi>10.1145/6462.6485]
• 18: David N. Nicol, High performance parallelized discrete event simulation of stochastic queueing networks, Proceedings of the 20th conference on Winter simulation, p.306-314, December 12-14, 1988, San Diego, California, United States [doi>10.1145/318123.318206]
• 19: V. F. Nicola , J. M. van Spanje, Comparative Analysis of Different Models of Checkpointing and Recovery, IEEE Transactions on Software Engineering, v.16 n.8, p.807-821, August 1990 [doi>10.1109/32.57620]
• 20: PRE~SS, B. R. 1990. Performance of discrete event simulation on a multiprocessor using optlmlstm and conservai;ive synchronization. In Proceedhzgs of the 1990 Internatzonal Conference on Parallel Processing (St. Charles, Ill, Aug 1990). Pennsylvania State University, University Park, 218 222.
• 21: PREISS, B.R. 1989a. The Yaddes distributed discrete event slmulatmn specification language and executmn enwronments. CCNG Tech Rep. E-181, Dept. of Electrical Engineering- and Computer Communications Networks Group, Univ. of Waterloo, Waterloo, Ontario
• 22: PREISS, B.R. 1989b The Yaddes distributed discrete event mmulatmn specification language and execution environments, In Proceedings of the SCS Mult~conferetwe on Dlstrtbuted Szmulatlon (Tampa, Fla., Mar. 1989) SCS, San Diego, Calif., 139-144.
• 23: PR~TSS, B R AND LouCKS, W. M. 1990 The in, pact o~ lookahead on the performance of conservative dmtributed simulation. In Proceedings of the 1990 European Multzconferencc--Stmulat~on Methodologies, Languages and Archztectures (Nuremberg, Germany, June 1990). SCS, San Diego, Cahf., 204-209
• 24: PREISS, B. R. AND LOUCKS, W.M. 1989. Predictmn and lookahead m distributed simulation. CCNG Tech Rep E-191, Dept. of Electrical Engineenng and Computer Commumcatlons Networks Group, Univ of Waterloo, Waterloo, Ontario.
• 25: P~E~SS, B. R. AND MAClNTY~E, I.D. 1990. YADDES--Yet Another Distributed Discrete Event Simulator: User manual CCNG Tech. Rep. E-197, Dept. of Electrical and Computer Engineering and Computer Communications Networks Group, Univ of Waterloo, Waterloo, Ontario.
• 26: PREISS, B. R., LOUCKS, W. M., AND MAClNTYRE, I.D. 1993. Effects of the checkpoint interval on time and space in Time Warp. CCNG Tech. Rep. E-230, Dept. of Electrical and Computer Engineering and Computer Communications Networks Group, Univ. of Waterloo, Waterloo, Ontario.
• 27: PREISS, B. R., MACINTYRE, I. D., AND LOUCKS, W.M. 1992. On the trade-off between time and space in optimistic parallel discrete-event simulation. In Proceedings of the 1992 Workshop on Parallel and Distributed S~mulat~on (Newport Beach, Calif., Jan. 1992). IEEE, New York, 33-42.
• 28: 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]
• 29: K. G. Shin , T.-H. Lin , Y.-H. Lee, Optimal checkpointing of real-time tasks, IEEE Transactions on Computers, v.36 n.11, p.1328-1341, Nov. 1987 [doi>10.1109/TC.1987.5009472]
• 30: Sang Hyuk Son , Ashok K. Agrawala, Distributed Checkpointing for Globally Consistent States of Databases, IEEE Transactions on Software Engineering, v.15 n.10, p.1157-1167, October 1989 [doi>10.1109/TSE.1989.559763]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Parallel; Discrete event

General Terms:
Performance, Theory

Keywords:
Time Warp, checkpointing, discrete-event simulation, parallel simulation