[ Back to homepage  Back to Information ] 
Introduction 
[ Back to top ] 
DiscreteEvents Simulation 
[ Back to top ] 
In the '70s, Bernard Zeigler defines a theory for discreteevents systems specification. It is a formal approach to build the models, using a hierarchical and modular approach (lately integrated with objectoriented 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 discreteevents 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 CellDEVS 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 CellDEVS Models. Several formal descriptions were presented, allowing the modeling and simulation of cell spaces. The formalisms allow the definition of binary, threestate 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 CellDEVS [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.
CellDEVS models were described formally, considering specifications for one cell and for general CellDEVS 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 costeffective 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 tenfold improvements for expert developers.
At present our goals are devoted to extend these efforts in other areas mentioned following:
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. CellDEVS models could be coupled with these traditional DEVS submodels. Also, it was proved that a bag is needed for the CellDEVS with zerotime transitions. Considering these factors, the CellDEVS 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 CellDEVS 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 handcoded could produce tenfold 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.
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 CellDEVS. 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 webbased simulation framework, providing a CellDEVS 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.
Several applications are being considered to apply CellDEVS 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 CellDEVS 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 threedimensional 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 twoway 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 CSTR3336, 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. 3053. 1990.
[Gar86] GARZIA, R.F.; GARZIA, M.R.; ZEIGLER, B.P. "Discrete Event Simulation", IEEE Spectrum, December 1986. pp. 3236.
[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. 562567.
[Gia95] GIAMBIASI, N.; FRYDMAN, C.; ESCUDE, B. "Hierarchical/Multiview modeling and simulation". In Proceedings of the 7th. European Conference on Computer Simulation. 1995.
[Gut95] GUTOWITZ, H. "Cellular Automata and the sciences of Complexity. Part III". To appear in the journal Complexity. November 1995.
[Gre94] GREENBERG, A.; LUBACHEVSKY, B.; NICOL, D.; WRIGHT, P. "Efficient Massively Parallel Simulation of Dynamic Channel Assignment Schemes for Wireless Cellular Comunications". Proceedings of the 8th. Workshop on Parallel and Distributed Simulation, pp. 187194, 1994.
[Ho89] HO, Y. "Special issue on discrete event dynamic systems", Proceedings of the IEEE, 77 (1), 1989.
[Jef85] JEFFERSON, D. "Virtual Time". ACM TOPLS, 7(3): 404425. July 1985.
[Jef87] JEFFERSON, D. "Distributed simulation and the Time Warp Operating System". In 11th. Symposium on OS principles. pp 7793. November 1987.
[Lin95] LIN, Y.; FISHWICK, P. "Asynchronous Parallel Discrete Event Simulation", IEEE Transactions on Systems, Man and Cybernetics. 1995.
[Lip90] LIPTON, R.; MIZELL, D. "TimeWarp vs. ChandyMisra: a worstcase comparison". Proceedings of the SCS Multiconference on Distributed Simulation. 22, 1 (Enero 1990). pp. 137143.
[Mis86] MISRA, J. "Distributed discreteevent simulations". ACM Computing surveys. Vol. 18, No. 1, 3965. 1986.
[Mos95] MOSCA, R., SCHENONE, M. "Urban Traffic: new design proposals through the employof microsimulators". 1995
[Nic94] NICOL, D.; FUJIMOTO, R. "Parallel Simulation Today". Annals of Operations reserach, vol. 53, 249285. Nov 1994.
[Ove92] OVEREINDER, B.; SLOOT, P. "Application of TimeWarp to parallel simulations with asynchronous cellular automata". 1992.
[Ove93] OVEREINDER, B.; SLOOT, P.; HERZBERGER, L. "TimeWarp on a transputer platform: pilot study with asynchronous cellular automata". 1993.
[Pra95] PRAEHOFER, H. "Multifacetted, Object Oriented modeling in the transportation domain". Proceedings of EUROCAST '95, LNCS, SpringerVerlag. 1995.
[Rig89] RIGHTER, R.; WALRAND, J. "Distributed simulation of discrete event systems". Proceedings of the IEEE. pp. 99. January 1989.
[Tof94] TOFFOLI, T. "Occam, Turing, von Neumann, Jaynes: How much can you get for how little? (A conceptual introduction to cellular automata)". Proceedings of ACRI'94. (1994).
[Wag95] WAGNER, P. "Traffic simulations using cellular automata: comparison with reality". Proceedings of Traffic and Granular Flow, 1995.
[Wai97a] WAINER, G.; FRYDMAN, C.; GIAMBIASI, N. "An environment for simulation of cellular DEVS models". En Proceedings of the 1997 SCS European Multiconference on Computer Simulation. Estambul, Turquía. 1997.
[Wai97b] WAINER, G.; GIAMBIASI, N. "CELLDEVS models with transport and inertial delays". en Proceedings of the SCS European Simulation Simposium on Industrial Simulation, Passau, Alemania. Octubre 1997.
[Wai97c] WAINER, G.; GIAMBIASI, N. "Modelling and simulation of CellDEVS models". Informe Técnico No. 97007, del Departamento de Computación, FCENUBA. Enviado a ACM Transactions on Modelling and Simulation. 1997.
[Wai97d] WAINER, G.; ALVARIÑO, A.; SAEZ, K. "Informe sobre algoritmos de sincronización en simulaciones paralelas". Informe interno. Departamento de Computación, FCEN/UBA. 1997.
[Wai98] WAINER, G. "Discreteevents cellular models with explicit delays". Ph.D. Thesis, Université d'AixMarseille III. 1998.
[Wol86] WOLFRAM, S. "Theory and applications of cellular automata". Vol.1, Advances Series on Complex Systems. World Scientific, Singapore, 1986.
[Zei76] ZEIGLER, B. "Theory of modeling and simulation". Wiley, 1976.
[Zei84] ZEIGLER, B. "Multifaceted Modelling and discrete event simulation". Academic Press, 1984.
[Zei90] ZEIGLER, B. "Objectoriented simulation with hierarchical modular models". Academic Press, 1990.
[Zei95] ZEIGLER, B. "Objectoriented simulation with hierarchical modular models". Revised to include source code for DEVSC++. Technical Report. Department of Electrical and Computer Engineering. University of Arizona. 1995.
[Zei95b] ZEIGLER, B.; KIM, D. "Design of high level modelling / high performance simulation environments". Technical Report, Department of Electrical and Computer Engineering, University of Arizona. 1995.
[Zei96] ZEIGLER, B.; MOON, Y.; KIM, D.; KIM, D. "DEVSC++: A high performance modelling and simulation environment". Technical Report, Department of Electrical and Computer Engineering, University of Arizona. In Proceedings of 29t. Hawaii International Conference on System Sciences, Jan. 1996.
[ Back to homepage 
Back to information 
Back to top ]

[
Information 
Courses 
Thesis 
Events ]
[
Student's work 
Goals 
Details of the Results 
Technical Assistance ]
Comments: Gabriel A. Wainer 
Webmaster: Sebastian Enrique
Last Update: March 31, 2000