Reference Guide 3: Formal System Description
The structure of a model(system) may be expressed in a mathematical language called a formalism. The discrete event formalism focuses on the changes of variable values and generates time segments that are piecewise constant. In essence the formalism defines how to generate new values for variables and the times the new values should take effect. An important aspect of the formalism is that the time intervals between event occurrences are variable. DEVS-C++ has been developed based on DEVS formalism. Models, the basic constructs needed for modeling and simulation, can be specialized into two major classes, an atomic model and a coupled model. The atomic model realizes the atomic level of the model formalism, while the coupled model embodies the hierarchical model composition constructs [1].
3.1 Parallel DEVS Formalism for Basic Models
Where
X : set of external input events;
S : a set of sequential states;
Y : a set of outputs;
dint : S -> S : internal transition function
dext : Q x Xb -> S : external transition function
Xb is a set of bags over elements in X,
(where dext(s,e,f) = (s,e));
dcon : S x Xb-> S : confluent transition function;
l : S -> Yb : output function generating external events at the output;
ta : S -> Real : time advance function;
Where Q = { (s,e) | s is an element of S, 0 <= e <= ta(s) }
e is the elapsed time since last state transition.
Figure 3 Systematic representation of a basic(atomic) model.
Figure 3 shows systematic representation of basic models. As an example, when an input packet arrives at the queueing system, the instance variable S which is the length of the queue should be incremented by 1. The function which carries the input and then changes the instance variable is the dext function. After an elapsed time given by the ta function, the system checks the queue, it removes some packets causing the length of the queue to decrease by the amount of the removed packets. In other words, the instance variable, the length of the queue, changes internally from the previous state to the next state which is less by the number of the removed packets than the previous one. Likewise, the internal function (dint) changes internal variables from previous state to the next. The dcon function decides what to do when both external and internal events occure together. It might, for example, decide the order between dext and dint functions. The l function produces output Y from the instance variables. ta returns the time to the next internal event.
Consider a rather simplistic model of a processor as a basic model in Figure 4. The basic model has instance variables: sigma, phase, processing_time, and job_id. If the processor is idle(“passive” phase) and a job arrives on the input port “in”, it stores the job_id, changes the phase to “busy”, and sigma(time left state variable) to processing_time. Such handling of incoming jobs is represented in the external transition function. When a job arrives while the processor is busy, “continue()” method updates sigma to reflect the passage of elapsed time, but leaves the next of the state unchanged. When the processor has finished processing, it places the job identity on port “out” and returns to the “passive” phase. This is done in the internal transition function. Sending of the job is done by the output function which is called just before the internal state transition function. Appendix A shows an example execution of single cycle of this model.
Figure 4 Modeling and trajectory for simple processor
3.2 DEVS Formalism for Coupled (Multi-component) Models
Two major activities involved in coupled models are specifying its component models, and defining the coupling which creates the desired communication links.
Where
D is a set of components names;
for each i in D,
Mi is a component model
Ii is the set of influencees for i
for each j in Ii,
Zi,j is the i-to-j output translation function
A coupled model contains the following information
-
- the set of components
- for each component, its influencees
- the set of input ports through which external events are received
- the set of output ports through which external events are sent
- the coupling specification consisting of
-
-
- the external input coupling connects the input ports of the coupled to one or more of the input ports of the components
- the external output coupling connects the output ports of the components to one or more of the output ports of the coupled model
- internal coupling connects output ports of components to input ports of other components
-
Figure 5 depicts coupled models in terms of a hierarchical tree, the coupling relation, and the structure of coupled model. In Figure 5-a, coupled model ABC has, as its compoments, an atomic model A and a coupled model BC. In turn, BC’s components are two atomic models, B and C. The Coupling relation, data path between models shown in Figure 5-b, is depicted by a line. Figure 5-c shows that Components is a container which holds items that can be atomic or coupled models. Pairs in the Coupling relation hold coupling information with port-to-port connections.
Figure 5 Various representation of coupled models
Figure 6 describes the GPT(generator/processor/transducer) architecture. Coupled model GPT has 3 components(D) which are G, T, and P. Note how the external input coupling connects the “start” port of GPT model to the “start” port of the enclosed G model. The external output coupling similarly connects the “out” port of T(transducer) to the “out” port of GPT. The output port of G(generator) is connected to the “in” port of P(processor) and to the “ariv” port of the T atomic model; the “out” port of P is connected to the “solved” port of T.
Once an external input signal “start” is injected, G generates its output periodically. The output of G goes to the input ports of P and T. The output of P goes to “solved” port of T. T gathers all information from G and P, and produces statistical information such as throughput and average processing time of P. Appendix B shows the source code of this GPT example model.
Figure 6 An example of coupled models: GPT model