Ejecución eficiente de códigos Monte Carlo en infraestructuras de Grid

Abstract

Entre los diferentes aspectos que rodean a la computación Grid, esta tesis se centra en la ejecución eficiente de códigos de Monte Carlo. Hay determinados problemas en los que, por su complejidad o tamaño, es muy difícil o imposible obtener una solución exacta. Esto no hace que sean dejados de lado; por el contrario, se han creado multitud de alternativas que permiten aproximaciones más o menos precisas al resultado teórico empleando una fracción de los recursos computacionales, lo que permite su uso en entornos reales. Entre estas alternativas se encuentra el llamado método de Monte Carlo (MC). Este método se apoya en el hecho de que algunos fenómenos complejos pueden ser modelados mediante la ejecución de diferentes simulaciones independientes, empleando números aleatorios para obtener los resultados. Gracias a esta particularidad, los códigos de Monte Carlo son ampliamente empleados en diferentes áreas del conocimiento. Además, su modularidad simplifica la ejecución en entornos distribuidos, donde la asignación de tareas a los recursos computacionales y la sincronización de las mismas dista de ser trivial. Debido a la alta demanda de recursos en muchas aplicaciones científicas -los códigos de MC entre ellas- la Computación Grid se ha erigido como una de las plataformas donde abordar problemas cada vez mayores y más ambiciosos. Además, ha permitido el acceso de la comunidad científica a grandes recursos computacionales, algo especialmente útil dado que el empleo de supercomputadores todavía dista de ser un recurso habitual en determinados entornos. Debido a las particularidades de este tipo de infraestructuras, la ejecución eficiente de aplicaciones distribuidas está lejos de ser trivial. A pesar del enorme trabajo realizado por la comunidad científica en este área (centrado en diferentes conceptos de “infraestructura Grid”, la aplicación a ejecutar o la información disponible) todavía falta una herramienta que permita ejecutar aplicaciones basadas en Monte Carlo en la Grid, que aproveche al máximo su flexibilidad y modularidad para obtener el mayor rendimiento posible. Para llevar a cabo esta tarea se ha seguido una estrategia innovadora. Aquí los códigos de Monte Carlo, los recursos disponibles y las infraestructuras Grid han sido caracterizados con la mayor información posible, de modo que ésta se pueda emplear para hacer una planificación precisa. Esto supone un avance respecto a las herramientas previamente existentes, dado que el empleo de un volumen mucho mayor de información en el proceso de planificación permite llevar a cabo políticas más eficientes tanto en tiempo de ejecución de la aplicación como en el empleo de recursos. Además se ha creado un nuevo algoritmo de self-scheduling llamado DyTSS (acrónimo de Dynamic Trapezoidal Self Scheduling, Auto-planificación Trapezoidal Dinámica), que utiliza esta información para decidir dónde ejecutar cada tarea y el tamaño de la misma. A pesar de que la gran mayoría de los trabajos de scheduling existentes se centran en el uso de simuladores o entornos controlados, en la presente investigación estas propuestas han sido implementadas y empleadas en infraestructuras Grid en producción. Para ello se muestra el funcionamiento de Montera (acrónimo de MONTE Carlo RApido), un framework desarrollado durante el transcurso de la presente tesis. En Montera se han incluido mecanismos que obtienen la información necesaria para los modelos antes mencionados, y se han implementado diferentes algoritmos de planificación entre los que se incluye DyTSS. En resumen, en esta tesis se han ejecutado los siguientes pasos: caracterización del entorno Grid orientada a códigos de MC; profiling de los códigos de MC; diseño de un algoritmo que emplea estos modelos para ejecutar de manera eficiente las aplicaciones; e implementación de todo lo anterior en una única aplicación software. SUMMARY. Among the different aspects that compound Grid Computing this thesis is focused on the efficient execution of Monte Carlo codes. Monte Carlo (MC) codes rely on the assumption that the behavior of complex phenomena can often be modeled by the execution of multiple simple simulations that employ random or pseudo-random numbers to compute their results. Thanks to this particularity, MC codes are widely used in various fields of computing simulations, solving problems where it is unfeasible or impossible to compute an exact result with a deterministic algorithm. The modularity of MC codes also simplifies the execution of distributed environments, where task distribution and synchronization is not trivial. Because of the high demand many scientific applications place on resources -MC codes among them- Grid computing has emerged as a powerful platform for facing new and more ambitious problems. Grid computing has enabled the scientific community to have easier access to large computing resources, something specially interesting nowadays that the employment of supercomputers is still far from being a commodity. Due to the particularities of this kind of infrastructure, the efficient execution of distributed applications is far from trivial. Although an enormous effort has been put into this area by the scientific community (with many different approaches focusing on different concepts of “Grid Infrastructure”, the particular characteristics of the application to be executed or the available and published information) there is still the lack of a specific tool for executing Monte Carlo based applications on the Grid, taking the most of its flexibility and modularity to obtaining the highest performance. To carry on this task an innovative strategy has been followed. Here, Monte Carlo codes, available resources and Grid Infrastructures have been characterized with as much information as possible, employing it to perform a precise scheduling. This represents an advantage respect the previously existing tools: the employment of a bigger volume of information in the scheduling process leads to more efficient policies both in execution time and in resource usage. Also, a new self-scheduling algorithm called DyTSS (acronim for Dynamic Trapezoidal Self-Scheduling) has been created. It employes this information to decide where to submit each task and its size. Even though most of the previous works on the area use simulators or controlled environments, in the current research these proposals have been implemented and employed on Grid infrastructures in production status. To do so Montera (acronym for MONTE carlo RApido, Fast Monte Carlo in spanish), a framework for efficient executions of Monte Carlo codes has been developed. Montera includes mechanisms that obtain the necessary information to the aforementioned models, and different scheduling algorithms -including DyTSS- have been implemented. In summary, this work describes a proposal for optimizing the execution of MC codes on the Grid. First, a characterization of both MC codes and Grid infrastructures is detailed. Then, an algorithm that employs this information to split the desired simulation into tasks of different sizes and submit them to the Grid is explained. Finally, Montera, a framework that implements the proposed characterizations and the algorithm, is presented.