PDF de programación - Núcleo de Monte Carlo y Camino Aleatorio en Ambientes de Alto Desempeño

CENTRO DE INVESTIGACION Y DE ESTUDIOS AVANZADOS

DEL INSTITUTO POLITECNICO NACIONAL



UNIDAD ZACATENCO

DEPARTAMENTO DE COMPUTACION

Núcleo de Monte Carlo y Camino Aleatorio en

Ambientes de Alto Desempeño














Tesis que presenta:
Fabiola Ortega Robles

Para obtener el grado de:

Maestra en Ciencias

En la especialidad de:

Ingeniería Eléctrica

Opción en computación





i













Director de Tesis: Dr. Sergio Victor Chapa Vergara


México, D.F. Agosto 2008



ii

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



iii

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.



iv

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 intensive 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



v

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.





































vi







DEDICATORIAS

He llegado al final de este camino para el comienzo de uno nuevo:

Con todo mi corazón a una de las dos personas que más amo:
Ma.Guadalupe Robles H. mi madre y mi mejor amiga.

A mis hermanas: Mónica y Lizbet: ustedes, mi mamá y yo,
siempre juntas apoyándonos sin importar las distancias.

A mis hermanos: Eduardo, Saúl y Miguel, deseo que
algún día volvamos estar todos juntos.

vii









viii

AGRADECIMIENTOS


Agradezco al Consejo Nacional de Ciencia y Tecnología por el apoyo económico
recibido.

Agradezco al Centro de Investigación y de Estudios Avanzados (CINVESTAV) del
IPN por el apoyo de la beca terminal.

Agradezco al Dr. Sergio V. Chapa Vergara por el apoyo brindado para poder concluir
el presente trabajo de tesis.

Agradezco a la Dra. Julieta Medina García por su tiempo, apoyo, comentarios y
sugerencias para el desarrollo del trabajo de tesis.

De igual forma agradezco a la Dra. Sonia Guadalupe Mendoza Chapa por su apoyo,
consejos y sugerencias. Además de darle gracias por su disposición a escucharnos y
apoyarnos incondicionalmente.

Agradezco al Dr. José Guadalupe Rodríguez García por sus sugerencias, comentarios
y su amistad brindada.

Agradezco a Jesús Cazares por su disposición permanente e incondicional para aclarar
mis dudas, así como por su amistad. Siempre tendrás en mí a una amiga.

Agradezco a todos los doctores investigadores del departamento de computación por
sus enseñanzas y conocimientos transmitidos.

Agradezco a Jesús Muedano C. por su apoyo y comprensión durante el tiempo que
estuve cursando mi maestría, por el tiempo y momentos que hemos pasado juntos.

Agradezco a m