A unifying framework for specifying DEVS parallel and distributed simulation architectures

Abstract

DEVS (Discrete Event System Specification) is an approach in the area of modeling and simulation that provides a means of specifying dynamic systems. A variety of DEVS tools have been implemented without a standard developmental guideline across the board, consequently revealing a lack of central frameworks for integrating heterogeneous DEVS simulators. When implementing a DEVS Simulator there are salient concepts that are intuitively defined, such as how events should be processed, what simulation architecture to use, what existing procedures (set of rules/algorithm) can be used, what should be the organizational architecture and so on. The aim of this paper is to propose a theoretical guide in building a DEVS distributed simulation as well as a formalization of underlying concepts to allow symbolic reasoning and automated code synthesis. From a review of existing implementation approaches, we propose a taxonomy of the identified concepts, including some formal definitions as they constitute the essential building blocks of performing Parallel Discrete-Event Simulation by utilizing DEVS. The contribution of this taxonomy and its impact as a unifying framework is that it provides a more systematic understanding of the process of constructing a DEVS simulator. Also, it offers an abstract way for integrating different and heterogeneous DEVS implementation strategies and thus can serve as a contribution to the on-going DEVS standardization efforts.

Keywords

DEVS Parallel Discrete-Event Simulation conceptual framework Simulation Tree Simulation Graph

Get full access to this article

View all access options for this article.

References

Fujimoto

. Parallel and distributed simulation systems. New York: Wiley, 2000.

Zeigler

Kim

Praehofer

. Theory of modeling and simulation. 2nd ed New York: Academic Press, 2000.

Wainer

. Discrete-event modeling and simulation: a practitioner’s approach. New York: CRC Press, 2009.

Balci

. The implementation of four conceptual frameworks for simulation modeling in high-level languages. In: proceedings of the 20th conference on winter simulation (WSC), San Diego, CA, 1988, pp.287–295.

Zeigler

. Theory of modeling and simulation. New York: Wiley-Interscience, 1976.

Chow

Zeigler

. Revised DEVS: a parallel, hierarchical, modular modeling formalism. In: proceedings of the 26th conference on winter simulation (WSC), Lake Buena Vista, FL, 1994, pp.716–722.

Kim

Seong

Kim

. Distributed simulation of hierarchical DEVS models: hierarchical scheduling locally and time warp globally. Trans Soc Comput Simulat Int 1996; 13: 135–154.

Jafer

Wainer

. Flattened conservative parallel simulator for DEVS and Cell-DEVS. In: proceedings of the international conference on computational science and engineering (CSE), Vancouver, Canada, 2009, pp.443–448.

Glinsky

Wainer

. Performance analysis of real-time DEVS models. In: Proceedings of the 34th conference on winter simulation (WSC), San Diego, CA, 2002, pp.588–594.

10.

Kim

Wang

Sagong

. Efficient distributed simulation of hierarchical models: transforming model structure into a non-hierarchical one. In: proceedings of the 33rd annual simulation symposium, 2000, p.227.

11.

Kim

Wang

. CORBA-based, multi-threaded distributed simulation of hierarchical DEVS models: transforming model structure into a non-hierarchical one. In: proceedings of international conference on computational science and its applications, Assisi, Italy, 2004, pp.167–176.

12.

Wainer

. CD++: a toolkit to DEVS. Software, Practice and Experience 2002; 32: 1261–1306.

13.

Himmelspach

Ewald

Leye

. Parallel and distributed simulation of parallel DEVS models. In: proceedings of spring simulation multi-conference, San Diego, CA, 2007, pp.249–256.

14.

Bryant

. Simulation of packet communication architecture computer systems. Technical Report MIT-LCS-TR-188. 1997. Cambridge, MA: Massachusetts Institute of Technology.

15.

Chandy

Misra

. Distributed simulation: a case study in design and verification of distributed programs. IEEE Trans Software Eng 1979; SE-5: 440–452.

16.

Misra

. Distributed discrete-event simulation. ACM Comput Surv (CSUR) 1986; 18: 39–65.

17.

Jefferson

. Virtual time. ACM Trans Program Lang Syst 1985; 7: 405–425.

18.

Himmelspach

Uhrmacher

. Sequential processing of PDEVS models. In: proceedings of the 3rd EMSS, Barcelona, Spain, 2006, pp.239–244.

19.

Jafer

Wainer

. Conservative DEVS – a novel protocol for parallel conservative simulation of DEVS and Cell-DEVS models. In: proceedings of spring simulation multi-conference (DEVS symposium), Orlando, FL, 2010, pp. 168–175.

20.

Liu

Wainer

. Parallel environment for DEVS and Cell-DEVS models. Simulation 2007; 83: 449–471.

21.

Glinsky

Wainer

. New parallel simulation techniques of DEVS and Cell-DEVS in CD++. In: proceedings of the 39th annual symposium on simulation, Huntsville, AL, 2006, pp.244–251.

22.

Chow

Zeigler

. The RTDEVS/CORBA environment for simulation-based design of distributed real-time systems. Simulation 2003; 79: 197–210.

23.

Mittal

Risco

Zeigler

. DEVS-based simulation web services for net-centric T&E. In: proceedings of the 2007 summer computer simulation conference, San Diego, CA, 2007, pp.357–366.

24.

Seo

Zeigler

. Automating the DEVS modeling and simulation interface to web services. In: proceedings of the spring simulation multi-conference, San Diego, CA, 2009.

25.

Park

Hunt

Zeigler

. Cost-based partitioning for distributed and parallel simulation od decomposable multiscale constructive models. Simulation 2006; 82: 809–826.

26.

Bolduc

J. -S. H

. Vangheluwe. A Modeling and Simulation Package for Classic Hierarchical DEVS, Technical Report. McGill University, School of Computer Science, 2002.

27.

Triccoli

Wainer

. Implementing parallel Cell-DEVS. In: proceedings of the 36th annual symposium on simulation, Washington, DC, 2003, pp.273–277.

28.

Sarjoughian

Zeigler

. DEVS and HLA: complementary paradigms for M&S. Trans Soc Comput Simulat 2000; 17: 187–197.

29.

Kim

. DEVS Framework and toolkits for simulators interoperation using HLA/RTI. In: proceedings of asia simulation conference, Beijing, China, 2005, pp.16–21.

30.

Christensen

Zeigler

. Hierarchical optimistic distributed simulation: combining DEVS and time warp. Doctoral Dissertation, University of Arizona, University of Arizona, 1990.

31.

Jafer

Wainer

. Conservative vs optimistic parallel simulation of DEVS and Cell-DEVS: a comparative study. In: proceedings of summer simulation conference, Ottawa, ON, 2010, pp.342–349.

32.

Wainer

. DEVS standardization: ideas, trends and future. In: Wainer

Mosterman

(eds) Discrete-event modeling and simulation: theory and applications. New York, New York: Taylor and Francis Group, 2010, pp.389–392.

33.

Wainer

. DEVS Standardization Study Group. Interim Final Report. 2005. Seattle, WA: The SISO Standards Activity Committee (SAC).

34.

Traoré

. SimStudio: a next generation modeling | simulation framework. In: proceedings of the 1st international conference on simulation tools and techniques for communications, networks and systems & workshops, Marseille, France, 2008.