Access the full text.
Sign up today, get DeepDyve free for 14 days.
Loading next page...
/lp/taylor-francis/partitioned-event-graph-formalizing-lp-based-modelling-of-parallel-90eGn9gWBt
References
References for this paper are not available at this time. We will be adding them shortly, thank you for your patience.
- Publisher
- Taylor & Francis
- Copyright
- © 2014 Taylor & Francis
- ISSN
- 1744-5051
- eISSN
- 1387-3954
- DOI
- 10.1080/13873954.2014.911750
- Publisher site
- See Article on Publisher Site
Abstract
Mathematical and Computer Modelling of Dynamical Systems, 2015 Vol. 21, No. 2, 153–179, http://dx.doi.org/10.1080/13873954.2014.911750 Partitioned event graph: formalizing LP-based modelling of parallel discrete-event simulation a a b a b Bing Wang *, Bo Deng , Fei Xing , Dongxia Wang and Yiping Yao a b Beijing Institute of Systems Engineering, Beijing, 100101, P.R. China; National University of Defense Technology, Changsha, 410073, P.R. China (Received 17 June 2012; accepted 29 March 2014) 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 transfor- mation framework for PDES, which has three model representation phases and distin- guishes 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. Keywords: parallel discrete-event simulation; event graph; logical process; structural operational semantics; model transformation AMS Subject Classification: 00A72; 00A71; 93C65; 65Y05; 68Q55 1. Introduction Parallel discrete-event simulation (PDES) has been recognized as a challenging field which bridges modelling and simulation, and high-performance computing [1]. PDES’s superior performance compared to sequential discrete event system (DES) derives from its explicit decomposition of a model into sub-models which spreads the computing load over distributed processors and speculatively pushes the simulation time forward. Logical process (LP) is the most commonly used modelling paradigm in PDES. LP was intro- duced to PDES to model the physical processes a system consists of. Because of the intuitive depiction of time and space, as well as the commonality in implementation on parallel machines, LP paradigm has been the dominant PDES modelling method for a long time. Recent research into the parallel simulation of LP-based models has usually attempted to overcome the performance bottleneck [2] of a sequential DES [3]. There has been *Corresponding author. Email: wangbing.nudt@gmail.com © 2014 Taylor & Francis 154 B. Wang et al. useful work on algorithm optimization, some novel hardware platform customization, and several effective modelling methodologies, but few effective methods for formalizing LP- based modelling of PDES. There are many formalisms for DESs, such as DEVS [4], Timed Automata [5], Petri Net, Process Algebra GSMP [6], StateChart [7], and Activity Cycle Diagrams [8]. These formalisms differ in their usability due to their underlying semantic models; as to the domains they are suitable to describe; as to what property, aspect, or granularity they can be used to analyse; and, in their expressive power [9]. These formalisms cannot be directly used on LP-based models in the PDES as they either underspecify or overspecify the LP paradigm. There are two key characteristics for LP paradigm sharing by most PDES platforms: event scheduling and state space partition. A novel formalism precisely specifying these characteristics is required. A recent paper presented a formalism named ‘extended event graph’ (EEG) [10] for PDESs. However, it incompletely reviewed the literature, and its extension of event graph (EG) formalism [11–13] requires a modification to correctly specify the LP paradigm. The DVE-like [14,15] modelling language in EEG does not fully describe the key character- istics of the LP paradigm. The ‘parallel event process’ [15][16, p. 27] specified in its denotational semantics is a characteristic rarely shared by PDES time management protocols. Additionally, the formal definitions of EEG and LP in ref. [10] fail to distin- guish the type and instance of specific elements in the formalism. This lack of distinction weakens its claim made for the rigorousness of the model transformation. In this paper, we develop a formalism for PDES based on the EG formalism, called partitioned event graph (PEG), to provide an unambiguous and platform-independent description of LP-based models. PEG not only offers a formal representation for the LP-based model, but also provides a structural operational semantics (SOS) on timed- labelled transition system (TLTS) [17, p. 105]. Therefore, PEG can be used for cross- platform model transformation, automatic compilation to programming languages, and formal analysis of PDES-model behaviour. PEG accomplishes this by formally specifying event scheduling and the state space partition of the LP paradigm. These two character- istics correspond to synchronization and partitioning efforts which are keys to the correctness and performance of PDES. The next section reviews the literature on formalizing LP-based modelling of PDES. Section 3 presents the PEG in detail. We construct a map between the PEG and the LP- based model, and define the SOS in a TLTS. Also, the Wallclock time execution and the related equivalence relationship are defined. Section 4 presents a PEG-based domain- specific modelling framework for PDES. Section 5 presents a domain-specific language (DSL) for the spatial stochastic simulation of chemical reactions based on PEG to demonstrate PEG-based framework’s capability. Section 6 closes the paper by discussing the major findings and providing some direction for future work. 2. Related works LP is a widely used term in PDES. Fujimoto et al. describe LP as a synonym for any sequential simulation or simulator [2, p. 40], while Curry et al. and Peschlow et al. introduce it to the sequential simulation branching [18,19]. The time-parallel simulation decomposes the model temporarily, and every computation unit is deemed an LP [2, p. 177]. In this paper, LPs are regarded as model entities and core execution units during the simulation [3,20]. They interact with each other by exchanging events. Mathematical and Computer Modelling of Dynamical Systems 155 The development of the PEG is based on the EG formalism. The EG, also known as the simulation graph [21] and the event relationship graph [22], explicitly expresses all the relationships between events, and is the most direct formalism for the event scheduling world view. EG has the same expressiveness as the Turing machine [11]. Infinitesimal perturbation analysis and mathematical programming are used to analyse the properties of EG models [23]. OMIGA and SIMKIT [13] are typical toolkits for EG- based modelling, but only with sequential execution. Viskit [24] provides a subscribe/ publish mechanism based on bridges, which consist of communication ports between sub-graph models. J. de Lara et al. present the distributed event graph (DEG) [25] which extends classical event graphs for component-based models in the sequential DES, and the operational semantics is given by means of graph transformation. The most common PDES modelling method is to directly use the application program interfaces (APIs) provided by PDES platforms, such as TWOS [26], GTW [27], SPEEDES [28], POSE [29], ROSS [30], and μsik [31]. API-based PDES modelling methods have low usability due to their tight platform coupling. DSLs hide platform details, making modelling more friendly to domain experts. For example, the Maisie [32] language is based on GTW and frees users from having to know API details. However, most domain-specific PDES modelling methods remain tightly coupled to specific platforms and the proprietary execution semantics hampers cross- platform reusability and formal analysis. Component-based modelling effectively reduces model construction difficulties and increases reusability. Sargent used visualization and a component-based method in the control flow graph [33] to construct LP-based models. Liu et al. [34] built a component- based modelling environment based on a variant of DEVS on top of the YinHe Simulation Utility of Parallel Environment (YHSUPE) [35]. Other EG-based modelling works include Jane [36] and Pave [37]. These efforts usually require direct transforming from component-based formalisms into underlying platforms because LP-based models are not natively component based. Mapping high-level formalisms into LP paradigms is another method of introducing formal method to PDES. Researchers from the University of Carleton have mapped cellular automata to LP paradigms [38] and implemented a Cell-DEVS based PDES platform [39]. Hybinnette mapped a multi-agent system into the LP-based model in Project SASSY [40]. Chen developed a middleware named HLA- Grid-RePast to execute agent-based model on the Grid [41]. Oguara et al., in Project MAS-PDES [42], organized LP-based models into reconfigurable tree structures based on influence conical and represented the transformation of information sharing among agents in the LP paradigm. However, each of these mappings is still directly linked to specific platforms. The lack of platform-independent representation makes it hard to do cross- platform migration and to verify transformation correctness. Nutaro represents the simulation of LPs as a stack-based computing process in order to facilitate formal analysis [43], but its idiomatic semantics makes it hard to incorporate into commonly used formal methods. Tapus et al. discuss the formal model and the operational semantics of speculative execution in distributed environments [44], but without taking into consideration the equivalence to a sequential execution, which is of key importance in PDES. In summary, formalisms for general discrete-event modelling do not yet fully depict certain key characteristics of the LP paradigm, including state space partition, event- driven semantics, and the partial order among events. Current LP-based modelling methods for PDES rely either on high-level programming language or artificial structure 156 B. Wang et al. to define the execution semantics. The lack of a formal semantics hampers further study on the transformation and the verification of LP-based models. 3. Partitioned event graph The PEG is presented in this section. First, the assumptions in developing the formalism are listed; then the PEG is defined formally; then the map between the LP-based Model and the PEG-based model is constructed; then, the SOS on TLTS is presented; and finally, the Wallclock time-based execution is discussed. 3.1. Assumptions Regulation of the system under investigation plays a central role in formal method. For the PEG formalism, the following assumptions are made: (1) There are no simultaneous events. In simulation, we are interested in the state trace generated by the system behaviour and not high-level interleaving concur- rency, and decoupling can be used to eliminate simultaneous events [45]. (2) The condition expression on edge should contain finite enumerable relations joined by Boolean operators, and thus the length of the edge condition is both enumerable and finite [21]. (3) The number of LP classes, of LPs (partitions), and of event types are each finite, and the number of event instances is enumerable, but not necessarily finite. (4) The state space of the simulation model is enumerable, but not necessarily finite, the same as in the discrete-event dynamic system [6]. (5) The model structure is static, no increase or decrease, in the number of LP instances during simulation. 3.2. Logical process-based model A general discrete-event model in event scheduling world view can be represented as follows: Definition 3.1: Discrete-event model Modelhi EventTSet; StateVarSet; INIT ; Time ; where ● EventT Set holds all of the event types, ● StateVarSet stands for the set of state variables, ● INIT stands for the initial configuration to EventTSet and StateVarSet, Time stands for the time base. For StateVarSet, the set of all evaluation functions to the state variable in it, is defined as EV ALðÞ fg SV ; :::; SV domain . The evaluation function η 2 EV ALðÞ maps 1 M sv 0<j j every SV 2 StateVarSet to a certain value v 2 domain ; where 0 <j M : j SV j Mathematical and Computer Modelling of Dynamical Systems 157 The LP-based model of a DES consists solely of LPs as atomic model entities, the set of which is marked as Set . LP Let L be the set of indices. The L-indexed set over Set is a tripleðÞ L; Set ; μ , where LP LP μ : L ! Set be the index function of Set . Since "LP 2 Set 9i 2 L; μðÞ i ¼ LP,we LP LP LP mark the LP as LP . The LP-based model of a DES should contain extra partition information on EventTSet and StateVarSet, respectively, and is formally represented in Definition 3.2. Definition 3.2: LP-based model Modelhi Set ; INIT ; Time ; where LP LP ● Time represents the time base, normally < is used. ● Set fg LP ji 2 L ; where LP i Δ η fLP hEventTSubset ; StateVarSet ; δ ; δ i; i 2 Lg where i i i i i (1) EventTSubset is a subset of EventTSet, and satisfies: "i 2 L: EventTSubset EventTSet ¨ EventTSubset ¼ EventTSet i2L i "ij 2 L:EventTSubset ˙ EventTSubset ¼ f i j (2) StateVarSet is a subset of StateVarSet, and satisfies: "i 2 L: StateVarSet StateVarSet ¨ StateVarSet ¼ StateVarSet i2L i "ij 2 L:StateVarSet ˙StateVarSet ¼ f i j (3) δ is the state transition function, and is represented as δ : EventTSubset S ! S ; i 2 L. i i i (4) δ is the event scheduling function, and is represented as δ : EventTSubset S ! }ðÞ EventTSet Time ; i 2 L, where S is the state i i i space of LP : Δ Δ S EV ALðStateVarSet Þ 2 StateVarSet domain and the state space i i i SV SV Δ Δ S i2L of Model is defined as S EV ALðStateVarSetÞ . LP ● INIT stands for the initial configuration to EventTSet and StateVarSet , where i 2 L. i i The schedule relationship for event types of LP ,markedas ScheduleRelationship , i i is a set of tuples consisting of an event type in LP and those event types scheduled by it. ScheduleRelationship Δ eT ; eT i from to eT 2 EventTSubset ^9 ð s 2 S ; 9t 2 Time; s:t:ðÞ eT ; t2 δ eT ; s Þg from i i to from i 158 B. Wang et al. The schedule relationship for Model is LP ScheduleRelationship ¨ ScheduleRelationship i2L i 3.3. Formal description The EG formalism describes the elements of an EG model, which is shown in Definition 3.3 [11]. Definition 3.3: Event graph M <V ; E; S; F; C; T ; A; B>; where V, the set of vertices corresponding to the events of M, E, the set of directed edges e ¼ <v ; v > that describe the scheduling/cancelling od o d relationships between pairs of events in M, S, the state space of M, it is depicted by a vector of state variable in DES, F ¼fg f : S ! S;"v 2 V , the set of state change functions, each function associ- ates with a vertex v, C ¼fg c : S !fg True; False ;"e 2 E , the set of condition functions, each func- tion associates with an edge e, T ¼fg t : S ! Time;"e 2 E , the time delay on each edge e(normally we use < ● e as Time Base), A ¼fg A ;"e 2 E , the set of attribute lists, if any, and each list associates with an ● e edge e, ● B ¼fg B ;"v 2 V , the set of parameter lists, if any, and each list associates with a vertex v. }ðÞ H marks a set consisting of the set of all subsets of a set H, the so-called powerset: }ðÞ H ¼fg xx j H . Definition 3.4: Partition For any set H, set Par }ðHÞ is a partition of H, if 0 0 0 ðÞ "I; I 2 Par: II ) I˙I ¼ f^ðÞt I ¼ H I2Par The partition of set H is marked as P . Definition 3.5: Projection For event graph M, Projection : V ! StateVarSet is defined as the set of all state variables accessed by a subset of V. Definition 3.6: Partitioned event graph The PEG corresponding with an event graph M <V ; E; S; F; C; T ; A; B>is PEG M ; P , where ProjectionðÞ I I 2 P is a partition of StateVarSet. hi fg j M V V The equivalence between the PEG and the LP paradigm is proved by generating a bidirectional map between them. Mathematical and Computer Modelling of Dynamical Systems 159 The introduction of attribute A and parameter B in Definition 3.3 is a notational convenience and does not bring change to the modelling power of the EG [22]. The method for removing parameters from the EG is presented in [11] and the EG-based model with cancelling edges can be transformed into an equivalent form with only scheduling edges [46]. Therefore, we only consider EG without attributes, parameters, and cancelling edges in the discussion. First, transformation from LP-based model to the corresponding EG-based model is performed. The corresponding EG model of the Set is LP defined as: EGhi EventTSet; ScheduleRelationship; StateSpace;¨ F ;¨ C ;¨ T : Set i2L i i2L i i2L i LP Since each event type belongs, and only belongs, to a single LP, which means that " T 2 EventTSet)9ðÞ i 2 L ^ eT 2 EventTSubset e i ^ "i; j 2 L ) eT 2 EventTSubset ^ eT 2 EventTSubset ) i ¼ j ; i j there exists a function Γ: EventTSet ! L, which maps each eT 2 EventTSet to the index i of the EventTSubset it belongs to. By applying a curry operation to δ , the state transformation function for LP is defined as: F Δ f : S ! S j"eT 2 EventT Set; f ¼ δ ðÞ eT ; i ¼ ΓðÞ eT : i eT i i eT The corresponding event scheduling function on the edge set of LP is defined as: C Δfc : S !fg True; Falsej"r 2 Schedule Relationship ; i r i i "s 2 S ; c ðÞ s ¼ IsTrueðÞ r:to 2 π δðÞ r:from; sg; i r EventT Set where π is the projection function from EventTSet × Time to EventTSet. EventT Set The time delay function on the edge set of LP is defined as: T Δ t : S ! Timej"r 2 Schedule Relationship i r i i "s 2 S t ðÞ s ¼ π δðÞ r:from; s ; i r Time where π is the projection function from EventTSet × Time to Time. Time Through the transformation procedure described above, an EG-based model EG is set LP generated from Set . LP Define P Δfg EventT Subset ;"i 2 L , according to the definition of EventTSubset and E i i Definition 3.4, P is a partition of EventTSet. On the one hand, since StateVarSet and E i EventTSubset belong and only belong to a single LP , there is a bidirectional map from i i P to P , on the other hand, StateVarSet E fg ProjectðÞ StateVarSet; xjx 2 P ¼fg StateVarSet ; i 2 L E i 160 B. Wang et al. is a partition of the state variable set StateVarSet, the constraint in Definition 3.6 is satisfied. The PEG-based model constructed from Set is PEG Δ EG ; P ; and Set Set E LP LP LP PEG is a PEG-based representation of Set . Set LP LP We have proved that any LP-based discrete-event model can be transformed into an EG-based model. Second, a transformation is constructed from an EG-based model to its corresponding LP-based model. Since for the PEG-based modelfg ProjectionðÞ I jI 2 P is a partition of StateVarSet, the construction of the map is similar to the procedure above. The LPs are constructed according to P andfg ProjectðÞ StateVarSet; xjx 2 P . Particularly, V V M ¼hi V ; E; S; F; C; T ; A; B corresponds to a discrete-event model in event scheduling world view, which is Model with jLj¼ 1. LP We have proved that any discrete-event model in PEG formalism can be described by the LP Paradigm. In summary, the bidirectional map between LP-based model and PEG-based model exists. 3.4. The structural operational semantics The SOS of the PEG is defined on an abstract machine with TLTS, which is an extended Labelled-Transition System. Definition 3.7: Labelled-transition system (LTS) LTSΔhi S; s ; Label; ! ; where S is the state space. s 2 S is the initial state. Label is the set of all actions, which stands for the event types. action ! is the set of time-passage transitions, and ! S Label S: s ! s ● a b stands forðÞ s ; action; s2! , in which s ; s 2 S, action 2 Label. a b a b Definition 3.8: Timed-Labelled Transition System TLTS ¼hi S; s ; Label; !; 7! ; where ● S, s , Label and ! are defined in the same way as in Definition 3.7. delay ● 7! is the set of time-passage transitions, and 7! S R S: s 7! s stands for a b ðÞ s ; delay; s2 7!, in which s ,s 2 S, delay 2 R . a b a b A TLTS contains two kinds of transitions: time-passage transitions corresponding to R and discrete transitions. Mathematical and Computer Modelling of Dynamical Systems 161 Based on the definitions above, we derive the definition of the SOSs of EG and PEG. The execution of an EG model is on an abstract machine whose configuration (global state) keeps track of the state of the component and the time of the last transition. The configuration of a PEG-based model is composed from the configuration of all partitions. The time used in the following definition refers to simulation time [2]. 3.4.1. Operational semantics of EG The SOS of the EG model is represented by TLTSðÞ EG ¼ <Config; config ; Label; !; 7!>; in which: ● Config ΔSTATE Time }ðÞ EventT Set TimeðÞ EventT Set Time PHASE Config is the state space, and "stateΔhi s; τ; Λ; Active; Phase 2 Config: (1) s 2 STATE, STATE = EVAL(StateVarSet). EVAL(StateVarSet) corresponds to the model’s StateSpace in the LP paradigm. StateVarSet stands for the set of state variables in EG-based model. The type of the state variable v is defined as dom(v). η 2 EVAL(StateVarSet) is an evaluation function for the StateVarSet. Cond(StateVarSet) is the set of Boolean expressions on StateVarSet. (2) τ 2 Time stands for the simulation time, delay stands for the simulation time delay. (3) Λ 2 }ðÞ EventT Set Time is the set of pending events. Define Λ.head as the reference to the event in Λ with the lowest timestamp, if the set is empty. (4) Active 2 EventTSet × Time is the cursor to the currently executing event if any. Active.Type 2 V¨fg NULL , Type stands for the Event Type of the cursor, Type = NULL means that there is no event executing currently. (5) Phase 2 PHASEΔfg Elapse; Scheduling , in which the event retrieval operation from the pending event set and the execution operation are treated as a single transaction. (6) The time base is represented by Time, which is < in this paper. config is the initial state. ● LabelΔV¨E, which is the union of the edge set and the vertex set of the PEG. ● Transition relationships ! and 7! are defined in below: (1) Event Execution ðÞ Phase ¼ Elapse^ðÞ Λ:head:TYPE ¼ EGvertex^ðÞ τ ¼ Λ:head:timestamp EGvertex 0 0 0 hi s; τ; Λ; Active; Phase !hi s ; τ; Λ ; Active ; Phase 0 0 0 0 0 where ðs ¼ f ðsÞ; Active ¼ Λ:head; Λ ¼ Λ fActive g; Phase EGvertex ¼ ExeSch; EGvertex 2 VÞ; 162 B. Wang et al. (2) Event Scheduling ðÞ Phase ¼ Scheduling ΛðÞ Active:TYPE ¼ EGvertex^ η EGedge :c ¼ True i ij EG ðÞ c;t edge ij 0 0 hi s; τ; Λ; Active; Phase !hi s; τ; Λ ; Active ; Phase 0 0 0 where Λ ¼ Λ¨ EGvertex ; τ þ 1 ; Active :TYPE ¼ NULL; Phase ¼ Elapse; EGvertex and EGvertex 2 V ; EGedge 2 E ; i j ij (3) Time Elapsing ðÞ Phase ¼ Elapse^ðÞ τ þ delay < Λ:head:timestamp delay hi s; τ; Λ; Active; Phase !hi s; τ þ delay; Λ; Active; Phase where (delay 2 Time). 3.4.2. Operational semantics of PEG In order to define the SOS of the PEG-based model, we first transform PEG Δhi M ; P ; P into the equivalent style PEGΔfg LP ; :::; LP , where M StateVarSet E 0 n1 LP Δf<StateVarSet ; EventTSubset >ji 2 Lg; ð0 i<nÞ: i i i The SOS of the PEG-based model is represented as a TLTS: TLTSðÞ PEG ¼ <Config; config ; Label; !; 7!>; in which Config ΔSRATE Time }ðÞ EventSet TimeðÞ EventSet Time PHASE Config is the state space, and "state Δhi s; τGVT ; Λ; Active; Phase 2 Config: s ¼ s ; ... ; s ; s 2 S 1 i jLj: (1) 1 jLj i i; (2) Λ ¼ Λ ; ... ; Λ ; 1 i jLj, which means that Λ is the composition of 1 jLj pending event sets of all LPs, and globally unique. (3) Active 2 EventTSet Time is the cursor to the currently executing event if any. (4) The notation, τΔτGVT ¼ Min ðÞ lvt , is the global simulation time in which i2L i lvt is the local simulation time of LP . i i (5) Phase 2 PHASE ¼fg Elapse; Scheduling : config is the initial state. ΔV¨E: Label The time base is represented by Time, which is < in this paper Transition relationships ! and 7! are defined in the following rules: ● Mathematical and Computer Modelling of Dynamical Systems 163 (1) Event Execution ðÞ EGvertex 2 EventT Subset^ðÞ Phase ¼ Elapse^ðÞ Λ:head:TYPE ¼ EGvertex^ðÞ τ ¼ Λ:head:timestamp 2 3 2 3 2 3 2 3 2 3 2 3 *+*+ .. . .. . .. . .. . .. . .. . EGvertex 0 0 0 0 4 5 4 5 4 5 4 5 4 5 4 5 s ; lvt ; Λ ; Active; Phase ! s ; lvt ; Λ ; Active ; Phase i i i i i i .. . .. . .. . .. . .. . .. . 0 0 0 0 0 where ðs ¼ f ðÞ s ; Active ¼ Λ:head; Λ ¼ Λ fg Active ; Phase EGvertex ¼ Scheduling; EGvertex 2 VÞ: (2) Event Scheduling ðÞ Phase ¼ Elapse^ðÞ τ þ delay < Λ:head:timestamp GVT 2 3 2 3 2 3 2 3 2 3 2 3 *+*+ s lvt Λ s lvt þ delay Λ 1 1 1 1 1 1 ... ... ... ... ... ... 4 5 4 5 4 5 4 5 4 5 4 5 s lvt þ delay ; ; ; Active; Phase delay ; ; ; Active; Phase i i lvti Λi Si Λi ... ... ... ... ... ... 7! þ delay s lvt Λ S lvt Λ jLj jLj jLj jLj jLj jLj where (delay 2 Time). (3) Time Elapsing If the vertex of the scheduling edge crosses the partition boundary it is identified as external event scheduling. If not, then it is internal. External event scheduling: If (EGvertex 2 Event T Subset ^ EGvertex 2 EventTSubset ^ km) i m j k ðÞ Phase ¼ Scheduling^ðÞ Active:TYPE ¼ EGvertex^ η EGedge :c ¼ True i ij 2 3 2 3 2 3 2 3 2 3 2 3 ; *+ *+ ... ... ... ... ... ... s lvt Λ s lvt Λ m m m m m m EGedge ðÞ c;t ij ... ... ... ... ... ... 0 0 4 5 4 5 4 5 4 5 4 5 4 5 ; ; ; Active; Phase ! ; ; ; Active ; Phase s lvt Λ s lvt Λ k k k k k k .. . .. . .. . .. . .. . 0 0 0 where Λ ¼ Λ ¨ EGvertex ; lvt þ t ; Active :TYPE ¼ NULL; Phase ¼ Elapse; k k j m EGvertex 2 V ; EGedge 2 EÞ: i ij Internal event scheduling: If EGvertex , EGvertex 2 EventTSubset i j m ðÞ Phase ¼ Scheduling^ðÞ Active:TYPE ¼ EGvertex^ η EGedge :c ¼ True i ij 2 3 2 3 2 3 2 3 2 3 2 3 ; *+ *+ EGedge ðÞ c;t ij 4 5 4 5 4 5 4 5 4 5 4 5 0 0 s ; lvt ; Λ ; Active; Phase ! s ; lvt ; Λ ; Active ; Phase m m m m m m 164 B. Wang et al. where 0 0 0 Λ ¼ Λ ¨ EGvertex lvt þ t ; Active :TYPE ¼ NULL; Phase m m j m ¼ Elapse; EGvertex ; 2 V ; EGedge 2 EÞ: i ij 3.4.3. Wallclock time-based execution The SOS of PEG in Section 3 is strictly sequential, hence the sequence of event execution in Wallclock time strictly conforms to the sequence in simulation time, which is non- decreasing timestamp order. The Wallclock time execution of TLTS and its equivalence relationship based on local causality constraint (LCC) [2] are introduced in order to study the concurrent execution of the LP-based model in PEG formalism. The following definitions are also introduced: Definition 3.9: I – Trace ω: I ! S, in which I represents the closed interval start from time 0, and S represents the t t 0 0 0 state space of the system, in which "t, then t ,if t t then ωðÞ t ! ωðÞ t , ωlt represents the supremum of I, and ω. ft represents the infimum of I. The ω.ls represents the final state, and ω.fs the initial state ω(0). For example, config ! config corresponds to the [0, d] – Trace, in which ω:fs = config, ω.ls = config’. Definition 3.10: Timed Execution of TLTS The Timed Execution of TLTS is an alternating sequence γ ¼ω a ω a ... ω a ... in 0 1 1 2 n1 n a þ1 which ω represents I-trace, a represents event type, and ω :ls ! ω :fs. The duration i i i iþ1 and initial state of γ is marked as γ.lt and γ.fs, respectively. γ:fs ¼ ω :fs, γ:ft ¼ ω :ft. For 0 0 limited Timed Execution, formulae γ:lt ¼ ω :lt, γ:ls ¼ ω :ls hold. The set of all possible n n Timed Execution of TLTS is marked as execs(TLTS). Definition 3.11: Wallclock time execution of TLTS The Wallclock time execution of TLTS is formed by attaching the Wallclock timestamp a . wct to each discrete-event type a in γ ¼ ω a ω a ... ω 1a ... The actual execution 0 1 1 2 n n sequence of TLTS in Wallclock time is γ ¼ ω a ω ... ω a ... . Define WC WC WC WC WC WC n 0 1 2 n1 the set of all possible Wallclock time execution of TLTS as execs (TLTS). WC If each LP adheres to the LCC, then the parallel execution will yield exactly the same results as a sequential execution of the same model, provided that simultaneous events are processed in the same order in both cases [2, p. 53]. This allows LCC to be regarded as a selection of all executions without causal error from execs (TLTS). The set of all Wallclock time executions of TLTS qualifying LCC is WC LCC defined as execs ðÞ TLTS execs ðÞ TLTS , and event is defined as e Δhi a ; ω ft , with WC i i i WC event type e .type = a , and execution time e :st ¼ ω :ft. i i i i If there is no causality between e and e , which is marked as e ||e , then exchanging e i j i j i with e in the Wallclock time execution, does not alter the result. This is stated by the following formula. For executions γ ¼ ω a ω ... a ω ... a ω ... WC WC WC WC WC WC WC WC 0 1 1 i i j j 0 0 γ ¼ ω a ω ... a ω ... a ω ... WC WC WC WC WC WC WC WC 0 1 1 j j i i Mathematical and Computer Modelling of Dynamical Systems 165 The following solutions are held to be true: 0 0 LCC 0 ω :fs ¼ ω :fs; γWC; γ 2 execs ðÞ TLTS ; and γWC γ : WC j WC WC WC WC In conclusion, even though parallel executions using different parallel time management algorithms can generate different Wallclock time executions, these executions result in the same final system state as the SOS describes in Section 3, as long as the time management algorithms all adhere to the LCC. 4. PEG-based model transformation framework for PDES In this section, a model transformation framework for PDES is proposed. In this frame- work, models transform through three phases, which are DSL, PEG formalism, and platform-specific API. Four personnel roles will be described. First, the abstract Grammar of PEG language, named Grammar , is laid out; second, the Framework is discussed in detail; third, the PEG transformation from the general EG to a PEG-based Model is accomplished by implement- ing imparametrization and partition. This approach is key to the application of the PEG. 4.1. Grammar of the PEG language The PEG language grammar, Grammar , is described in this section. Grammar PEG PEG specifies how to analyse the model and provides the partition information of the PEG. A use case of Grammar is presented. PEG The Extended Backus–Naur Form (EBNF)-styled grammar of PEG is shown in Figure 1, in which Function employs the ECMAScript grammar [47]. The single airport model [2, p. 34], in PEG language, is demonstrated in Algorithm 1. 4.2. The PEG-based domain-specific modelling framework for PDES In this framework, the model in DSL is transformed into an executable model through the PEG formalism, as shown in Figure 2. The transformation has three phases. First, the transformation from DSL to EG is performed; second, the resulting EG-based model is partitioned into a PEG-based model; and, third, the PEG-based model is transformed into an executable model on specific PDES platform. Simulation experiments are conducted after further configuration to Random Number Generator, Queue Algorithms, and Time Management Algorithms. Briefly, with PEG, the tripartite phasing decouples DSL from specific simulation platform API. Algorithm 1: Single Airport Model in PEG Language 1 model airport; 2 StateVar { 3 integer ln_.The.Air 10; 4 integer On_The_Ground 0; 5 boolean Runway_Free True; 6 double R 10.0; 7 double G 15.0; 8} 9 166 B. Wang et al. 10 EventPartition EventSetl { 11 Event ArrivalEvent = “ARRIVAL” (); 12 Event DepartureEvent = “DEPARTURE” (); 13 Event LandedEven t = “LANDED” (); 14 } 16 Edges { 17 Edge Arrival_Landed { 18 type schedule 19 events (ArrivalEvent, LandedEvent) 20 condition [isRunwa_Free = True] 21 priority default 22 delay 0 23 } 24 Edge Landed_Landed { 25 type schedule 26 events (LandedEvent, LandedEvent) 27 condition [True] 28 priority default 29 delay 0 30 } 31 Edge Landed_Departure { 32 type schedule 33 events (LandedEvent, DepartureEvent) 34 condition [get In _The_Air >0] 35 priority default 36 delay 0 37 } 38 } Four roles are involved in the PEG-based PDES of domain-specific models (DSMs): (1) Expert A: an expert with Domain Knowledge, familiar with domain knowledge, models the domain problem using the selected DSL. (2) Expert B: an expert with DES Modelling Knowledge, familiar with the grammar, semantics, and analysis of EG formalism, models the domain problems using EG. (3) Expert C: an expert with Language Analyser Construction Knowledge develops language interpreter, parser and lexical analyser in order to further transform the DSL into the target language. (4) Expert D: an expert with Parallel Simulation Platform Knowledge, who is familiar with the experiment configuration and software/hardware deployment customized towards a specific simulation platform. Generally speaking, the model transformation is divided into three phases: model-to- model transformation, model reconstruction, and model to code transformation [48]. The transformation from a DSM to the general EG-based model is a model-to-model transformation. In the cooperation of experts of four roles, information is passed through several abstraction levels and aspects of the system. Mathematical and Computer Modelling of Dynamical Systems 167 1 //a model has a name and a number of definitions (states, event partitions, edges) 2 MODEL ::= ’ model ’ I d e n t i f i e r ’ ; ’ STATEVARIABLES EVENTPARTITION EDGELIST 4 //the state variables 5 STATEVARIABLES ::= ’ StateVar { ’ StateVariableDeclaration ( ’ ; ’ StateVariableDeclaration ) ’ } ’ 6 StateVariableDeclaration ::= Variable Assignment 8 //a variable has a type and a name 9 V ari ab le ::= BasicType I d e n t i f i e r 10 BasicType ::= ’ s t r i n g ’ | ’double ’ | ’ integer ’ | ’ boolean ’ 11 Identifier ::= ( ’a ’ . . ’z ’ | ’A ’ . . ’Z ’ | ’ ’) ( ’ a ’ . . ’z ’ | ’A ’ . . ’Z ’ | ’ ’ | ’0 ’.. ’9 ’) ∗ 12 Assignment ::= Number | STRING | Function 13 STRING ::= ( any c h a r a c t e r ) ∗ 14 Number ::= intNumber | realNumber 16 //an event partition definition is being composed from the events defined for it 17 EVENTPARTITION::= ’ E v e n t P a r t i t i o n ’ I d e n t i f i e r ’ {’Event ∗ ’ } ’ 19 //each event has a name, and a string representation and a set of parameters 20 EVENT::= ’ Event ’ I d e n t i f i e r ’= ’ STRING ’ ( ’ I d e n t i f i e r ’ ) ’ ’ ( ’ ParameterSet ’ ) ’ ’ ; ’ 21 // state transition function F 22 STATETRANSITION::= ” S ta te Tr a ns it io n ” I d e n t i f i e r ’=’ Function ; 23 ParameterSet ::= ( Variable ’ ; ’ ) ∗ 25 //edge definitions 26 EDGELIST ::= ’ Edges ’ ’ { ’ EDGE∗ ’ } ’ 27 EDGE::= ’ Edge ’ I d e n t i f i e r ’ { ’ ’ type ’ EdgeType ’ events ( ’ eventPair ’ ) ’ ’ c o n d i t i o n [ ’ Condition ’] ’ ’ p r i o r i t y ’ P r i o r i t y ’ delay ’ TimeDelay ( ’ functions ( ’ ( Function ’ ; ’ ) ∗ )’)+ ’ } ’ 28 EdgeType ::= ’ Schedule ’ | ’ Cancel ’ 29 EventPair ::= I d e n t i f i e r I d e n t i f i e r 30 Condition ::= ’ True ’ | ’ False ’ | Function 31 Priority ::= ’ default ’ | ’ lowest ’ | ’lower ’ | ’low ’ | ’high ’ | ’higher ’ | ’ highest ’ 32 TimeDelay ::= Number | Function // lvt+a.random() Figure 1. Grammar of PEG. The transformation from PEG-based model to simulation platform-specific API description is a model to code transformation. First, the general EG-based model is transformed into a parameter-free EG-based model by the parameter expansion algorithm. Next, the parameter-free EG-based model is transformed to a PEG-based model. Both are model reconstructions. Figure 2. PEG-based model transformation framework for PDES. 168 B. Wang et al. The tripartite transformation provides flexibility at two points. The first phase enables a platform-independent representation and a formal analysis of the model’s property. The second phase eases the cross-platform migration by focusing the map from PEG formal- ism, instead of reforming the models each time from the very beginning. 4.3. Transforming general EG- to PEG-based model Transforming general EG formalism into PEG formalism is carried out as follows: Imparametrization of the parametric EG-based model This procedure eliminates the attribute and the parameter. The preconditions of this operation are the domain of parameter on the node, and the domain of the attribute on the edge are, respectively, either finite, or can be transformed into a partition with finite cardinality. A partition is a set of nonempty subsets of the domain such that every domain element is in exactly one of these subsets. The parameter expansion method is shown in Algorithm 2, in which the first loop is an expansion through Domain([i]). Since Domain ([i]) and Domain([j]) are both finite sets, this loop contains finite operations. Algorithm 2: Imparametrization Algorithm for General EG-based Model 1 V = ;, E = ; temp temp 2 for each v in V with parameter [i] //Iteration through the vertex Set 3 add v to V temp 4 for each i in Domain([i]) //Expand the Parameter Set of single vertex 5 if (v 2 V = = False) 6 add V to V 7 //Generate vertex, state change function, and state variable set according to i 8 generate V,f ,SV i vi i 9 endif 10 for each e 2 <v, * > //expand the attributes on each edge starting from v 11 add e to E temp 12 //Domain([j]) is the expression set defined on V E Domain([i]) 13 if e has attribute as j(i)//if attribute [j] of e is defined on [i]. 14 domain = Domain([j (i)]) 15 else //if attribute [j] of e is not defined on [i]. 16 domain = Domain([j]) 17 endif 18 for each j in domain 19 generate e =< v ,v′ > j i j 20 if (e 2 E = = false) 21 t =t (j) ej e 22 c =c (j) ej e 23 add e to E 24 endif 25 endfor 26 endfor 27 endfor 28 endfor 29 V= V – V temp 30 E= E – E temp Mathematical and Computer Modelling of Dynamical Systems 169 Generating partitions for state variable set and event set The influencer functions (influencer) and influencee functions (influencee) in all event vertexes to state variables are generated for the EG-based model in order to reflect the causality between state variables and events in literature [49,50]. The notation f .write represents the set of state variables modified by the state transition function of event type vertex v. The notation f .read represents the set of state variables read by the state transition function of v. The notation t .read represents the set of state variables read by the time increment function t, on edge e. The notation c .read represents the set of state variables read by the condition function c on edge e. Iterating through the EG-based model obtains these sets. OutCom stands for the set of outcoming edges started from vertex v. influencer ¼fg V ! }ðÞ SV j"sv 2 SV ; sv 2 influencerðÞ v , sv 2 f (1) The notation influencer stands for the set of state variables modified by state transition function f of vertex v. influencee ¼ V ! }ðÞ SV j"sv 2 SV ; sv 2 influenceeðÞ v (2) , sv 2 f :read¨¨ ðt :read¨c :read Þ v e e e2OutCom Project ¼fV ! }ðSVÞj"sv 2 SV ; Project ðvÞ¼ influenceeðvÞ¨influencerðvÞg (3) Construct directed bipartite G ¼ðV ; SV ; E Þ; E ¼ E ¨E based on EG. b b b write read E ¼f<u ; u > 2 V SVju 2 influencerðu Þg (4) write v sv sv v E ¼f<u ; u > 2 SV Vju 2 influenceeðu Þg (5) read sv v sv v ● Construct the Adjacency Matrix of bipartite G as AðGÞ ¼ða Þ; in which ij jVjjSVj a 2f1; 0; 1g. ij < 1 , <u ; sv > 2 E ¨E i j read read a ¼ 0 , <u ; sv > 2fV SV E E g (6) ij i j read write 1 , <u ; sv > 2 E E i j write read ● Partition Generation. The adjacent matrix AðG Þ¼ðja jÞ of the base graph G′ of G is also with jVjjSVj ij rank, but does not distinguish between influencer and influencee. The set of all connected components of G′ is generated by the minimum spanning tree algorithm [51]. Given that G′ has ω connected components as, G ; G ; :::; G ðω 2Þ where G is not 1 2 ω i empty, by proper arranging the row/line of G, we can get: 170 B. Wang et al. 0 1 MðG Þ 0 B C MðG Þ B C MðG Þ¼ B C (7) @ A 0 MðG Þ For example, the adjacent matrix of the corresponding undirected underlying graph G′ of the discrete-event model in Figure 3(a) is: 0 1 11 00 0 B C 00 10 0 B C B C 01 00 0 B C @ A 00 11 1 00 00 1 ω = 2 corresponds to the situation in Figure 3(b). ● Further partition of a single connected component If ω = 1 or, the estimated computational load of a single connected component exceeds the single criteria, then further partitions are required which will result in (Read/Write) access to the stat variables across different partitions. Shadow events and state variables are introduced in order to enforce boundary constraints requiring that each event in each partition access only its own state variables. (1) Write access across partitions: a shadow event is created for each write access to state variable that crosses partitions, shown in Figure 3(c). (2) Read access across partitions: two shadow events and a shadow state variable are created for each read access to state variable that crosses partitions, shown in Figure 3(d). 5. Case study In this section, we present a DSL for the spatial stochastic simulation of chemical reactions using Abstract Next Subvolume Method (ANSM) [52,53], to demonstrate the capability of the PEG-based framework presented in Section 4. A spatial variation of the Lotka–Volterra System (LVSystem) [54,55] is used as the benchmark model, and described in Figure 4. First, a DSL for the LVSystem model is presented. Second, the DSM is transformed into a generic PEG-based model, and then into theexecutablecodeon YHSUPE. Third, we evaluate the performance of parallel simulations. 5.1. Model description Pronounced oscillatory behaviour is produced using the setup in Gillespie’s work [56]. An N×N2D grid is taken as the space for the Lotka–Volterra Model. N denotes the number of subvolumes in the model and represents the scale of the model. Num and predator Num stand for the predator and prey the population in a subvolume. Initially there prey Mathematical and Computer Modelling of Dynamical Systems 171 Figure 3. Event graph partition based on bipartite graph. 172 B. Wang et al. Figure 4. EG-based model description of LVSystem in ANSM. (a) Event processing and schedul- ing in ANSM. (b) EG-based model description. are 1000 of each in every subvolume of the 2D grid. The diffusion rate constants of the predators and preys are noted as d and d . The reaction constant is noted as c . predator prey i The grass population is assumed to never change. The parameter setup for the LVSystem model is in Table 1. Figure 4(b) is the parameterized EG-based model for LVSystem in ANSM, in which the target is the number of the subvolume. A single subvolume contains the state variables and the event types. State variables define the quantity and quality of the reactants in the subvolume. The event processing and scheduling is shown in Figure 4 Mathematical and Computer Modelling of Dynamical Systems 173 Table 1. Model parameters setup. Diffusion rate Population constant Reaction Reaction rate constant Num ¼ 1000 d ¼ 2:5 Grass þ Prey ! 2Prey c ¼ 0:01 predator predator 1 Num ¼ 1000 d ¼ 5 Predator þ Prey ! 2Predator c ¼ 0:01 prey prey 2 Num ¼ 1000 d ¼ 0 Predator ! Null c ¼ 10 grass grass 3 (a) [53], in which RandomEvent is an event type which corresponds to self-scheduling, and acts as described in the appendix of [57]. ReceiveEvent is an event type correspond- ing to diffusion, is assumed to be scheduled by an adjacent subvolume, and addresses the reactants diffusing in. 5.2. Domain-specific language for LVSystem The DSM transformation of the LVSystem is performed in the following procedure: (1) Specify the data and behaviour provided by the DSM, and construct the EG-based model, according to ANSM. (2) Formulate the grammar of the DSL, and implement the interpreter from that language to the EG formalism using ANTLR [58]. (3) Initialize the EG-based model, and partition the general EG-based model to PEG- based model using Algorithm 4.3. (4) Implement the interpreter from the PEG formalism to YHSUPE using ANTLR. (5) Configure the simulation experiment and deploy software/hardware environment according to requirements. The grammar of the DSL is shown in Figure 5. The model description of the LVSystem is shown in Figure 6. The domain-specific parallel spatial stochastic simulation subsystem is built on top of the YHSUPE. After the parameter and attribute expansion of the EG-based LVSystem model using Algorithm 2, a parameter-free EG-based model is obtained as shown in Figure 7.By dividing the EG-based model into a set of connected components, we get the PEG-based model; the partition is shown in Figure 8. 5.3. Simulation experiments The simulation experiments are executed on a PowerLeader Baode PR4310D Cluster (Shenzhen, Guangdong, P.R. China) with 20 computing nodes. Each computing node is equipped with two Intel 1.6 GHz Quad-Core Xeon Processors (Santa Clara, CA, USA), 8 GB RAM and interconnected with a 10 Gbps Infiniband connection. The operating ustre.1.6.5smp. The system on each node is Red Hat 3.4.6–8, with kernel 2.6.9–67.0.7, EL GCC version is 4.1.1. The discs are shared by all computing nodes. All the experiments in this paper were conducted atop YHSUPE. Every logical processor is mapped to a single OS process, and occupies the CPU core assigned as much as possible. 174 B. Wang et al. 1 DomainSpecificMODEL ::= ’name ’ Identifier ’; ’ SCALE SPECIES REACTIONS STATE RC RD 2 SCALE ::= ’ scale ’ intNumber 3 SPECIES ::= ’ s p e c i e s : ’ VarSet 4 REACTIONS ::= ’ r e a c t i o n s : ’ R e a c t i o n S e t 5 STATE ::= ’ s t a t e : ’ S t a t e v a r S e t 6 RC ::= ’ rc : ’ RcSet 7 RD ::= ’ dc : ’ RdSet 8 VarSet ::= ’ { ’( Identifier ’; ’) ∗ ’ } ’ 9 ReactionSet ::=( Equation ) ∗ 10 Equation ::= ’ { ’ I dentifier ’=’ intNumber Identifier ( ’+ ’ intNumber Identifier )+ ’−>’ intNumber I d e n t i f i e r ( ’+ ’ intNumber I d e n t i f i e r )+ ’ } ’ 11 StatevarSet ::= VarvalueSet 12 RcSet ::= VarvalueSet 13 RdSet ::= VarvalueSet 14 VarvalueSet ::= ’ { ’( varvalue ’ , ’ ) ∗ ’ } ’ 15 varvalue ::= I d e n t i f i e r ’: ’ intNumber 16 Identifier ::= ( ’a ’.. ’ z ’ | ’A’.. ’Z’ | ’ ’) ( ’ a ’ . . ’ z ’ | ’A’.. ’Z’ | ’ ’ | ’0 ’.. ’9 ’) ∗ Figure 5. Grammar of the script language for the LVSystem model. 1 name : { SaptialLotkaVolterra } 2 scale X 3 \\[ Subvolume ] 4 species : {A;B;C} 5 reactions : 6 {r1 = 1A + 1B −> 2B+A} 7 {r2 = 1C + 1B −> 2C} 8 {r3 = 1C −> 0C} 9 \\[ parameters ] 10 state : {A:1000 , B:1000 , C:1000 } 11 rc : {r1 :0.01 , r2 :0.01 , r3 :10 } 12 dc : {d1 :0 , d2 :5 , d3 :2.5 } Figure 6. Model description for the LVSystem. Figure 7. The parameter-free EG-based model for LVSystem. The DSM of the LVSystem is transformed into an executable model of YHSUPE using the model transformation framework we proposed. The performance of parallel simulation using Breathing Time Warp (BTW) [59] as time management algorithm was Mathematical and Computer Modelling of Dynamical Systems 175 Figure 8. The partition of the parameter-free EG-based model for LVSystem. investigated. Rollbackable pseudo random number generators are used. The Qheap [60]is used as the event queue. A block style static partition is employed, in which nearby LPs are dispatched to the same logical processor, or if not the same, as nearby as possible. Figure 9 shows the comparison of speedup on a 100 × 100 grid and a 64 × 64 grid of LVSystem. It also shows the speedup variation according to the number of processors used in the experiments. The relationship between the speedup and the number of processors deployed is shown. The model size for the blue line is 100 × 100 and for red line is 64 × 64. The speedup grows quickly at first, and then declines slowly as the number of processors involved increases from 1 to 18. The inflection points for 100 × 100 model is 8 processors, while for 64 × 64 model is 4 processors. The speedup growth comes from computing power utilization, while the decline is due to the model size not matching the scale of physical platform. Performance penalty is more severe for models of smaller size. 6. Conclusion and outlook In this work, we have extended the classical event graphs to formalize the LP-based model of PDES. PEG formalism is a well-defined interpretation of the elements in the LP paradigm and serves as an unambiguous and platform-independent description of the LP- based model. The SOSs rigorously represent the timed behaviour of the LP-based model. 176 B. Wang et al. Figure 9. Simulation results: speedup of BTW under different hardware scales and model sizes. Though the SOS is sequential, it generates exactly the same result as parallel executions do with any time management algorithms. In our case, Wallclock time execution and its equivalence relationship based upon LCC is introduced. In the model transformation framework for PDES, the models are transformed using PEG formalism, from a DSL into a platform-specific API, while four personnel role types are distinguished. Based on this framework, a DSL for the PDES of LVSystem is presented, and preliminary parallel simulation results using YHSUPE are obtained. This case study shows that the PEG-based framework cannot only effectively transform a DSL into the LP paradigm, but also result in efficient parallel simulation on a specific platform. In short, PEG formally specifies the characteristics of event scheduling and state partition in the LP paradigm and thus provides modellers with a mean to formally analyse an LP-based model’s behaviour and a cross-platform model transformation. There are several directions for further work. First, PEG formalism is not designed as a high-level specification of DESs and does not allow create/delete vertexes/edges at run-time. This would make mapping high-level formalisms (such as DEVS [4]) with an indeterministic and dynamic structure to PEG an important direction for the future. Second, a more specialized language that only allows coding valid models of PEG formalism, and incorporates automatic model partitioning for general EG-based model should be developed. Third, the SOS of the PEG presented in this paper formed a basis for formal verification. By transforming the PEG-based model into a timed automata- based model, mainstream model checking tools such as DiVinE (Brno, Moravia, Czech Republic) [14] can be used to study the properties of LP-based model as a necessary supplement to the simulation approach. Fourth, the current sequential operation seman- tics of the PEG yields exactly the same results as any parallel execution adhering to the LCC does, and serves as a basis for further study of formalizing parallel execution. To develop an abstract machine with concurrent and speculative operation semantics for PEG, such as introducing Tapus’s semantics [44], is of great interest. Acknowledgements The authors would like to show their gratitude to Prof. Lee W. Schruben, Prof. Adelinde M. Uhrmacher, Dr Jan Himmelspach, and Dr Roland Ewald for their help throughout the development Mathematical and Computer Modelling of Dynamical Systems 177 of this work, and to Stephen Laudig J.D. for his language editing assistance. Authors are greatly thankful to the reviewers for their valuable comments to improve this paper. Funding This work is partly supported by the China Scholarship Council [grant number 2007U39612]; the National Natural Science Foundation of China (NS-FC) [grant number 61271252], [grant number 61003075]. References [1] J. Liu, J.J. Cochran, L.A. Cox, P. Keskinocak, J.P. Kharoufeh, and J.C. Smith, Parallel Discrete-Event Simulation, John Wiley & Sons, Inc., Hoboken, NJ, 2011. [2] R.M. Fujimoto, Parallel and Distributed Simulation Systems, John Wiley and Sons, Hoboken, NJ, 2000. [3] J. Misra, Distributed discrete-event simulation, ACM Comput. Surv. 18 (1986), pp. 39–65. [4] B.P. Zeigler, H. Praehofer, and T.G. Kim, Theory of Modeling and Simulation, 2nd ed., Vol. 2, Academic Press, Waltham, MA, 2000. [5] R. Alur, Timed Automata, Computer Aided Verification, Springer-Verlag, New York, 1999, pp. 688. [6] C.G. Cassandras and S. Lafortune, Introduction to Discrete Event Systems, 2nd ed., Springer- Verlag, New York, 2008. [7] D. Harel, Statecharts: a visual formalism for complex systems, Sci. Comput. Programming. 8 (1987), pp. 231–274. [8] R.J. Paul, Activity cycle diagrams and the three-phase method,in Proceedings of the 25th Conference on Winter Simulation, WSC ‘93, Los Angeles, CA, ACM, New York, 1993, pp. 123–131. [9] J.M. Wing, FAQ on PI-calculus, Microsoft Internal Memo, 2002. [10] W. Xia, Y. Yao, and X. Mu, An extended event graph-based modelling method for parallel and distributed discrete-event simulation, Math. Comput. Model. Dyn. Syst. 18 (2012), pp. 287– 306. doi:10.1080/13873954.2012.655697. [11] E.L. Savage, L.W. Schruben, and E. Yücesan, On the generality of event-graph models, INFORMS J. Comput. 17 (2005), pp. 3–9. doi:10.1287/ijoc.1030.0053. [12] L. Schruben, Simulation modeling with event graphs, Commun. ACM. 26 (1983), pp. 957– [13] A. Buss, Component Based Simulation Modeling with Simkit, Vol. 1, San Diego, CA, IEEE Computer Society, Los Alamitos, CA, 2002, pp. 243–249. [14] J. Barnat, L. Brim, M. Češka, and P. Rockai, DiVinE: parallel distributed model checker (Tool paper),in Parallel and Distributed Methods in Verification and High Performance Computational Systems Biology (HiBi/PDMC 2010), Twente, IEEE Computer Society, Washington, DC, 2010, pp. 4–7. [15] P. Šimeček, DIVINE – distributed verification environment; Master’s thesis, Faculty of Informatics, Masaryk University, Czech Republic, 2006. [16] R. Eshuis, Reconciling statechart semantics, Sci. Comput. Programming. 74 (2009), pp. 65– 99. doi:10.1016/j.scico.2008.09.001. [17] E. Posse, Modelling and Simulation of Dynamic Structure Discrete-Event Systems, School of Computer Science McGill University, Montreal, QC, 2008. [18] R. Curry, C. Kiddle, R. Simmonds, and B. Unger, Sequential performance of asynchronous conservative PDES algorithms,in PADS ‘05: Proceedings of the 19th Workshop on Principles of Advanced and Distributed Simulation, IEEE Computer Society, Washington, DC, 2005, pp. 217–226. [19] P. Peschlow, M. Geuer, and P. Martini, Logical process based sequential simulation cloning,in Simulation Symposium, ANSS 2008, 41st Annual (2008), IEEE Computer Society, Washington, DC, 2008, pp. 237–244. [20] K.M. Chandy and J. Misra, Distributed Simulation: A Case Study in Design and Verification of Distributed Programs,in Software Engineering, IEEE Transactions on SE-5, IEEE Computer Society, Washington, DC, 1979, pp. 440–452. 178 B. Wang et al. [21] E. Yücesan and L. Schruben, Structural and behavioral equivalence of simulation models, ACM Trans, Model. Comput. Simul. 2 (1992), pp. 82–103. [22] L.W. Schruben, Graphical Simulation Modeling and Analysis: Using SIGMA for Windows, 1st Course Technology Press, Boston, MA, 1995. [23] L.W. Schruben, T.M. Roeder, W.K. Chan, P. Hyden, and M. Freimer, Advanced event scheduling methodology,in Proceedings of the 35th Conference on Winter Simulation: Driving Innovation, WSC ‘03, New Orleans, Louisiana Winter Simulation Conference, IEEE Computer Society, Washington, DC, 2003, pp. 159–165. [24] A.H. Buss and P.J. Sanchez, Building complex models with LEGOs (Listener Event Graph Objects), Winter Simulation Conference, Vol. 1, Los Alamitos, CA, IEEE Computer Society, Washington, DC, 2002, pp. 732–737. [25] J. de Lara, Distributed event graphs: formalizing component-based modelling and simulation, Electron. Notes. Theor. Comput. Sci. 127 (2005), pp. 145–162. [26] D.O. Rich and R.E. Michelsen, An assessment of the ModSim/TWOS parallel simulation environment,in WSC ‘91: Proceedings of the 23rd Conference on Winter Simulation, Phoenix, AZ, IEEE Computer Society, Washington, DC, 1991, pp. 509–518. [27] S. Das, R. Fujimoto, K. Panesar, D. Allison, and M. Hybinette, GTW: a time warp system for shared memory multiprocessors,in Simulation Conference Proceedings, Winter, Lake Buena Vista, FL, IEEE Computer Society, Washington, DC, 1994, pp. 1332–1339. [28] J.S. Steinman, SPEEDES: synchronous parallel environment for emulation and discrete event simulation,in Proceedings of the SCS Multiconference on Advances in Parallel and Distributed Simulation, January, IEEE Computer Society, Washington, DC, 1991, pp. 95–101. [29] T.L. Wilmarth, POSE: Scalable General-purpose Parallel Discrete Event Simulation, University of Illinois, Champaign, IL, 2005. [30] C.D. Carothers, D. Bauer, and S. Pearce, ROSS: a high-performance, low memory, modular time warp system, Workshop on Parallel and Distributed Simulation, Los Alamitos, CA, IEEE Computer Society, Washington, DC, 2000, pp. 53–60. [31] K. Perumalla, μsik: a micro-kernel for parallel/distributed simulation systems,in Workshop on Parallel and Distributed Simulation, June, IEEE, Monterey, CA, 2005, pp. 59–68. [32] R.L. Bagrodia and W.T. Liao, Maisie: a language for the design of efficient discrete-event simulations, IEEE Trans. Software. Eng. 20 (1994), pp. 225–238. doi:10.1109/32.277572. [33] R.G. Sargent, Some recent advances in the process world view,in Proceedings of the 36th Conference on Winter Simulation, WSC ‘04, Washington, DC, Winter Simulation Conference, IEEE Computer Society, Washington, DC, 2004, pp. 293–299. [34] G. Liu, Y. Yao, and B. Liu, VISICOM: a component-based parallel discrete event modeling framework, International Conference on Advances in System Simulation, (2010), pp. 158–163. [35] B. Hou, Y. Yao, B. Wang, and D. Liao, Modeling and simulation of large-scale social networks using parallel discrete event simulation, Simulation. 89 (2013), pp. 1173–1183. [36] K.S. Perumalla and R.M. Fujimoto, Interactive parallel simulations with the Jane framework, Future. Gener. Comput. Syst. 17 (2001), pp. 525–537. [37] R.L. Bagrodia, Parallel languages for discrete-event simulation models, IEEE Computational. Sci. Eng. 5 (1998), pp. 27–38. doi:10.1109/99.683737. [38] G.A. Wainer and N. Giambiasi, N-dimensional cell-DEVS models, Discrete Event Dynamic Systems. 12 (2002), pp. 135–157. doi:10.1023/A:1014536803451. [39] Q. Liu, Algorithms for Parallel Simulation of Large-Scale DEVS and Cell-DEVS Models, Carleton University, Ottawa, ON, 2010. [40] M. Hybinette, E. Kraemer, Y. Xiong, G. Matthews, and J. Ahmed, SASSY: a design for a scalable agent-based simulation system using a distributed discrete event infrastructure,in Proceedings of the 38th Conference on Winter Simulation, WSC ‘06, Monterey, California Winter Simulation Conference, IEEE Computer Society, Washington, DC, 2006, pp. 926–933. [41] D. Chen, G.K. Theodoropoulos, S.J. Turner, W. Cai, R. Minson, and Y. Zhang, Large scale agent-based simulation on the grid, Future. Gener. Comput. Syst. 24 (2008), pp. 658–671. [42] T. Oguara, D. Chen, G. Theodoropoulos, B. Logan, and M. Lees, An adaptive load manage- ment mechanism for distributed simulation of multi-agent systems, Ninth IEEE International Symposium on Distributed Simulation and Real-Time Applications. 1 (2005), pp. 179–186. doi:10.1109/DISTRA.2005.9. [43] J. Nutaro and H. Sarjoughian, Design of distributed simulation environments: a unified system- theoretic and logical processes approach, Simulation. 80 (2004), pp. 577–589. Mathematical and Computer Modelling of Dynamical Systems 179 [44] C. Tapus, Distributed Speculations: Providing Fault-Tolerance and Improving Performance, California Institute of Technology, Pasadena, CA, 2006. [45] F. Wieland, The threshold of event simultaneity,in Proceedings of the eleventh workshop on Parallel and distributed simulation, PADS ‘97, Lockenhaus, Austria IEEE Computer Society, Washington, DC, 1997, pp. 56–59. [46] R.G. Ingalls, D.J. Morrice, E. Yucesan, and A.B. Whinston, Execution conditions: a formaliza- tion of event cancellation in simulation graphs, INFORMS J. Comput. 15 (2003), pp. 397–411. [47] ECMA International, ECMA-262: ECMAScript Language Specification, 5.1 ed., Geneva, [48] A.W. Brown, S. Iyengar, and S. Johnston, A rational approach to model-driven development, IBM Syst. J. 45 (2006), pp. 463–480. doi:10.1147/sj.453.0463. [49] E.H. Page, Beyond speedup: PADS, the HLA and Web-based simulation,in Proceedings of the Thirteenth Workshop on Parallel and Distributed Simulation, PADS ‘99, Atlanta, GA, IEEE Computer Society, Washington, DC, 1999, pp. 2–9. [50] E.H. Page, Simulation Modeling Methodology: Principles and Etiology of Decision Support, Department of Computer Science, Virginia Tech, Blacksburg, 1994. [51] M.L. Fredman and D.E. Willard, Trans-dichotomous algorithms for minimum spanning trees and shortest paths, J. Comput. Syst. Sci. 48 (1994), pp. 533–551. doi:10.1016/S0022-0000 (05)80064-9. [52] B. Wang, Y. Yao, Y. Zhao, B. Hou, and S. Peng, Experimental analysis of optimistic synchronization algorithms for parallel simulation of reaction-diffusion systems,in Proceedings of the 2009 International Workshop on High Performance Computational Systems Biology, Vol. 0 of HIBI ‘09, Oct., IEEE Computer Society, Washington, DC, 2009, pp. 91–100. [53] B. Wang, B. Hou, F. Xing, and Y. Yao, Abstract next subvolume method: a logical process- based approach for spatial stochastic simulation of chemical reactions, Comput. Biol. Chem. 35 (2011), pp. 193–198. doi:10.1016/j.compbiolchem.2011.05.001. [54] R.B. Schinazi, Predator-prey and host-parasite spatial stochastic models, The Annals of Applied Probability. 7 (1997), pp. 1–9. doi:10.1214/aoap/1034625250. [55] J.O. Loffler, W. Rand, and U. Wilensky, A spatial model of the red queen effect,in GECCO ‘07: Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, London, ACM, New York, 2007, pp. 490–491. [56] D.T. Gillespie, Exact stochastic simulation of coupled chemical reactions, J. Phys. Chem. 81 (1977), pp. 2340–2361. doi:10.1021/j100540a008. [57] J. Elf and M. Ehrenberg, Spontaneous separation of bi-stable biochemical systems into spatial domains of opposite phases, IEE Proc. Syst. Biology. 1 (2004), pp. 230–236. doi:10.1049/ sb:20045021. [58] T. Parr, The Definitive ANTLR Reference: Building Domain-Specific Languages, Pragmatic Bookshelf, Dallas, TX, 2007. [59] J.S. Steinman, Breathing time warp,in PADS ‘93: Proceedings of the Seventh Workshop on Parallel and Distributed Simulation, San Diego, CA, ACM, New York, 1993, pp. 109–118. [60] J.S. Steinman, C.A. Lee, L.F. Wilson, and D.M. Nicol, Global virtual time and distributed synchronization, SIGSIM Simul. Dig. 25 (1995), pp. 139–148.
Journal
Mathematical and Computer Modelling of Dynamical Systems – Taylor & Francis
Published: Mar 4, 2015
Keywords: parallel discrete-event simulation; event graph; logical process; structural operational semantics; model transformation; 00A72; 00A71; 93C65; 65Y05; 68Q55