Algoritmo MPI paralelo para el cálculo aproximado del valor de PI por el método de Montecarlo

José Jesús Soto Sánchez1

1 CIDETEC IPN, U. P. Adolfo López Mateos, Av. Juan de Dios Bátiz s/n casi esq. Miguel Othón de Mendizábal, Edif. del CIDETEC, Col. Nva. Industrial Vallejo, Del. Gustavo A.

Madero, 07700, México, D. F. 1jsotos0801@ipn.mx

Resumen. El presente trabajo describe el método Monte Carlo para calcular el valor aproximado de PI. Muestra el programa implementado en Message Passing Interface (MPI), el cual fue compilado y puesto a prueba en el clúster de tipo Beowulf del Centro de Innovación y Desarrollo Tecnológico en Cómputo del Instituto Politécnico Nacional de México.

Palabras Clave: método Monte Carlo, Message Passing Interface (MPI), cálculo de PI.

1 Introducción

El método de Montecarlo (MC) es un procedimiento matemático que nos permite simular un sistema, con la ayuda de ordenadores. En general se aplica a problemas cuyo comportamiento global se puede modelar mediante una distribución de probabilidad [1]. Esta técnica es aplicable en numerosos campos, no sólo en el de las matemáticas (evaluaciones de integrales) sino también en ingeniería ambiental (crecimiento de bosques y estudios de contaminación), economía (análisis de mercado y crecimiento de PIB), biología molecular (interacción de moléculas de ADN), medicina (radiaciones) y muchas otras.

El método Monte Carlo es un método numérico que permite resolver problemas físicos, matemáticos y estadísticos mediante la simulación de variables aleatorias [2]. El Método Monte Carlo es un método no determinístico (entiéndase, un algoritmo que con la misma entrada ofrece muchos posibles resultados) o estadístico numérico usado para aproximar expresiones matemáticas complejas y costosas de evaluar con exactitud.

La denominación Monte Carlo fue popularizado por los científicos Stanislaw Ulam, Enrico Fermi, John Von Neumann, and Nicholas Metropolis, entre otros, quienes ya trabajaban sobre muestreo estadístico. Hace referencia al Casino de Montecarlo en Mónaco por ser la “capital del juego de azar”, al ser la ruleta un generador simple de números aleatorios. El nombre y el desarrollo sistemático de los métodos de Monte Carlo datan aproximadamente de 1944 y han mejorado enormemente al ser implementados en computadoras con tecnologías de vanguardia.

1.1 ¿Para qué se utiliza el Método Montecarlo?

Es un método que utiliza números aleatorios para calcular numéricamente expresiones matemáticamente complejas y difíciles de evaluar con exactitud, o que no pueden resolverse analíticamente. Algunos ejemplos son:

• Aproximar el valor de PI. • Cálculo de integrales definidas.

El método de Monte Carlo proporciona soluciones aproximadas a una gran variedad de problemas matemáticos, haciendo posible la realización de experimentos con muestreos de números pseudoaleatorios en una computadora. El método es aplicable a cualquier tipo de problema, ya sea estocástico o determinista.

2 Cálculo de integrales definidas

Basicamente, una integral es una suma de infinitos sumandos, infinitamente pequeños. Dada una función f(x) de una variable real x y un intervalo [a,b] de la recta real, la integral

� �������

�

(1)

es igual al área de la región del plano xy limitada entre la gráfica de f, el eje x, y las líneas verticales x=a y x=b, donde son negativas las áreas por debajo del eje x.

Fig. 1. La integral definida de una función representa el área limitada por la gráfica de la función, con signo positivo cuando la función toma valores positivos y negativo cuando toma valores negativos.

Ahora bien, Si X es una variable aleatoria con densidad f y g : R � R es una función, entonces el valor esperado de la v. a. g(X) es

E[g(X)] = g�x� f �x� dx��� (2)

La ley Fuerte de los Grandes Números, indica que: Si X1, X2, . . .es una sucesión de v. a. i. i. d., todas con media µ; entonces

lim�→� ��� � �� · · · � ���� =µ (3)

2.1 Integrales múltiples

El método de Monte Carlo para el cálculo de integrales en una variable no es muy eficiente, comparado con otros métodos numéricos que convergen más rápidamente al valor de la integral. Pero sí cobra importancia en el caso del cálculo numérico de integrales múltiples:

� g�x1, . . . , xl � dx1 . . . dxl!

" (4)

Para calcular la cantidad

# = �!

"� g�x1, . . . , xl � dx1 . . . dxl

!

" (5)

Utilizamos el hecho que

% = E[g(U1 … Ul)] (6)

con U1, . . . ,Ul independientes y uniformes en (0, 1). Si

&11, … , & 1(

&21, … , & 2(

.

.

.

&*1, … , & *(

(7)

son n muestras independientes de estas l variables, podemos estimar

%~ ,- .& /

1, … , &/(0

*�

123

(8)

3 Cálculo aproximado del valor de PI.

Una aplicación a las integrales múltiples es el cálculo aproximado del valor de PI Recordemos que el área A, de un círculo de radio r es

4 = 567 (9)

y por lo tanto π está dado por el valor de la integral

� 5�97:;7<3���, =��� �=3

> (10)

Si X e Y son v.a.i.i.d., uniformes en (-1, 1), ambas con densidad f (x) =1/2 en (-1, 1), entonces su densidad conjunta será:

f (x, y) = f (x)f (y) =1/4, en (0, 1) × (0, 1). Si U1,U2 ~ U(0, 1), entonces

X = 2U1 – 1 Y = 2U2 – 1 verifican X, Y ~ U(-1, 1).

3.1 Cálculo de PI

( = ?1, @/ �7 + =7 ≤ 10, D. D.E

(11)

Entonces:

FG(H = I��7 + =7 ≤ 1� = 54 (11)

3.2 Algoritmo (estructurado) para el cálculo de PI

Algoritmo 1. Para el cálculo de PI.

PI �0; for i = 0 to n do

Generar U,V ~ U(0, 1); X � 2U - 1; Y � 2V - 1; if X2 + Y2 ≤ 1 then PI � PI + 1 end end

PI � 4 * PI/n

4 Message Passing Interface MPI

MPI es una especificación para una application programming interface (API) que permite a muchas computadoras comunicarse con alguna otra. Es usado en agrupaciones de computadoras llamadas “clusters” y supercomputadoras. MPI es un lenguaje independiente de protocolos de comunicación, usado para programar computadoras en paralelo. Las metas de MPI son: alto performance, escalabilidad y portabilidad; es ampliamente aceptado por la Academia y la Industria [3]. La implementación del lenguaje MPI es diferente de los lenguajes estructurados. Muchos desarrollos se combinan con C, C++ y lenguaje ensamblador. Se hace uso de MPI para llevar a cabo la paralelización del algoritmo para el cálculo del valor de PI utilizando el método Monte Carlo.

4.1 Programa (paralelizado) para el cálculo de PI

Programa 1. Para el cálculo de PI. /* Programa MPI que usa el metodo monte carlo para calcular el valor de PI */ #include <stdlib.h> #include <stdio.h> #include <math.h> #include <string.h> #include <mpi.h> #define USE_MPI double stream_id; int SEED; void genera(){ SEED=(rand() % 100000); srand(SEED); stream_id=(rand() % 100000000); stream_id=(stream_id / 100000000); } int main(int argc, char *argv[]) { int niter=0; double a,b; int i,j,count=0,mycount; /* # de puntos en el primer cuadrante de un circulo unitario */ double c; double pi; int myid,numprocs,proc; MPI_Status status; int master =0;

int tag = 123; MPI_Init(&argc,&argv); MPI_Comm_size(MPI_COMM_WORLD,&numprocs); MPI_Comm_rank(MPI_COMM_WORLD,&myid); if (argc <=1) { fprintf(stderr,"Utiliza: montecarlompi numero_iteraciones\n"); MPI_Finalize(); exit(-1); } sscanf(argv[1],"%d",&niter); /* primer argumento es el numero de iteraciones*/ mycount=0; for ( i=0; i<niter; i++) { genera(); a = (double)stream_id; genera(); b = (double)stream_id; c = a*a+b*b; if (c<=1){ mycount++; } } if (myid ==0) { /*proceso maestro, obtiene los resultados de otros*/ printf ("proceso maestro"); count = mycount; for (proc=1; proc<numprocs; proc++) { MPI_Recv(&mycount,1,MPI_REAL,proc,tag,MPI_COMM_WORLD,&status); count +=mycount; } pi=(double)count/(niter*numprocs)*4; printf("\n # de eventos= %d, el valor de pi es %2.12f\n",niter*numprocs,pi); } else { /* todos los proceso esclavos envian el resultado al maestro */ printf("Proceso %d enviando= %d al proceso maestro\n",myid,mycount); MPI_Send(&mycount,1,MPI_REAL,master,tag,MPI_COMM_WORLD); } MPI_Finalize(); /* termina el programa MPI */ return(0); }

5 Conclusiones

El programa paralelizado se codificó y compiló en el clúster de tipo Beowulf del Centro de Innovación y Desarrollo Tecnológico en Cómputo (CIDETEC) del Instituto Politécnico Nacional como parte del aprendizaje en materia de Paralelización de Algoritmos en estudios de posgrado. En la figura 2 se aprecia el cálculo aproximado del valor de PI, así como el tiempo que tarda en ejecutarse el programa con 10 nodos y 195 procesos.

Fig. 2. Cálculo aproximado del valor de PI, para 10 nodos y 195 procesos.

Este tipo de aproximaciones no son del todo exactas, sin embargo verifica el hecho de paralelizar algoritmos. Podemos apreciar en la figura 3, los valores que calcula el algoritmo para la variable c=a*a + b*b, para 1 nodo y 102 procesos enviados. Estos valores son resultado de elevar al cuadrado números pseudoaleatorios que representan las muestras para el método MonteCarlo.

Fig. 3. Cálculo aproximado del valor de c=a*a + b*b

Los valores mayores que la unidad no son considerados por el método para el cálculo del valor de PI. A continuación se muestra la tabla 1, con diferentes pruebas realizadas, se aprecian los tiempos de procesamiento y se observan los resultados obtenidos en una gráfica posteriormente.

Tabla 1. Tiempo de procesamiento para el cálculo aproximado del valor de PI.

Tiempo (seg) Número de Nodos Número de procesos Valor aproximado 0.519 1 102 3.176470588235 0.520 1 122 3.245901639344 0.524 1 130 3.261538461538 0.519 5 219 3.141552511416 0.598 5 315 3.149206349206 0.675 10 103 3.184466019417 0.696 10 195 3.158974358974 0.724 10 219 3.141552511416 0.888 10 315 3.149206349206

En la gráfica siguientellevar a cabo el procesamiento con los diferentes valores de procesosanterior).

Fig. 4. Gráfica que representa el tiempo consum

Se aprecia en la siguiente gráficano varia considerablemente

Fig. 5. Gráfica que representa el ejecución del programa.

0

0.5

1

1 2 3

3.08

3.1

3.12

3.14

3.16

3.18

3.2

3.22

3.24

3.26

3.28

1 2

En la gráfica siguiente (figura 4) se aprecia que el tiempo no es muy distante para llevar a cabo el procesamiento con los diferentes valores de procesos (de la tabla

Gráfica que representa el tiempo consumido para cada ejecución del programa.

aprecia en la siguiente gráfica (figura 5), que el cálculo aproximado del valor de PI varia considerablemente, pero no es tan exacto como otros métodos.

Gráfica que representa el cálculo aproximado del valor de PI para cada ejecución del programa.

Tiempo (seg)4 5 6 7 8 9

Tiempo (seg)

3 4 5 6 7 8 9

Valor aproximado

se aprecia que el tiempo no es muy distante para (de la tabla

ido para cada ejecución del programa.

del valor de PI

para cada

Tiempo (seg)

Valor aproximado

Referencias

1. Salvadó Artells, Marçal: Facultat de Medicina i Ciències de la Salut Departament de

Ciències Mèdiques Bàsiques. Desarrollo de un programa de simulación basado en el método de Montecarlo para el cálculo de dosis con maniquíes divididos en voxels. Aplicaciones en tomografía computarizada. Tesis Doctoral, Reus 2004. http://www.tesisenred.net/TESIS_URV/AVAILABLE/TDX-0307106-114909/Tesis_msalvado.pdf

2. Aguilera, María Eugenia: Universidad Santo Tomás, Primer Claustro Universitario de

Colombia. Estimación de la tasa de favoritismo en la elección presidencial mediante el uso del estimador de Regresión Local Polinomial. Comunicaciones en Estadística. Junio 2009, Vol. 2, No. 1. http://www.usta.edu.co/revista_estadistica/documents/vol2n1/2_Aguilera.pdf

3. Em Karniadakis, George and M. Kirby, Robert: Cambridge University. Parallel Scientific

Computing in C++ and MPI. A seamless approach to parallel algorithms and their implementation. Cambridge University Press .