Efficient distributed simulation

ABSTRACT

Discrete-event systems are used to model a number of engineering applications ranging from performance analysis of large scale communication networks, computer-aided-design (CAD) of circuits to simulation of manufacturing systems. Except for a small set, these systems are analytically intractable and in addition prohibitive to evaluate numerically. Simulation of such complex systems is exceedingly slow to run (and also to develop). Therefore, the development of simulation speedup methods is of crucial importance in its potential of making feasible the evaluation of a vastly larger set of engineering systems. New analytical models are proposed for the analysis of asynchronous, distributed simulation of discrete-event systems. Vectored distributed simulation and a new rollback algorithm, Wolf, are examined in this framework and comparison with existing systems is attempted. A number of examples illustrate the advantages to such a realization of distributed simulation. Implementation of our algorithms on a distributed computing system confirm analytical results predicting a considerable reduction in error propagation, and an enhancement in forward computation.

REFERENCES

• 1: Berry, O. and Jefferson, D. {1985}, "'Critical path analysis of distributed simulations," Proc. $C3 Dist. Simul. Conf., 57-60.
• 2: Chandy, M. {1988}, "Distributed simulation tutorial," SCS Multiconf. on Distributed Simulation.
• 3: K. M. Chandy , P. F. Reynolds, Scheduling partially ordered tasks with probabilistic execution times, Proceedings of the fifth ACM symposium on Operating systems principles, p.169-177, November 19-21, 1975, Austin, Texas, United States
• 4: Cohen, G., Dubois, D., Quadrat, J. P., and Viot, M. { 1985}, "A linear-theoretic view of discrete-event processes and its use for performance evaluation in manufacturing," }EEE Trans. Aut. Control, AC-30, 210-220.
• 5: Daily, W. { 1987}, "Wire-Efficient VI.~I Multiprocessor Communication Networks," Proc. of the Stanford Conference on VLSI, 1987,, 390-415,
• 6: Guy Fayolle , Peter J. B. King , Isi Mitrani, On the Execution of Programs by Many Processors, Proceedings of the 9th International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.217-228, May 25-27, 1983
• 7: Fujlmoto, R. {1987}, "Performance Measurements of Distributed Simulation Strategies," Technical Report UUCS-87-O26a, Univ. of Utah.
• 8: Gafni, A. {1988}, "Rollback Mechanisms for Optimistic Distributed Simulation Systems," Proc. of Disvributed Simulation Conf., SCS, San Diego. "88.
• 9: Glynn, P. and Iglehart, D. {1987}, "Importance sampling for stochastic simulations," Tech. Report No. 49, Dept. of O. R., Stanford University.
• 10: Amar Gupta, Multimicroprocessors, IEEE Press, Piscataway, NJ, 1987
• 11: Philip Heidelberger, Statistical analysis of parallel simulations, Proceedings of the 18th conference on Winter simulation, p.290-295, December 08-10, 1986, Washington, D.C., United States [doi>10.1145/318242.318448]
• 12: Ho. Y. C. {1985}, "A survey of the pertttrbation analysis of discrete evem dynamical systems," Ann. Oper. Res. 3, 393-402.
• 13: Hu, T.C. {1961}, "Parallel sequencing and assembly line problems," Oper. Res., 9, 841-848.
• 14: 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]
• 15: Kleijnen, J.P.C. { 1974-5}, "Statistical Techniques in Simulation, Part I and 11". Marcel Dekker.
• 16: Klimov, G.P. { 1974}, "Time sharing service systems I," Th. Prob. Appl., 19, 532-551.
• 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: Livny, M. { 1985}, "A study of parallelism in distributed simulation," Proc. SCS Dist. Simul. Conf. 94- 98.
• 19: Madisetti, V., Walrand, J., and Messerschmitt, D. {1989a}, "A High Performance Simulation Methodology for Dynamical Discrete Event Systems." Proc. of SCS Western Multiconference on Simulation and Modeling, Jan 5-7, 1989, San Diego.
• 20: 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]
• 21: Madisetti, V., Messerschmitt, D. {1988b}, "Distributed computation on Concurrent Processors."Proc. of Allerton Conf. September 1988.
• 22: M. Ajmone Marsan , G. Balbo , G. Conte, Performance models of multiprocessor systems, MIT Press, Cambridge, MA, 1987
• 23: Randolph Nelson , Don Towsley , Asser N. Tantawi, Performance Analysis of Parallel Processing Systems, IEEE Transactions on Software Engineering, v.14 n.4, p.532-540, April 1988 [doi>10.1109/32.4676]
• 24: Parekh, S. and Walrand, J. {1986}, "Quick simulation method for excessive backlogs in networks of queues." IEEE Trans. Aut. Control, to appear.
• 25: Brian D. Ripley, Stochastic simulation, John Wiley & Sons, Inc., New York, NY, 1987
• 26: Walrand, J. { 1988}, An Introduction to Queueing Networks, Prentice-Hall.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  D. Software
  D.4 OPERATING SYSTEMS

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Distributed

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