Thorsten Pawletta, Hochschule Wismar - University of Technology, Business &
Design
Thesis
Subject:
|
Parallelisation of Transaction-Oriented Simulation using Message Passing in SCEs
|
Problem:
Computer Simulation is an important application area
for computer systems. It can give answers about the dynamic behaviour
of real or virtual systems. But the growing complexity of computer
simulations that are performed these days can lead to very long
execution times. Performing these computer simulations distributed in a
network cluster of commodity computers. Message Passing Systems like
PVM are widely used for the development of distributed applications in
such network clusters.
SCEs (scientific and technical computing environments) like Matlab
are very useful for fast prototyping. The concepts of distributed
computer simulation can be implemented in Matlab using an existing
Message Passing toolbox. This allows experiments and optimisations to
be performed in a fast and cost effective way.
The project looks at relevant aspects of parallel programming and
describes possible options for the parallelisation of computer
simulations. The findings are applied to transaction-oriented
simulation and a selected solution is demonstrated by implementing a
prototype distributed simulation system using Matlab.
Possible options for the parallelisation of computer simulations
|
|
Parallelisation at experiment level: Several independent simulation runs will be performed on different processors or computers. |
|
|
Parallelisation of utility functionality:
Utility functions of the simulator (e.g. random number generation) will
be performed parallel to the simulation run on other processors or
computers. |
|
|
Parallelisation at simulation model level:
This approach allows to speedup even single simulation runs. The
simulation model is partitioned and the resulting model partitions are
performed in parallel by separate logical processes (LPs). The speedup
of the simulation will depend on how well the simulation model can be
partitioned, the synchronisation method used and the mapping. |
Synchronisation methods
There are three classes of synchronisation methods which are
conservative, optimistic and hybrid methods. Conservative methods will
only perform guaranteed events and therefore guarantee that the events
are executed in the correct order. Optimistic methods allow the
violation of the causal order at first but they provide mechanisms to
roll back and re-execute events to correct the causal order if
required. And hybrid methods try to combine the advantages of conservative and optimistic methods.
Synchronisation method requirements
The synchronisation method used will have to meet the following requirements:
- Applicable to transaction-oriented simulation
-
Relatively low communication overhead
- Relatively simple communication algorithm
Solution
Parallelisation at experiment level has been covered
extensively by past research and cannot be used to speedup single
simulation runs. Regards the parallelisation of utility functions a
significant speedup cannot be expected considering today's simulation
algorithms and the proposed target system of network clusters. For
these reasons the work concentrated on the parallelisation at
simulation model level as a promising approach.
The SPEEDES algorithm was chosen as the synchronisation method
because it is a hybrid method that combines advantages of conservative
and optimistic synchronisation methods and it uses a relatively simple
communication algorithm with a low overhead.
The SPEEDES algorithm
Similar to optimistic synchronisation methods the SPEEDES algorithm
will execute all events in its local event lists in chronological order
as soon as possible but only guaranteed events are sent between the
LPs. Events that need to be sent to other LPs are first stored in a
local lists of outgoing events and after a GVT approximation has been
received from the simulation control instance all outgoing events that
are guaranteed by this GVT are sent to their destination LPs. In order
to calculate the GVT an LP sends a special message to the simulation
control instance as soon as its local simulation time reaches the
minimum event time from its outgoing event list. As soon as the
simulation control instance received this message from all LPs it will
calculate the GVT and send it back to every LP. When an LP receives new
events from another LP then the received events are added to its local
event list and the LP performs a rollback of already executed events if
required.
Implementation
The following points had to be considered regards the implementation of a
distributed simulation system based on the SPEEDES algorithm:
- Analysis of the GPSS language
- Adaptation of the SPEEDES algorithm to transaction-oriented simulation
- Specification of the model partitioning in the model description
-
Generating and terminating of transactions in a distributed simulation system
-
Exchange of transactions between LPs
-
Implementation and optimization of the state management
The investigations into the adaptation of the SPEEDES algorithm to
transaction-oriented simulation showed that it is necessary to include
the priorities of the transactions into the GVT calculation. The
adapted SPEEDES algorithm therefore uses an information set containing
the time and priority information in order to calculate the GVT. This
GVT calculation will first select the messages containing the minimum
event time and from these the one with the highest priority. The
example shown in the graph below demonstrates the GMT calculation using
time and priority information:
The SPEEDES algorithm needs a central process for the GVT
calculation. Therefore the distributed simulation system was
implemented using the master-slave architecture. A central master
process performs the GVT calculation and also starts, controls and
terminates the LPs which act as slave instances. The graph below shows
this architecture and the communication sequence between the central
master process and the LP instances.
Conclusion
The project investigates options for the
parallelisation of transaction-oriented simulation using message
passing in a scientific and technical computing environment (SCE). A
possible solution is demonstrated by a prototype distributed simulation
system. This implementation uses the SPEEDES algorithm which first had
to be adapted to the transaction-oriented simulation paradigm.
Resulting from the implementation and the validation using example
models the conclusion is drawn that the SPEEDES algorithm is
suitable for the implementation of transaction-oriented simulation in a
distributed environment but that the full potential of parallel
transaction-oriented simulation cannot be achieved using the SPEEDES
algorithm because the simulation time does not change while a
transaction is moved through the system which often results in only a
single transaction being exchanged after each GVT calculation.
Complete thesis
The complete thesis (with the exception of some parts of the appendix) can be downloaded here.
Download of the complete thesis in German (PDF, 536 KB)
Further research
Further research related to this subject can be found at the link below:
M.Sc. thesis - Transaction-Oriented Simulation In Ad Hoc Grids
or alternatively in arXiv.org, paper ID 0704.1827