PDF de programación - Práctica 1 - Cálculo del Número PI por el Método de Montecarlo

Manuel Arenaz
[email protected]

Cálculo del Número PI por el Método de Motecarlo

Algoritmo Secuencial para el Cálculo del Número PI

Método de Montecarlo

  Generación de experimentos aleatorios independientes
consistentes en generar N puntos (x,y) con x,y∈[0,1] y
contar el número C de puntos (x,y) que caen dentro del
cuadrante de un círculo de radio 1.




πr2
π/4

  Área de un círculo:
  Área del cuadrante:
  Probabilidad:
C/N = π/4  π = 4C/N

  La aproximación del número π es
más precisa cuando N→∞.

© Manuel Arenaz, 2009

2

Cálculo del Número PI por el Método de Motecarlo

Algoritmo Paralelo para el Cálculo del Número PI

Paralelización

  Reparto del trabajo correspondiente a la generación de
N experimentos entre un conjunto de P procesadores.
  Cada procesador genera Np puntos (x,y) con x,y∈[0,1] y
cuenta el número Cp de puntos (x,y) que caen dentro del
cuadrante de un círculo de radio 1.

…

p=0
 C0

© Manuel Arenaz, 2009

p=P-1
 CP-1

  Número de experimentos:
Np = N/P con p∈ {0,…P-1}
  Estimación de π = 4C/N
donde C=C0+…+Cp-1
es el nº total de aciertos

3

Cálculo del Número PI por el Método de Motecarlo

Algoritmo Paralelo para el Cálculo del Número PI

Paralelización

N,P

N,P

N,P

  Inicialmente sólo el
proceso maestro del
programa paralelo
conoce los valores de
N y P.
  Paso 1: Envío de N y P
a los procesos esclavos
del programa paralelo
  pvm_send/pvm_recv
  pvm_mcast/pvm_recv

© Manuel Arenaz, 2009

4

Cálculo del Número PI por el Método de Motecarlo

Algoritmo Paralelo para el Cálculo del Número PI

Paralelización

  Paso 2: Cada proceso
del programa paralelo
realiza el trabajo que le
corresponde.
  Cálculo del número de
experimentos Np = N/P.

  Realización de los
experimentos para
calcular Cp.

Np=N/P Np=N/P Np=N/P

Cp

Cp

Cp

© Manuel Arenaz, 2009

5

Cálculo del Número PI por el Método de Motecarlo

Algoritmo Paralelo para el Cálculo del Número PI

Paralelización

  Paso 3: Los procesos
esclavos del programa
paralelo envían el resultado
Cp que han calculado al
proceso maestro
  El proceso maestro calcula el

númro total de aciertos

C = C0+…+Cp-1

Cp

Cp

Cp
C

π=4C/N

  … y a continuación calcula el



valor estimado de π

π = 4C/N

© Manuel Arenaz, 2009

6

Cálculo del Número PI por el Método de Motecarlo

Entrono de Trabajo en el Laboratorio

Entorno de Trabajo

  Máquina virtual paralela restringida a un único PC.
  Sistema de ficheros en red compartido.

  Lenguaje C
  Compilador gcc
  PVM 3.0
  XPVM 1.0

© Manuel Arenaz, 2009

7

Cálculo del Número PI por el Método de Motecarlo

Algoritmo para el Cálculo del Número PI

Compilación

  Crear la estrutura de directorios con la que está

configurado PVM en las máquinas del laboratorio:

  Almacenar código fuente en $HOME/pmv3/src/
  Almacenar ejecutables en $HOME/pvm3/bin/LINUX/

  Compilación como cualquier programa C

Incluyendo el fichero de cabeceras pvm3.h en el código fuente

 
  Enlazando el código ejecutable con las librerías libpvm3.a y libgpvm3.a.

  Usar el script compilepvm.

© Manuel Arenaz, 2009

8

Cálculo del Número PI por el Método de Motecarlo

Compilación y Ejecuciónde Programas Paralelos PVM

Arranque Entorno PVM
  Dos daemons gestionan las comunicaciones:
  PVM daemon ‘pvmd’
  PVM group daemon ‘pvmgs’
  Arranque de los daemons:
  pvmd se arranca al ejecutar los comandos ‘pvm’ y ‘xpvm’

desde un terminal del sistema.

  pvmgs se arranca al ejecutar el comando ‘pvmgs&’ en

background desde un terminal del sistema.

  El script de compilación compilepvm comprueba el

estado del entorno PVM antes de compilar un
programa paralelo PVM.

© Manuel Arenaz, 2009

9

Cálculo del Número PI por el Método de Motecarlo

Compilación y Ejecuciónde Programas Paralelos PVM

Ejecución de Programas Paralelos
  Altarnativas para ejecutar el programa paralelo PVM:
  desde un terminal, como cualquier otro programa UNIX.
  desde la consola PVM usando el comando spawn:







$ pvm
pvm> spawn -> prog_pvm

  Desde el entorno gráfico XPVM usando el comando spawn:



$ xpvm


activando la opción de menu ‘TASKS->SPAWN’.

  Comprobar que no existen procesos PVM colgados de

pruebas anteriores


$ ps -aefl | grep pvm



© Manuel Arenaz, 2009

10

Cálculo del Número PI por el Método de Motecarlo

La consola de PVM

La consola de PVM

  Comandos más importantes de la consola PVM:

 

 

 

 

 

 

 

 

 

“help”: Ayuda sobre los comandos disponibles en la consola
“spawn file”: Ejecución de un proceso PVM almacenado en el fichero file.
En este modo de ejecución no funciona la entrada por teclado!!
Es posible redireccionar la salida del programa PVM a la pantalla (e.g., “spawn -> file”)
“ps”: Muestra los procesos que hay en la máquina virtual.
“conf”: Muestra los computadores que forman parte de la máquina virtural.:
“add/delete hosts”: Añade/Elimina computadores de la máquina virtual.
“kill tid”: Elimina el proceso de identificador tid.
“reset”: Elimina todos los procesos del usuario y reinicializa el daemon
pvm3d.
“quit”: Sale de la consola pero el daemon pvm3d sigue ejecutándose.
“halt”: Sale de la consola y elimina el daemon pvm3d.

© Manuel Arenaz, 2009

11

Cálculo del Número PI por el Método de Motecarlo

Material

  Código secuencial para el cálculo del número PI por el
método de Montecarlo
  Plantilla de programa paralelo PVM escrito siguiendo
el paradigma de programación SPMD (Simple Program
Multiple Data)
  Script de compilación y arranque de la máquina virtual
de PVM en el laboratorio 0.3
  Transparencias del seminario de PVM
  Transparencias de uso de XPVM

© Manuel Arenaz, 2009

12