PARALLEL ALGORITHMS FOR CELLULAR MODELS SIMULATION
Abstract
DEVS is a sound formal modeling and simulation (M&S) framework based on generic dynamic system concepts. Cell-DEVS is a formalism for cell-shaped models based on DEVS. This work presents a new simulation technique for execution of DEVS and Cell-DEVS models in parallel environments. These techniques are modifications to the original Time Warp mechanism offered by WARPED kernel. Time Warp functionalities are revised to include two new algorithms namely, Local Rollback Frequency Model (LRFM) and Global Rollback Frequency Model (GRFM). The resulting simulator is used as new simulation engine for CD++, an M&S toolkit that implements DEVS and Cell-DEVS theories. The results obtained allowed us to achieve considerable speedups due to the reductions that LRFM and GRFM protocols perform on number of rollbacks and anti-messages.
References
-
B. Zeigler , T. Kim and H. Praehofer , Theory of Modeling and Simulation: Integrating Discrete Event and Continuous Complex Dynamic Systems ( Academic Press , 2000 ) . Google Scholar -
G. Wainer and N. Giambiasi , Discrete Event Modeling & Simulation: Enabling Future Technologies ( Springer-Verlag , 2001 ) . Google Scholar - Martin, D. E.; McBrayer, T. J.; Radhakrishnan, R.; Wilsey, P. A. "WARPED - A Time Warp Parallel Discrete Event Simulator (Documentation for version 1.0)" . Google Scholar
- ACM Transactions on Programming Languages and Systems 7(3), 405 (1985), DOI: 10.1145/3916.3988. Google Scholar
- Software - Practice and Experience 32, 1261 (2002), DOI: 10.1002/spe.482. Crossref, ISI, Google Scholar
- Transactions of the Society for Computer Simulation International 17(2), 73 (2000). Google Scholar
-
R. M. Fujimoto , Parallel and Distributed Simulation Systems ( Wiley-Interscience , 2000 ) . Google Scholar -
R. E. Bryant , Simulation of Packet Communication Architecture Computer Systems ( Massachusetts Institute of Technology , Cambridge, MA. USA , 1977 ) . Google Scholar W. Klüpfel , Theoretical and Practical Issues in Cellular Automata (Springer-Verlag, 2001) pp. 63–71. Crossref, Google Scholar-
B. Al-Aubidy , Artificial Intelligence, Simulation and Planning ( Buenos Aires, Argentina , 2007 ) . Google Scholar - Benfenati, F., Valtorta, F., Greengard, P.; "Computer Modelling of Synapsin 1 Binding to Synaptic Vesicles and F-actin". Implications for Regulation of Neurotransmitter Release. 1990 . Google Scholar
- Parallel Computing 22, 789 (1996), DOI: 10.1016/0167-8191(96)00024-5. Crossref, ISI, Google Scholar
- Glinsky, E. "New Techniques for Parallel Simulation of DEVS and Cell-DEVS Models in CD++". M. A. Sc.Thesis. Carleton University. Canada. 2004 . Google Scholar
R. Radhakrishnan , An Object-Oriented Time Warp Simulation Kernel, Proceedings of the International Symposium on Computing in Object-Oriented Parallel Environments (ISCOPE'98),LNCS 1505 (Springer-Verlag, 1998) pp. 13–23. Google Scholar-
E. Szulsztein and G. Wainer , New Simulation Techniques in WARPED Kernel , Proceedings of JAIIO ( 2000 ) . Google Scholar - ACM Transactions on Modeling and Computer Simulation 8(2), 103 (1998), DOI: 10.1145/280265.280267. Crossref, Google Scholar
-
A. Troccoli and G. Wainer , Implementing Parallel Cell-DEVS , Proceedings of 36th IEEE/SCS Annual Simulation Symposium ( 2003 ) . Google Scholar - Q. Liu, G. Wainer. "Optimistic Simulation of DEVS and Cell-DEVS Models with PCD++". Accepted for publication in Simulation, Transactions of the SCS. Accepted: May 2007 . Google Scholar
- Scientific American 223, 120 (1970). Crossref, ISI, Google Scholar
- Rothermel, R. "A mathematical model for predicting fire spread in wild-land fuels". Research Paper INT-115. Ogden, UT: U.S. Department of Agriculture, Forest Service, Intermountain Forest and Range Experiment Station. 1972 . Google Scholar
S. Jafer and G. Wainer , An environment for advanced parallel simulation of cellular models, Proceedings of Unconventional Computing 2007 Computational Problems Workshop (2007) pp. 53–74. Google Scholar


