Academic
Publications
Parallel Algorithms for Cellular Models Simulation

Parallel Algorithms for Cellular Models Simulation,10.1142/S0129626407003010,Parallel Processing Letters,Shafagh Jafer,Gabriel A. Wainer

Parallel Algorithms for Cellular Models Simulation  
BibTex | RIS | RefWorks Download
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 consider able speedups due to the reductions that LRFM and GRFM protocols perform on number of rollbacks and anti-messages. Modeling and simulation (M&S) methodologies have become crucial for implementing, designing, and analyzing a broad verity of systems. Among the exis ting simulation techniques, the DEVS (Discrete Event System Specification) formalism (1) provides a discrete-event M&S approach which allows construction of hierarchical models in a modular manner. DEVS is a sound formal framework based on generic dynamic systems concepts that allows model reuse, and reduc tion in development and testing time due to its hierarchical approach in constructing models. Cell-DEVS (2) is an extension to DEVS which integrates DEVS and cellular automata by presenting each cell as an atomic DEVS model. Cell-DEVS introduced a novel mechanism for computation based on asynchronous cellular models with explicit timing constructions. The technique has be en used to develop a wide variety of models in diff erent fields, ranging from environmental sciences, traffi c, biology and physics. When large complex models are defined, the computing power of a parallel simulato r can improve execution times. Here, we present new techniques for executing DEVS and Cell-DEVS models in parallel and distributed environments based on the WARPED kernel (3), an implementation of the Time Warp protocol (4). Our optimistic simulator, called as PCD++, is built as a new simulation engin e for CD++ (5), an M&S toolkit that implements the DEVS and Cell-DEVS formalisms. Algorithms in CD++ and the WARPED kernel are redesigned based on Near Perfect State Information technique to carry o ut optimistic simulations using a non-hierarchical approach that reduces the communication overhead. Two new algorithms namely, Local Rollback Frequency Model (LRFM) and Global Rollback Frequency Model (GRFM) have been implemented and used by our PCD++ simulator. These two algorithms have been tested using different Cell-DEVS models. Here we present in details an evacuation model of a ship and a model of the Synapsin-Vesicle reaction in neurons. Also, a brief description of two other mod els namely Fire Propagation model, and Game of Life model are provided. We have designed many Cell-DEVS models which vary in size, complexity, and functionality. As the main contribution of this work, we have implemented two new optimism control mechanisms based on NPSI protocols. These two protocols, namely LRFM and GRFM were integrated into the existing optimistic PCD++ simulator and therefore two distinct optimism controlling simulators were modeled. This led to
Journal: Parallel Processing Letters - PPL , vol. 17, no. 3, pp. 263-285, 2007
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.