3 Formalism: 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

M = <X,S,Y,d_int,d_ext,d_con,l,ta>

Where

X : set of external input events;

S : a set of sequential states;

Y : a set of outputs;

d_int: S -> S : internal transition function

d_ext : Q x X^b -> S : external transition function

_ext

_con

l : S -> Y^b : output function generating external events at the output;

ta : S -> Real : time advance function;

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 d_ext 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 (d_int) changes internal variables from previous state to the next. The d_con function decides what to do when both external and internal events occure together. It might, for example, decide the order between d_ext and d_int 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. DN = <D, {M_i}, {I_i}, {Z_i,j}>

Where

for each i in D,

M_i is a component model

I_i is the set of influencees for i

for each j in I_i,

Z_i,jis 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