The DEVS Formalism

The origins of the DEVS formalism, ascribable to Bernard Zeigler, are rooted back in the mid seventies (1976). Because of Zeigler's interest in the continuous simulation of systems with frequent discontinuities [Cellier05] one of this new formalism's main purposes were to provide a common framework for continuous as well as for discrete-event models.
The DEVS formalism was among the first discrete systems theories with a mathematical background: while before the advent of the computer, continuous systems were mostly described by differential equations, with the growing computational power of computers discrete-event simulations were made possible but usually lacked a profound mathematical theory. Only roughly since the early seventies, it was recognized that deeper, i.e. mathematical, understanding of complex systems can help their efficient simulation, and research in this area began to be carried out. The DEVS formalism was one of the resulting mathematically well-founded methodologies in the area of discrete-event systems simulation.

During the past years, several implementations of the theoretical concept defined by the DEVS formalism have emerged (see the introductory part of [Kofman03] for examples), among which also PowerDEVS [Kofman03].

The next two sections will discuss the theory of the DEVS formalism as it has been defined by Zeigler. The first section covers the topic of atomic models which actually reveals the fundamental principles of the formalism. The second section discusses an "extension" of these ideas, namely a) the possibility of linking models to each others such that they form a coupled (multi-component) system and b) the hierarchic use of a coupled model as a component of another coupled model.

Atomic Models

A DEVS model has the following structure (see also [Cellier05], Chapter 11): M=(X,Y,S, dint(s), dext(s,e,x), λ(s), ta(s)) where the variables have the following meaning:

The above figure illustrates the mechanism of a DEVS model: the system receives inputs (see the uppermost graph) at certain time instants, changes its states according to the internal and external transitions, and gives outputs (see the lowermost graph). The graph in the middle shows the state trajectory of the system. Apparently, the system starts in state s1 and changes to state s2 after the time advance ta(s1) has been elapsed. Right before executing the internal transition, it generates the output y1. When it receives the input x1, it again changes its state, this time though undergoing the external transition. Note that no output is produced. When the time advance of state s3 has been elapsed, it produces an output (y2), executes the internal transition again and thereby changes to state s4.

Coupled Models

DEVS models can describe arbitrarily complex systems. The only drawback is that the more complex the system is, the more difficult it is to set up the correct functions (dint, dext, time-advance and lambda-function) that describe the system. Fortunately, most complex systems can be broken down into simpler submodels that are easier to handle. It is therefore convenient not to have just one model that tries to simulate the whole system, but an interconnection of a number of smaller models that, together, represent the system. Even though this approach seems to be very intuitive, it is only possible because DEVS models are closed under coupling [Cellier05], which means that a coupled model can can be described by the same functions as an atomic model (internal, external, time-advance and lambda function). Due to this fact, coupled models can be seen as atomic models, too, which allows for hierarchical modelling.
The following figure illustrates these ideas: the model N consists of two coupled atomic models Ma and Mb. N can be seen as an atomic model itself and it is therefore possible to connect it to further models (coupled or atomic ones).

In such a network where submodels interact with each other through ports, so that output events of one submodel are transformed automatically into input events for other submodels, events do not only carry the output value but also a number indicating the port where the event is appearing. Hence, inputs and outputs take the following form:
X=Y= [real numbers] x [non-negative integers]
The figure above suggests this circumstance by numbering the input and output ports of the models.
Besides "normal" connections between submodels (Ma and Mb in our case), there are also connections that lead to or come in from the outside: as already mentioned, model N can be seen as an atomic model with two input and two output ports. Events coming in through port number 0 are immediately forwarded to submodel Ma, those from port number 1 to Mb. This kind of connection is called external input connection. Analogous, the connections leading from the output ports of the submodels to the output ports of the surrounding model N are called external output connections.

The behaviour of model N is determined by the behaviour of its submodels Ma and Mb. The actual task of N is to wrap Ma and Mb in order to make them look like as if they were one single model. The dynamics of N (or any multi-component/coupled model) can be defined by the following loop [Kofman03]:
  1. Evaluate the atomic model that is the next one to execute an internal transition. Let this model be called d* and let tn be the time when the transition has to take place.
    In case there are more than one candidates ready to execute their internal transitions, choose the one that is designed by the so called tie-breaking function (the tie-breaking function imposes an ordering onto the components of the model, such that in case of two components ready to execute their internal transition, the simulation knows which one to process first).
  2. Advance the simulation time (of the coupled model) to t=tn and let d* execute the internal transition. Note that tn=tcur+ta(scur).
  3. Forward the output event produced by d* to all atomic models that are connected to d* and let them execute their external transitions.
    Go to step 1.
While until now we have justified coupled models by the need of splitting up too complex models into smaller, simpler submodels, it has of course also the reverse effect of allowing the predefinition of a number of atomic models (a "model pool" of frequently used models such as switches, comparators, etc.), which then can be used to build more complex models.

Generated at 2020-10-25T03:17:45Z by OpenModelicaOpenModelica 1.17.0~dev-83-g00c75fd using GenerateDoc.mos