Partitioned event graph: formalizing LP-based modelling of parallel discrete-event simulation

摘要

Logical process (LP) is a modelling paradigm widely used in parallel discrete-event simulation (PDES). However, effective methods for formalizing LP-based modelling of PDES are lacking. This prevents an unambiguous, platform-independent description of LP-based models. We present a formalism named partitioned event graph (PEG) as a solution. PEG extends classical event graph formalism towards a formal specification for LP-based PDES models. We map between PEG and LP-based models, define the structural operational semantics (SOS) in a timed-labelled transition system, and discuss the Wallclock time-based execution. We propose a PEG-based model transformation framework for PDES, which has three model representation phases and distinguishes amongst four kinds of personnel roles. Finally, we present a domain-specific language (DSL) for the PDES of a Lotka-Volterra system and obtain preliminary parallel simulation results using YinHe Simulation Utilities for Parallel Environment (YHSUPE). The case study shows that the PEG-based framework not only effectively transforms a DSL into the LP paradigm, but will also result in efficient parallel simulation on a specific platform. In summary, by setting out specific characteristics for event scheduling and state space partition in the LP paradigm, PEG provides a formal method for model behaviour analysis and cross-platform model transformation.