Extending the DEVS formalism for massively parallel simulation | Discrete Event Dynamic Systems Skip to main content
Springer Nature Link
Log in

Extending the DEVS formalism for massively parallel simulation

  • Published:
Discrete Event Dynamic Systems Aims and scope Submit manuscript

Abstract

The use of multiprocessors for discrete event simulation is an active research area where work has focused on strategies for model execution with little regard for the underlying formalism in which models may be expressed. However, a formalism-based approach offers several advantages including the ability to migrate models from sequential to parallel platforms and the ability to calibrate simulation architectures to model structural properties. In this article, we extend the DEVS (discrete event system specification) formalism, originally developed for sequential simulation, to accommodate the full potential of parallel processing. The extension facilitates exploitation of both internal and external event parallelism manifested in hierarchical, modular DEVS models. After developing a mapping of the extended formalism to parallel architectures, we describe an implementation of the approach on a massively parallel architecture, the Connection Machine. Execution results are discussed for a class of models exhibiting high external and internal event parallelism, the so-called broadcast models. These verify the tenets of the underlying theory and demonstrate that significant reduction in execution time is possible compared to the same model executed in serial simulation.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Baik, D.K. 1985. Performance evaluation of hierarchical simulators: distributed model transformations and mappings. Ph.D. dissertation, Wayne State University, Detroit, MI.

    Google Scholar 

  • Bain, W.L., and Scott, D.S. 1988. An algorithm for time sychronization in distributed discrete event simulation.Distributed Simulation 1988, San Diego, CA, pp. 30–33.

  • Barel, M. 1982. A flexible, high performance multiprocessor for data network simulation.ACM Perform. Eval. Rev., 11(1).

  • Bryant, R.E. 1977. Simulation of packet communication architecture computer systems. MIT-LCS-TR-188, Massachusetts Institute of Technology.

  • Bryant, R.E. 1979. Simulation of a distributed system.IEEE Proc. Distrib. Comput. Systems.

  • Chandy, K.M., and Misra, J. 1981. Asychronous distributed simulation via a sequence of parallel computations.Comm. ACM, 24(11), pp. 198–206.

    Article  MathSciNet  Google Scholar 

  • Christensen, R.C. 1990. Hierarchical optimistic distributed simulation: combining DEVS and time warp. Ph.D. dissertation, University of Arizona, Tucson, ZA.

    Google Scholar 

  • Concepcion, A.I. 1985a. Distributed simulation on multiprocessors: specification, design and architecture. Ph.D. dissertation, Technical Report CSC-85-001. Dept. of Computer Science, Wayne State University, Detroit, MI.

    Google Scholar 

  • Concepcion, A.I. 1985b. The implementation of the hierarchical abstract simulator on the HEP computer.Proc. Winter Simulation Conf., CA.

  • Concepcion, A.I., Baik, D.K., and Zeigler, B.P. 1985. Distributed simulation of hierarchical models.Proc. Workshop on Parallel Processing Using the HEP, Norman, OK, pp. 365–385.

  • Concepcion, A.I., and Zeigler, B.P. 1983. Distributed simulation of distributed system models. Technical Report Dept. of Computer Science, Wayne State University, Detroit, MI.

    Google Scholar 

  • Concepcion, A.I., and Zeigler, B.P. 1985. Distributed modelling and simulation: A review. Technical Report, Dept. of Computer Science, Michigan State University, East Lansing, MI.

    Google Scholar 

  • Concepcion, A.I., and Zeigler, B.P. 1988. DEVS formalism: a framework for hierarchical model development.IEEE Trans. Software Eng., SE-14(2).

    Google Scholar 

  • Dekker, L., Kercoffs, E.J.H., Vansteenkiste, G.C., and Zuidervastat, J.C. 1979. Outline of a future parallel simulator.Proc. IMACS Congress Simulation of Systems, Sorrento, North Holland.

    Google Scholar 

  • Dijkastra, E.W., and Scholten, C.S. 1980. Termination detection for diffusing computations.Inform. Proc. Lett., 11(1), pp. 1–4.

    Article  Google Scholar 

  • Fujimoto, R.M. 1989a. Performance measurements of distributed simulation strategies.Trans. Soc. Comput. Simulation. 6(2), pp. 89–132.

    Google Scholar 

  • Fujimoto, R.M. 1989b. The virtual time machine.Int. Symp. Parallel Algorithms Architectures, pp. 199–208.

  • Fujimoto, R.M. 1990. Parallel discrete event simulation.Comm. ACM, submitted.

  • Fujimoto, R.M., Tsai, J. and Gopalakrishnan, G. 1988. Design and performance of special purpose hardware for time warp.Proc. 15th Annual Symp. Computer Achitecture. pp. 401–408.

  • Groselj, B., and Tropper, C. 1989. A deadlock resolution scheme for distributed simulation.Proc. SCS Multiconf. Distributed Simulation, 21(2), pp. 108–112.

    Google Scholar 

  • Hillis, W.D. 1985.The Connection Machine. Cambridge, MA: MIT Press.

    Google Scholar 

  • Jefferson, D. 1985. Virtual time.ACM Trans. Program. Lang. Systems, 7(3), pp. 404–425.

    Article  MathSciNet  Google Scholar 

  • Jefferson, D., Beckman, B., Wieland, F., Blume, L., DiLorento, M., Hontalas, P., Reiher, P., Sturdevant, K., Tupman, J., Wedel, J., and Younger, H. 1987. The time warp operating system.11th Symp. Operating Systems Principles, Vol. 21(5), pp. 77–93.

    Google Scholar 

  • Jefferson, D., and Sowizral, H. 1985. Fast concurrent simulation using the time warp mechanism.Proc. 1985 Conf. Distributed Simulation, San Diego, CA, pp. 63–69.

  • Kim, T.G. 1988. A knowledge-based environment for hierarchical modelling and simulation. Ph. D. dissertation, University of Arizona, Tucson, AZ.

    Google Scholar 

  • Mirsa, J. 1986. Distributed discrete event simulation.ACM Comput. Surveys, 18(1), pp. 39–65.

    Article  Google Scholar 

  • Melman, M., and Livny, M. 1984. The DISS methodology of distributed system simulations.Simulation, April, pp. 163–176.

  • Nicol, D.M. 1988. Parallel discrete-event simulation of FCFS stochastic queueing networks.ACM/SIKGPLAN PPEEALS 1988, pp. 124–137.

  • Nicol, D.M. 1989. The cost of conservative synchronization in parallel discrete event simulations. Technical Report, Department of Computer Science, College of William and Mary.

  • Peacock, J.K., Wong, J.W., and Manning, E.G. 1979. Distributed simulation using a network of processors.Comput. Networks. 3(1), pp. 44–56.

    Article  Google Scholar 

  • Pimentel, J.R. 1983. Real-time simulation using multiple microcomputer.Simulation, March.

  • Reynolds, P.F. 1983. Active logical processes and distributed simulation: an analysis.Proc. Winter Simulation Conf.

  • Su, W.K., and Seitz, C.L. 1989. Variants of the Chandy-Misra-Bryant distributed discrete-event simulation algorithm.Proc. SCS Multiconf. Distributed Simulation, Vol. 22, No. 2, pp. 38–43.

    Google Scholar 

  • Wang, Y-H. 1987. The implementation of the hierarchical abstract simulator on the iPSC computer. Master thesis, Dept. of Electrical and Computer Engineering, University of Arizona, Tucson, AZ.

    Google Scholar 

  • Wang, Y-H. 1992. Discrete-event simulation on a massively parallel computer. Ph.D. dissertation, Dept. of Electrical and Computer Engineering, University of Arizona, Tucson, AZ.

    Google Scholar 

  • Yamamoto, K. 1982. On distributed simulation.NATO Advanced Institute Workshop, Simulation and Modelling: An Integrative View, Ottawa, Canada.

  • Zeigler, B.P. 1976.Theory of Modelling and Simulation. New York: Wiley (reissued by Kreiger, Malabra, FL, 1985).

    Google Scholar 

  • Zeigler, B.P. 1985.Multifacetted Modelling and Discrete Event Simulation. London, UK and Orlando, FL: Academic Press.

    Google Scholar 

  • Zeigler, B.P. 1986. DEVS-scheme: a Lisp-based environment for hierarchical, modular discrete event models. Technical Report AIS-2, CERL Lab., Dept. of Electrical Computer Engineering, University of Arizona, Tucson, AZ.

    Google Scholar 

  • Zeigler, B.P. 1987. Hierarchical, modular discrete-event modelling in an object-oriented environment.Simulation, 49(5), pp. 219–230.

    Google Scholar 

  • Zeigler, B.P. 1990.Object-Oriented Simulation with Hierarchical Modular Models: Intelligent Agents and Endomorphic Systems. Boston: Academic Press.

    Google Scholar 

  • Zeigler, B.P., and Zhang, G. 1990. Mapping Hierarchial discrete event models to multiprocessor systems: concepts, algorithm, and simulation.J. Parallel Distrib. Comput., 9, pp. 271–281.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. AI-Simulation Group, Department of Electrical and Computer Engineering, University of Arizona, 85721, Tucson, AZ

    Yung-Hsin Wang & Bernard P. Zeigler

Authors
  1. Yung-Hsin Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bernard P. Zeigler
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Wang, YH., Zeigler, B.P. Extending the DEVS formalism for massively parallel simulation. Discrete Event Dyn Syst 3, 193–218 (1993). https://doi.org/10.1007/BF01439849

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01439849

Key Words

Search

Navigation