Time warp simulation using time scale decomposition

ABSTRACT

In this paper we consider time scale decomposition as well as spatial decomposition to induce massive parallelism and reduce overhead in distributed discrete-event simulations. We confine our study to the Time Warp strategy and to systems where the durations of activities differ by several orders of magnitude (i.e., systems with fast and slow activities). We show that, for such systems, a large overhead due to rollbacks is encountered when spatial decomposition is used. Moreover, performance degrades as the difference increases between the rates of fast and slow events. Several initial experiments using queueing-network models were designed to evaluate the effectiveness of time scale decomposition in increasing the parallelism and reducing the overhead. These experiments were conducted on a distributed simulation testbed that was implemented on an 18-processor Multimax 320. The application of the above simulation techniques to stochastic Petri net models is illustrated using an example of performability analysis of a fault-tolerant distributed system.

REFERENCES

• 1: H. H. Ammar , S. M. Rezaul Islam, Time Scale Decomposition of a Class of Generalized Stochastic Petri Net Models, IEEE Transactions on Software Engineering, v.15 n.6, p.809-820, June 1989 [doi>10.1109/32.24734]
• 2: AMMAR, H. H., AND DENG, S. Parallel simulation of stochastic Petri nets using spatial decomposition. In Proceedzngs of the 1991 IEEE Internatzonal Symposzum on Ctrcuits and Systems (Singapore, June 1991). IEEE, New York, pp. 26-29.
• 3: Orna Berry, Performance evaluation of the time warp distributed simulation mechanism, University of Southern California, Los Angeles, CA, 1986
• 4: BLUM, A., DONATIELLO, L., HEIDELBERGER, P., LAVENBERG, S. S., AND MACNAIR, E.A. Experiments with decomposition of extended queueing network models In Proceedings of the International Conference on Modeling Techntques and Tools for Performance Analys~s. Institut National de Recherche en Informatique et en Automat~que, Paris, 1984.
• 5: CHAND~, K. M., A~D SHERMAN, R. Space-tnne and simulation. In Proceedings of the SCS Multiconference on Distributed Simulation (Mar. 1989), vol. 21.
• 6: COURTOIS, P.J. DecomposabilLty: Queuezng, and Computer System Appllcattons. Academic Press, New York, 1977.
• 7: COURTOIS, P. J., AND SEMAL, P. Computable bounds for conditional steady state probabilities in large Markov chains and queueing models. IEEE J. Sel. Areas Commun. SAC-4, 6 (Sept. 1986).
• 8: FUJIMOTO, R. M. Lookahead in parallel discrete event simulation. In Proceedings of the 1988 International Conference on Parallel Processing (1988).
• 9: Albert G. Greenberg , Boris D. Lubachevsky , Isi Mitrani, Unboundedly parallel simulations via recurrence relations, Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.1-12, April 1990, Univ. of Colorado, Boulder, Colorado, United States
• 10: 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]
• 11: 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]
• 12: Kishar Shridharbhai Trivedi, Probability and Statistics with Reliability, Queuing and Computer Science Applications, Prentice Hall PTR, Upper Saddle River, NJ, 1982
• 13: Stephen S. Lavenberg , Richard R. Muntz , Behrokh Samadi, Performance Analysis of a Rollback Method for Distributed Simulation, Proceedings of the 9th International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.117-132, May 25-27, 1983
• 14: LIN, Y., AND LAZOWSKA, E. Optimality considerations for Time Warp parallel simulation. Tech. Rep., Dept. of Computer Science, Univ. of Washington, 1989.
• 15: 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]
• 16: MADDESETTI, V., WALRAND, J., AND MESSERSCHMIDT, D. On estimating the progress of optimistic distributed computation: Multiple processor case. Tech. Rep., Dept. of EECS, Univ. of California, Berkeley, 1989.
• 17: Debasis Mitra , Isi Mitrani, Analysis and Optimum Performance of Two Message-Passing Parallel Processors Synchronized by Rollback, Proceedings of the Tenth International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.35-50, December 19-21, 1984
• 18: D. M. Nicol, Analysis of synchronization in massively parallel discrete-event simulations, ACM SIGPLAN Notices, v.25 n.3, p.89-98, Mar. 1990
• 19: RANDELL. System structure for software fault tolerance. IEEE Trans. Softw. Eng. SE-J, 2 (June 1975).
• 20: 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]
• 21: REIHER, P., BELLENOT, S., AND JEFFERSON, D. Temporal decomposition of simulations under the Time Warp operating systems. In Proceedings of the SCS Multiconference on Parallel and Distributed Simulation (Jan. 1991), vol. 23.
• 22: loss, H.S. Stochastic Processes. Wiley, New York, 1983.
• 23: SAUER, C. H., AND CiclANDY, K.M. Computer Systems Performance Modelmg. Prentice-Hall, Englewood Cliffs, N.J., 1981.
• 24: SHIN, K. G., AND LEE, Y.-H. Evaluation of error recovery blocks used for cooperating processes. IEEE Traus. Softw. Eng. SE-IO, 6 (Nov. 1984).
• 25: SIMON, H. A., AND ANDO, h. Aggregation of variables in dynamic systems. Econometrica 29 (1961).
• 26: 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: Distributed

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

  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies
      I.6.8 Types of Simulation
          Subjects: Discrete event

General Terms:
Algorithms, Design, Experimentation, Performance, Theory

Keywords:
fault-tolerant systems, parallel simulation, performability analysis, queueing networks, stochastic petri nets, system modeling, time-scale decompositions