On constructing optimistic simulation algorithms for the discrete event system specification

ABSTRACT

This article describes a Time Warp simulation algorithm for discrete event models that are described in terms of the Discrete Event System Specification (DEVS). The article shows how the total state transition and total output function of a DEVS atomic model can be transformed into an event processing procedure for a logical process. A specific Time Warp algorithm is constructed around this logical process, and it is shown that the algorithm correctly simulates a DEVS coupled model that consists entirely of interacting atomic models. The simulation algorithm is presented abstractly; it is intended to provide a basis for implementing efficient and scalable parallel algorithms that correctly simulate DEVS models.

REFERENCES

• 1: David Bruce, The treatment of state in optimistic systems, Proceedings of the ninth workshop on Parallel and distributed simulation, p.40-49, June 13-16, 1995, Lake Placid, New York, United States
• 2: Chow, A., Zeigler, B., and Kim, D. H. 1994. Abstract simulator for the parallel DEVS formalism. In Proceedings of the 5th Annual Conference on AI, Simulation, and Planning in High Autonomy Systems. IEEE Press, 157--163.
• 3: Alex Chung Hen Chow , Bernard P. Zeigler, Parallel DEVS: a parallel, hierarchical, modular, modeling formalism, Proceedings of the 26th conference on Winter simulation, p.716-722, December 11-14, 1994, Orlando, Florida, United States
• 4: Eric Richard Christensen , Bernard P. Zeigler, Hierarchical optimistic distributed simulation: combining devs and time warp, The University of Arizona, 1990
• 5: Ferscha, A. 1995. Parallel and distributed simulation of discrete event systems. In Handbook of Parallel and Distributed Computing. McGraw-Hill, Inc., New York, NY.
• 6: Fujimoto, R. 1990. Performance of Time Warp under synthetic workloads. In Proceedings of the SCS Multiconference on Distributed Simulation. Society for Computer Simulation, Vol. 22. San Diego, CA, 23--28.
• 7: Richard M. Fujimoto, Parallel and Distribution Simulation Systems, John Wiley & Sons, Inc., New York, NY, 1999
• 8: Ezequiel Glinsky , Gabriel Wainer, New Parallel Simulation Techniques of DEVS and Cell-DEVS in CD++, Proceedings of the 39th annual Symposium on Simulation, p.244-251, April 02-06, 2006 [doi>10.1109/ANSS.2006.32]
• 9: Jonathan I. Leivent , Ronald J. Watro, Mathematical foundations for time warp systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.5, p.771-794, Nov. 1993 [doi>10.1145/161468.161470]
• 10: Qi Liu , Gabriel Wainer, Parallel Environment for DEVS and Cell-DEVS Models, Simulation, v.83 n.6, p.449-471, June 2007 [doi>10.1177/0037549707085084]
• 11: Oded Maler , Zohar Manna , Amir Pnueli, From Timed to Hybrid Systems, Proceedings of the Real-Time: Theory in Practice, REX Workshop, p.447-484, June 03-07, 1991
• 12: Zohar Manna , Amir Pnueli, Verifying Hybrid Systems, Hybrid Systems, p.4-35, January 1993
• 13: Martin, D. E., McBrayer, T. J., Radhakrishnan, R., and Wilsey, P. A. 1999. WARPED: A TimeWarp parallel discrete event simulator (Documentation for version 1.0). http://www.ececs.uc.edu/paw/warped/doc/index.html.
• 14: Friedemann Mattern, Efficient algorithms for distributed snapshots and global virtual time approximation, Journal of Parallel and Distributed Computing, v.18 n.4, p.423-434, Aug. 1993 [doi>10.1006/jpdc.1993.1075]
• 15: Mesarovic, M. and Takahara, Y. 1989. Abstract Systems Theory. Springer-Verlag.
• 16: James Joseph Nutaro , Bernard P. Zeigler, Parallel discrete event simulation with application to continuous systems, The University of Arizona, 2003
• 17: James Nutaro , Hessam Sarjoughian, Design of Distributed Simulation Environments: A Unified System-Theoretic and Logical Processes Approach, Simulation, v.80 n.11, p.577-589, November 2004 [doi>10.1177/0037549704050919]
• 18: R. Rajan , P. A. Wilsey, Dynamically switching between lazy and aggressive cancellation in a Time Warp parallel simulator, Proceedings of the 28th Annual Simulation Symposium, p.22, April 25-28, 1995
• 19: Robert Rönngren , Michael Liljenstam, On event ordering in parallel discrete event simulation, Proceedings of the thirteenth workshop on Parallel and distributed simulation, p.38-45, May 01-04, 1999, Atlanta, Georgia, United States
• 20: Hussam M. Soliman, On the selection of the state saving strategy in time warp parallel simulations, Transactions of the Society for Computer Simulation International, v.16 n.1, p.32-36, March 1999
• 21: Frederick Wieland, The threshold of event simultaneity, Proceedings of the eleventh workshop on Parallel and distributed simulation, p.56-59, June 10-13, 1997, Lockenhaus, Austria
• 22: Qing Xu , Carl Tropper, XTW, A Parallel and Distributed Logic Simulator, Proceedings of the 19th Workshop on Principles of Advanced and Distributed Simulation, p.181-188, June 01-03, 2005 [doi>10.1109/PADS.2005.40]
• 23: Christopher H. Young , Nael B. Abu-Ghazaleh , Philip A. Wilsey, OFC: A Distributed Fossil-Collection Algorithm for Time-Warp, Proceedings of the 12th International Symposium on Distributed Computing, p.408-418, September 24-26, 1998
• 24: Zeigler, B. P., Ball, G., Cho, H., Lee, J., and Sarjoughian, H. 1999. Implementation of the DEVS formalism over the HLA/RTI: problems and solutions. In 1999 Fall Simulation Interoperability Workshop.
• 25: Bernard P. Zeigler , Tag Gon Kim , Herbert Praehofer, Theory of Modeling and Simulation, Academic Press, Inc., Orlando, FL, 2000
• 26: Yi Zeng , Wentong Cai , Stephen J Turner, Batch based cancellation: a rollback optimal cancellation scheme in time warp simulations, Proceedings of the eighteenth workshop on Parallel and distributed simulation, May 16-19, 2004, Kufstein, Austria [doi>10.1145/1013329.1013343]

INDEX TERMS

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

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

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