Simulación de eventos discretos
| ||||
Simulación de eventos discretos.Una simulación dirigida por eventos o simulación de eventos discretos utiliza un modelo de estados discretos, en donde, a partir de ciertas condiciones iniciales el modelo genera nuevos eventos sobre la marcha (obedeciendo alguna propiedad estadística).
Sumario
La simulación distribuida de eventos discretos
Existen simulaciones que requieren de horas e incluso días para poder obtener un resultado, y una simulación centralizada de eventos discretos no es la mejor opción, por tanto se tiene que recurrir a la simulación distribuida de eventos discretos para acelerar el proceso de obtención de resultados.
Ambos tipos de simulaciones requieren de una estructura de datos llamada lista, que se encargue de extraer y guardar eventos que se procesaran en la simulación. En el enfoque distribuido cada una de las máquinas que forman parte de la simulación deben contar con su propia lista y su reloj local, esto trae consigo inherentemente algunos problemas, como la ejecución ordenada de los eventos de acuerdo a sus dependencias de causa y efecto, casos de ínter-bloqueos, entre otros.
Problemas abiertos de la DDES
A pesar de los importantes avances en las tecnologías que dan sustento a la DDES (son las siglas de Distributed Discrete Event Simulation, su traducción es: simulación distribuida de eventos discretos) y hacen posible el estudio de sistemas de mayor escala y complejidad, las necesidades parecen preceder a las soluciones. La siguiente generación de sistemas VLSI, por ejemplo, requerirá de herramientas de simulación de alto rendimiento con las que pueda estudiarse el comportamiento de circuitos formados por decenas o cientos de millones de transistores.
Además de sus problemas inherentes de sincronización, en los futuros escenarios de aplicación de la DDES se prevén nuevos problemas de construcción, relacionados con la administración del número de elementos de procesamiento que pueden participar. Se espera que los próximos simuladores sean capaces de decidir la mejor técnica de sincronización que deban aplicar a cada simulación que se les presente, inicializar el experimento de acuerdo con criterios de eficiencia en tiempo y memoria, e incluso, reconfigurarlo sobre la marcha a partir de los mismos criterios o como respuesta ante contingencias.
Si se considera el comportamiento dinámico de los componentes que pueden participar en un sistema distribuido es importante incorporar técnicas de tolerancia a fallas, especialmente cuando se observa una tendencia hacia la simulación sobre ambientes heterogéneos (diferentes tipos de computadoras y redes, incluyendo Internet). En muchas aplicaciones de la DDES no puede tolerarse que la reducción en las capacidades de cálculo obliguen a restaurar la ejecución desde cero. Se espera que, de manera automática, un sistema con estas características sea capaz de reconocer un comportamiento erróneo y reponer el curso normal de su ejecución.
Contribución al estado del conocimiento
La propuesta de esta idónea comunicación de resultados, consiste en la utilización de técnicas para la administración de recursos redundantes con el objetivo de tolerar fallas de paro. En concreto se trata de utilizar un conjunto de componentes redundantes, provistos por una red P2P, para reemplazar a otras máquinas que pudieran quedar fuera de operación, restaurando el sistema hasta un estado global previo, desde el que se retoma la ejecución de la simulación.
Un valor adicional de la propuesta es que tiene posibilidades de aplicación no solamente en el contexto de la simulación distribuida, sino que puede aplicarse sobre cualquier sistema distribuido basado en comunicación por paso de mensajes.
La simulación por computadora
La simulación por computadora es una técnica numérica de análisis cuantitativo, con la que pueden realizarse experimentos sobre un modelo, a _n de obtener salidas relacionadas con el rendimiento del sistema que representa . Los resultados que se producen a partir de un programa para computadora, representan la solución del modelo y expresan las salidas del sistema como función de sus valores de entrada y sus parámetros de configuración. A partir de la comparación de los resultados de la simulación con un conjunto de medidas conocidas del sistema, el modelo puede validarse o redefinirse mediante un proceso iterativo de depuración hasta que pueda confiarse en el valor predictivo de los resultados.
Entre la variedad de técnicas de simulación descritas en la literatura, aquellas que pueden ser de interés para su uso en computadoras son: la emulación, la simulación Montecarlo, la simulación dirigida por trazas y la simulación dirigida por eventos.
Simulación de eventos discretos
Una simulación que utiliza hardware o firmware se llama emulación. Un emulador de terminal, por ejemplo, simula un tipo de terminal utilizando otra. Un emulador de procesador simula un conjunto de instrucciones de un procesador, mediante otro. Aunque la emulación es un tipo de simulación, sus objetivos están más relacionados con el diseño de hardware y no tanto con el análisis de desempeño.
Una simulación Montecarlo se utiliza para modelar fenómenos probabilistas cuyas propiedades no cambian en el tiempo, por lo que se le conoce también como simulación estática. Igualmente se utiliza para evaluar expresiones deterministas usando técnicas de probabilidad.
Una simulación dirigida por trazas utiliza como entrada un registro de los eventos que pueden presentarse en un sistema real, ordenados de manera cronológica. En este tipo de simulación, como en el que le sigue, un evento se entiende como una acción discreta que causa un cambio en el estado del modelo. La simulación por trazas es ampliamente usada para el análisis de sistemas de computo, se les ha empleado con mucho éxito para afinar o revisar los algoritmos que administran recursos, como en procedimientos para manejo de paginas, manejo de caché, de calendarización, de prevención de interbloqueo (deadlock) y de asignación dinámica de recursos, entre otros. Una simulación dirigida por eventos o simulación de eventos discretos utiliza un modelo de estados discretos, en donde, a partir de ciertas condiciones iniciales el modelo genera nuevos eventos sobre la marcha (obedeciendo alguna propiedad estadística).
Hay que observar que el término discreto no se aplica sobre los valores de tiempo usados en la simulación. Una simulación dirigida por eventos puede usar valores continuos o discretos de tiempo. Cualquiera que sea la técnica de simulación, la selección de un lenguaje de computadora para su implantación es uno de los pasos más importantes del proceso. Existen, al menos, cuatro selecciones posibles: Un lenguaje de simulación, un lenguaje de propósito general, una extensión de un lenguaje de propósito general y un paquete de simulación.
Todas las simulaciones de eventos discretos tienen una estructura común. Independientemente del sistema que se modela, la simulación tendrá la mayoría de los elementos que se describen enseguida. Si se utiliza un lenguaje de propósito general, todos los componentes tendrán que ser implantados por el analista. En cualquier otro caso, el software que se utilice proveerá estas partes [22]: Calendarizador de eventos Mantiene una lista o registro cronológico de los eventos que deben suceder y ofrece un conjunto de operaciones para su manipulación.
Programa un evento e para que ocurra en el tiempo t.
- Retiene un evento e durante un intervalo de tiempo dt.
- Cancela un evento e, previamente programado.
- Retiene un evento e por tiempo indefinido.
- Reprograma un evento e que se había retenido por tiempo indefinido.
El calendarizador es uno de los componentes que se ejecutan con más frecuencia durante la simulación. Se le invoca antes de cada evento y puede llamársele varias veces cuando se atiende un evento, para programar, o cancelar, otros tantos. El diseño de un calendarizador eficiente es, en consecuencia, una tarea muy delicada que incide en el desempeño del simulador.
Reloj y mecanismo de actualización de tiempo
Cada simulación tiene al menos una variable que representa el tiempo simulado. El calendarizador es responsable de actualizarla y avanzar este tiempo. Existen dos maneras de completar esta operación: Puede utilizarse una unidad de tiempo que sirve para incrementar el reloj en cantidades fijas, cada vez que se actualiza el reloj el calendarizador debe revisar si existen eventos programados para ocurrir en este nuevo tiempo (a esta forma de operar el reloj también se le conoce como simulación dirigida por tiempo). Alternativamente, el calendarizador puede avanzar el reloj hasta el instante en que debe ocurrir el siguiente evento programado. Obsérvese como, en la primera técnica el reloj sólo puede tomar valores discretos, mientras que con la segunda, el reloj puede tomar valores continuos.
- Variables de estado Este es un conjunto de variables, posiblemente globales, que describen el estado del sistema.
- Rutinas para manejo de eventos Cada evento es simulado por una rutina que actualiza el estado del sistema y puede generar nuevos eventos.
- Rutinas de entrada Sirven para ingresar los parámetros del modelo. Típicamente un experimento de simulación se diseña para repetir varias veces una ejecución modificando de manera controlada las condiciones iniciales y con ello elaborar ciertas inferencias estadísticas.
- Generador de reportes Estas son las rutinas de salida que se ejecutan al final de la simulación. Calculan los resultados finales y los imprimen en un formato específico.
- Rutinas de inicialización Sirven para determinar el estado inicial de las variables del sistema e inicializar la generación de números seudo-aleatorios.
Fuentes
- Nicol, D.M. and Balci, Strategic Directions in Simulation Research , Winter Simulation Conference, 1999 Farrington, P.A. and Nembhard, H.B. and Sturrock, D.T.and Evans, G.W. Page(s) 1509-1520.
- Schneider, B. F., What Good are Models and What Models are Good?, Distributed Systems , ACM, 1993, Mullender, S. pages 17-26, Second Edition.
- Beltrao-Moura, J.A., Redes locales de computadoras, McGraw Hill, 1990.
- Jain, R. The art of computer systems performance analysis,John Wiley and sons,1991.
