Practica2






















Práctica 2

Método de Monte Carlo y Superaceleración



















ÍNDICE

1 Objetivos 2
2 El método de Monte Carlo aplicado al cálculo de PI 2
2.1 El método 2
2.2 Tres versiones secuenciales 3
2.3 Un modelo paralelo 6
2.4 Tablas de tiempos 9
3 Divide y vencerás con superaceleración 10
3.1 Problemática de medición de tiempos en sistemas multinúcleo 10
3.2 Comprobandolos efectos del optimizador de código 11
3.3 Comprobando los efectos de las técnicas de “prefetch” 12
3.4 Análisis del sistema de caches y el conjunto de trabajo de los procesos 16
3.5 Ejemplo del uso de las primitivas scatter y reduce 16
4 ANEXOS 18
4.1 Fichero Makefile 18
4.2 Ficheros ocupar y ocuparNucleo.c 19
4.3 Fichero cuentaPar2.c 20

1 Objetivos
Comprender el modelo de Monte Carlo aplicadoal cálculo del número PI
Problemática de paralelizar basándose en generación de números aleatorios
Primeros problemas para determinar la condición de terminación
Problemática de la medición de tiempos: optimizador de código, técnicas de prefetch y planificación de procesos en sistemas multinúcleo
Ejemplo del modelo divide y vencerás que evidencia superaceleración
Uso de primitivas de comunicacióncolectiva: scatter y reduce
2 El método de Monte Carlo aplicado al cálculo de PI
2.1 El método
De los dos métodos explicados en las clases de teoría, vamos a seguir el primero, cuya representación gráfica es la siguiente:
Dado que el área del círculo es  y el área del cuadrado que lo circunscribe es 4, la relación entre ambas áreas es /4.
Esta relación de áreas es la misma en el cuadrantesuperior derecha, donde podemos imaginar unos ejes cartesianos con origen en el centro del círculo y amplitud 1 en cada eje.
El método consiste en elegir al azar puntos del cuadrante (con coordenadas x,y comprendidas entre 0 y 1), de tal forma que contabilizaremos los puntos que caen dentro del semicírculo.
Si el método de elegir números al azar es bueno y probamos suficientes veces, sea M, la relaciónentre puntos que nos han caído dentro del semicírculo y puntos totales escogidos, debe ser una aproximación a /4.
El esbozo de programa secuencial que calcularía PI de esta forma es el siguiente:
enCirculo = 0;
for (i=1; i<=M; i++) {
x = aleatorio(0.0, 1.0);
y = aleatorio(0.0, 1.0);
if ((x*x + y*y)<=1.0) enCirculo++;
}
PI = (4.0 * enCirculo) / (double) M;



2.2 Tres versionessecuenciales
En este apartado se va a probar la ejecución del algoritmo básico contado en el apartado anterior, pero con tres variantes que tienen que ver con la condición de terminación del cálculo.
Antes de nada, al igual que en la primera práctica, situarse en el directorio asociado a esta segunda práctica denominado “$HOME/p2” y copiarse todos los ficheros que residan en el correspondiente directoriodel usuario “propar00”, entre los que se encuentran piUno.c, piDos.c y piTres.c que tienen el código completo de las tres versiones que se van a probar.
La primera versión del programa es como el esbozo presentado en la sección anterior. El cómputo termina tras un bucle que se ejecuta un cierto número de veces, cuyo valor se fija con un parámetro en la línea de comandos al invocar el ejecutable.El código es el siguiente:
// PCM. Procesamiento Paralelo Curso 05/06 EUI 10/03/06 |
// |
// piUno.c: Programa que calcula el numero PI mediante el metodo |
// de Monte Carlo basado en circulo de radio 1 inscrito en |
// cuadrado de lado 2. |
// Terminacioncontrolada por: Numero de iteraciones |

#include
#include
#include
#include
#include

//--------------------------------------------------------------------
int main( int argc, char *argv[] ) {

int i, iteraciones, enCirculo=0;
double x, y, pi;
struct timeval t0, t1, t;

// Control parametro => Numero de iteraciones
if...

Leer documento completo

Regístrate para leer el documento completo.