Efficient flattening algorithm for hierarchical and dynamic structure discrete event models.

*(English)*Zbl 1368.68312##### MSC:

68U20 | Simulation (MSC2010) |

65C20 | Probabilistic models, generic numerical methods in probability and statistics |

##### Keywords:

DEVS; flattening algorithm; dynamic structure model; graph-based acceleration; hierarchical model
PDF
BibTeX
XML
Cite

\textit{J. W. Bae} et al., ACM Trans. Model. Comput. Simul. 26, No. 4, Article No. 25, 25 p. (2016; Zbl 1368.68312)

Full Text:
DOI

**OpenURL**

##### References:

[1] | Adedoyin Adegoke, Hamidou Togo, and Mamadou K. Traoré. 2013. A unifying framework for specifying DEVS parallel and distributed simulation architectures. SIMULATION: Transactions of the Society for Modeling and Simulation International 90, 7 (2013), 1293–1309. |

[2] | Amin Alvanchi, SangHyun Lee, and Simaan AbouRizk. 2011. Modeling framework and architecture of hybrid system dynamics and discrete event simulation for construction. Computer-Aided Civil and Infrastructure Engineering 26, 2 (2011), 77–91. |

[3] | Jang Won Bae, Jeong Hoon Kim, Il-Chul Moon, and Tag-Gon Kim. 2016. Accelerated simulation of hierarchical military operations with tabulation technique. Journal of Simulation 10, 1, 36–49. |

[4] | Jang Won Bae and Tag Gon Kim. 2010. DEVS based plug-in framework for interoperability of simulators. In Proceedings of the 2010 Spring Simulation Multiconference (SpringSim’10). Society for Computer Simulation International, San Diego, CA, 127:1–127:7. http://dx.doi.org/10.1145/1878537.1878670. |

[5] | Jang Won Bae, GeunHo Lee, and Il-Chull Moon. 2012. Formal specification supporting incremental and flexible agent-based modeling. In Proceedings of the 2012 Winter Simulation Conference (WSC’12). 1–12. |

[6] | Jang Won Bae, SeHoon Lee, Jeong Hee Hong, and Il-Chul Moon. 2014. Simulation-based analyses on massive evacuation from metropolis during bombardment. SIMULATION: Transactions of the Society for Modeling and Simulation International 90, 11 (2014), 1244–1267. |

[7] | Yaneer Bar-Yam. 1997. Dynamics of Complex Systems. Addison-Wesley, Reading, MA. 213 pages. · Zbl 1074.37041 |

[8] | Fernando J. Barros. 1996. The dynamic structure discrete event system specification formalism. Transactions of the Society for Computer Simulation International 13, 1 (1996), 35–46. |

[9] | Federico Bergero and Ernesto Kofman. 2014. A vectorial DEVS extension for large scale system modeling and parallel simulation. Simulation 90, 5 (2014), 522–546. |

[10] | Federico Bergero, Ernesto Kofman, and François Cellier. 2013. A novel parallelization technique for DEVS simulation of continuous and hybrid systems. SIMULATION (Aug. 2013), 663–683. Issue 6. DOI:http://dx.doi.org/10.1177/0037549712454931 |

[11] | Jong Hyuk Byun, Chang Beom Choi, and Tag Gon Kim. 2009. Verification of the DEVS model implementation using aspect embedded DEVS. In Proceedings of the 2009 Spring Simulation Multiconference. Society for Computer Simulation International, San Diego, CA, 151. |

[12] | Bin Chen and Hans Vangheluwe. 2010. Symbolic flattening of DEVS models. In Proceedings of the 2010 Summer Computer Simulation Conference. Society for Computer Simulation International, 209–218. |

[13] | Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2001. Transitive closure of a directed graph. In Introduction to Algorithms. MIT Press and McGraw-Hill, 632–634. |

[14] | Richard M. Fujimoto. 1999. Parallel and Distribution Simulation Systems. John Wiley & Sons, New York, NY. |

[15] | Judith L. Gersting. 2007. Mathematical Structures for Computer Science. W. H. Freeman. 807 pages. |

[16] | Ezequiel Glinsky and Gabriel A. Wainer. 2005. DEVStone: A benchmarking technique for studying performance of DEVS modeling and simulation environments. In Proceedings of the 9th IEEE International Symposium on Distributed Simulation and Real-Time Applications (DS-RT’05), October 10-12, 2005, Montreal, Canada. 265–272. DOI:http://dx.doi.org/10.1109/DISTRA.2005.18 |

[17] | Kumar K. Goswami and Ravishankar K. Iyer. 1993. Use of hybrid and hierarchical simulation to reduce computation costs. In Proceedings of the International Workshop on Modeling, Analysis, and Simulation on Computer and Telecommunication Systems (MASCOTS’93). Society for Computer Simulation International, San Diego, CA, 197–202. |

[18] | Gang Guo, Bin Chen, Xiao Gang Qiu, and Zhen Li. 2012. Parallel simulation of large-scale artificial society on CPU/GPU mixed architecture. In Proceedings of the 2012 ACM/IEEE/SCS 26th Workshop on Principles of Advanced and Distributed Simulation. IEEE Computer Society, 174–177. |

[19] | Alexander Helleboogh, Giuseppe Vizzari, Adelinde M. Uhrmacher, and Fabien Michel. 2007. Modeling dynamic environments in multi-agent simulation. Autonomous Agents and Multi-Agent Systems 14, 1 (2007), 87–116. DOI:http://dx.doi.org/10.1007/s10458-006-0014-y · Zbl 05387466 |

[20] | Jan Himmelspach, Roland Ewald, Stefan Leye, and Adelinde M. Uhrmacher. 2007. Parallel and distributed simulation of parallel DEVS models. In Proceedings of the 2007 Spring Simulation Multiconference, Vol. 2. Society for Computer Simulation International, 249–256. |

[21] | Thomas Homer-Dixon, Jonathan Leader Maynard, Matto Mildenberger, Manjana Milkoreit, Steven J. Mock, Stephen Quilley, Tobias Schröder, and Paul Thagard. 2013. A complex systems approach to the study of ideology: Cognitive-affective structures and the dynamics of belief systems. Journal of Social and Political Psychology 1, 1 (2013), 337–363. |

[22] | Xiaolin Hu and Bernard P. Zeigler. 2004. A high performance simulation engine for large-scale cellular DEVS models. In Proceedings of the High Performance Computing Symposium (HPC’04). 3–8. |

[23] | Xiaolin Hu, Bernard P. Zeigler, and Saurabh Mittal. 2005. Variable structure in DEVS component-based modeling and simulation. SIMULATION: Transactions of the Society for Modeling and Simulation International2 81, 2 (2005), 91–102. |

[24] | Moon Ho Hwang. 2005. Tutorial: Verification of real-time system based on schedule-preserved DEVS. In Proceedings of 2005 DEVS Symposium. 2–8. |

[25] | Shafagh Jafer and Gabriel Wainer. 2009. Flattened conservative parallel simulator for DEVS and cell-DEVS. In Proceedings of the International Conference on Computational Science and Engineering, 2009 (CSE’09). Vol. 1. IEEE, 443–448. |

[26] | Jae-Hyun Kim and Tag Gon Kim. 2001. DEVS-based framework for modeling/simulation of mobile agent systems. SIMULATION: Transactions of the Society for Modeling and Simulation International 76, 6 (2001), 345–357. |

[27] | Kihyung Kim, Wonseok Kang, Bong Sagong, and Hyungon Seo. 2000. Efficient distributed simulation of hierarchical devs models: Transforming model structure into a non-hierarchical one. In Proceedings of the Simulation Symposium 2000 (SS’00). IEEE Computer Society, Washington, DC, 227–233. |

[28] | Se Jung Kwon and Tag Gon Kim. 2012. Design and implementation of event-based DEVS execution environment for faster execution of iterative simulation. In Proceedings of the 2012 Symposium on Theory of Modeling and Simulation - DEVS Integrative M&S Symposium (TMS/DEVS’’12). Society for Computer Simulation International, San Diego, CA, 14:1–14:8. |

[29] | Wan Bok Lee and Tag Gon Kim. 2003. Simulation speedup for DEVS models by composition-based compilation. In Proceedings of the Summer Computer Simulation Conference. |

[30] | Seong Yong Lim and Tag Gon Kim. 2001. Hybrid modeling and simulation methodology based on DEVS formalism. In Summer Computer Simulation. |

[31] | Qi Liu and Gabriel Wainer. 2010. Accelerating large-scale DEVS-based simulation on the cell processor. In Proceedings of the 2010 Spring Simulation Multiconference on (SpringSim’10). ACM Press, New York, NY, 124:1–124:8. DOI:http://dx.doi.org/10.1145/1878537.1878667 |

[32] | Martina Maggio, Kristian Stavåker, Filippo Donida, Francesco Casella, and Peter Fritzson. 2009. Parallel simulation of equation-based object-oriented models with quantized state systems on a GPU. In Proceedings of the 7th International Modelica Conference. |

[33] | Alexander Muzy and James J. Nutaro. 2005. Algorithms for efficient implementations of the DEVS & DSDEVS abstract simulators. In Proceedings of the 1st Open International Conference on Modeling & Simulation (OICMS’& Simulation (OICMS’’05). 1–8. |

[34] | Alexandre Muzy and Bernard P. Zeigler. 2014. Specification of dynamic structure discrete event systems using single point encapsulated control functions. International Journal of Modeling, Simulation, and Scientific Computing 5, 3 (2014), 1450012. DOI:http://dx.doi.org/10.1142/S1793962314500123. |

[35] | Ernesto Posse, Jean-Sébastien Bolduc, and Hans Vangheluwe. 2003. Generation of DEVS modelling and simulation environments. In Proceedings of the 2003 Summer Computer Simulation Conference. 139–146. |

[36] | H. Pranevicius, L. Simaitis, M. Pranevicius, and O. Pranevicius. 2011. Piece-linear aggregates for formai specification and simulation of hybrid systems: Pharmacokinetics patient-controlled analgesia. Elektronika ir Elektrotechnika 110, 4 (2011), 81–84. |

[37] | Gauthier Quesnel, Raphaël Duboz, and Éric Ramat. 2009. The virtual laboratory environment–An operational framework for multi-modelling, simulation and analysis of complex dynamical systems. Simulation Modelling Practice and Theory 17, 4 (2009), 641–653. · Zbl 05725997 |

[38] | Hesham Saadawi and Gabriel Wainer. 2009. Verification of real-time DEVS models. In Proceedings of the 2009 Spring Simulation Multiconference (SpringSim’09). Society for Computer Simulation International, San Diego, CA, Article 143, 8 pages. |

[39] | Jeyaveerasingam G. Shanthikumar and Robert G. Sargent. 1983. A unifying view of hybrid simulation/analytic models and modeling. Operations Research 31, 6 (1983), 1030–1052. http://www.jstor.org/stable/170837. · Zbl 0523.68091 |

[40] | Fahad A. Shiginah and Bernard P. Zeigler. 2011. A new cell space DEVS specification: Reviewing the parallel DEVS formalism seeking fast cell space simulations. Simulation Modelling Practice and Theory 19, 5 (2011), 1267–1279. · Zbl 06019973 |

[41] | Eugene Syriani, Hans Vangheluwe, and Amr Al Mallah. 2011. Modelling and simulation-based design of a distributed devs simulator. In Proceedings of the Winter Simulation Conference (WSC’11). 3007–3021. |

[42] | Mamadou K. Traoré. 2009. A graphical notation for DEVS. In Proceedings of the 2009 Spring Simulation Multiconference (SpringSim’09). Society for Computer Simulation International, San Diego, CA, Article 162, 7 pages. |

[43] | Adelinde M. Uhrmacher. 2001. Dynamic structures in modeling and simulation: A reflective approach. ACM Transactions on Modeling and Computer Simulation (TOMACS) 11, 2 (2001), 206–232. |

[44] | Hans L. M. Vangheluwe. 2000. DEVS as a common denominator for multi-formalism hybrid systems modelling. In IEEE International Symposium on Computer-Aided Control System Design, 2000 (CACSD’00).. IEEE, 129–134. |

[45] | Gabriel Wainer. 2000. Improved cellular models with parallel cell-DEVS. Transactions of the SCS 17, 2 (2000), 73–89. |

[46] | Gabriel Wainer and N. Giambiasi. 2001. Application of the cell-DEVS paradigm for cell spaces modelling and simulation. Simulation 76, 1 (2001), 22–39. · Zbl 0980.68133 |

[47] | Gabriel A. Wainer. 2004. Modeling and simulation of complex systems with cell-DEVS. In Proceedings of the 36th Conference on Winter Simulation. 49–60. |

[48] | Gregory Zacharewicz, Maâmar El-Amine Hamri, Claudia Frydman, and Norbert Giambiasi. 2010. A generalized discrete event system (g-DEVS) flattened simulation structure: Application to high-level architecture (HLA) compliant simulation of workflow. Simulation 86, 3 (2010), 181–197. · Zbl 05868929 |

[49] | Bernard P. Zeigler, Tag Gon Kim, and Chilgee Lee. 1990. Variable structure modelling methodology: An adaptive computer architecture example. Transactions of the Society for Computer Simulation 7, 4 (1990), 291–320. |

[50] | Bernard P. Zeigler and Tuncer I. Ören. 1986. Multifaceted, multiparadigm modeling perspectives: Tools for the 90’s. In Proceedings of the 18th Conference on Winter Simulation. 708–712. |

[51] | Bernard P. Zeigler, Herbert Praehofer, and Tag Gon Kim. 2000. Theory of Modeling and Simulation (2nd ed.). Vol. 132. Academic Press. DOI:http://dx.doi.org/10.1159/000074301 · Zbl 1011.93031 |

[52] | Bernard P. Zeigler and Hessam S. Sarjoughian. 2013. Dynamic structure: Agent modeling and publish/subscribe. In Guide to Modeling and Simulation of Systems of Systems. Springer, 125–143. |

[53] | Bernard P. Zeigler and Guoqing Zhang. 1990. Mapping hierarchical discrete event models to multiprocessor systems: Concepts, algorithm, and simulation. Journal of Parallel and Distributed Computing 9, 3 (1990), 271–281. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.