DEVS Simulation
 SES

 

DEVS Simulation   Discrete Event System Specification

The Abstract DEVS Simulator is a technology-agnostic description of a correct DEVS simulator or simulation engine in the same way that a calculator program is executing an algorithm that describes its operation in terms that abstract away the implementation details.

The analogy between DEVS simulation and calculation is spelled out more fully in the DEVS Calculator Analogy.


How DEVS Simulator Works

The DEVS formalism has an associated well-defined concept of simulation engine to execute models and generate their behavior. A coupled model in DEVS consists of component models and a coupling specification that tells how outputs of components are routed as inputs to other components. The simulator for a coupled model is illustrated in Figure 1. It consists of a coordinator that has access to the coupled model specification as well as simulators for each of the model components. The coordinator performs the time management and controls the message exchange among simulators in accordance with the coupled model specification. The simulators respond to commands and queries from the coordinator by referencing the specifications of their assigned models. The simulation protocol works for any model expressed in the DEVS formalism. It is an algorithm that has different realizations that allow models to be executed on a single host and on networked computers where the coordinator and component simulators are distributed among hosts. By replacing the simulators and their models at the leaves of Figure 1 by coordinators and their coupled models, we get a picture of how the DEVS protocol works for hierachical coupled models.

Among the benefits of DEVS model/simulator separation are that it enables re-implementing the underlying DEVS simulation engine so as to achieve significantly reduced execution run times [13].


Atomic Model Simulator

Object oriented implementations of Atomic models have the following methods to represent the DEVS formalism's functions:

  • delta-internal: the internal transition function
  • delta-external: the external transition function
  • delta-confluent: the confluent transition function
  • output: the output function
  • time advance: the time advance function

The atomic model simulator can be described as follows:

variables:
	parent 		-- parent coordinator
	tl 			-- time of last event
	tn 			-- time of next event
	DEVS 		-- associated model
		with total state (s, e) 			
	y 			-- output message bag 

when receive i-message  (i, t)  at time t
	tl = t - e
	tn = tl + ta(s)

when receive *-message (*, t) at time t
	if  t = tn then 
		y = *(s)   
		send y-message (y, t) to parent coordinator

when receive x-message (x, t) {
	if (x = * and  t = tn)  then 
		s = *int (s)
	else if (x != * and  t = tn)  then 
		s = *con (s)
	else if  (x != * and (tl * t * tn)) 
		e = t ??tl
		s = *ext (s, e, x)
		tl = t
		tn = tl + ta(s)
          

Algorithm 1   Simulator for Atomic DEVS


Coupled Model Simulator

Consider a DEVS hierarchical model as represented in a hierarchical tree. The role of the hierarchical tree and the couplings between pairs of models in the tree can be described as follows:

Coupled models contain other models (coupled or atomic) and this defines the natural parent-child relationship in the tree among the models. Atomic models, as their names imply, do not contain other models.

The models have inports through which input is provided.

They also have outports that hold the aggregated output of the model, which will be drained when the output function of the model is exercised.

A model is said to become imminent when a certain sleep has been completed: this results in the execution of the delta-internal function. The sleep is determined dynamically by the model through the time advance function.

An outport of a model can be connected to any subset of the inports of its siblings in the model tree, or to an outport of its parent coupled model. An inport of a model can also receive a connection from an inport of its parent.

In a particular implementation of the DEVS Abstract Simulator, the DEVS/C++ simulator maintains adjacency lists for ports and parent model pointers.

In order to propagate messages, the DEVS/C++ simulator precomputes the mail destinations for each port, dynamically and selectively updating these precomputed destination and origin sets when links, ports, or models are added to or deleted from the simulation. For example, when an outport is connected, it first calculates all the reachable inports on atomic models (the leafset) and on coupled models (the nonleafset). Likewise, when an inport is connected, similar reverse reachable sets are computed. The advantage of this obviously lies in the fact that these reachability calculations are done only when models (or ports or links) are added or deleted dynamically, and only in the part of the model tree that changed, thus adding to the efficiency of the implementation.

In the following we distinguish between leafset elements and atomic models they correspond to. The leafset elements contain various pointers and slots such as the next event time and last event time that are not kept in the models themselves (for implementation independence).

A general-purpose templated priority queue for storing leafset elements by various keys could be a name, a next event time or other convenient index such as class name. An AVL tree structure is used to order leafset elements by their next event times: if two models have the same next event times (up to a time granule equivalence), tie breaking uses the pointer value. A reverse pointer in the element points back to its location in the priority queue makes searches efficient.


Figure 1.   The DEVS Hierarchical Model Tree


The simulation cycle is as follows:

  1. Advance the clock to the earliest next event time in the priority queue.
  2. Collect all the leafset elements that are first in the priority into a set I. (representing the imminent models, i.e., those that have the smallest next event time, up to the time granule equivalence.)
  3. Execute the output functions of the models pointed to by this set, and propagate the output messages directly to the inports in the leafset of the outports that produced the output. These messages are collected into the input message bags for the models in the receptive leafset.
  4. Collect into a set M, all the leafset elements representing models that have non-empty bags waiting on their imports.
  5. For all the elements in I intersect M (the confluent set), execute the associated model's delta-confluent function, feeding it the input bag and the elapsed time computed from the clock time and the last event time.
  6. For the remaining imminents in I, execute the delta-internal function of the associated model.
  7. For the remaining models in M, execute the associated model's delta-external function, feeding it the input bag and the elapsed time computed from the clock time and the last event time.

After steps 5), 6) and 7), reinsert the leafset element into the priority queue after updating its next event time obtained from the time advance function of its associated model.

Steps 1) through 7) are repeated until no models are imminent or a termination condition, such as exceeding a time or a number of iterations, is satisfied.