Reparto de experimentos de simulación en redes heterogéneas de estaciones de trabajo Angel F. Perles, Antonio Martí, Juan José Serrano Departamento de Informática de Sistemas y Computadores Universidad Politécnica de Valencia e-mail: [email protected] [email protected] [email protected]

Resumen Este artículo presenta un proyecto para realizar experimentos de simulación concurrentes en masa sin tener que preocuparse de localizar los recursos computacionales para llevarlos a cabo. Para ello, se aprovechan las diferentes estaciones de trabajo desocupadas de los laboratorios de las universidades y centros de investigación. Básicamente se monitorizan modelos de simulación clásicos que se lanzan y supervisan en paralelo, intentando evitar, en cualquier caso, que la comunicación entre procesos cause un “overhead” grande. El enfoque consiste en añadir y eliminar máquinas, con diferentes arquitecturas y sistemas operativos, a un cluster heterogéneo y dinámico que permita ejecutar una aplicación distribuida. La comunicación entre las máquinas y la coordinación de los procesos se hace usando PVM v3 (Parallel Virtual Machine), que permite aprovechar las infraestructuras de red típicas de cualquier centro de trabajo. Un diseño asíncrono de las comunicaciones de los modelos de simulación con los monitores permite explotar el rendimiento máximo de estos modelos al evitarse sincronizaciones que penalizan los speed-up. Es necesario aplicar métodos de reparto dinámico de la carga debido a que el entorno de ejecución usado se comparte con otros usuarios. Para ello se monitoriza el rendimiento de los programas de simulación y se decide si se mueven a otras máquinas usando técnicas de checkpointing.

1

Introducción

Las técnicas de simulación discreta orientadas a eventos han demostrado ser una herramienta imprescindible para el análisis y el desarrollo de todas las tecnologías susceptibles de ser planteadas con un modelo de simulación. Sin embargo, muchos hemos sufrido el enorme consumo de recursos informáticos y los largos tiempos de respuesta al ejecutar modelos de simulación medianamente complejos. Una de las líneas de investigación actuales para mejorar los tiempos de respuesta [1] explota la posibilidad de descomponer el modelo de simulación en submodelos que se puedan ejecutar concurrentemente. El principal problema es mantener la consistencia lógica de las colas de eventos, por tanto, usar técnicas de simulación distribuida no es tarea fácil y requiere un gran esfuerzo de descomposición y sintonización del modelo. En cualquier caso, una deficiente sintonización produce pobres speed-up. Una técnica alternativa consiste en explotar la posibilidad de ejecutar réplicas de modelos de simulación en paralelo que pueden mejorar los tiempos de respuesta al explotar las posibilidades del “paralelismo estadístico”. En esta línea hay trabajos como PIRS [2], cuyo planteamiento consiste en ejecutar réplicas independientes de tamaño fijo en un conjunto de máquinas; la simulación termina cuando se han ejecutado suficientes réplicas como para construir un intervalo de confianza adecuado para las variables de salida del modelo. En nuestro caso planteamos la posibilidad de fijar inicialmente la cantidad de réplicas que permitan optimizar la explotación de recursos computacionales y hacer correr estas hasta que se obtiene el intervalo de confianza adecuado. Este planteamiento intenta sacar el máximo provecho estadístico de los modelos lanzados concurrentemente, posibilitando análisis estadísticos más elaborados y un mejor aprovechaFinanciado parcialmente por CICYT, TAP 96-1090-C01

miento de los recursos; sin embargo da lugar a una mayor complejidad en el desarrollo de la aplicación distribuida, pues se pretende usar máquinas de diferentes potencias y compartidas con otros usuarios, siendo necesario desarrollar técnicas específicas de reparto dinámico de la carga. Para tomar las decisiones de reparto de carga se mide el rendimiento de los modelos monitorizando el avance del tiempo de simulación con respecto al tiempo de reloj del ordenador y monitorizando la cantidad de eventos de simulación que se tratan por unidad de tiempo [3]. Para migrar la carga de las simulaciones se propone el uso de librerías estándar para checkpointing [4], que han demostrado su viabilidad en entornos y aplicaciones distribuidas como MIST [5] y CONDOR/Carmi [6]. Se pretende que la herramienta se pueda aplicar a cualquier simulador público o comercial actualmente disponible. En este aspecto, se ha buscado una forma general de monitorizar y controlar simulaciones y se ha probado en SMPL [7]. Se ha buscado que la instrumentación necesite de pocos cambios en el modelo original, que no implique la modificación de las librerías originales de simulación pues no suelen estar disponibles, y que el “overhead” causado al modelo sea el mínimo posible. La técnica de inyección de eventos en la cola de simulación ha permitido lograr estos objetivos.

2

Estructura de la herramienta

La figura 1 muestra la estructura de la aplicación, que se plantea como un sistema distribuido trabajando bajo PVM [8] donde máquinas heterogéneas UNIX y Windows se incorporan y eliminan dinámicamente.

Figura 1. Estructura de la herramienta de simulación distribuida El primer proceso que se lanza es el Master Monitor (MM), que coordina todo el sistema y extrae los experimentos de simulación a tratar de una base de datos. Su primer cometido es lanzar los procesos Machine and Load Manager (MLM) y User Interface Server (UIS). El MLM incorpora dinámicamente las máquinas que forman la máquina virtual PVM, añadiendo máquinas cuando éstas estén disponibles y eliminándolas cuando fallen o dejen de estar disponibles. En toda máquina que se incorpore, MLM lanzará el Load Monitor (LM), un proceso monitor de la carga. Usando la información de potencia de las máquinas, las máquinas incorporadas y la carga, MLM decidirá dónde y cómo se lanzarán las simulaciones que requiera MM.

El Local Simulation Monitor (LSM) gestiona el funcionamiento de las simulaciones que forman parte de un experimento, recoge la información estadística que generan y la analiza para decidir el fin de la simulación. Los programas de simulación (SIM) están preparados para que puedan ser gestionados por el entorno. El acceso al sistema se hace mediante el User Interface (UI) a través de un User Interface Server (UIS). Este UI pretende ofrecer una forma sencilla y uniforme de especificar los experimentos. La versión actual es un proceso dentro de la máquina virtual PVM, pero se desea que esta interfaz esté disponible en cualquier máquina equipada con un “web browser” con capacidad de ejecutar aplicaciones Java.

3

Instrumentación de las simulaciones

Un objetivo básico es poder manejar y extraer información de los modelos desarrollados en los lenguajes de simulación más habituales. En el software de simulación clásico no se plantea un funcionamiento como aplicación distribuida, así que es necesario adaptarlos para que esto sea posible. Unas mínimas modificaciones del modelo y el diseño de una librería a tres capas (figura 2) que se enlaza con el programa ha permitido la instruFigura 2. Estructura de las librerías enlazadas mentación. En este caso aplicada a con los programas a monitorizar SMPL [7]. El “overhead” temporal que causa la extracción de muestras de información se ha minimizado usando la técnica de inyectar eventos especiales en la cola de eventos del simulador, que toman el control de éste cuando sea necesario enviar muestras del estado al monitor. El “overhead” introducido es proporcional a las veces que se muestree el modelo y a las condiciones de las comunicaciones simulación monitor. Tiempo de respuesta (segundos) 208.803

Overhead comparado con SMPL 0%

220.419

6%

218.553

5%

0.05

SMPL modificado 1 muestra requerida (programa monitorizado)

219.486

5%

0.46

SMPL modificado 10 muestras requeridas

227.932

9%

4.39

SMPL modificado 100 muestras requeridas

286.464

37%

34.91

SMPL modificado 1000 muestras requeridas

1127.419

440%

8.87

SMPL modificado 10000 muestras requeridas

Muestras/ segundo

Descripción SMPL SMPL modificado y lanzado como programa SMPL normal

Tabla 1. Tiempos de respuesta de un programa SMPL instrumentado La tabla 1 muestra los resultados de una prueba de overhead sobre el modelo SMPL de una cola M/M/1. La simplicidad de este modelo hace que cualquier adición de código en el bucle de tratamiento de eventos se aprecie notablemente en el tiempo de respuesta del modelo, por lo que es un buen candidato para este experimento. El modelo se ha ejecutado con el SMPL estándar para un tiempo de simulación que ha sido equivalente a 208’8 segundos en Pentiums 166 con 32 Mb de RAM bajo Linux y Windows 95. Como cabe esperar, el aumento de las muestras requeridas causa un aumento del tiempo de respuesta, y las comunicaciones juegan un papel predominante en los resultados. Un sobremuestreo aumenta notablemente el overhead, pudiéndose llegar a un colapso cuando se requieren excesivas muestras. Como resultado de estas pruebas y basándose en el esquema de ins-

trumentación usado, se puede extrapolar que un programa instrumentado se ejecuta prácticamente igual de rápido que su versión estándar, siempre y cuando se mantenga una tasa de muestreo baja. Las comunicaciones van a ser el único factor que afecte el rendimiento. Estas tienen lugar cuando hay que enviar una muestra y son en sentido modelo -> monitor. El planteamiento de comunicaciones que se ha seguido intenta evitar los problemas de sincronización que se detectaron en un prototipo previo llamado PSMPL (Parallel SMPL) [9] y se ha pretendido que sean totalmente asíncronas. Si se mantiene una tasa de muestreo baja el efecto de las comunicaciones no se apreciará prácticamente en el tiempo de respuesta. El sistema de mensajes usa un esquema de coP V M m e ss a g e municaciones independiente del entorno de computación distribuida elegido, recubriéndose el modelo de PVM con tipos de mensajes más sencillos de manipular, menos propensos a errores y que facilitan el desarrollo de la aplicación distribuida. Así, los mensajes son un conjunto desordenado de < id e n tifie r,d a ta > tu p le tuplas donde “identificador” Figura 3. Codificación de los es un entero que describe el tipo de “dato” asociado mensajes sobre PVM (ver figura 3). Este planteamiento facilita su adaptación a otros entornos de computación distribuida como MPI [10].

4

Reparto de carga

La naturaleza de la herramienta descrita y el contexto de funcionamiento implica un esfuerzo en el diseño del reparto de carga para obtener speed-up’s satisfactorios, sobretodo si se usan métodos de análisis estadístico como el de las réplicas, pues en este método es necesario tener medidas de todas las réplicas para el cálculo del intervalo de confianza, y el retraso de una de ellas provoca el retraso global de toda la simulación [13]. La velocidad a la que se ejecutan los modelos depende, principalmente, de la potencia de la máquina usada y de la carga que ésta tenga. Como se trata de máquinas de diferente potencia y diferentes sistemas operativos, es imprescindible clasificarlas de alguna forma para poder hacer deducciones sobre el rendimiento que ofrecerán al ejecutarse los modelos. La mejor forma de hacer esta clasificación es usar un modelo de simulación sintético que permita obtener un índice que será directamente proporcional al rendimiento que se obtenga con otros modelos. Dicho modelo permite evaluar las características de la máquina al ejecutar las estructuras típicas de los simuladores. Las características de las máquinas y la información recogida por los monitores de carga instalados en cada estación permiten hacer un primer reparto de carga de grano grueso; sin embargo, las fluctuaciones de carga del entorno multiusuario usado y los errores de estimación del rendimiento obligan a aplicar un reparto dinámico de la carga que permita afinar más en el aprovechamiento de los recursos. Los modelos están preparados para contabilizar la cantidad de eventos tratados por unidad de tiempo y enviar esta información junto a los datos estadísticos de las entidades del modelo. Dicha información y el tiempo simulado hasta el momento permite estimar si es conveniente mover la carga a otras máquinas. La carga de procesos se mueve de una máquina a otra usando técnicas de checkpointing, que además permiten aplicar técnicas de garantía de funcionamiento, pues el entorno de computación es sumamente inestable.

5

Prototipo de interfaz de usuario

Para el uso de esta herramienta se propone una interfaz de usuario sencilla que permita el acceso al sistema de simulación y facilite la especificación genérica de experimentos de simulación. Se ha desarrollado un primer prototipo usando C++ Builder de Borland, aunque la intención es traducirlo a Java para facilitar su disponibilidad a través de un “web browser”. La interfaz de usuario permite especificar el nombre del programa de simulación que contiene el modelo y aprovecharse de la instrumentación realizada en él para extraer información que facilite el diseño del experimento. Esto se hace lanzando un modelo y sacrificandolo tan pronto se tenga la información del lenguaje de simulación usado y los datos sobre las variables de entrada y de salida del modelo. La figura 4 muestra parte de la información extraída del ejecutable “mm1”; en la figura 5 se usa la información correspodiente a las variables de entrada del modelo para especificar los datos de los experimentos a realizar. La figura 5 muestra la monitorización del experimento en ejecución. La figura 4 muestra un experimento finalizado con todas sus variables de salida. Algunas de las variables corresponden a información sobre el rendimiento del simulador que permiten realizar el reparto dinámico de la carga.

Figura 4. Extracción de datos de la simulación

Figura 5. Especificando los datos del experimento

Figura 6. Experimento en ejecución

6

Conclusiones y trabajo futuro

El planteamiento de este entorno para simulaciones en masa viene de experiencias previas [9][13], resolviendo aquí los inconvenientes encontrados y proponiendo una herramienta aplicable a diferentes lenguajes de simulación. El sistema de mensajes usado hace muy flexible el diseño de la aplicación distribuida al facilitar la descomposición de los procesos en subprocesos y minimizar los errores de programación. Se ha probado la viabilidad de instrumentar lenguajes de simulación para que sean monitorizados sin modificar las librerías de simulación y haciendo unos mínimos cambios en los modelos, y con un overhead mínimo. Dado que las simulaciones se van a ejecutar en un entorno heterogéneo y multiusuario, se ha hecho hincapié en buscar métodos que permitan medir el rendimiento de las simulaciones, quedando perfectamente resuelto este proFigura 7. Resultados de un experimento blema. Los resultados obtenidos nos animan a continuar en esta línea. Se pretende orientar el esfuerzo a conseguir técnicas que obtengan un reparto de carga satisfactorio sin incrementar excesivamente los costes que supone la migración de los procesos de simulación. Dado que el entorno de computación donde se ejecuta la herramienta es sumamente inestable y propenso a fallos, se plantearán y desarrollarán las adecuadas técnicas de garantía de funcionamiento que se adapten a las necesidades específicas del entorno. La interfaz de usuario se traducirá a Java para que pueda ser utilizada desde cualquier ordenador con un “browser” preparado para Java. El análisis de la salida estadística intentará sacar el máximo provecho a las simulaciones lanzadas concurrentemente. Técnicas de reducción de la varianza [15] y las series temporales estandarizadas [16] parecen las mejores candidatas.

7

Referencias

[1] Richard M. Fujimoto. Parallel discrete event simulation. Communications of the ACM. N. 10. October 1990 [2] Yi-Bing Lin, Parallel Independent Replicated Simulation on a Network of Workstations, Proceedings of the 8th Workshop on Parallel and Distributed Simulation (PADS'94). Vol. 24. Num. 1 . July 1994 [3] Christopher D. Carothers and Richard M. Fujimoto, Background Execution of Time Warp Programs” proceedings Parallel and Distributed Simulation (PADS’96) May, 1996 [4] James S. Plank, Micah Beck, Gerry Kingsley and Kai Li. Libckpt: Transparent Checkpointing under Unix. USENIX Winter 1995 Technical Conference. New Orleans, Lousiana. January 16-20, 1995 [5] Jeremy Casas, Dan Clark., Ravi Konuru, Steve Otto, Robert Prouty, Jonathan Walk Pole, MPVM: A Migration Transparent Version of PVM, Technical Report 95-002, Oregon Graduate Institute of Science and Technology, Department of Computer Science and Enginieering, February 1995

[6] Jim Pruyne and Miron Livny, Managing Checkpoints for Parallel Programs, Dpt. Of Computer Sciences. University of Wisconsin-Madison. 1998 [7] M.H.MacDougall, Simulating Computer Systems, The MIT Press, Cambridge, Massachusetts. 1987 [8] A.Geist, A.Beguelin, J.Dongarra, W.Jiang, R.Manchek and V.Sunderam, PVM3 user's guide and reference manual, Technical Report ORNL/TM-12187, Oak Ridge National Laboratory, May 1994 [9] A.Perles, J. Serrano. Evaluación y análisis de PVM 3. Aprovechamiento para la simulación discreta por el método de las réplicas. Trabajo fin de carrera. Diciembre 1994 [10] MPI: A Message-Passing Interface Standard, University of Tennesse, Knoxville, May 1994 [11] Jiangjiang Song and Heng Kek Choo, Aplication-Level Load Migration and Its Implementation on top of PVM [12] Leen Dikken, Frank van der Linden, Joep Vesseur and Peter Sloot, Dynamic PVM. Dynamic Load Balancing on Parallel Systems,. High-Performance Computing and Networking, proceedings 1994, vol. 797 pp. 273-277 Technical Report 95-002, Oregon Graduate Institute of Science and Technology, Department of Computer Science and Enginieering, February 1995 [13] A.Perles, J. Serrano. Simulación paralela y distribuida. Métodos de análisis estadístico de la salida. Departamento de Informatica de Sistemas y Computadores. Universidad Politécnica de Valencia. Septiembre 1997 [14] A.M.Law and W.D.Kelton, Simulation Modeling and Analysis. McGraw-Hill. 1991 [15] Lee Schruben. Confidence Interval Estimation Using Standardized Time Series. Operations Research. December 1983.