Dynamic structure Discrete Event System Specification (DSDEVS) is an advanced modeling formalism that allows DEVS models and their couplings to be dynamically changed. The modeling power and advantages of DSDEVS have been well studied, however, the performance aspect is generally overlooked. This paper provides a comprehensive performance measurement of DSDEVS for a large-scale cellular space model. We consider the modeling and simulation layers for performance analysis, and carry out performance measurement based on a token ring model and a fire spread model. The results show that DS modeling can improve simulation performance for large-scale cellular space models, due to the fact that it makes the simulation focus only on those active models, and thus is more efficient than when the entire cellular space is loaded. On the other hand, the DS overhead cannot be ignored and can become significant and even dominant when a large number of cells are dynamically added/deleted.
Barros, F.J.1997. Modeling Formalisms for Dynamic Structure Systems. ACM Transactions on Modeling and Computer Simulation7(4), 501-515.
2.
Zeigler, B.P. , T.G. Kim , and H. Praehofer.2000. Theory of Modeling and Simulation, 2nd edition. Academic Press, New York, USA.
3.
Uhrmacher, A.M.2001. Dynamic Structures in Modeling and Simulation - A Reflective Approach. ACM Transactions on Modeling and Simulation11(2), 206-232.
4.
Zeigler, B.P. , T.G. Kim and C. Lee .1991. Variable structure modelling methodology: An adaptive computer architecture example. Transactions of the Society for Computer Simulation7(4), 291- 319.
5.
Barros, F.J. , and M.T. Mendes.1997. Forest fire modelling and simulation in the DELTA environment. Simulation Practice and Theory5(3), 185-197.
6.
Muzy, A., E. Innocenti, D.R.C. Hill, A. Aïello, J.F. Santucci, and P.A. Santoni.2004. Dynamic structure cellular automata in a fire spreading application. Proceedings of the First International Conference on Informatics in Control, Automation and Robotics, IEEE/CSS/ IFAC/ACM/AAAI/ APPIA, Setubal, Portugal, 143- 151.
7.
Hu, X., B.P. Zeigler, and S. Mittal.2005. Variable Structure in DEVS Component-Based Modeling and Simulation. Simulation: Transactions of the Society for Modeling and Simulation International81(2), 91-102.
8.
Wainer, G., and N. Giambiasi.2002. N-Dimensional Cell-DEVS. Discrete Events Systems: Theory and Applications12(1), 135- 157.
9.
Wainer, G.A.Modeling and simulation of complex systems with Cell-DEVS. 2004. Proceedings of the 36th conference on winter simulation 1, 45-56.
10.
Ntaimo, L., B. Khargharia, B.P. Zeigler and M.J. Vasconcelos .2004. Forest fire spread and suppression in DEVS, Simulation: Transactions of the Society for Modeling and Simulation International, 80 (10), 479-500.
11.
DEVS-Java Reference Guide, www.acims.arizona.edu
12.
Mittal, S., E. Mak, and J.J. Nutaro.2006. DEVS-Based Dynamic Model Reconfiguration and Simulation Control in the Enhanced DoDAF Design Process. Journal of Defense Modeling and Simulation (JDMS)3(4), 239-267.
13.
Sun, Y. and X. Hu.2007. Performance measurement of DEVS dynamic structure on forest fire spreading simulation. Proceedings of the 14th AI, Simulation and Planning in High Autonomy Systems (AIS 2007) 12.
14.
Finney, M.A.1998. FARSITE: Fire area simulator - Development and Evaluation. Research Paper RMRS-RP-4. US Deptartment of Agriculture, Forest Service, 52.
15.
Filippi, J-B. , and P. Bisgambiglia.2002. Enabling large scale and high definition simulation of natural systems with vector models and JDEVS. Proceedings of the 2002 Winter Simulation Conference. 1964-1970.
16.
Berger, M.J. and P. Colella.1989. Local Adaptive Mesh Refinement for Shock Hydrodynamics. J of Computational Physics , 82, 64- 84.
17.
Hu, X. and L. Ntaimo.2006. Dynamic Multi-resolution Cellular Space Modeling for Forest Fire Simulation. Proceedings of the DEVS Integrative M&S Symposium (DEVS'06), Spring Simulation Multiconference , April 2-5, 95-102.
18.
Hu, X. and B.P. Zeigler.2004. A High Performance Simulation Engine for Large-Scale Cellular DEVS Models. High Performance Computing Symposium (HPC'04), Advanced Simulation Technologies Conference , April, 3-8.
19.
Hall, S.B., S.M. Venkatesan, and D.B. Wood.2003. A Faster Implementation of DEVS in the Joint MEASURE Simulation Environment. In Proceedings of the Summer Computer Simulation Conference, Montreal , July.
20.
Shiginah, F.A. and B.P. Zeigler.2006. Transforming DEVS to non-modular form for faster cellular space simulation. In Proceedings of 2006 DEVS Symposium, 86-91.
21.
Zeigler, B., D. Kim, and S. Buckley.1999. Distributed supply chain simulation in a DEVS/CORBA execution environment. In Proceedings of the 1999 Winter Simulation Conference, Phoenix, AZ, 1333-1340.
22.
Zeigler, B., and H.S. Sarjoughian .1999. Support for hierarchical modular component-based model construction in DEVS/HLA. Simulation Interoperability Workshop, March 14-19, Orlando, FL.
23.
Zhang, M., B. Zeigler, and P. Hammonds.2006. DEVS/RMI - An auto-adaptive and reconfigurable distributed simulation environment for engineering studies. Spring Simulation Multiconference - DEVS Integrative M&S Symposium , Huntsville, AL.
24.
Mittal, S., J.L. Risco-Martín, and B.P. Zeigler.2007. DEVSML: Automating DEVS Execution Over SOA Towards Transparent Simulators. DEVS Symposium, Spring Simulation Multiconference, Norfolk, Virginia, 287-295.
Sunwoo, P.2003. Hierarchical Model Partitioning for Distributed Simulation of Hierarchical and Modular DEVS Models. Ph.D. Dissertation, University of Arizona, May.
27.
Foster, I. , C. Kesselman, and S. Tuecke.2001. The Anatomy of the Grid: Enabling Scalable Virtual Organizations. International Journal of High-Performance Computing Applications15(3), 200-222.
28.
Foster, I.1998. Computational Grids. Reprinted by permission of Morgan Kaufmann Publishers from The Grid: The Blueprint for a Future Computing Infrastructure .
29.
Song, H.J. , X. Liu , D. Jakobsen, R. Bhagwan, X. Zhang, K. Taura, and A. Chien.2000. The MicroGrid: a Scientific Tool for Modeling Computational Grids. Scientific Programming8(3), 127-141.
30.
31.
Seo, C., S. Park, B. Kim, S. Cheon, and B.P. Zeigler.2004. Implementation of Distributed high-performance DEVS Simulation Framework in the Grid Computing Environment. In Proceedings of the 2004 Advanced Simulation Technologies Conference (ASTC '04) - High Performance Computing Symposium 2004 (HPCS 2004), 9-15, Arlington, VA.
32.
Rothermel, R.1972. A mathematical model for predicting fire spread in wildland fuels. Research Paper INT-115. Ogden, UT: US Department of Agriculture, Forest Service, Intermountain Forest and Range Experiment Station.
33.
Wyman, F.P.1975. Improved event-scanning mechanisms for discrete event simulation. Communications of the ACM, 18, 350- 353.
34.
Vaucher, J.G., and P. Duval.1975. A comparison of simulation event list algorithms. Communications of the ACM, 18, 223-230.
35.
Steinman, J.S.1996. Discrete-event simulation and the event horizon part 2: Event list management. In PADS '96: Proceedings of the Tenth Workshop on Parallel and Distributed Simulation , 170-178.
36.
Rönngren, R., J. Riboe and R. Ayani.1991. Lazy queue: An efficient implementation of the pending-event set. In ANSS '91: Proceedings of the 24th Annual Symposium on Simulation, 194-204.
37.
McCormack, W.M., and R.G. Sargent.1981. Analysis of future event set algorithms for discrete event simulation. Communications of the ACM, 24, 801-812.
38.
Jones, D.W.1986. An empirical comparison of priority-queue and event-set implementations. Communications of the ACM, 29, 300-311.
39.
Chung, K. , J. Sang and V. Rego.1993. A performance comparison of event calendar algorithms: an empirical approach. Software, Practice and Expererience, 23, 1107-1138.
40.
Bahr, H., and R. DeMara.2004. Smart priority queue algorithms for self-optimizing event storage. Simulation Modeling Practice and Theory, 12 (April), 15-40.
41.
Sleator, D.D., and Tarjan, R.E.1985. Self-adjusting binary search trees. Journal of the ACM32, 3 (July), 652-686.
42.
Vaucher, J., and G.P. Duval.1975. A comparison of simulation event list algorithms. Communications of the ACM18(4), 223-230.
43.
Brown, R. and Calendar queue.1988. A fast O(1) priority queue implementation for the simulation event set problem. Communication of the ACM31(10), 1220-1227.
44.
Zeigler, B.P. , and H. Sarjoughian.2002. Introduction to DEVS Modeling and Simulation with JAVA: A Simplified Approach to HLA-Compliant Distributed Simulations, The University of Arizona, Tucson, Arizona, USA, http://www.acims.arizona.edu
45.
Fujimoto, R.M.1999. Parallel and Distribution Simulation Systems. Wiley: New York .
46.
Glinsky, E., and G. Wainer.2005. Abstract simulation algorithms for Parallel CD++. Technical Report SCE-05-11. Carleton University. 2005.
47.
Zacharewicz, G., N. Giambiasi, and C. Frydman.2005. Improving the Lookahead Computation in G-DEVS/HLA Environment. In Proceedings of the 9th IEEE International Symposium on Distributed Simulation and Real-Time Applications, 273-282, Montreal, Canada 2005 .
48.
Glinsky, E., and G.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, 273-282, Montreal , Canada 2005.
49.
Siow MongGoh, R. and I. Li-Jin Thng .2005. Two-Amalgamated Priority Queues. ACM Journal of Experimental Algorithmics, 9(1.6), 1-45.
50.
L'Ecuyer, P., and Y. Champoux.2001. Estimating small cell-loss ratios in ATM switches via importance sampling. ACM Transactions on Model Computer Simulation, 11(1), 76-105.
51.
Willig, A.2005. Performance Evaluation Techniques, Fundamentals and Big Picture. Telecommunication Networks Group, Technical UniversityBerlin.
52.
Le Boudec, J.Y.2007. Performance Evaluation of Computer and Communication Systems. EPFL.
53.
Jain, R.1991. The Art of Computer Systems Performance Analysis. John Wiley & Sons: Chichester.
