Approach to a Simulation Virtual Machine: Object-oriented Implementation of CDEVs and PDEVs
Chapter One
Objective of the Study
Our main objective is to present a DEVS virtual machine that will take a DEVS model and map its simulation onto any hardware host like a LAN, a WAN, a Grid, a Cluster, the Internet, and so on. The virtual machine is structured in 3 layers; the modeling layer which receives the DEVS model, the simulation layer which simulates the model using either the pessimistic synchronization algorithm or the optimistic synchronization algorithm, and the last layer which is the Middleware layer that allows the mapping of the simulation onto any hardware host.
The kernel of the virtual machine will contain a CDEVS implementation of the simulator, PDEVS implementation of the simulator, and the distributed versions of them.
Chapter Two
Discrete Event System Specification (DEVS)
Discrete Event Simulation
In discrete event simulation, the operation of a system is represented as a chronological sequence of events. Each event occurs at an instant in time and marks a change of state in the system. There are three common types of world views (simulation strategies) used in discrete event simulation languages – event scheduling, activity scanning, and process interaction (the combination of the first two). From the user’s point of view, the specifics of the underlying simulation method are generally hidden.
Discrete event simulations include the following components:
- Clock: The simulation must keep track of the current simulation time, in any suitable measurement units for the system being modeled. Here because because events are instantaneous the clock skips to the next event start time as the simulation
- Event List: An event is described by the time at which it occurs and a type, indicating the code that will be used to simulate that event. Therefore the simulation maintains at least one list of simulation events, sometimes called the pending event set because it lists events that are pending as a result of previously simulated event but have yet to be simulated themselves. The pending event set is typically organized as a priority queue, sorted by event time (Douglas 1986). That is, regardless of the order in which events are added to the event set, they are removed in strictly chronological
- Random Number Generators: Depending on the system model, the simulation needs to generate random variables of various
- Statistics: Also depending on the system model there are some aspects of interest that needs to be Therefore the simulation typically keeps track of the system’sstatistics.
- Ending Condition: Theoretically a discrete-event simulation could run forever. So the simulation designer must decide when the simulation will end. Typical choices are “at time t” or “after processing n number of events” or, more generally, “when statistical measure X reaches the valuex”.
Discrete Event System Specification (DEVS)
DEVS abbreviating Discrete Event System Specification is a modular and hierarchical formalism for modeling and analyzing general systems that can be discrete event systems which might be described by state transition tables, and continuous state systems which might be described by differential equations, and hybrid continuous state and discrete event systems (Wikipedia 2007).
DEVS formalism was invented by Dr. Bernard P. Zeigler, and was introduced to the public in his first book Theory of Modeling and Simulation in 1976 when he was an associate professor at University of Michigan. DEVS can be seen as an extension of Moore machine which is a finite state automaton where the outputs are determined by the current state alone (and do not depend directly on the input). The extension was done by
- associating the lifespan with each state (Zeigler1976).
- providing a hierarchical concept with the coupling operation (Zeigler1984).
Many extended formalism from DEVS have been introduced with their own purposes, after Zeigler proposed a hierarchical simulation algorithm for DEVS model simulation in 1984. Throughput this report we will be using the term CDEVS or Classic DEVS for the Zeigler’s formalisms. And DESS short for Discrete Event System. Some of extensions include: DESS(Discrete Event System)/DEVS for combined continuous and discrete event systems, P-DEVS for parallel DESs, G- DEVS for piecewise linear state trajectory modeling of DESS, RT-DEVS for real-time DESS, Cell-DEVS for cellular DESS, Fuzzy-DEVS for fuzzy DESS, Dynamic Structuring DEVS for DESS changing their coupling structures dynamically, and so on.
We used (Zeigler, Herbert, and Tag, 2000) for most of the things followed in this chapter.
Classic DEVS (CDEVS)
DEVS defines system behaviour as well as system structure. System behaviour in DEVS formalism is described using input and output events as well as states.
In the classic DEVS formalism, Atomic DEVS captures the system behavior, while Coupled DEVS describes the structure of system.
CDEVS Atomic Model
An atomic DEVS model is defined as a 7-tuple
M = < X, Y, S, ta, δext, δint, λ >
where
X is the set of input values Y is the set output values
S is the set of states (or also called the set of partial states) ta: S → R+0,∞ is the set of positive reals with 0 and ∞.
δext : Q х X → S is the external transition function, where Q = {(s, e) | s Є S, 0 ≤ e ≤ ta(s) is the total state set
e is the time elapsed since last transition
δint : S → S is the internal transition function λ: S → Y is the output function
The interpretation of these elements is illustrated in Fig. 2.1.
Chapter Three
Modeling the Simulation System
This section presents the modeling of both CDEVS and the PDEVS simulation systems, using the Unified Modeling Language (UML). The static view is shown by a class diagram and the dynamic view by a sequence diagram. We start with the CDEVS Paradigm.
The Static View of the CDEVS Simulator:
Two figures are shown here, Fig 3.1 which shows the Class Diagram of the CDEVS Model and the Class Diagram for the Simulator is shown in Fig 3.2.
Remarks
Model:
- The Array Lists X_ and Y_ store the list of Inputs and Outputs ports structure of the model respectively. And the Abstract Simulator sim_ is the simulator that simulates the model
- The two methods add Input Port Structure and add Output Port Structure respectively add an input and output structures to the model, and there corresponding getter methods return the
- To add data on a input port and output port the methods add Input Port Data and add Output Port Data are used respectively and their corresponding getter methods are used to get the
Atomic Model:
- State_ and state Index_ keep track of the states of the atomic model. The abstract methods deltaInt, delta Ext, lamda, and ta are for the Modeler to implement in such a way that it suits his/her
Coupled Model:
- EIC_ stores the external input coupling, EOC_ stores the external output coupling, IC_ stores the internal coupling, and sub Models_ is the list of sub models in the coupled model. And their corresponding add methods add a port to the coupling list and a add model in case of subModels_.
- The getter methods take a port and return the list of ports linked (input, or output, or internal or the combination of the three) with the
- The select method is to be implemented by the
Port:
- A port can either be an input or output port, and it has a name, a value, description and a model. In addition to the setter and getter methods for the attributes listed above it also has a Boolean method “equals” that takes a port and return a Boolean
State:
- It has a list of state variables, a getter and setter methods for state variables, and an add method to add a state variable to the
State Variable:
- It has the name, value, status, and description of a state variable and their corresponding setter and getter methods.
Chapter Four
Translation to Code
Both the CDEVS and the PDEVS Simulator Algorithms are implemented in Java. The CDEVS Simulator consists of 6 packages as shown below in Fig 4.1.
Chapter Five
Case Study and Comparison
Case Study: The Microwave Oven Example
We modelled a Microwave Oven using the DEVS Formalism and simulate the model using the CDEVS Simulator and then the PDEVS Simulator.
Consider the microwave structure specified by DEVS below:
Chapter Six
Conclusion
We were able to present and provide two packages, one for the CDEVS object oriented implementation and the other for the PDEVS object oriented implantation. These can be used as our modeling level in the undergoing approach to a simulation virtual machine. We are now left with the distribution of the simulation onto any hardware host like a LAN, a Grid, a Cluster, the Internet and so on. The other thing that we will add is a user friendly method of capturing models and transforming them to either CDEVS or PDEVS modeling formalism.
After completion of the above two pot holes, we will come up with a simulation virtual machine that is can be reused for general purpose environment (as opposed to domain-specific), and at the same time exploiting the computing power of nowadays technologies by allowing distribution of the simulation to gain: execution time reduction, real-time execution, virtual environments geographically distributed, and potential for fault tolerance.
References
- Douglas, W. Jones 1986. Implementations of Time, Proceedings of the 18th Winter Simulation Conference
- Fujimoto, Richard M. 2000. Parallel and Distributed Simulation Systems, Wiley Series on Parallel and Distributed Computing.
- Paul A. Fishwick and Yi-Bing Lin 1996. Asynchronous Discrete Event Simulation, IEEE Transactions on Systems, Man and Cybernetics.
- Wikipedia 2007. http://en.wikipedia.org/wiki/DEVS .
- Zeigler, Bernard P. 1976. Theory of Modeling and Simulation (First Edition). Wiley Interscience, New York.
- Zeigler, Bernard P. 1984. Multifacetted Modeling and Discrete Event Simulation. Academic Press, London; Orlando.