Simulation

“Das ganze tschechische Volk ist eine Simulantenbande”

Jaroslav Hašek: The Good Soldier Švejk                

What is Simulation
Continuous Simulation
Discrete Simulation
Object Oriented Simulation
On Line Simulation
References


What is Simulation

At the most general level Simulation should be considered as a form of Cognition. (Cognition = action or process of acquiring knowledge.) There are three basic methods how to get an information (knowledge) of objective reality: Experiment, Analysis, Simulation. Let's take one practical example to demonstrate the nature of these three methods. The system being investigated is a gas station with one attendant. The question is "what is the average time spent by a car in the gas station". To get the answer we have three possibilities:

Experiment: take stop watches and measure the time every car spends in the station. Count the cars, at the end sum all times and divide them by the number of cars.

Analysis: use a formula of the Queueing Theory to compute the average time spent in the system directly. To use a formula you will have to assume certain queueing model which means a considerable simplification of the real system and you will need some quantitative parameters (here arrival intensity - number of cars arriving per time unit and service intensity - number of cars served per time unit).

Simulation: write a simulation model that generates randomly arrivals of cars and duration of services. It must also sequence properly all activities to have a one-to-one correspondence with the real system. Also observation, collection of statistical data, and evaluation must be programmed (for each car compute the time spent, accumulate these times, count number of cars, at the end compute and display the average).

These three methods can not be ranked because all of them have advantages and disadvantages. They can be compared only in the context of certain particular case taking into account various criteria. Nevertheless some basic facts are obvious:

Experiment is always the most accurate method, that should be used whenever it is feasible. Unfortunately very often the experiment is:
- Too dangerous (behavior of a nuclear reactor in critical situations, landing with a plane with one jet off, etc.)
- Too expensive (all cases that cause a damage, long experiments studying throughput of a data network using leased phone lines, etc.)
- Not possible at all if the system being investigated is not available (evaluation of more possible alternatives in the design stage.)

Analysis (mostly mathematical) is typically based on strong assumptions that are rarely true in practical life. Another possible drawback of analytical methods is too complicated apparatus used and/or too time consuming computation. An example of this is analysis of Queueing Networks. On the other hand using formulae gives mostly fast results and it is possible to check a large number of alternatives by simply inserting different values of parameters to the formula(e). Experimental methods are mostly much more time consuming. Another problem of analysis is availability of necessary parameters. Their exact measuring is also not necessarily feasible or it is impossible in the design stage. Using estimated data or data taken from other similar systems decreases credibility of results.

Simulation is also an experimental method. Instead of experimenting with the real system the experiments are performed with the simulation model (whose design is thus the key point of simulation studies). Also simulation has many drawbacks. Here are the most important ones:
- Too demanding creation of simulation models. Programming simulation models in general languages (like Pascal) is too difficult. There are efficient simulation languages but their mastering represents a big initial investment not always justified. There are simulation tools based typically on some graphical technique that simplify or even automate creation of simulation models of certain class of systems. If you want to learn more about one such tool, proceed to the page Petri Nets.
- Limited knowledge of the system being simulated. First of all some quantitative parameters must be known. In the above example it is necessary to generate random intervals between arrivals and random service times. Here simulation is much more flexible than analysis - simulation languages support generation of random numbers with practically any distribution. In the above example both random figures can be based on any (e.g. experimentally obtained) distributions. Nevertheless any distribution needs either several parameters (if it is a theoretical one) or directly the Distribution Function (if the distribution is obtained by measuring). There can be also things in the system (typically in the design stage) that can not be quantified and often it is necessary to accept the fact that there might be aspects we are not aware of at all.
- Too time consuming computation. An example is analysis of large scale systems with many components working in parallel. Because application of real parallelism is still not common, such systems are simulated by a program performed by a single processor. Parallel activities are then performed one at a time (even if the user has an impression of parallelism and during the design of the simulation model "thinks in parallel"). The result of this is the fact that simulation could be much slower than the real time (1 second of the model time takes 10 minutes of the CPU time). This of course disables application of simulation in real time control.

A general rule of thumb could be like that:
"If the experiment is feasible, use it. It is always the best method because all aspects are taken into account. Even if other methods were used during the design stage, experiment can serve as a final evaluation of the system. If the experiment is not feasible try to find an appropriate analytical method. If it is not available, use simulation."
Simulation is not only the last resort as it looks like in the above rule. Simulation can contribute very much to understanding of the system being analyzed not only by supplying answers to the questions that were originally given. Very often creation of the simulation model is the first occasion where certain things are taken into account. Specification of the simulated system can (and often it does) reveal errors or ambiguities in the system design. So simulation can help very much by avoiding future very expensive updating of the ready system.

Go back to Heading
Go back to Home page

Continuous Simulation

Continuous simulation languages developed in late fifties as simulators of Analogue computers. Simulation on analogue computers is based on creating an analogue electronic system whose behavior is described by the same mathematical model (set of differential equations) as the system being investigated. The electronic system is created by interconnecting standard blocks based mostly on operational amplifiers modified to act as integrators, adders, and other functional units. Then the user performs experiments with this electronic system by applying suitable inputs and recording the voltage at certain output points (oscilloscope, plotter). The changing voltage represents a time function, that is the same as the function that describes the changes in the original system whose physical nature may be totally different (mechanical displacement, temperature, etc.). The main problem of analogue computers is an analogue implementation of certain operations like multiplication, generation of some functions, generation of delays and others. Digital computers perform all these functions very easily and today continuous simulation is performed only on them. Nevertheless there is one operation where the analogue computers are better - integration. Digital computers use numerical integration that is generally slower and less accurate compared with the integration of an analogue integrator. Some special applications based on fast response use therefore the so called Hybrid computers, that contain analogue and digital parts connected by A/D and D/A converters. The digital part does everything except integration. It computes inputs of integrators, that are then converted by D/A converters to analogue signals inputted to analogue integrators. Their outputs are treated in the opposite way. The digital part also controls the interconnection of the analogue part, that might thus change during computation.

Classification of Continuous Simulation Languages

Block oriented simulation languages are based on the methodology of analogue computers. The system must be expressed as a block diagram that defines the interconnection of functional units and their quantitative parameters. "Programming" means entering the interconnection of the blocks and their description. Then the user adds statements and/or directives that control the simulation. If the system is described as a set of equations, they must be converted to a block diagram. This conversion is a simple straightforward process. The typical blocks available in most continuous block oriented languages are integrators, limiters, delays, multipliers, hysteresis, constant values, adders, holders, gain (coefficient) and other.

Expression oriented continuous languages are based on writing expressions (equations) that represent the mathematical model. So the system simulated must be expressed by a set of equations. Then the user adds statements and/or directives that control the simulation. Some languages enable both block and expression based ways of system definition. Simulation control means selection of: the integration method (because some languages offer more), the integration step, the variables (outputs of blocks) that should be observed, the intervals for collecting data for printing and/or plotting, scaling of outputs (that may be also done automatically), duration of the simulation runs, number of repetitions and the way certain values are changed in them, etc.

Download the file models1.zip that contains several continuous simulation models written in the Turbo Pascal language. Models are created using a simple continuous simulation environment based on Expression oriented approach and can be easily modified to model any other systems described by differential equations.

Go back to Heading
Go back to Home page


Discrete Simulation

Discrete simulation deals with systems whose dynamics can be considered (due to the level of abstraction) as a sequence of events at discrete time points. The key point of a discrete simulation language is the way it controls the proper sequencing of activities in the model. This is also the way a user must "view the world" when using the language and a base for classification of discrete simulation languages.

Classification of Discrete Simulation Languages

Flowchart oriented languages are represented by the language GPSS (General Purpose Simulation System), that exists in many versions on various computers. The user must view the dynamics of the system as a flow of the so called Transactions through a block diagram. Transactions are generated, follow a path through a network of blocks, and are destroyed on exit. In blocks transactions may be delayed, processed, and passed to other blocks. Blocks are in the program represented by statements that perform the Activities of the model.

Activity oriented languages are not based on explicit scheduling of future activities. For each activity the user describes the condition under which the activity can take place (that also covers scheduling if the condition is reaching certain time). The algorithm of the simulation control repeatedly increments time and tests conditions of all activities. The disadvantage of this approach is obvious - it is necessary to evaluate all conditions in every step, that may be very time consuming. On the other hand it is conceptually very simple and the algorithm can be easily implemented in general high level languages (there are simulation languages based on this approach, but not widely used). Download the file models2.zip that contains two models of a simple queuing system (in Turbo Pascal) that demonstrate the activity oriented approach. These models are accompanied by several units that implement operations on two way linked lists that are later used to implement stacks and queues.

Event oriented languages are based on direct scheduling and canceling of future events. The approach is very general. The user must view the dynamics of the system simulated as a sequence of relatively independent events. Every event may schedule and/or cancel another events. The system routine must keep record of scheduled events. That's why every event is represented by the so called Event notice, that contains the time, the event type, and other user data. Event notices are kept in the so called Calendar, where the event notices are ordered by the scheduled time. After completion of an Event routine, the system removes the event notice with the lowest time from the calendar, updates the model time by its time, and starts the corresponding routine. This is repeated until the calendar becomes empty or the program stops because of other reason. Scheduling means inserting event notices to the calendar by the scheduled time, canceling removes them. The approach based on explicit expressing of events is called Discrete Event Simulation, that is sometimes generalized to discrete simulation as such. A typical representative of this group of languages is the language SIMSCRIPT (but its version II.5 supports also process oriented simulation).

Process oriented languages are based on the fact, that events are not independent. An event is typically a consequence of other previous events. In other words it is often possible to define sequences of events that may be viewed as entities of a simulation model at higher level of hierarchy. A sequence of events is called Process. Unlike events process has a dimension in time. Process based abstract systems are very close to reality, that is always made of various objects that exist and act in parallel interfering with each other. Process way of viewing system dynamics is thus very natural. Mostly a process models an activity of a real object. It is believed, that process oriented discrete simulation is the best way how to create discrete simulation models. Typical representatives of this group of languages are MODSIM, SIMSCRIPT II.5, and the system class SIMULATION of the Simula language.

Go back to Heading
Go back to Home page

Object Oriented Simulation

Object Oriented Simulation (OOS) can be considered as a special case of Object Oriented Programming (OOP). Some principles of OOP like existence of a varying number of instances of interfering objects have been in standard use in simulation environment for a long time, often using other terminology. The Simula language (used to be called Simula 67) is the first true object oriented language. Being more than 30 years old, it still has most (and all important) mechanisms and principles of OOP. Some things like classes, inheritance, virtual methods, etc. have been defined in Simula long time before they were rediscovered by the OOP boom in last years. To learn more about Simula, visit the page of ASU (Association of Simula Users). You can also browse the document Introduction to OOP in Simula based on a talk presented at the University of Malta on the occasion of the Simula's 30th anniversary. MODSIM is another object oriented simulation language.

These are the most commonly accepted features of OOS:

1. The algorithm or system dynamics is expressed in terms of objects (actors) that exist in parallel and that interact with each other. Every object is represented by:
- parameters (that may be assigned actual values when generating objects)
- attributes (also called internal attributes or value attributes)
- methods (also called actions or procedure attributes)
- life, that represents the activity started upon object creation.
Objects can interact in these ways:
- direct access to parameters and attributes
- mutual calling of methods
- communication and synchronization of objects lives.
Simply speaking: Object = Data + Procedures that is called Encapsulation. Very often the object's data or a part of it is hidden and values can be accessed and modified only through (well defined) methods. This concept is called Information hiding.

2. Similar objects (actors) are grouped to the so called classes also called prototypes. A class describes objects that have the same parameters, attributes, methods, and lives. A class declaration is interpreted as a pattern. It is possible to create any number of individual objects (actors) called object instances. Instances may differ in values of their parameters and/or attributes. It is necessary to make a clear difference between a class as such and object instances generated using the class declaration. A class can be also interpreted as a knowledge of certain type of objects. Such knowledge is represented by a data part and by operations that can be performed on the data. This is similar to abstract data types, but classes are much richer. An abstract data type can be in this context considered as a degenerate case of a class that makes no use of inheritance.

3. Objects can be classified hierarchically by the so called inheritance. Very often the term subclass is introduced. A subclass Y of a class X inherits all parameters, attributes, and methods from the class X. Its declaration can add any number of additional parameters, attributes, and methods. A subclass may also add some activity to the life of the parent class. A subclass can be used as a parent class of other subclasses, etc. Some OOP languages (not Simula) enable the so called multiple inheritance. In this case a subclass can inherit from more than one parent classes. A subclass may be interpreted as a more detailed knowledge than the one defined by the parent class. So the parent class represents a general knowledge, that may be further specialized by declarations of subclasses in any number of steps. Inheritance acts in certain way against strong typing of languages like Pascal. Typically it is possible to declare reference variables that may refer to an instance of certain class and to instances of all its subclasses. It might be desirable, that certain methods then behave in different way according to the current object instance being referenced, that may change dynamically during program execution. This concept called polymorphism is supported by the mechanism called late binding and the methods involved are called virtual methods, that may change at every level of hierarchy.

4. Parallel existence of object instances needs facilities supporting cooperation and synchronization of their lives. Object's life does not have necessarily a time dimension, but in case of OOS it has. Simula objects as such can interact without the notion of time. The Simula system class SIMULATION defines the class "Process" whose life exists in time. There are facilities for the processes to communicate and to synchronize their lives

Go back to Heading
Go back to Home page


On Line Simulation

Internet together with Java and JavaScript offer incredible possibilities in problem solving. Instead of time consuming downloading and installation of software packages, it is possible to open directly various solvers, especially for problems that are not frequent and that do not require time consuming computation. As my first step in this direction, I wrote simple simulation models in JavaScript that solve and simulate single queue systems and queueing networks. Procede to the On-Line Solvers & Simulators page to try simulation now.

Go back to Heading
Go back to Home page


References

This page contains an extract from the text:
Sklenar, J.: Simulation (University of Malta, 2000) that is used in several Operations Research related courses taught at the Maltese University.
You can also find a lot of stuff on Internet because all search engines return many entries on "simulation". You can start with the following places, that contain other links, references, information on institutions, conferences, etc.

Go back to Heading
Go back to Home page


This article is translated to French language by Kate Bondareva.