Hierarchical partitioning algorithm for optimistic distributed simulation of DEVS models

Abstract

The partitioning problem of models is one of the most important issues which may affect the performance of distributed simulation. This paper presents a novel partitioning algorithm for the optimistic distributed simulation of hierarchical, modular Discrete Event System Specification (DEVS) models. The proposed algorithm pursues the following three goals to achieve the overall objective of the minimum simulation time: (1) to balance the computational loads of partitions, (2) to maximize the parallel execution of independent models, and (3) to minimize inter-processor communication. To maximize parallel execution of independent models, the proposed algorithm utilizes the hierarchical structural information of models available from the hierarchical model design methodology of the DEVS formalism. Through benchmark simulation experiments, we show that the proposed algorithm achieves good performance.