Instant Download

Download your project material immediately after online payment.

Project File Details


3,000.00

100% Money Back Guarantee

File Type: MS Word (DOC) & PDF
File Size:3,054 KB
Number of Pages:71

ABSTRACT

Discrete Event System Specification (DEVS) formalism is a Modeling and Simulation (M&S)
framework that provides a means of specifying systems. It separates a model from its simulator.
The former describes the structure and the behavior of a system, while the later generates the
trajectories of these descriptions. P-DEVS (Parallel DEVS) is the version of DEVS that allows one
to express at the modelling level, the parallelism present in a system. Though the algorithm is
well defined, its implementation remains challenging. This thesis presents implementations of
the Parallel DEVS simulation algorithm developed as simulation engines. This work proposes the
classification of the algorithms that exists based on implementation approach. Our goals include
the implementation of the algorithms, benchmarking and analysis. The implementations are
classified as Object Oriented based approach (OOP) that uses OOP paradigm to be realized,
process based approach that uses threads of execution for realization and hybrid simulators that
uses a mix of the paradigms to be realized.

TABLE OF CONTENTS

Abstract …………………………………………………………………………………………………………………………………….. iii
ACKNOWLEDGEMENT …………………………………………………………………………………………………………………. iv
DEDICATION ……………………………………………………………………………………………………………………………….. v
Table of Contents ……………………………………………………………………………………………………………………….. vi
List of Figures …………………………………………………………………………………………………………………………… viii
1 INTRODUCTION ……………………………………………………………………………………………………………………. 1
1.1 Context ………………………………………………………………………………………………………………………… 1
1.2 Problem Statement ……………………………………………………………………………………………………….. 2
1.3 Objectives and Motivation ……………………………………………………………………………………………… 2
1.4 Approach Adopted ………………………………………………………………………………………………………… 2
1.5 Organization of Document ……………………………………………………………………………………………… 4
2 RELATED WORK ……………………………………………………………………………………………………………………. 5
2.1 Object Oriented Approach p-devs implementations ………………………………………………………….. 5
2.2 Adaptations of M&S world views to devs …………………………………………………………………………. 7
2.3 Other related works ………………………………………………………………………………………………………. 7
3 STATE OF THE ART ………………………………………………………………………………………………………………… 9
3.1 DEVS ……………………………………………………………………………………………………………………………. 9
3.2 Parallel DEVS ………………………………………………………………………………………………………………. 14
3.3 algorithms for parallel-devs simulation ………………………………………………………………………….. 17
3.3.1 Ziegler and Chow’s P-DEVS Algorithm …………………………………………………………………….. 18
3.3.2 Analysis of Ziegler and Chow’s PDEVS Algorithm ……………………………………………………… 20
3.3.3 Chow’s PDEVS Algorithm ………………………………………………………………………………………. 21
3.3.4 Analysis of Chow’s PDEVS Algorithm ………………………………………………………………………. 24
3.3.5 Schwatinski and Pawletta PDEVS Algorithm …………………………………………………………….. 24
3.3.6 Analysis of the Schwatinski and Pawletta PDEVS Algorithm ………………………………………. 27
3.3.7 Ziegler’s original algorithm ……………………………………………………………………………………. 28
3.3.8 Analysis of Ziegler’s PDEVS Algorithm …………………………………………………………………….. 30
4 PROPOSAL …………………………………………………………………………………………………………………………. 32
4.1 SimStudio …………………………………………………………………………………………………………………… 32
4.2 Domain of algorithms ………………………………………………………………………………………………….. 33
4.3 Specification of pdevs algorithms implemented ……………………………………………………………… 34
4.3.1 Message Passing ………………………………………………………………………………………………….. 35
vii
4.3.2 OOP based Approach Specification ………………………………………………………………………… 36
4.3.3 Process Based Approach Specification ……………………………………………………………………. 40
5 APPLICATION / CASE STUDY …………………………………………………………………………………………………. 43
5.1 Case study of crossroad in a road network ……………………………………………………………………… 43
5.2 devs specification of the road network ………………………………………………………………………….. 43
6 BENCHMARKING AND ANALYSIS…………………………………………………………………………………………… 51
6.1 Experimental Setup ……………………………………………………………………………………………………… 51
7 CONCLUSION ……………………………………………………………………………………………………………………… 53
7.1 Perspective …………………………………………………………………………………………………………………. 53
7.2 Contributions and limitations ……………………………………………………………………………………….. 53
7.3 Future works ………………………………………………………………………………………………………………. 54
8 REFERENCES ………………………………………………………………………………………………………………………. 55
APPENDIX …………………………………………………………………………………………………………………………………. 57

CHAPTER ONE

1 INTRODUCTION
Complex Information Technology (IT) based business, engineering, and military systems are at
the root of this century’s global challenges of economy, climate and energy. We are used to
building such systems directly in the real world and letting use and Mother Nature tell us how
good they are. However, it is getting increasingly dangerous, costly, risky, or even unethical to do
so. Building a model of the system and testing within a virtual space is more and more the only
workable alternative where by “virtual” we include a wide range of representations of the
eventual fielded reality including models wholly within a single computer, network distributed
emulations, physically analogous and immersive environments. Modeling and Simulation (M&S)
supply the basis for such environments. Computer based modeling refers to the construction of
such environments while computer simulation connotes the experimentation using them to
study alternative designs and architectures.
Introduced in the last century as a rigorous systems-theory basis for discrete event modeling and
simulation, the DEVS (Discrete Event System Specification) formalism[1][2] has become an
engine for advances in M&S technology and the support of “build and test in virtual reality”.
1.1 CONTEXT
Discrete Event System Specification (DEVS) presents a modular hierarchical realization of
Modeling and Simulation (M&S) of discrete events, which has found importance in fields ranging
from science of weather forecast to economics of population and its effects. DEVS is also a
unifying model that can be used to specify all systems since its semantics allow for reactive and
autonomous systems at the same time. Moreover, most systems exhibit inherent parallelism[3]
as pertains to the system itself in terms of more than one event can occur together at a single
time, and the DEVS formalism that deals with this situation is the Parallel-DEVS (P-DEVS)[4]. It is
2
an extension to the DEVS, and provides a way to deal with simultaneously scheduled events. It
supports parallel execution of internal and external events that occur at the same simulation
time. It eliminates the serialization constraints existing in the original DEVS definition and enables
more efficient execution of models in parallel and distributed environments.
1.2 PROBLEM STATEMENT
The algorithms for proper Simulation of P-DEVS models exists and is well defined. However,
proper analysis of the different algorithms in terms of implementation approach and possible
suitability to specific types of systems have not been fully investigated. Implementation could yet
also prove to be challenging due to subtleties of the technologies used.
1.3 OBJECTIVES AND MOTIVATION
The main objective of the study is to illustrate the global view for implementation of P-DEVS and
progressively experiment on the different implementations for proper analysis. This will be
achieved by creating prototypes of the different implementations and using test cases to analyze
them.
The motivation for our study is the need to analyze holistically, the different algorithms based on
different approaches to implementation since most researchers just implement one algorithm
with a single or few related approaches.
1.4 APPROACH ADOPTED
In recent times, several formalisms are in existence and are being used to model and simulate
different types of systems. In this work, we focus on the DEVS formalism, which has been proven
to be a universal formalism to represent Discrete Event Systems. DEVS is a sound formal
The outcomes of this work are:
 A package containing different implementations of P-DEVS (object-oriented, processoriented
and hybrid).
 Toy case used for benchmarking and the results.
3
framework based on generic dynamic systems concepts that supports provably correct, efficient,
event-based simulation. The framework enables the construction of models in a hierarchical,
modular fashion, allowing component reuse and reducing development and testing time. P-DEVS
is an extension to DEVS that provides a better way to handle simultaneously scheduled events,
while keeping all the major properties of the original formalism.
We present theoretical analysis of the different P-DEVS algorithms using a unified example of
DEVS components and UML sequence diagram to illustrate the flow of activities. The example
proposes the use of a highly interconnected model as illustrated below.
𝑀1 𝑀2
𝑀3 𝑀4
𝑀1 𝑀2
𝑀3 𝑀4
𝑀1 𝑀2
𝑀3 𝑀4
𝑀1 𝑀2
𝑀3 𝑀4
𝑀0 𝑀0
𝑀0 𝑀0
Figure 1: All Figure 2: All connections of Model 0 at time t connections of Model 1 at time t
Figure 3: All connections of Model 2 at time t Figure 4: All connections of Model 3 at time t
4
Each of the individual component model of the composite model except from Model 0 has output
linking all others except itself while Model 0 has External Input Coupling with all other individual
models. The theoretical simulation of this composite model will be analyzed using sequence
diagram of the UML (Unified Modeling Language) to illustrate its behavior whenever events occur.
We will then perform experimental analysis on the algorithms by implementing them using
different software engineering approaches on the JAVA programming language and using toy
cases to benchmark performance index.
1.5 ORGANIZATION OF DOCUMENT
The plan of this dissertation is as follows: Chapter 2 presents a survey of P-DEVS based M&S tools
related to our work presented in subsequent chapters. In chapter 3, we review the Classic DEVS
(C-DEVS) and P-DEVS formalisms, as well as behavior of selected P-DEVS simulator algorithms
that exist in literature. Chapter 4 introduces the methodology of how the abstract simulators
implemented was carried out. Chapter 5 presents a case study illustrating complex model
specification and realization using our simulator. While Chapter 6 expatiates on the toy cases
used and the performance benchmark results of the implementations. Then in Chapter 7, we
conclude the work done with a summary of contributions, limitations and a discussion of future
work and perspectives.
𝑀0
𝑀1 𝑀2
𝑀3 𝑀4
𝑀0
Figure 5: All connections of Model 4 at time t

GET THE FULL WORK

DISCLAIMER: All project works, files and documents posted on this website, projects.ng are the property/copyright of their respective owners. They are for research reference/guidance purposes only and the works are crowd-sourced. Please don’t submit someone’s work as your own to avoid plagiarism and its consequences. Most of the project works are provided by the schools' libraries to help in guiding students on their research. Use it as a guidance purpose only and not copy the work word for word (verbatim). If you see your work posted here, and you want it to be removed/credited, please call us on +2348157165603 or send us a mail together with the web address link to the work, to hello@projects.ng. We will reply to and honor every request. Please notice it may take up to 24 or 48 hours to process your request.