[ Volver a la página principal ]

Simulación de Sistemas de Eventos Discretos Basados en Celdas
Información


Tabla de Contenidos
Ir al tope ]


Integrantes
TdC ]Ir al tope ]

Para ir a la página de integrantes haga click aquí.

Introducción
TdC ]Ir al tope ]

La resolución de problemas técnicos y de análisis relacionados con sistemas en el mundo real suele atacarse por medio de la elaboración y manipulación de modelos de dichos sistemas. La modelización permite realizar variedad de estudios y experiencias sin necesidad de construir los ambientes físicos que modelan, permitiendo a su vez detectar fallas y errores en los diseños. En otros casos permiten evitar los riesgos de experimentos, y analizar su comportamiento y resultados de forma segura.

FIGURA 1
FIGURA 1 - Resolución de problemas

Como puede verse en la figura 1, estos métodos permiten elaborar soluciones que se prueban en los modelos estudiados para posteriormente ser implementados en un entorno físico dado. En la actualidad, los métodos de resolución de problemas de sistemas reales complejos pueden repartirse en dos grandes clases: la de métodos analíticos y la de métodos basados en simulación.

Los métodos analíticos permiten establecer soluciones generales a partir de las cuales se deducen soluciones particulares por afectación de valores a las variables de las expresiones simbólicas producidas. En muchos casos la utilización de estos métodos presenta restricciones, principalmente a causa de la complejidad de los sistemas a modelar. Por ende, su aplicación precisa simplificar el modelo del sistema a tal nivel, que las soluciones obtenidas son difícilmente interpretables y/o aplicables en el mundo real.

Frente a tal situación, los métodos basados en simulación ofrecen una alternativa. Estos métodos, aunque no pueden proveer soluciones generales, permiten encontrar soluciones particulares aplicables al sistema real (por lo tanto, si el problema puede resolverse de forma satisfactoria por un método analítico, el uso de simulación no se justifica).

En la actualidad, las aplicaciones de simulación por computadora se van haciendo cada vez mas comunes, ya que el desempeño de las técnicas actuales permite tratar modelos de gran complejidad cualitativa y cuantitativa para reproducir fielmente el comportamiento dinámico de sistemas reales complejos. Un gran número de este tipo de aplicaciones están orientadas a aplicaciones en la industria, permitiendo analizar el comportamiento de procesos complejos a bajo costo, sin necesidad de implementar los sistemas para probar el funcionamiento de un nuevo proceso, con la consiguiente disminución de costos y riesgos. Las ventajas de la simulación son múltiples: el tiempo de desarrollo del sistema real puede reducirse, las decisiones pueden chequearse artificialmente, un mismo modelo puede usarse muchas veces, etc. La simulación es más simple de utilizar que ciertas técnicas analíticas y precisa menos simplificaciones.

Para que un formalismo sea adecuado para modelar y simular sistemas, es necesario poder especificar el sistema real con la ayuda de un paradigma que no contenga detalle alguno sobre la técnica futura de implementación del modelo. En la actualidad existen distintas clases de formalismos que lo permiten, por ejemplo, los modelos de eventos discretos. Este dominio es relativamente nuevo (sobre todo en relación con los modelos continuos que tienen una historia muy antigua con un soporte matemático muy anterior al desarrollo de la simulación por computadora).

Este tipo de formalismo está especialmente orientado a la modelización de sistemas artificiales (es decir, aquellos creados por el hombre), en donde las variables son discretas y a tiempo continuo. Estos reciben el nombre de Sistemas Dinámicos de Eventos Discretos (DEDS - Discrete Events Dynamic Systems) en oposición a los Sistemas Dinámicos de Variables Continuas (CVDS - Continuous Variable Dynamic Systems) que se describen por ecuaciones diferenciales. Un paradigma de simulación para DEDS asume que el sistema simulado sólo cambia de estados en puntos discretos en tiempo simulado, o sea que el modelo cambia de estado ante la ocurrencia de un evento [Ho89].

Muchas de las aproximaciones existentes para modelar sistemas de eventos discretos tratan de describir diferentes fenómenos del mismo sistema real combinando diversas técnicas. Esto hace muy difícil el desarrollo posterior de las simulaciones, así como su mantenimiento. Para evitar estos problemas, al comienzo de los años '70, B. Zeigler [Zei76] propuso un formalismo para especificar modelos de eventos discretos conocido como DEVS (Discrete EVents dynamic Systems). Fue demostrado que dicho formalismo permite reproducir por completo el comportamiento de un sistema dinámico que tenga trayectorias de entrada/salida constantes por segmentos.

Esta aproximación propone una teoría de modelización de eventos discretos que permite hacer descripción modular de los fenómenos a modelar, atacando la complejidad por medio de un enfoque jerárquico. Es una metodología formal de modelización de sistemas complejos en base a submodelos simples, que pueden ser posteriormente acoplados para crear modelos complejos, que pueden simularse con alto grado de seguridad.

El formalismo de Zeigler provee una forma de especificar un modelo, que se describe como un conjunto compuesto de una base de tiempo, entradas, salidas y funciones para calcular los siguientes estados y salidas. El formalismo define cómo generar nuevos valores para las variables y los momentos en los que estos valores deben cambiar. Los intervalos de tiempo entre ocurrencias son variables, lo que tiene algunas ventajas: en los formalismos con una única granularidad es difícil describir los modelos donde hay muchos procesos operando en distintas escalas de tiempo, y la simulación no es eficiente ya que los estados deben actualizarse en el momento con menor incremento de tiempo, lo cual desperdicia recursos de las computadora cuando se aplica a los procesos mas lentos. Los modelos a tiempo continuo tienen la ventaja de permitir mayor precisión de los modelos (tanto conceptuales como de implementación), así como una reducción sustancial en los requerimientos de recursos de la computadora (especialmente, tiempo de procesamiento).

Además de un medio para construir modelos simulables, provee una representación formal para manipular matemáticamente modelos de eventos discretos. Esta aproximación se integró posteriormente con nociones de programación orientada a objetos [Zei84, Zei90, Zei95]. El objetivo es crear una Base de Modelos, y permitir la reutilización de los modelos creados, mejorando de esta forma la seguridad de las simulaciones realizadas, reduciendo el tiempo de chequeo de nuevas simulaciones y mejorando la productividad.

Un modelo DEVS se construye en base a un conjunto de modelos básicos (atómicos), que se combinan para formar modelos acoplados. Los modelos atómicos son objetos modulares independientes, con variables de estado y parámetros, funciones de transición internas, externas, de salida y avance de tiempo. Un modelo acoplado especifica cómo se conectan las entradas y salidas de sus componentes. Los nuevos modelos también son modulares, y pueden usarse para construir modelos de mayor nivel de complejidad.

FIGURA 2
FIGURA 2 - Ejemplo de acoplamiento de modelos DEVS (A1, A3, A4: modelos atómicos)

Por otro lado, en la década del '50, J. Von Neumann y S. Ulam definieron un formalismo útil para modelización de sistemas espaciales usando una aproximación jerárquica: los Autómatas Celulares [Tof94]. En el plano conceptual, un autómata celular es un conjunto infinito n-dimensional de celdas ubicadas geométricamente. Cada punto de la grilla espacial infinita (llamado una celda o célula) puede tener un estado elegido de un alfabeto finito. Todas las celdas contienen el mismo aparato de cálculo y se conectan entre sí de forma uniforme. El estado de las celdas se actualiza simultáneamente y de forma independiente de las demás en pasos de tiempo discreto. Para ello se define la vecindad de una celda, que es un conjunto de celdas cercanas. Esta vecindad en general es homogénea para todas las celdas (aunque otros formalismos más complejos permiten definir autómatas con vecindades no homogéneas ni en celdas cercanas). Los estados de las celdas en la grilla se actualizan de acuerdo con una función de transición local. Por ende, el estado de una celda en un momento dado sólo depende de su propio estado en el instante de tiempo previo, y de los estados de sus vecinos en ese mismo momento.

FIGURA 3
FIGURA 3 - Sección de un autómata celular binario

Los autómatas celulares se suelen usar, al igual que las ecuaciones diferenciales, para la modelización de sistemas físicos complejos. Existen modelos de autómatas para modelar la dinámica en fluidos y gases, colonias de animales, modelos ecológicos, entre otros. El formalismo permite especificar modelos de sistemas con distintos niveles de descripción, por lo que permiten atacar una mayor complejidad que las ecuaciones diferenciales [Gut95, Wol86].

Los autómatas celulares son modelos a tiempo discreto, lo que reduce la precisión, la eficiencia de las simulaciones y el grado de paralelismo del modelo. Sin embargo, las transiciones de estado de cada celda suelen ser independientes de otras del autómata, y un autómata puede comportarse de forma muy inhomogénea. Estos problemas pueden evitarse por medio del uso de un modelo de autómatas celulares con relojes asincrónicos, y manejados por eventos. Si se usan relojes independientes, el tiempo de iteración para cada celda puede ser diferente. Con respecto a los fundamentos teóricos de los temas presentados hasta este punto, puede encontrarse mayor información básica en [Wai96].

Tomando estos formalismos como base, en [Wai97a] se definió un nuevo formalismo que incorpora modelos celulares a la jerarquía de clases definida por Zeigler, definiendo los mecanismos necesarios para dicho objetivo. Se establecieron mecanismos para simular una célula, y otros para definir un modelo acoplado celular. A su vez se definió una técnica de simulación abstracta para estos modelos, y se analizaron técnicas para realizar "achatamiento" de los modelos jerárquicos previo a su incorporación a las bases de modelos (debido a motivos de eficiencia en la simulación ya que la jerarquía de modelos impone un overhead importante que disminuye la eficiencia).

En la actualidad, se ha finalizado la construcción de una herramienta que implementa dicho formalismo [BBW98], con el fin de permitir la definición de modelos complejos de esta clase. Para ello, se ha usado como base una herramienta de simulación DEVS de reciente desarrollo [Gia95].

Habiendo finalizado con estas definiciones, se propuso una extensión al formalismo de celdas DEVS [Wai97b] que permite incluir construcciones del tipo "transport-delay" [Gho96]. Esta construcción suele ser usada en el dominio de los lenguajes de descripción de hardware, y permite reflejar la propagación directa de señales sobre líneas de ancho de banda infinito. Además del diseño de hardware, es útil para modelar otros fenómenos físicos que puedan describirse como espacios de celdas (por ejemplo, propagación del fuego en un bosque, reproducción de peces en un área del océano, descripción del tráfico en una ciudad, evolución de sistemas ecológicos, etc.).

Otra modificación fue la extensión del formalismo (que en un principio sólo permite estados binarios) para incluir un tercer estado. Este tipo de estado es útil para especificar campos de celdas en los cuales se desconoce los estados en un alto porcentaje de celdas del campo.

Estos formalismos fueron integrados con construcciones del tipo de demora inercial (inertial delay), que permiten representar semánticas con desalojo. El significado de la construcción es que, si no se mantiene un valor de entrada para una función durante el tiempo suficiente (la demora inercial), el cambio de estado no debe realizarse. En cambio, si dicho valor se mantiene durante ese tiempo, el estado cambia luego de la demora. La construcción también se usa en el campo de diseño de hardware, ya que ciertos circuitos sólo cambian de estado dependiendo de la entrada de energía y de la duración de esta entrada. Aquí también puede usarse la construcción en otra clase de fenómenos complejos, ayudando al modelador a representar comportamientos de esta clase.

En la actualidad se está analizando la incorporación de estos formalismos a la jerarquía propuesta por Zeigler, y la implementación de los simuladores abstractos que permitirán simular este nuevo tipo de modelos. La idea es generar, en base a parámetros, un modelo celular completo para que un usuario no experimentado pueda modelar sistemas complejos sin la necesidad de programar. Con tal fin, se ha definido un lenguaje básico de especificación, que deberá ser incorporado a la jerarquía de clases, e integrado a la ejecución de los modelos de implementación. Estos formalismos han sido definidos en [Wai97c].

Finalizada esta etapa, el trabajo estará centrado en el análisis de cómo proceder a la simulación distribuida de los citados modelos. La idea primordial es encarar el estudio de algoritmos de simulación paralelos y distribuidos existentes, y proponer mejoras orientadas a la simulación de modelos celulares. En muchos casos, las simulaciones de sistemas reales son poco eficientes. El principal problema de velocidad está relacionado con la complejidad de los modelos a especificar, y a su vez tiene causas estadísticas, ya que para ser estadísticamente significativa, una simulación debe generar un número suficiente de evoluciones típicas del sistema.

Un medio obvio de obtener una simulación mas rápida es dedicar más recursos. En particular, se puede acelerar una simulación usando un sistema multiprocesador en vez de un solo procesador. Como la mayoría de las simulaciones son de sistemas que tienen muchos componentes operando en paralelo, parece razonable suponer que la simulación también explote el paralelismo inherente al sistema. La simulación paralela de eventos discretos (PDES), muchas veces llamada simulación distribuida, se refiere a la ejecución de un programa de simulación de eventos discretos en una computadora paralela. El uso de múltiples procesadores parece ser una aproximación promisoria para mejorar la velocidad.

FIGURA 4
FIGURA 4 - Mecanismos de descomposición. (a) Replicación independiente; (b) Compilador paralelizante; (c) funciones distribuidas; (d) eventos distribuidos; (e) descomposición del modelo

El uso de soluciones de simulación paralela permite mejorar los tiempos para obtener muestras significativas para estudiar el sistema real deseado, y por otro lado, permite modelar de forma intuitiva eventos que son inherentemente paralelos. Este es el caso general para los autómatas celulares. La finalidad será analizar distintas estrategias posibles a utilizar en el marco de las soluciones de simulación paralela existentes en las que se hace descomposición del modelo [Fer95, Fuj90, Gar86, Lin95, Nic94, Rig89].

En la actualidad hay dos enfoques principales para hacer simulación paralela con descomposición del modelo en módulos que ejecutan de forma asincrónica. Uno de ellos, pesimista, trata de establecer los caminos de los mensajes en la simulación para evitar errores de causalidad (aquellos en los que el futuro pueda afectar al pasado, por llegada en orden temporal erróneo de los mensajes que se están transmitiendo en un sistema multiprocesador [Cha79, Lip90, Mis86]). Este enfoque trata de preestablecer los caminos de los mensajes, evitando, además, deadlocks.

Otros mecanismos, optimistas, permiten un mayor grado de paralelismo ignorando los posibles errores de causalidad y presuponiendo que los mensajes llegarán en el orden temporal correcto [Jef85, Jef87]. Ante la ocurrencia de errores de causalidad (es decir, casos de llegada de mensajes con timestamps inferiores a la hora de simulación actual), el protocolo debe realizar rollback y recuperación al estado previo a la hora del mensaje recién llegado. Cada una de las técnicas tiene sus ventajas y problemas [Lip90], y se adaptan mejor o peor a distintos tipos de simulaciones. Ambas técnicas básicas han sido difusamente estudiadas, y se han propuesto gran variedad de soluciones. Hasta este momento se ha realizado un estudio completo y exhaustivo de técnicas de simulación paralela, cuyos resultados pueden verse en [Wai97d]. En este momento se están estudiando métodos de incorporar estas técnicas a las jerarquías de modelos celulares DEVS, para permitir mayor eficiencia en estas simulaciones.

Finalmente, es necesario analizar la utilidad de la propuesta por medio de la implementación de modelos complejos. En la actualidad se emplean técnicas similares a las presentes, que han demostrado su aplicabilidad en distintos dominios:

Referencias
TdC ]Ir al tope ]

(Nota: en los casos en los que faltan detalles en las referencias bibliográficas, se debe a que fueron trabajos obtenidos vía la Internet, en los que no figuraban los detalles correspondientes).

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

[Gia95] GIAMBIASI, N.; FRYDMAN, C.; ESCUDE, B. "Hierarchical/Multi-view 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 I-II". 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. 187-194, 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): 404-425. July 1985.

[Jef87] JEFFERSON, D. "Distributed simulation and the Time Warp Operating System". In 11th. Symposium on OS principles. pp 77-93. 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. "Time-Warp vs. Chandy-Misra: a worst-case comparison". Proceedings of the SCS Multiconference on Distributed Simulation. 22, 1 (Enero 1990). pp. 137-143.

[Mis86] MISRA, J. "Distributed discrete-event simulations". ACM Computing surveys. Vol. 18, No. 1, 39-65. 1986.

[Mos95] MOSCA, R., SCHENONE, M. "Urban Traffic: new design proposals through the employof micro-simulators". 1995

[Nic94] NICOL, D.; FUJIMOTO, R. "Parallel Simulation Today". Annals of Operations reserach, vol. 53, 249-285. Nov 1994.

[Ove92] OVEREINDER, B.; SLOOT, P. "Application of Time-Warp to parallel simulations with asynchronous cellular automata". 1992.

[Ove93] OVEREINDER, B.; SLOOT, P.; HERZBERGER, L. "Time-Warp 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, Springer-Verlag. 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. "CELL-DEVS 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 Cell-DEVS models". Informe Técnico No. 97-007, del Departamento de Computación, FCEN-UBA. 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.

[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. "Object-oriented simulation with hierarchical modular models". Academic Press, 1990.

[Zei95] ZEIGLER, B. "Object-oriented simulation with hierarchical modular models". Revised to include source code for DEVS-C++. 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. "DEVS-C++: 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.


[ Volver a la página principal | Volver al tope ]

[ Información | Cursos | Tesis | Eventos ]
[ Trabajos de Alumnos | Objetivos | Detalle de Resultados | Asesoría Técnica ]
Departamento de Computación - Facultad de Cs. Exactas y Naturales - Universidad de Buenos Aires

Sugerencias: Gabriel A. Wainer - Webmaster: Sebastian Enrique
Última modificación: Septiembre 28, 1999