Parallel Simulation of Hierarchical Modular DEVS Models: A Modified Time Warp Approach

Abstract

The DEVS (discrete event system specification) formalism specifies a discrete event system in a hierarchical, modular form. This article describes P-DEVSim++, a parallel simulation environment for DEVS models. In P-DEVSim++, the internal events as well as the external events of abstract simulators associated with DEVS models can be proceed in parallel. For such processing, we propose an optimistic algorithm for parallel, distributed simulation based on the time warp approach. The proposed algorithm localizes the rollback of a model within itself, not possible in the standard time warp approach. An advantage of such localization is simulation speedup. The performance of the proposed algorithm is analyzed. For such analysis, we assume that all components of the simulated system are totally distributed in a fully connected distributed environment. The analysis shows that the algorithm is faster than an algorithm which can execute only external events in parallel by the number of imminent components in the best case. For verifying our algorithm, we simulate a benchmark model (the Columbian health care system) in a fully connected distributed memory emulator running on Sun SPARCII. Simulation results show that significant speedup is made possible with our algorithm in a parallel environment. Currently, we are realizing P-DEVS ++ in a real hypercube machine of KAICUBE-II. A five-dimensional hypercube computer developed at KAIST.