iscar-ucm/xdevs

xDEVS: A cross-platform Discrete EVent System simulator

xDEVS

Introduction

xDEVS stands for A cross-platform (x) Discrete EVent System simulator. This library includes a set of C, C++, C#, Go, Java, Python and Rust repositories that provide an event-driven simulation interface. This interface follows the formalism Discrete Event System Specification (DEVS). The project final goal is to elaborate the fastest DEVS simulation interface with capacity to simulate models in virtual and real time, and to run simulations in sequential (single-threaded), parallel (multi-threaded) and distributed (not shared memory) architectures.

Research in the xDEVS interface can be found in xDEVS: A toolkit for interoperable modeling and simulation of formal discrete event systems. Please, cite our article in case you find xDEVS useful. This way we can gain visibility:

• Risco-Martín, JL, Mittal, S, Henares, K, Cardenas, R, Arroba, P. xDEVS: A toolkit for interoperable modeling and simulation of formal discrete event systems. Softw Pract Exper. 2022; 1- 42. doi:10.1002/spe.3168

There are seven repositories associated with xDEVS, each one offering the equivalent simulation interface for each corresponding programming language.

• xDEVS/C (xdevs.c)
• xDEVS/C++ (xdevs.cpp)
• xDEVS/C# (xdevs.cs)
• xDEVS/Go (xdevs.go)
• xDEVS/Java (xdevs.java)
• xDEVS/Python (xdevs.py)
• xDEVS/Rust (xdevs.rs)

All the repositories are included as submodules inside this main repository.

Top features

• PDEVS Modeling and Simulation formalism
• Object-Oriented Programming
• Support for sequential, parallel and distributed (this last feature only in Java and Python, for now) architectures.
• Good performance, compared to other simulation engines

Quick start

Switch to the corresponding particular language. A README file will be found to start with minimal examples and demos.

The DEVS formalism

The Discrete EVent system Specification (DEVS) formalism [1] was first introduced by Zeigler in 1976, to provide a rigorous common basis for discrete-event modeling and simulation. A “common” basis means that it is possible to express popular discrete-event formalisms such as event-scheduling, activity-scanning and process-interaction using the DEVS formalism.

The class of formalisms denoted as discrete-event is characterized by a continuous time base where only a finite number of events can occur during a finite time-span. This contrasts with Discrete Time System Specification (DTSS) formalisms where the time base is isomorphic to N, and with Differential Equation System Specification (DESS, or continuous-time) formalisms in which the state of the system may change continuously over time.

The Formalism Transformation Graph (FTG) published by H. Vangheluwe in [3] and shown in Figure 1, depicts behavior-conserving transformations between some important formalisms. The graph distinguishes between continuous-time formalisms on the left-hand side, and discrete formalisms (both discrete-time and discrete-event) on the right-hand side. Although the graph suggests that formalisms can be mapped onto a common formalism on their respective sides, very few transformations allow crossing the middle-line: this illustrates why hybrid systems (those that bring together both discrete and continuous systems) are difficult to solve.

Figure 1. Formalism transformation graph (FTG) [3].

The traditional approach to solve continuous-time problems is based on discretization, which approximates a continuous-time model by a discrete-time system (difference equations). A partitioning of the time-axis, as is the case in discretization, is however hard to harmonize with a partitioning of the state space, as is performed in discrete-event systems. In this regard, mapping continuous-time formalisms (ODEs and semi-explicit DAEs) onto the DEVS formalism (this corresponds to the arrow going from “scheduling-hybrid-DAE” to “DEVS” on the FTG) may be performed through quantization.

The closure property (under composition or coupling) of systems such as DEVS offers the possibility to describe a model as a hierarchical composition of simpler sub-components. Apart from the obvious advantages associated with modularity (conceptual level, component reusability), a significant gain in the efficiency of simulating large, complex dynamic systems can also be achieved by using multi-rate integration (employing different integration frame rates for the simulation of fast and slow sub-components), either on a single or on multiple processors (parallelization).

Although some continuous-time formalisms (e.g., causal-block diagram simulation tools) allow model hierarchization, multi-rate integration mixes poorly with traditional approaches where discretization along the time-axis forces the simulator to work explicitly with the global time base. This, in contrast to discrete-event formalisms where the simulator is concerned with local state space changes, and the time base is dealt with implicitly. Discrete event concepts are thus better suited for parallel distributed simulation, and much effort has been devoted to the development of conservative (e.g., Chandy-Misra approach), optimistic (e.g., Time-Warp) and real-time (e.g., DARPA’s Distributed Interactive Simulation) parallel discrete event simulation techniques. The relevance of DEVS in that context is illustrated by the concept of the DEVS bus which concerns the use of DEVS models as “wrappers” to enable a variety of models to inter operate in a networked simulation. The DEVS bus has been implemented on top of the DoD’s High Level Architecture (HLA) standard, itself based on the Run-Time Infrastructure (RTI) protocol.

According to DEVS theory, the system of interest is seen as a model and the corresponding simulator. The model represents a simplified version of reality and its structure. The model is built considering the conditions of experimentation of the system of interest, including the work conditions of the real system and its application domain. Thus, the model is restricted to the experimental framework under which it was developed.

This model is subsequently used to build a simulator. The simulator is able to change the state of the model by running all the necessary state transitions already defined in the model. All the transitions are executed in an appropriate order, according to the model definition.

DEVS was created for modeling and simulation of discrete-event dynamic systems. As a result, it defines a formal way to define systems whose states change either upon the reception of an input event or due to the expiration of a time delay. In order to deal with the system under study, the model can be organized hierarchically in such a way that higher-level components in a system are decomposed into simpler elements.

The formal separation between model and simulator and the hierarchical and modular nature of the DEVS formalism have enabled carrying out of formal proofs on the different entities under study. One of them is the proof of composability of the subcomponents (including legitimacy and equivalence between multicomponent models). The second is the ability to conduct proofs of correctness of the simulation algorithms, which result in simulators rigorously verified. All the proofs are based on formal transformations between each of the representations, trying to prove the equivalence between the entities under study at different levels of abstraction. For instance, we can prove that the mathematical entity simulator is able to execute correctly the behavior described by the mathematical entity model, which represents the system. Different mathematical mechanisms are used to prove these points, including the mathematical manipulation of the abstraction hierarchy, observation of I/O trajectories (to ensure that different levels of specification correctly describe the system’ structure) and decomposition concepts (DEVS is closed under composition, which means that a composite model integrated by multiple components is equivalent to an atomic component).

The reader should refer to the book Theory of Modeling and Simulation [1], to understand the details behind the mathematical background of these techniques.

The parallel DEVS formalism

The parallel DEVS approach was introduced, after 15 years, as a revision of Classic DEVS. Currently, parallel DEVS is the prevalent DEVS, implemented in many libraries. In the following, unless it is explicitly noted, the use of DEVS implies parallel DEVS.

DEVS enables the representation of a system by three sets and five functions: input set (X), output set (Y), state set (S), external transition function (δ_ext), internal transition function (δ_int), confluent function (δ_con), output function (λ), and time advance function (ta).

DEVS models are of two types: atomic and coupled. Atomic DEVS processes input events based on their model’s current state and condition, generates output events and transition to the next state. The coupled model is the aggregation/composition of two or more atomic and coupled models connected by explicit couplings. Particularly, an atomic model is defined by the following equation:

A=< X, Y, S, δ_ext, δ_int, δ_con, λ, ta >

where:

• X is the input set, usually defined as the set of pairs port-value (see DEVS with ports in [1]).
• Y is the output set, usually defined as the set of pairs port-value (see DEVS with ports in [1])..
• S is the state set.
• δ_ext : Q × X^b → S is the external transition function, Q={(s,e):s ∈ S, e ∈ [0,ta(s)]} is total state set and e is the elapsed time since the last transition, whereas X^b is the set of bags over elements in X. This function is automatically executed when an external event arrives, changing the current state if needed.
• δ_int : S → S is the internal transition function. This function is executed right after the output (λ) function and is used to change the state S.
• δ_con: Q × X^b → S is the confluent function. This transition decides the next state in cases of collision between external and internal events, i.e., an external event is received and elapsed time equals time-advance. Typically, δ_con(s,ta(s),x) = δ_ext(δ_int(s,0,x).
• λ : S → Y^b is the output function. Y^b is the set of bags over elements in Y. When the time elapsed since the last output function is equal to ta(s), then λ is automatically executed.
• ta : S → R₀⁺ ∪ ∞ is the time advance function.

The formal definition of a coupled model is described as:

M = < X, Y, C, EIC, EOC, IC >

where:

• X is the input set, usually defined as the set of pairs port-value (see DEVS with ports in [1])..
• Y is the output set, usually defined as the set of pairs port-value (see DEVS with ports in [1])..
• C is the set of DEVS component models (atomic or coupled). Note that C makes this definition recursive.
• EIC is the external input coupling relation, from external input ports of M to component input ports of C.
• EOC is the external output coupling relation, from component output ports of C to external output ports of M.
• IC is the internal coupling relation, from component output ports of c_i ∈ C to component output ports of c_j ∈ C, provided that i ≠ j.

Given the recursive definition of M, a coupled model can itself be a part of a component in a larger coupled model system giving rise to a hierarchical DEVS model construction.

EXAMPLE 1

A processor atomic model consumes a job j. When the processor receives a job through an input port, thus the processor remains busy until the processing time j_p is finished. Then it sends the job through an output port.

The processor model can be formally described as

Processor=〈X,S,Y,δ_int,δ_ext,δ_con,λ,ta〉

• X = {(in, j ∈ J)}, where J is a set of Jobs.
• S = phase={“busy”,”passive”} × σ ∈ R₀⁺ × j ∈ J
• Y = {(out, j ∈ J)}
• ta(phase,σ,j) = σ
• λ(phase,σ,j) = j
• δ_int(phase,σ,j) = (“passive”, ∞, ∅)
• δ_ext(phase,σ,j,e,(in,j’)) = {(“busy”,j_p‘,j’) if phase=”passive”, (“busy”,σ-e,j) if phase=”busy”
• δ_con(phase,σ,j,(in,j’)) = δ_ext(δ_int(phase,σ,j),0,(in,j’))

EXAMPLE 2

Figure 2 shows an example of a DEVS coupled model with three components, M1, M2 y M3, as well as their couplings. These models are interconnected through the corresponding I/O ports presented in the Figure. The models are connected to the external coupled models through the EIC and EOC connectors. M1, M2 and M3 can be atomic or coupled models.

Figure 2. A DEVS coupled model

Following the previous coupled model definition, the model in Figure 2 can be formally defined as:

N =〈 X, Y, C, EIC, EOC, IC 〉

where:

• X is the set of input events.
• Y is the set of output events.
• C = {M1,M2,M3}
• EIC = {(N,in)→(M1,in)}
• EOC = {(M3,out)→(N,out)}
• IC = {(M1,out)→(M2,in),(M2,out)→(M3,in)}

EXAMPLE 3

The Experimental frame – Processor model is usually presented as one of the initial examples to start to practice with DEVS modeling and simulation. It is a DEVS coupled model consisting of three atomic models and one coupled model (see Figure 3).

Figure 3. Experimental frame (ef)-processor (p) model; boxes: models; arrows: couplings; arrow labels: input/output port names.

The Generator atomic model generates job-messages at fixed time intervals and sends them via the “out” port. The Transducer atomic model accepts job-messages from the generator at its “arrived” port and remembers their arrival time instances. It also accepts job-messages at the “solved” port. When a message arrives at the “solved” port, the transducer matches this job with the previous job that had arrived on the “arrived” port earlier and calculates their time difference. Together, these two atomic models form an Experimental frame coupled model. The experimental frame sends the generators job messages on the “out” port and forwards the messages received on its “in” port to the transducers “solved” port. The transducer observes the response (in this case the turnaround time) of messages that are injected into an observed system. The observed system in this case is the Processor atomic model. A processor accepts jobs at its “in” port and sends them via “out” port again after some finite, but non-zero time period. If the processor is busy when a new job arrives, the processor discards it. Finally the transducer stops the generation of jobs by sending any event from its “out” port to the “stop” port at the generator, after a given simulation time interval.

Based on Figure 3, we can define the coupled model for this example as:

EFP=〈 X, Y, C, EIC, EOC, IC 〉

where:

• X = ∅.
• Y = ∅.
• C = {EF,P}
• EIC = ∅
• EOC = ∅
• IC = {(EF,out)→(P,in),(P,out)→(EF,in)}

The Experimental Frame coupled model can be defined as:

EF=〈 X, Y, C, EIC, EOC, IC 〉

where:

• X = {(in,j∈J)}, where J is a set of Jobs.
• Y = {(out,j∈J)}, where J is a set of Jobs.
• C = {G,T}
• EIC = {(EF,in)→(T,solved)}
• EOC = {(G,out)→(EF,out)}
• IC = {(G,out)→(T,arrived),(T,out)→(Generator,stop)}

We have defined the behavior of the Processor model in a previous example. Now, we describe the functionality of both the Generator and Transduced models. The Generator model can be formally described as

Generator=〈 X, S, Y, δ_int, δ_ext, δ_con, λ, ta 〉

• X = {(stop,ν)}, where ν is any event
• S = (phase={“active”,”passive”})×σ∈R0+×i=1,2,…,N:ji∈J
• Y = {(out,ji∈ J)}
• ta(phase,σ,i) = σ
• λ(phase,σ,i) = ji
• δ_int(phase,σ,i) = (“active”,σ,i+1)
• δ_ext(phase,σ,i,e,(in,ν)) = (“passive”,∞,i)
• δ_con(phase,σ,i,(in,ν)) = δ_ext(δ_int(phase,σ,i),0,(in,ν))

The Transducer model can be formally described as

Transducer=〈 X, S, Y, δ_int, δ_ext, δ_con, λ, ta 〉

• X = {(arrived,j∈J),(solved,j∈J}, where J is a set of jobs
• S = (phase = {“active”,”passive”}) × (σ ∈ R₀⁺ ) × (clock ∈ R₀⁺ × J_A∈J × J_S∈J where J_A and J_S are sets of arrived and solved jobs, respectively.
• Y = {(stop,ν)}, where ν is any event.
• ta(phase,σ,clock,J_A,J_S) = σ
• λ(phase,σ,clock,J_A,J_S) = ν
• δ_int(phase,σ,clock,J_A,J_S) = (“passive”,∞,clock+σ,J_A,J_S)
• δext(phase,σ,clock,J_A,J_S,e,(arrived,j^a),(solved,j^s))= … … = (active,σ-e,clock+e,J_A={j^a,J_A} if j^a≠∅, J_S={j^s,J_S}:j_t^s=clock if j^s≠∅) , where the time in which the job is solved is set to clock with j_t^s = clock.
• δ_con(phase,σ,clock,J_A,J_S,(arrived,j^a),(solved,j^s))=δ_ext(δ_int(phase,σ,clock,J_A,J_S),0,(arrived,j^a),(solved,j^s))

Bibliography

1. Zeigler, B. P.; Muzy, A. & Kofman, E. Theory of modeling and simulation: discrete event & iterative system computational foundations Academic press, 2018.
2. Mittal, S. & Risco-Martín, J. L. Netcentric system of systems engineering with DEVS unified process CRC Press, 2013.
3. Vangheluwe, H. DEVS as a common denominator for multi-formalism hybrid systems modelling CACSD. Conference Proceedings. IEEE International Symposium on Computer-Aided Control System Design (Cat. No.00TH8537), 2000, 129-134