Strategies to Implement Parallel Discrete Event System Specification Algorithms

Strategies to Implement Parallel Discrete Event System Specification Algorithms.

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.

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
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

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”.

References

P. Zeigler, H. Praehofer, and T. G. Kim, Theory of modeling and simulation: integrating discrete event and continuous complex dynamic systems. Academic press, 2000.
P. Zeigler, Theory of Modeling and Simulation, Wiley, N.Y., First Edition. 1976.
C. Cave and R. E. Wassmer, “UNDERSTANDING INHERENT PARALLELISM.” 2008.
C. H. Chow and B. P. Zeigler, “Parallel DEVS: A parallel, hierarchical, modular, modeling formalism,” in Proceedings of the 26th conference on Winter simulation, 1994, pp. 716–722.
Wainer, “CD++: a toolkit to develop DEVS models,” Softw. Pract. Exp., vol. 32, no. 13, pp. 1261–1306, 2002.
Bonaventura, G. A. Wainer, and R. Castro, “Advanced IDE for modeling and simulation of discrete event systems,” in Proceedings of the 2010 Spring Simulation Multiconference, 2010, p. 125.

Comments are closed.

Hey Hi

Don't miss this opportunity

Enter Your Details