"Núcleo de Monte Carlo y Camino Aleatorio en
Ambientes de Alto Desempeño"

Fabiola Ortega Robles

            
Texto completo de la Tesis    



Resumen

El cómputo de alto desempeño es utilizado dentro del área de la computación científica (principalmente), para dar solución a problemas que demandan una gran cantidad de manejo de instrucciones y datos. Dentro de este tipo de cómputo, se pueden encontrar diferentes paradigmas tales como: cómputo de alto desempeño local, distribuido y de red amplia.

En particular, el método de Monte Carlo (MC) ha sido utilizado en diferentes áreas de las ciencias como la Física, Mecánica Cuántica, Finanzas, Biología, etc. Su versatilidad se da por su naturaleza estadística, la cual engloba métodos básicos, lo que permite que MC pueda ser adaptado a una gama de diferentes áreas y problemas. Dicho método puede ser utilizado para realizar experimentación numérica o simulación de problemas difíciles de atacar en una forma analítica, así como problemas complejos tanto en el espacio de datos como en el número de instrucciones a ejecutar (lo que se traduce en mayores tiempos de procesamiento).

Este método se ha tornado durante varios años muy importante, debido a que a través de su uso es posible verificar modelos matemáticos, validar o corroborar experimentos, además que hace posible la obtención de predicciones. La complejidad al utilizar Monte Carlo depende del problema y del área en particular en donde es aplicado.

En nuestro trabajo de tesis se presenta un núcleo de Monte Carlo, el cual va estar compuesto de un conjunto de funciones de distribución para la generación de números aleatorios, tanto continuas como discretas. Estos números aleatorios son generados con un determinado comportamiento, según la distribución seleccionada. En nuestro caso son utilizados para simular procesos que son modelados mediante las métodos de integración Wiener, Ito y Feynman, las cuales requieren de la generación de trayectorias aleatorias.

Se realiza la creación de muestras, que se componen por un conjunto de trayectorias aleatorias. Para la creación de muestras con una gran cantidad de trayectorias, se requiere de un cómputo intensivo, una de las razones por las que este tema fue de nuestro interés.

El diseño he implementación de la biblioteca para la generación de muestras se realizó en forma paralela, lo que permite mejorar el desempeño en cuanto a cómputo se refiere. Para la paralelización se utilizo la biblioteca MPI (Message Passing Interface) haciendo uso del modelo SPMD (del inglés, Simple Program Multiple Data) en un cluster de computadoras.

Por otro lado, el núcleo de Monte Carlo y los métodos de Wiener e Ito fueron desarrollados como servicios Web, para su uso dentro de un “framework” llamado Taverna, el cual permite el desarrollo de “workflows” o flujos de trabajo. Además, el uso de Taverna se da en la Grid para realizar cómputo de alto desempeño en forma distribuida a través de redes heterogéneas y de forma transparente al usuario. Todo esto con la finalidad de que pueda ser utilizado por un grupo de usuarios que no tengan conocimiento o no estén familiarizados con la programación, lo que permite que se concentren solo en su propio problema.

Nuestro diseño fue ejecutado en un cluster de computadoras utilizando diferentes parámetros para la generación de trayectorias, en donde cada procesador del cluster obtuvo paralelamente un conjunto de trayectorias las cuales conforman una muestra. En las pruebas realizadas se utilizaron diferentes números de procesadores con diferentes tamaños de población. Al aumentar el número de procesadores utilizando un mismo tamaño de población fue posible disminuir el tiempo de cómputo.


        Abstract

High Performance Computing (HPC) is mainly used in scientific computing in order to find solutions to problems which requires multiple instructions and data processing. In this type of computing, one can find different paradigms, such as Local High Performance Computing, Distributed Computing and Wide Network Computing.

Particularly, the Monte Carlo method (MC) has been used in different areas of science, e.g., Physics, Quantum Mechanics, Finances, Biology, etc. Its versatility is given by its
statistics nature that includes basic methods, this allows that MC to be adapted to a huge kind of problems and different areas. MC can be used to do numeric experimentation, simulation of problems which are difficult to solve in an analytic manner, complex problems in a sense of data space and in the number of instructions to execute (this means more processing time).

This method has become very important with the years because this method is useful to verify mathematical models, to validate and corroborate experiments, and furthermore it makes it possible to obtain predictions. The complexity in the use of Monte Carlo method depends on the problem and also depends on the particular area where it is applied.

In this thesis we present one Monte Carlo core. This core is composed of a set of distribution functions to generate continuous and discrete random numbers. These random numbers are generated with a certain behavior, according to the selected distribution. In our case, they are used to simulate processes that are modeled by Wiener integration methods, Ito and Feynman, which require generation of random trajectories.

We create samples that consist of a set of random trajectories. For the creation of samples with a huge amount of trajectories, it is required an intens ive computing, that is one of the reasons for which this subject is of our interest.

The design and the implementation of the library required for the generation of samples was made in parallel, this allows improving the computing performance. MPI (Message Passing Interface) was used for the parallelization of the library, making use of the model SPMD ( Single Program Multiple Data) in a cluster of computers.

On the other hand, Monte Carlo core, Wiener and Ito methods were developed as Web services, for their use within “framework” called Taverna, which allows the development of  “workflows”. In addition, the use of Taverna occurs in the Grid to obtain calculation of high performance in a distributed form through heterogeneous networks and transparently to the user. All this is done in order to enable it to be used by users that do not have programming knowledge or for those that are not familiarized with computer programming. It allows users to be concentrated only in their main problem.

Our design was executed in a cluster of computers using different parameters for the generation of trajectories. Each processor of cluster obtained, in a parallel form, a set of trajectories which conform a sample. In the tests different numbers of processors with different population size were used. When we increment the number of processors fixing the size of the population, it is possible to reduce the computing time.