Cell Based Discrete-Event Simulation - Information : Introduction

[ Back to homepage | Back to Information ]

Discrete-Events Simulation (Basic Facts)
Summary of the Project
References

In the '70s, Bernard Zeigler defines a theory for discrete-events systems specification. It is a formal approach to build the models, using a hierarchical and modular approach (lately integrated with object-oriented programming techniques). The paradigm allows the developer to build a Model Base, permitting easy reuse of models that has been validated. In this way, the security of the simulations can be improved, reducing the testing and maintenance times, and improving the productivity of the development process. The discrete-events nature of the formalism also allows to reduce the execution times of complex simulations.

Cellular Automata are also widely used to model other kind of complex systems. A CA is basically an infinite field of cells executing the same instructions syncrhonously and simultaneously.

The proposal of the Cell-DEVS paradigm considers each cell of a CA as a discrete events model, hierarchical and modular. In this way, complex models can be defined, using a continuous time base. It also allows to associate several kinds of delays for each cell, allowing the definition of complex models easily.

Finally, complex systems simulation usually requires significate amounts of compute time. Therefore, the use of sequential models makes difficult the obtention of significate results through simulations. To improve the performance, several approaches for parallel and distributed simulation have been proposed. At present there are two techniques widely known for distributed coordination. The pessimist approaches tries to know the distribution order of the messages, processing them such as to avoid causality errors. Other mechanisms, called optimist, allows a higher degree of parallelism by ignoring the possible causality errors, presuming that the messages will arrive in the correct temporal order. When a causality error occurs, the protocol rolls the simulation back to the state previous to the time of the recently arrived message.

One goal of this project was related with the definition of the Cell-DEVS Models. Several formal descriptions were presented, allowing the modeling and simulation of cell spaces. The formalisms allow the definition of binary, three-state and generic cell spaces. The concepts of delays employed belong to the domain of the digital circuit simulation, and have been adapted to the cellular automata, as one of the main contribution to the new formalism.

An environment for modeling and simulation of the cell spaces was defined, allowing to verify empirically the efficiency of the proposed solutions.

A flatten simulation mechanism was also defined, so as to improve the execution times of the cell spaces (that improved in up to one order of magnitude).

The tools allow to build automatically a cellular model from its specification, simplifying the verification problems of the model, allowing rapid development of the simulators, mainly due to the improvements obtained in the phases of testing and maintenance.

Summary of the project

[ Back to top ]

In recent years, a wide number of artificial systems has become commonplace (i.e., computer networks, traffic controllers, flexible manufacturing plants, embedded applications, etc.). The development cost of such systems is crucial for their successful implementation, and their complex analysis has been attacked using simulated models. It is well known that the use of a formal modeling approach can produce important cost reductions. Fortunately, several modeling paradigms have been developed.

As the specified models are analyzed through simulation, their timing information becomes crucial. Hence, it is needed a paradigm allowing timed models, representing the event dates in the system. The DEVS formalism (Discrete EVents systems Specification) proposed by Bernard Zeigler [Zei76,Zei84], allows this kind of specifications. Here, the model's timing is described as a lifetime for each state variable.

DEVS is a discrete events paradigm that allows a hierarchical and modular description of the models. Each DEVS model can be behavioral (atomic) or structural (coupled), consisting of inputs, outputs, state variables, and functions to compute the next states and outputs. The paradigm improves the security of the simulations, reducing the testing time and increasing productivity.

We've been interested in modeling systems that can be represented as executable cell spaces. The Cellular Automata formalism [Wol86] has been widely used to describe complex systems with these characteristics. These automata evolve by executing a global transition function that updates the state of every cell in the space. The behavior of this function depends on the results of a function that executes locally in each cell.

Conceptually, these local functions are computed synchronously and in parallel, using the state values of the present cell and its neighbors. This discrete time paradigm constrains the precision and efficiency of the simulated models. Furthermore, it is usual that several cells do not need to be updated in every step, wasting computation time. These problems can be solved using a continuous time base, providing instantaneous events that can occur asynchronously at unpredictable times.

These ideas served as a basis for an approach called Timed Cell-DEVS [Wai98]. A main contribution of the work consists in adapting delay constructions and associated them with functional components. The extensions allow to define explicit timing for each cell, providing a simple mechanism to define it. The specifications of the formalism were used to build a set of tools for modeling and simulation of cell spaces. As a result, the approach allows a modeler to describe complex temporal behavior avoiding the detailed mechanism used for the delays.

Cell-DEVS models were described formally, considering specifications for one cell and for general Cell-DEVS coupled models. The methods presented allow automatic definition of cell spaces using the DEVS formalism. Integration of multiple views for each submodel is possible, letting to combine different models in an efficient fashion. The use of a formal approach allowed to prove properties regarding the cellular models. It also provided a sound basis to build simulation tools related with the formal specifications.

The paradigm was implemented in several versions of a tool, allowing efficient and cost-effective development of simulators. Two descriptions for the simulation mechanisms were included. The first one considered a hierarchical simulation mechanism. Subsequently, a method to flatten the hierarchical description of the cell spaces was given. As shown by the experimental application results, the formalism showed ten-fold improvements for expert developers.

At present our goals are devoted to extend these efforts in other areas mentioned following:

Parallel Cell-DEVS

If we call e to the elapsed time since the occurrence of an event, a model can exist in the DEVS structure at either e=0 or e=D(s). A modeler can use the select function to solve the conflicts of simultaneous scheduled events in coupled models. In these cases, ambiguity arises when a model scheduled for an internal transition receives an event. These problems were solved defining the Parallel DEVS. Cell-DEVS models could be coupled with these traditional DEVS submodels. Also, it was proved that a bag is needed for the Cell-DEVS with zero-time transitions. Considering these factors, the Cell-DEVS models were redefined to include parallel behavior.

A general environment for parallel simulations was built, considering the use of optimist/pessimist synchronization approaches. A mapping between the Cell-DEVS simulators and these algorithms were defined, and at present, they are being used to build a parallel extension of the tools. After, an extension to the HLA standard will be faced. This approach will enhance the production of results. By introducing a parallel coordinator, execution speedups of several orders of magnitude can be achieved without touching the specifications. Furthermore, a parallel implementation of each problem hand-coded could produce ten-fold delays in the development.

The approach here presented also permits including a parallel coordinator, achieving execution speedups of several orders of magnitude without changes in the specifications. Therefore, this approach can provide important reduction in the implementation of parallel applications for cellular models.

Modeling specification languages

At present, several modifications were done to the specification language used to define the cell's behavior. The first one is related with the topology of the cellular models. At present, the defined models include rectangular meshes. Nevertheless, several existing cellular models have triangular or hexagonal patterns. Therefore, the tool is being extended to run these approaches. In a first stage, a translator is being used to define rectangular rules derived from the triangular and hexagonal ones. Then, the extended topologies will be included in the tool.

A set of new delay constructions has been defined. These ones allow to define complex timing behavior for inertial delays, improving the definition of timing behavior for cellular models. These constructions are being combined with the new definitions of parallel Cell-DEVS. The new local confluent functions should be included in the specification language, allowing the modeler to define the cell's behavior under simultaneous events. The simulation mechanisms are being extended to include a theory of quantized DEVS models.

The specification of cellular models can be impoved using a specialized graphical interface. The models will be defined using a graphical extension of the specification language, and a graphical output will be defined. These tools will be integrated in a web-based simulation framework, providing a Cell-DEVS simulation server.

Also, a high level specification language is being defined with the goal to introduce DEVS traditional models in the modeling tool. In this way, standard DEVS models could be updated in a simple fashion, providing the basis for a model's Data Base.

Finally, we have started facing the analysis of an enterprise modeling language (CIMOSA) and the present efforts in providing a standard in this field (UEML). CIMOSA constructions does not have a well defined semantics. The goal is to use the DEVS formalism to provide this semantics. Therefore, CIMOSA constructions can be directly translated into parallel DEVS frameworks, allowing the definition of complex enterprise models that can be formally validated and can execute efficiently using a parallel environment.

Applications

Several applications are being considered to apply Cell-DEVS models. A first group of models are related with the definition of physical problems. The first ones include surface tension analysis, lattice gases and studies of ecological systems. A second group of applications include the analysis of crystal growth. In the latter case, different isotropies will be studied, including triangular, rectangular and hexagonal meshes.

Several multimodel applications are being faced. First, a detailed study of development times is being extended to consider the integration of mixed DEVS and Cell-DEVS models. The goal is to characterize the development activities and the cost reductions in more complex applications. Also, multidimensional models are being studied. They are being used to represent different aspects of the same three-dimensional system as a cubic zone of a higher dimensional space.

A final group of applications include a specification language used to define traffic simulations as cell spaces. The streets can be defined, analyzing the traffic direction, number of tracks, etc. Once the urban section is defined, the traffic flow is automatically set up. Therefore, a modeler can concentrate in the problem to solve, instead of being in charge of defining a complex simulation system.

A city section is specified by a set of streets connecting two crossings. The vehicles advance in a right line (surpassing slower vehicles), up to their arrival to a crossing. The speed of each vehicle is represented through a random transport delay. Each street is represented as a sequence of segments. These represent a section of one block of length, where every track has the same traffic direction (one way). Consequently, to build a two-way street is necessary to define one segment for each direction. Several models were defined, depending on the number of lanes, their direction, and maximum speeds in the streets.

Once defined the basic behavior for a city section, different components can be defined. These are also part of the specification language, and include definitions for traffic lights, railways, men at work, street holes, transit signals, parked cars, and so on. Finally, special behavior has been defined for special vehicles: trucks, vans and high priority cars (ambulances, policemen, firefighters).

References

[ Back to top ]

[BBW98] BARYLKO, A.; BEYOGLONIAN, J.; WAINER, G. "GAD: a General Application tool for DEVS modelling and Simulation". Proceedings of 1998 IASTED International Conference on Applied Modelling and Simulation. Hawaii, U.S.A. 1998.

[Cam95] CAMERON, G.; WYLIE, B.; MC. ARTHUR, D. "PARAMICS: Moving Vehicles on the Connection Machine". Proceedings of IEEE Supercomputing '95. 1995.

[Cha79] CHANDY, K; MISRA, J. "Distributed simulation: a case study in design and verification of distributed programs", IEEE TOSE, September 1979.

[Cho94] CHOW, A.; ZEIGLER, B. "Revised DEVS: a parallel, hierarchical, modular modeling formalism". Proc. Winter Simulation Conf., 1994.

[Ebl89] EBLING, M. et al. "An ant foraging model implemente on the time warp operating system". Distributed Simulation 1989. pp. 21.

[Eck95] ECKART, J.D. "A Cellular automata simulation system". Technical Report Radford University. 1995.

[Fer95] FERSCHA, A.; TRIPATHI, S. "Parallel and distributed simulation of discrete event systems". Technical Report CS-TR-3336, Dept. of Computer Science, University of Maryland, College Park, MD. En Proceedings of the 9th. Workshop on Parallel and Distributed Systems. 1995.

[Fuj90] FUJIMOTO, R. "Parallel Simulation of Discrete Events". Communications of the ACM Vol. 33. No. 10. pp. 30-53. 1990.

[Gar86] GARZIA, R.F.; GARZIA, M.R.; ZEIGLER, B.P. "Discrete Event Simulation", IEEE Spectrum, December 1986. pp. 32-36.

[Gho96] GHOSH, S.; GIAMBIASI, N. "On the need for consistency between the VHDL language constructions and the underlying hardware design". Proceedings of the SCS multiconference on Simulation in Industry. Genoa, Italia. 1996. pp. 562-567.