Optimal memory management for time warp parallel simulation

ABSTRACT

Recently there has been a great deal of interest in performance evalution of parallel simulation. Most work is devoted to the time complexity and assumes that the amount of memory available for parallel simulation is unlimited. This paper studies the space complexity of parallel simulation. Our goal is to design an efficient memory management protocol which guarantees that the memory consumption of parallel simulation is of the same order as sequential simulation. (Such an algorithm is referred to as a optimal.) First, we derive the relationships among the space complexities of sequential simulation, Chandy-Misra simulation [2], and Time Warp simulation [7]. We show that Chandy-Misra may consume more storage than sequential simulation, or vice versa. Then we show that Time Warp never consumes less memory than sequential simulation. Then we describe cancelback, an optimal Time Warp memory management protocol proposed by Jefferson. Although cancelback is considered to be complete solution for the storage management problem in Time Warp, some efficiency issues in implementing this algorithm must be considered. We propose an optimal algorithm called artifical rollback. We show that this algorithm is easy to implement and analyze. An implementation of artificial rollback is given, which is integrated with processor scheduling to adjust the memory consumption rate based on the amount of free storage available in the system.

REFERENCES

• 1: Ian F. Akyildiz , Liang Chen , Samir R. Das , Richard M. Fujimoto , Richard F. Serfozo, Performance analysis of “Time Warp” with limited memory, Proceedings of the 1992 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.213-224, June 01-05, 1992, Newport, Rhode Island, United States
• 2: CHANDY, K M., AND MISRA, J Distributed simulation: A case study in design and verification of distributed programs. IEEE Trans. Softw. Eng. SE-5, 5 (Sept. 1979), 440-452.
• 3: FUJIMOTO, R. M. Performance measurements of distributed simulation strategies. Trans. ,~oc Comput. S~mul. 6, 2 (Apr. 1989), 89-132.
• 4: FUJiMOTO, R. M. Time Warp on a shared memory multiprocessor. In Proceedings of the 1989 International Conference on Parallel Processing. ACM, New York, 1989, pp. 242 249.
• 5: 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]
• 6: GAFNI, A. Rollback mechanisms for optimistic distributed simulation. In Proeeedtngs of the 1988 SCS Multlconference on D~stributed Strnulation. SCS, 1988, pp. 61 67.
• 7: 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]
• 8: 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]
• 9: JEFFERSON, D. Private communication. 1991.
• 10: Fred J. Kaudel, A literature survey on distributed discrete event simulation, ACM SIGSIM Simulation Digest, v.18 n.2, p.11-21, June 1987 [doi>10.1145/29497.29499]
• 11: LIN, Y.-B., A~D LAZOWSKA, E.D. Design issues on optimistic distributed simulation. Submitted for publication.
• 12: L~N, Y.-B., AND LAZOWSKA, E. D. Determining the global virtual time in a distributed simulation. In Proceedings of the International Con/~rence on Parallel Processtng. 1990, pp. 201-209.
• 13: Y. B. Lin , E. D. Lazowska, Exploiting Lookahead in Parallel Simulation, IEEE Transactions on Parallel and Distributed Systems, v.1 n.4, p.457-469, October 1990 [doi>10.1109/71.80174]
• 14: LIN, Y.-B., AND LAZOWSKA, E.D. Optimality considerations for Time Warp parallel simulation. In Proceedings of the 1990 SCS Multiconference on Distributed Simulation. SCS, 1990, pp. 29-34.
• 15: Yi-Bing Lin , Edward D. Lazowska, A study of time warp rollback mechanisms, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.1 n.1, p.51-72, Jan. 1991 [doi>10.1145/102810.102813]
• 16: Yi-Bing Lin , Edward D. Lazowska, A time-division algorithm for parallel simulation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.1 n.1, p.73-83, Jan. 1991 [doi>10.1145/102810.214307]
• 17: LIN, Y.-B., LAZOWSKA, E. D., AND BA~R, J.-L. Conservative parallel simulation for systems with no lookahead. Tech. Rep. 89-07-07, Dept. of Computer Science and Engineering, Univ. of Washington, 1989.
• 18: L~N, Y.-B., LAZOWSKA, E. D., ANO BAILEY, M. L. Comparing synchronization protocols for parallel logic-level simulation. In Proceedings of the International Conference on Parallel Processing. 1990, pp. 223 227.
• 19: LIPTON, R. J., AND MIZELL, D.W. Time Warp vs. Chandy-Misra: A worst-case comparison. In Proceedings of the 1990 SCS Multiconference on Distributed Simulatwn. SCS, 1990, pp. 137 143.
• 20: Louc~s, W. M., AND PRE~SS, B. R. The role of knowledge in distributed simulation. In Proceedings of the 1990 SCS Multlconference on Distributed Simulatton. SCS, 1990, pp. 9-16.
• 21: MADISETTI, V., WALRAND, J., AND MESSERSCHMITT, D. Synchronization in message-passing computers--Models, algorithms, and analysis. In Proceedings of the 1990 SCS Multiconference on Distributed Szmulation. SCS, 1990, pp. 35-48.
• 22: Jayadev Misra, Distributed discrete-event simulation, ACM Computing Surveys (CSUR), v.18 n.1, p.39-65, March 1986 [doi>10.1145/6462.6485]
• 23: David M. Nicol, Parallel discrete-event simulation of FCFS stochastic queueing networks, Proceedings of the ACM/SIGPLAN conference on Parallel programming: experience with applications, languages and systems, p.124-137, July 19-21, 1988, New Haven, Connecticut, United States
• 24: PREISS, B.R. Performance of discrete event simulation on a multiprocessor using optimistic and conservative synchronization. In Proceedings of the International Conference on Parallel Processing. 1990, pp. 218-222.
• 25: PRE~SS, B. R., MACINTYRE, I. D., AND LO~CKS, W.M. On the trade-off between time and space in optimistic parallel discrete-event simulation. In Proceedings of the 6th Workshop on Parallel and Distributed Simulation. 1992, pp. 33-42.
• 26: Paul F. Reynolds, Jr., Heterogenous distributed simulation, Proceedings of the 20th conference on Winter simulation, p.206-209, December 12-14, 1988, San Diego, California, United States [doi>10.1145/318123.318190]
• 27: RIGHTER, R., AND WALED, J. C. Distributed simulation of discrete event systems. Proc. IEEE 77, i (Jan. 1989), 99 133.
• 28: SAMAOL B. Distributed simulation, algorithms and performance analysis. Ph.D. thesis, Computer Science Dept., Univ. of California, Los Angeles, 1985.
• 29: D. B. Wagner , E. D. Lazowska, Parallel simulation of queueing networks: limitations and potentials, Proceedings of the 1989 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.146-155, May 23-26, 1989, Oakland, California, United States

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Synchronization
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies
      D.4.4 Communications Management
          Subjects: Message sending
      D.4.7 Organization and Design
          Subjects: Distributed systems

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

General Terms:
Performance

Keywords:
Time Warp, artificial rollback, discrete event simulation, parallel simulation