ABSTRACT

During centuries, several modelling techniques have helped people to analyze and study very complex problems in diverse areas: physical systems, chemical experiments, social interaction, biological behavior, etc. Several tools have appeared to support such analysis. Analytical methods let people to attack these problems, allowing the advance of science and technology.

Recently, several new complex systems appeared, which cannot be studied with standard techniques. Suppose, for instance, that we want to analyze the traffic flow in an urban center. The use of traditional analytical techniques (such as Differential Equations) has little application in these areas, because the equations are impossible to be found (and if you find them, their resolution cannot be achieved). In this area, computers have helped to improve in the problem solving through the use of simulations.

Simulations let the users to experiment with a "virtual" system, letting him to make changes in the system or its testing conditions, allowing to find solutions to punctual problems (for instance, you can make experiments with the traffic without needing to do any real changes, and after you found the best solution, you can change traffic rules, lights, lane directions, etc., knowing that you will have good results).

Our main goal is devoted to provide tools that can be used in this kind of situations. We use formal methods to build our tools, because it is known that using formal techniques produce reduction in the development cost and delivery time. Nevertheless, we hide the formal complexities, and the user only has to focus in the problem-solving task, avoiding most programming details.

At present we are trying to apply these techniques in systems that must provide real-time responses. For instance, you can feed a simulation with real time data (telling, for instance, that there is a traffic jam; or that every central for celluar phones in a given city section is busy), and use the simulator to find the best solution on-line (for instance, suggest the best alternative route in an electronic sign, or tell another cellular phone central to take care of the zone), providing the best response for the users of these complex systems. Detailed information will be posted in this webpage in the future.

Recently, DEVS theory has been extended by a rigorous theory for quantized systems (Zeigler, Ball et al. 1999). A quantized system is characterised by equivalence of its inputs and outputs. Filtering can be based on quantization, since a quantized system cannot distinguish inputs within an equivalence class: only when values are bigger than the quantum, an output is sent . Quantization theory has been applied to Cell-DEVS, and promising results has been obtained (Wainer and Zeigler, 2000). The empirical results show exponential reductions in the number of messages involved in a simulation (crucial when the simu-lator is distributed) and linear increase of the error in the simulations.

Real-time systems are built as sets of components interacting with their environment. In several cases, these systems must satisfy "hard" timing constraints. These are highly reactive systems, where the deci-sions can lead to catastrophic consequences (control systems in avionics, nuclear systems, industrial automation, transport, robotics or telecommunications). In these systems not only correctness is critical, but also the timing of the executing tasks. Validation of these complex systems can be done with several approaches, but most existing results has not been useful for large-scale systems. In several cases, simu-lations are used to analyze this validity.

DEVS provides a good framework for these purposes, because it is a mathematical paradigm with well defined concepts of coupling of components, hierarchical, modular model construction, support for dis-crete event approximation of continuous systems and an object-oriented substrate. Recent research has used DEVS as a framework for Real-time systems modelling (Hong et al., 1997, Kim et al., 2000). The basic idea is based on the construction of a DEVS Executive based on the abstract DEVS simulators. DEVS has also been implemented to execute over CORBA to address the requirements of scalable and efficient model execution (Cho and Zeigler, 2000). None of these approaches has considered well-known problems in real-time software. For instance, transient system overloading can occur (system failures gen-erating alarm tasks devoted to solve the problem can generate a task load that cannot be supported by the system). The techniques of imprecise computation allow real-time systems to provide controlled degra-dation under transient overloads (Liu et al 1994, Liu 2000). The basic idea is that when overloading oc-curs, the executing real-time tasks return results with smaller precision. This theoretical framework will be combined with the quantization theory, to provide a technique of im-precise real-time simulations. Quantized versions of a given model can be used deadlines cannot be achieved. Instead, if there is enough time to compute a precise result, a non-quantized version (or a ver-sion with smaller quantum) is executed. A problem related with using DEVS as a basis is that this for-malism was developed to represent systems with a time invariant structure. This approach is not useful for certain Real-time systems, where overloading situations must be considered. In these cases, alterna-tive tasks or controlling daemons should be activated to avoid loosing deadlines in the most critical tasks, supporting faults. Recently, (Barros 1998) has presented a new concept to represent DEVS systems that support changes in structure dynamically.

In the short term, we plan to finish some of our present work (introduced in the previous section), and to start the development of a Real-Time DEVS environment. This include the following tasks: · Graphical interfaces: several graphical tools have been developed, but them need to be integrated and tested thoroughly. In this way, we can provide an easiest way to define simulation models. · Model compilers: during the development of some of our recent work we found that some of the constructions provided by our specification languages need to be improved, allowing more powerful definition of the simulation models. The languages will be redefined and the compilers rebuilt. · Real-Time simulators: the definition of a Real-Time DEVS environment based on our present tools can be attacked in the short term, as it only requires the redefinition of the simulation mechanism (which is well documented and separated from the modelling technique). Nevertheless, analysis of timeliness is a much more complex problem that will be attacked in the long term. · RT-DEVS Theory: we will also start defining theoretical studies related with the execution of DEVS models in Real Time, putting special emphasis in distributed environments. In this phase, we will thoroughly analyze the existing bibliography in the area, and will study new developments in distrib-uted real-time systems. The execution of real-time tasks in parallel is an NP-hard problem, but some constrained solutions have been proposed (Stankovic, 1993). In this phase we will study recent ad-vances in the theory of distributed real-time execution, and try to define if any of the existing ap-proaches is applicable to DEVS modelling and simulation in real-time.

In the long term, we can classify our contributions from different points of view. From the methodologi-cal point of view, the proposal considers the development of a theory of dynamic Real-time DEVS using imprecise computing. The goal is to provide security, reduction in the development times, and the ad-vantages of a formal framework to run models. The results can be applied to develop real-time systems. Quantum size adjustment might also control execution of tasks under real-time deadline constraints since larger quantum sizes in computation reduce not only the messages but the time required for task comple-tion, thus enabling application of the techniques of imprecise computation. From the practical point of view, it is expected to provide a set of tools that can be applied to develop real-time software, and simu-lations with hardware-in-the-loop (requiring real-time response). By invoking appropriate execution en-gines, we will provide the ability to execute models in both logical time (the usual simulation clock) and real time (constrained to wall-clock time). From the application of the results, these environments would be applied in a wide range of applications, ranging from personal communication systems, control in in-dustrial plants, robotics, cellular communication or traffic controllers.

References

AMEGHINO, J.; WAINER, G. "Application of the Cell-DEVS paradigm using N-CD++". Proceedings of the 32nd SCS Summer Multiconference on Computer Simulation. Vancouver, Canada.
BARROS, F. "Modelling formalisms for dynamic structure systems". ACM Transactions on Modeling and Computer Simulation. Vol 7, No. 4, October 1997. Pp. 501-515.
CHO, Y. K.; ZEIGLER, B. P., et al. Design Considerations for Distributed Real-Time DEVS. AIS 2000, Tucson, AZ. 2000.
DAICZ, S.; TROCCOLI, A.; WAINER, G.; ZLOTNIK, S. "Using the DEVS paradigm to implement a simulated processor". Proceedings of the 33rd Anual Conference on Computer Simulation. 2000
FISHWICK, P.A. "Web-based Simulation: Some Personal Observations". Proceedings of the 1996 Win-ter Simulation Conference, San Diego, pp. 772-779, 1996.
HONG, J.; SONG, H. et al. "A Real-time discrete event system specification formalism for seamless real-time software development". Discrete Event Dynamic systems, 7, 355-375. 1997. KIM, T.G.; CHO, S.M.; AND LEE, W.B. "DEVS Framework for Systems Development: Unified Speci-fication for Logical Analysis, Performance Evaluation and Implementation". In "Advances in discrete-events simulation", Springer-Verlag (to be published in November 2000).
LIU, J. "Real-Time Systems". Prentice-Hall, 2000.
LIU, J.; LIN, H. et al. "Imprecise computations". Proceedings of the IEEE. Vol. 82, No. 1,January 1994.
MARTIN, D.; MCBRAYER, T.; RADHAKRISHNAN, R.; WILSEY, P. "TimeWarp Parallel Discrete Event Simulator". Tech. Rep. Computer Architecture Design Laboratory, University of Cincinnati. 1997.
SIPPER, M. "The emergence of cellular computing". IEEE Computer. July 1999. Pp. 18-26. STANKOVIC, J. "Hard Real-Time systems". IEEE Press. 1993.
TALIA, D. "Cellular processing tools for high-performance simulation". Computer. Sept. 2000 pp.44-52. WAINER, G. "Discrete-events cellular models with explicit delays". Ph.D. Thesis, Université d'Aix-Marseille III. 1998.
WAINER, G.; GIAMBIASI, N. "Timed Cell-DEVS: modelling and simulation of cellular models". In "Advances in discrete-events simulation", Springer-Verlag (to be published in November 2000).
WAINER, G.; ZEIGLER, B. "Experimental results of Timed Cell-DEVS quantization". In Proceedings of AIS'2000. Tucson, Arizona. U.S.A. 2000. ZEIGLER, B."Theory of Modeling and Simulation". Academic Press. 1976.
ZEIGLER, B.; BALL, G. et al. "Bandwidth Utilization/Fidelity Tradeoffs in Predictive Filtering". SIW, Orlando, FL. 1999. ZEIGLER, B.; KIM, T.; PRAEHOFER, H. "Theory of Modeling and Simulation: Integrating Discrete Event and Continuous Complex Dynamic Systems". Academic Press. 2000.

Methods and proposed approach

In a first stage, we will study several recent advances related with the project. We will seek the recent bibliography thoroughly, mainly trying to attack recent solutions related with distributed real-time execu-tion, recent development of real-time simulation, and novel applications for this kind of approaches. We will attack the problem using the same methodologies that we have been using for our previous research. This includes a cycle of incremental development, including the following phases:

. Formal definitions: using formal specifications (mostly mathematical notations) implies a complex ini-tial effort, but provides good results. You can find problems in your specifications in an early phase, and the final costs of developing the solutions are highly reduced. The definitions cannot be easily used to interact with end users, but they are useful for the developers. One drawback is that researchers without previous experience (i.e., students on training) have to spend some time getting used to the formalisms.

. Software development: once the problem has been attacked formally, and basic properties have been proved, software will be developed following the formal specifications. There will be interaction between formal definitions and software development, by providing software prototypes and executable versions with reduced functionality, trying to detect problems in the formal definitions.

. Application development: in a first stage, we will build several prototype applications. The goal will be to test of the tools, finding problems, and restarting a development cycle. After this first testing stage has been finished successfully, we will be devoted to build complex applications using the tools. For instance, we will provide quantified traffic controllers, using performance polymorphism to run quantized versions of the traffic models under overloading of the simulation system. In this way, the simulator can provide a non precise response in real-time, providing, for instance, a good alternative route to be displayed in electronic signs, or reprogramming of traffic lights. Similar ideas will be used for network (http servers) or cellular phone flow. In this case, under the detection of congestion, a real-time simulator will be acti-vated. Besides these, we will seek industrial and scientific partners who could provide us with complex problems to be solved with the tools.

. Performance testing: this phase will be run concurrently with the software development and applica-tion construction phases. The idea is to make thorough tests on the centralized and distributed versions of the systems. One difficult task will be in the area of distributed real-time simulations: we may be con-strained to provide an environment that can be applied only partially (i.e.: not every real-time distributed system could be modelled using our tools). In some cases we will be able to relax the system constrains (timeliness, precedence, system loading, etc.); in other cases, the desired problem could not be solved.

. Web-based diffusion: we plan to include every new solution provided in our web-based simulation site. This will be a way of providing service to the scientific/technical community, but also to receive complex problems to be used as a workbench for testing of the tools.

Anticipated significance of the work

A final result of this project will be the provision of a set of tools that can be used to analyze any kind of models, with special emphasis in discrete-event models. Also, these models could be run in real-time envi-ronment, providing timely responses. This kind of service is crucial in automated systems, whose diffu-sion and complexity are increasing in a daily basis. The provision of a web-based simulation environment including our tools will allow the Canadian community to have access to a powerful set of tools that can be used to analyze a wide variety of problems. The web-based tools will be controlled for access and dif-fusion, allowing the authors of the models to keep the copyright of their developed models, and allowing them to post the final versions of their works for public domain. International users will be welcome, providing the advantages of mutual international cooperation and also the enrichment of the Canadian scientific community by having availability to a rich model database. We will be also providing high performance results by parallel execution. In a first stage, centralized so-lutions will be provided. Nevertheless, once the parallel versions are finished, they will be available to run complex scientific and technical problems with high performance. The tools will be made available for the scientific community, and they are planned to be developed using public domain compilers (GNU C++, MPIch, Java) under a variety of environments (at present, all our tools run under Windows environments, and most existing Unix platforms, including Linux, Solaris, SunOs, AIX, and Irix). In this way, any ex-isting laboratory can use the tools with little effort. As a result of the application of these tools, several complex problems could be solved, ranging from complex traffic situations (a problem with growing complexity and demand), up to physical problems, passing by all the range of hi-tech applications (net-work analysis, wireless systems, PCS, etc.).