Ordering of simultaneous events in distributed DEVS simulation

Simultaneous events are the events scheduled to occur at the same simulation time. This paper proposes a new event ordering mechanism for handling simultaneous events of DEVS models in distributed simulation. The DEVS formalism provides a formal framework for specifying discrete event models in a modular, hierarchical form. Thus, the formalism can ease the model verification and validation problems of distributed simulation. Also, the formalism separates models from underlying simulation algorithms. Hence, DEVS models can be simulated in both sequential and distributed environments without any modification. One important issue for such framework is to obtain the same results in both simulation environments. However, in distributed simulation of DEVS models, the processing order of simultaneous events may affect the simulation results. Thus, some ordering mechanism of events is required for well-defined simulation results. The proposed mechanism orders simultaneous events correctly with respect to their causal relationships in distributed DEVS simulation. Also, the mechanism guarantees the same ordering of simultaneous events in both sequential and distributed simulation environments.     

DEVS methodology for evaluating time-constrained message routing policies

Due to its ability to support temporal issues of systems, discrete event simulation is widely applicable to real-time system design. This paper presents a methodology for the modeling and simulation of time-constrained message routing policies for hypercube interconnected real-time systems. The methodology is based on a framework called the DEVS (discrete event systems specification) formalism which supports modular and hierarchical specification of discrete event models. Within the methodology, we first develop DEVS specification for models for hypercube computers and experimental frames to measure the performance of alternative message routing policies. We then implement such specification in DEVSIM++, a C++-based modeling/simulation environment that implements the DEVS formalism. Simulations of various message routing policies are performed, and the performances of such policies are compared.     

A Real-Time Discrete Event System Specification Formalism for Seamless Real-Time Software Development

We present a time domain extension of the hierarchical and modular discrete event specification (DEVS) formalism. This extension is important for establishing a seamless real-time software development framework. Formalisms help describe a system unambiguously. If formal models are implemented without any consistent frameworks, however, it is hard to guarantee that there is no semantic gap between models and codes. Real-Time DEVS, named RTDEVS, is an extension of DEVS that can be characterized in three perspectives: the real time execution of models, the addition of time interval functions, and the activity specification for each state. After analyzing a system, the framework based on RTDEVS helps to expand each model of the system for executing in a real-time environment. In order to support the RTDEVS formalism, we propose abstract executive concepts based on the abstract simulator concepts of the DEVS formalism. Also, we implement an RTDEVS execution engine, named DEVS Executive, which runs on real-time Mach.     

DEVS formalism: a framework for hierarchical model development

A methodology is being developed to map hierarchical, modular discrete event models onto distributed simulator architectures. Concept developed for the first step of the methodology concerning model representation are discussed. The DEVS (Discrete Event System Specification) is extended to facilitate modular, hierarchical model specification. Procedures for top-down model development are expressed with the extended formalism and illustrated with a computer system model design     

Self-reproducible DEVS formalism

System reproduction model to the growing system structure can be used to design modeling formalisms for variable system architectures having historical characteristics. We introduce a discrete event system specifications (DEVS)-based extended formalism that a system structure gradually grows through self-reproductions of system components. The proposed formalism is applied to atomic DEVS modeling and coupled DEVS modeling. As extended-atomic DEVS model, atomic self-reproduction (SR) DEVS modeling to a system component makes virtual-child atomic DEVS models. By SR DEVS modeling, a child coupled model can be also reproduced from a parent coupled model. When a system component model reproduces its system component, a child component model can receive its parent model characteristics including determined role or behavior, and include different structure model characteristics. A virtual-child model that has its parent characteristics can also reproduce next child model which may show similar attributes of the grand-parent model.     

DEVS-BASED INTELLIGENT CONTROL: SPACE-ADAPTED MIXING SYSTEM EXAMPLE

This paper reviews a methodology for event-based intelligent control employing the DEVS (discrete event system specification) formalism. In this control paradigm, the controller expects to receive confirming sensor responses to its control commands within definite time windows determined by its DEVS model of the system under control. We apply the DEVS-based intelligent control paradigm to a space-adapted mixing system. The event-based approach is compared with conventional sequential control methods.     

Distributed simulation of DEVS and Cell-DEVS models in CD++ using Web-Services

Discrete event system specification (DEVS) is a modeling and simulation formalism that has been widely used to study the dynamics of discrete event systems. Cell-DEVS is a DEVS-based formalism that defines spatial models as a cell space assembled of a group of DEVS models connected together. CD++ is a modeling and simulation toolkit capable of executing DEVS and Cell-DEVS models that has proven to be useful for executing complex models. We present the design and implementation of a distributed simulation engine, known as D-CD++, which exposes CD++ simulation utilities as machine-consumable services. In addition, we present the design and implementation of the Web-Service components which enable D-CD++ to expose the simulation functionalities to remote users. Enabling CD++ with Web-Services technology provides a solid framework for interoperating different DEVS implementations in order to achieve a standard DEVS Modeling Language and simulation protocols. This paves the road towards DEVS standardization, while providing a mashup approach, which can lead to higher degree of reuse and reduced time to set up and run experiments, and making sharing among remote users more effective. To prove this fact, we integrate it within larger services (such as a 3D visualization engine), showing the mechanism to incorporate to other environments (including geographical information systems, web-based applications and other modeling and simulation tools) through using standard Web-Service tools. Performance of D-CD++, major bottlenecks and communication overheads are analyzed.     

Discrete-event modelling of fire spreading

We deal here with the application of discrete-event System Specification (DEVS) formalism to implement a semi-physical fire spread model. Currently, models from physics finely representing forest fires are not efficient and still under development. If current softwares are devoted to the simulation of simple models of fire spread, nowadays there is no environment allowing us to model and simulate complex physical models of fire spread. Simulation models of such a type of models require being easily designed, modified and efficient in terms of execution time. DEVS formalism can be used to deal with these problems. This formalism enables the association of object-oriented hierarchical modelling with discrete-event techniques. Object-oriented hierarchical programming facilitates construction, maintenance and reusability of the simulation model. Discrete-events reduce the calculation domain to the active cells of the propagation domain (the heated ones).     

基于DEVS/CD++的抢险救灾物资保障仿真建模研究

突发自然灾害条件下的抢险救灾行动是典型的离散事件系统,在分析离散事件系统规范(DEVS)模型描述的基础上,构建了抢险救灾物资保障DEVS仿真模型,分析了仿真实体,设计了仿真流程,给出了耦合模型和主要原子模型结构。并在CD++中对该模型进行了仿真试验,得到了较为合理的仿真结果,为开展抢险救灾应急保障模拟训练奠定了基础。     

Using a Discrete-Event System Specifications (DEVS) for designing a Modelica compiler

We introduce a new architecture for the design of a tool for modeling and simulation of continuous and hybrid systems. The environment includes a compiler based on Modelica, a modular and a causal standard specification language for physical systems modeling (the tool supports models composed using certain component classes defined in the Modelica Standard Library, and the instantiation, parameterization and connection of these MSL components are described using a subset of Modelica). Models are defined in Modelica and are translated into DEVS models. DEVS theory (originally defined for modeling and simulation of discrete event systems) was extended in order to permit defining these of models. The different steps in the compiling process are show, including how to model these dynamic systems under the discrete event abstraction, including examples of model simulation with their execution results.     

REALIZATION THEORY OF DISCRETE-EVENT SYSTEMS AND ITS APPLICATION TO THE UNIQUENESS AND UNIVERSALITY OF DEVS FORMALISM

Many man-made systems have discrete event nature. Many modeling formalisms for discrete-event mechanisms have invented and been used for many problems. Among those models, the DEVS formalism is to provide natural and universal models in some sense.

This paper first provides a realization theory of general discrete-event systems. That is, a behavioral definition of discrete-event system is defined, and then a state transition function of the system is constructed. Based on the realization, the uniqueness problem of representations for discrete-event systems is positively solved. Furthermore, as an application of that solution, this paper shows both the fact that a legitimate DEVS with surjective internal transition function is unique up to isomorphism in the class of state representations of the state system defined from the DEVS, and the fact that any discrete-event system has a DEVS realization. In this sense the DEVS modeling facility has the uniqueness and universality in modeling discrete event mechanisms.     

A general framework for concurrent simulation on neural networkmodels

The analysis of complex neural network models via analytical techniques is often quite difficult due to the large numbers of components involved and the nonlinearities associated with these components. The authors present a framework for simulating neural networks as discrete event nonlinear dynamical systems. This includes neural network models whose components are described by continuous-time differential equations or by discrete-time difference equations. Specifically, the authors consider the design and construction of a concurrent object-oriented discrete event simulation environment for neural networks. The use of an object-oriented language provides the data abstraction facilities necessary to support modification and extension of the simulation system at a high level of abstraction. Furthermore, the ability to specify concurrent processing supports execution on parallel architectures. The use of this system is demonstrated by simulating a specific neural network model on a general-purpose parallel computer     

DEVSpecL: DEVS specification language for modeling,simulation and analysis of discrete event systems

Discrete EVent Systems Specification (DEVS) formalism supports specification of discrete event models in a hierarchical modular manner. This paper proposes a DEVS modeling language called DEVS Specification Language (DEVSpecL) based on which discrete event systems are modeled, simulated and analyzed within a DEVS-based framework for seamless systems design. Models specified in DEVSpecL can be translated in different forms of codes by code generators, which are executed with various tools for models verification, logical analysis, performance evaluation, and others.     

Knowledge-based environment for investigating multicomputer architectures

Multicomputers for massively parallel processing will eventually employ billions of processing elements, each of which will be capable of communicating with every other processing element. A knowledge-based modelling and simulation environment (KBMSE) for investigating such multicomputer architecture at a discrete-event system level is described. The KBMSE implements the discrete-event system specification (DEVS) formalism in an object-oriented programming system of Scheme (a dialect), which supports building models in a hierarchical, modular manner, a systems-oriented approach not possible in conventional simulation languages. The paper presents a framework for knowledge-based modelling and simulation by exemplifying modelling a hypercube multicomputer architecture in the KBMSE. The KBMSE has been tested on a variety of domains characterized by complex, hierarchical structures such as advanced multicomputer architectures, local area computer networks, intelligent multi-robot organizations, and biologically based life-support systems.     

Action-Level Real-Time Network-on-Chip Modeling

To simulate time-constrained operations and scheduling for Network-on-Chip (NoC) systems, we introduce a new set of component specifications at flit level grounded in Action-Level Real-Time DEVS formalism. These models capture the dynamics of NoC systems through action-based behavior under strict execution time intervals. These DEVS-based models are well-suited for development and simulation of asynchronous NoC architectures. This is achieved by extending the DEVS-Suite simulator to support real-time executions of ALRT-DEVS models. Representative simulation models capturing structure and behavior of prototypical Mesh NoC systems are developed. A set of experiments are designed, implemented, executed, and analyzed to show the kind of real-time simulation capabilities that can be achieved for Network-on-Chip systems.     

众核处理器和众核集群的并行模拟

模拟器是计算机体系结构研究的重要工具.近年来并行计算机体系结构的发展给计算机模拟带来了巨大的挑战.一方面,随着体系结构朝着多核以及众核处理器发展,模拟的目标系统规模随着模拟核数以摩尔定律的速度增加而不断增大;另一方面,串行模拟的速度因为模拟器运行所在宿主机主频提速减缓而停滞不前.上述两方面的原因使得传统的串行模拟方式无法满足对新兴体系结构模拟规模和速度的需求.以众核处理器和众核集群这两种体系结构为例,并行模拟技术在并行计算机体系结构模拟中是必要而且可行的.对于众核处理器的模拟,使用并行离散事件模拟对其进行加速,在模拟精度不变的前提下,提高模拟速度10.9倍.对于众核集群的模拟,模拟的目标系统总规模达到1024核,并且支持MPI/Pthreads混合编程的运行环境.     

A review of: “FRACTALS EVERYWHERE”, by Michael Barnsley,Academic Press,San Diego,California, USA 1988

The modelling and analysis of multi-component discrete event systems is a challenging research area. Over 30 years, modelling and simulation research of discrete event system specification (DEVS) has been developed with (1) dense-time, (2) the I/O concept, and (3) hierarchical model construction. Nevertheless, DEVS model verification research began relatively recently considering the whole DEVS research history. In the meantime, over 15 years, the automata theory has been developed to cover the dense-time behaviour verification of discrete event systems. Especially, timed automata (TA) has performed the key role in the field.

This paper builds on the research results that have been achieved from both theories of DEVS and TA. Thus contributions of this paper can be seen from each side. From the viewpoint of the DEVS theory, a finite and nondeterministic DEVS has been found as a verifiable class. From the viewpoint of the TA theory, a TA which is modular and hierarchical as well as verifiable, is proposed. To show the results, this paper uses the top down manner in which a general formalism is defined first and then its sub-classes are introduced.     

Retargeting sequential image-processing programs for data parallel execution

New compact, low-power implementation technologies for processors and imaging arrays can enable a new generation of portable video products. However, software compatibility with large bodies of existing applications written in C prevents more efficient, higher performance data parallel architectures from being used in these embedded products. If this software could be automatically retargeted explicitly for data parallel execution, product designers could incorporate these architectures into embedded products. The key challenge is exposing the parallelism that is inherent in these applications but that is obscured by artifacts imposed by sequential programming languages. This paper presents a recognition-based approach for automatically extracting a data parallel program model from sequential image processing code and retargeting it to data parallel execution mechanisms. The explicitly parallel model presented, called multidimensional data flow (MDDF), captures a model of how operations on data regions (e.g., rows, columns, and tiled blocks) are composed and interact. To extract an MDDF model, a partial recognition technique is used that focuses on identifying array access patterns in loops, transforming only those program elements that hinder parallelization, while leaving the core algorithmic computations intact. The paper presents results of retargeting a set of production programs to a representative data parallel processor array to demonstrate the capacity to extract parallelism using this technique. The retargeted applications yield a potential execution throughput limited only by the number of processing elements, exceeding thousands of instructions per cycle in massively parallel implementations.     

A software framework for fine grain parallelization of cellular models with OpenMP: Application to fire spread

We are dealing here with the parallelization of fire spreading simulations following detailed physical experiments. The proposal presented in this paper has been tested and evaluated in collaboration with physicists to meet their requirements in terms of both performance and precision. For this purpose, an object-oriented framework using two abstraction levels has been developed. A first level considers the simulation as a global phenomenon which evolves in space and time. A local level describes the phenomena occurring on elementary parts of the domain. In order to develop an extensible and modular architecture, the cellular automata paradigm, the DEVS discrete event system formalism and design patterns have been used. Simulation treatments are limited to a set of active elements to improve execution times. A new kind of model, called Active-DEVS is then specified. The model is computed with a fine grain parallelization very efficient for present day multi-core processors which are elementary units of modern computing clusters and computing grids. In this paper, the parallelization with Open MultiProcessing (OpenMP) standard directives on Symmetric MultiProcessing (SMP) architectures is discussed and the efficiency of the retained solution is studied.