proPar
Curso 15/16
6
1 Computadores Paralelos
3
2 Programación basada en paso de mensajes
3 Técnicas básicas de programación paralela
2, 3, 2 Compulsiva, Divide y Vencerás, Pipeline,
2, 2
5
Síncrona, Equilibrado de carga y Terminación
4 Programación basada en memoria común
5 Algoritmos y aplicaciones
4
Ordenación, …
proPar
Temario
3 Paralelismo compulsivo
1 Computación paralela ideal
2 Transformación geométrica de imágenes
3 Fractales: El conjunto de Mandelbrot
4 Los métodos de Monte Carlo
Compulsiva-2
proPar
Computación paralela ideal
Compulsiva-3
entrada
• Independencia
total
• Equilibrio de
carga perfecto
salida
Quasi ideal
• Maestro reparte
trabajos y recolecta
resultados
• Los esclavos no se
comunican entre sí
• Poca comunicación
frente a cómputo
maestro
e1
e2
eN
proPar
Transformación geométrica de imágenes Compulsiva-4
512
Color: RGB
Tonalidad Grises
512
Digital:
dibujarPixel(f,c,color) RamVideo | mapaPixels
Construir o manipular
ppm y pgm
jasper
Muchos formatos:
jpg, giff, tiff, bmp, ...
http://netpbm.sourceforge.net/
proPar
Transformación geométrica de imágenes Compulsiva-5
Girar:
x’ = x cos + y sen
y’ = y cos - x sen
Desplazar, Escalar, ...
N
N
Igual para todo pixel
M
¿Un P * pixel?
1024*768 = 786.432
¡ No tan fácil !
M
proPar
Transformación geométrica de imágenes Compulsiva-6
• Girar no es tan fácil
512x512
30º
proPar
Transformación geométrica de imágenes Compulsiva-7
• Girar no es tan fácil
30º + filtro
¡ En 40 mseg !
proPar
Transformación geométrica de imágenes Compulsiva-8
• Girar no es tan fácil
[30º + filtro] 12 veces
proPar
Transformación geométrica de imágenes Compulsiva-9
• Girar no es tan fácil
[1º + filtro] 360 veces
¿Qué pasa?
proPar
Transformación geométrica de imágenesCompulsiva-10
• Girar no es tan fácil
[1º + filtro] 360 veces
Giros incrementales [1, 2, ….] desde el original => 9,311 seg
proPar
Transformación geométrica de imágenesCompulsiva-11
• Un filtrado es más facil
proPar
Transformación geométrica de imágenesCompulsiva-12
Sea imagen de 1024*768 (786.432) y 16P => 49.152 pixels * P
¿ Cómo repartir el trabajo ?
filas
rectángulos
columnas
1024
64
48
256
192
768
¿Cómo sería con modelo cluster?
¿Eficiencia?
Se adapta más al modelo de multiprocesadores:
(memoria común)
proPar
Fractales: El conjunto de Mandelbrot Compulsiva-13
Zk+1 = Zk2 + Cj
1
int colores[256][256]
1 …...... 2 ……….. 3 ………………….… 2 ………
0
0
Columna
255
1.. 2 .. 3…………….. 4 --- 9 --- 256 0….. 462 ----- 3
Fila
1 6 7 ---- 55 0 ……………………………….… 20-5
mandelsec.txt
255
512 colores [3+3+3]
1 .......... 2 ………... 3 …………………... 2………..
dibujarPixel (f, c,
colores[f][c])
2
proPar
Fractales: El conjunto de Mandelbrot Compulsiva-14
Representaciones gráficas contenidas en una fórmula
Conjunto de Mandelbrot {M}
a
+2
Z0 = 0
Zk+1 = Zk + Cj
K = 0..
Imaginario
2
b Cj = a + b i
m / |Zm| > 2  Cj  {M}
Condición de divergencia
0
Cj  {M} diverge Zm => Color(m)
?
Cj  {M} no diverge => Negro
-2
-2
0
Real +2
K = 0..N => # Colores a utilizar
proPar
Fractales: El conjunto de Mandelbrot Compulsiva-15
¿Programa secuencial?
0
Columnas
+2
Sea mapaPixel 256*256 y 512 colores
255
0
Imaginario
Filas
for (f=0; f<256; f++)
for (c=0; c<256; c++) {
pixelAPunto(f,c,&a,&b);
color = mandelbrot(a,b);
dibujarPixel(f,c,color);
}
0
255
-2
-2
0
Real +2
proPar
Fractales: El conjunto de Mandelbrot Compulsiva-16
#define MAX_ITER = 256
int mandelbrot (double A, double B) {
double X = 0.0, Y = 0.0;
double XX, YY, distancia;
int i = 0;
do {
XX = X;
YY = Y;
X = ((XX*XX) - (YY*YY)) + A;
Y = (2.0 * (XX*YY)) + B;
i++;
distancia = X*X + Y*Y;
} while ((i < MAX_ITER) && (distancia <= 4.0));
if (i == MAX_ITER) return 0;
else
return i;
}
proPar
Fractales: El conjunto de Mandelbrot Compulsiva-17
¿ Paralelización ?
0
Columnas
Filas
0
maestro
¿Necesario?
e1
e2
eN
e1
?
e4
e7
a. Asignación estática de trabajos
filas, columnas, cuadrantes 255
¡ Ineficiente ! O(7.763)
1*2*3*
O(127.031)
e1
maestro
O(1.772.374)
0** 1 300 .
0 1 8 239 ..
e7
e4
255
proPar
filaIni
colIni
filaFin
colFin
Fractales: El conjunto de Mandelbrot Compulsiva-18
=
=
=
=
((yo-1)
((yo-1)
filaIni
colIni
%
/
+
+
(int) sqrt(numEsclavos)) * filasCuadrante;
(int) sqrt(numEsclavos)) * colsCuadrante;
filasCuadrante;
colsCuadrante;
// Calcular el cuadrante que me corresponde
coloresFilaCuadrante[colsCuadrante+1] = colIni;
for (f=filaIni; f<filaFin; f++) {
coloresFilaCuadrante[colsCuadrante] = f;
cc = 0;
for (c=colIni; c<colFin; c++) {
planoPixelAPunto (f, c, &X, &Y);
coloresFilaCuadrante[cc++] = mandelbrot (X, Y);
}
MPI_Send (coloresFilaCuadrante, colsCuadrante+2, MPI_INT,
0, 1, MPI_COMM_WORLD);
}
PC1 Ventana de 912x1264
#Cores Tiempo Aceleración Eficiencia
1
55:945
4
15:419
3,63
0,91
16
13:899
4,03
0,25
proPar
Fractales: El conjunto de Mandelbrot Compulsiva-19
Ver video
proPar
Fractales: El conjunto de Mandelbrot Compulsiva-20
b. Asignación dinámica de trabajos
Granja de procesadores
0
0
Columna
Fila
255 O( --- )
568
24295
60963
89130
0
e1
1
e2
maestro
255
{Trabajos pendientes}*
¿pixels, filas, cols, ....?
20122
568
4
2
e3
e4
3
proPar
Los métodos de Monte Carlo
Compulsiva-21
• Idea: Uso de números aleatorios – Casino de Monte Carlo
• Orígenes: 1944 – Stan Ulaw y VonNewmann – Bomba atómica
• Aplicaciones:
 Diseño de reactores nucleares














Cromo dinámica cuántica
Simular aleatoriedad
Radioterapia contra el cáncer
de los procesos
Densidad y flujo de tráfico
físicos, térmicos, …
Evolución estelar
Econometría
Pronóstico del índice de la bolsa
Prospecciones en explotaciones petrolíferas
Diseño de VLSI
Física de materiales
Ecología
Criptografía
Valoración de cartera de valores
Programas de ordenador
Métodos cuantitativos de organización industrial
proPar
Los métodos de Monte Carlo
Compulsiva-22
Se basan en la utilización de números aleatorios: Ejemplo1 => 
proPar
Los métodos de Monte Carlo
Compulsiva-23
Se basan en la utilización de números aleatorios: Ejemplo1 => 
Círculo de radio 1 inscrito en cuadrado de lado 2
2
Área del círculo = 
¿/4?
Área del cuadrado = 4
1
¿  / 4 = 785 / 1.000 =>  = 3,14 ?
2
Aquí quedan 785
Tiro 1.000 pelotitas
proPar
Los métodos de Monte Carlo
Compulsiva-24
Se basan en la utilización de números aleatorios: Ejemplo1 => 
Círculo de radio 1 inscrito en cuadrado de lado 2
2
Área del círculo = 
¿/4?
Área del cuadrado = 4
1
2
¿M?
Suficientemente grande
enCirculo = 0;
for (i=0; 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);
proPar
Los métodos de Monte Carlo
Compulsiva-25
¿ Paralelización ?
maestro
Cada esclavo computa:
e1
e2
eN
M/N puntos aleatorios
¡ Todos los esclavos calculan lo mismo !
Generador
de aleatorios
Pensar en mecanismos
más eficientes
proPar
Los métodos de Monte Carlo
Compulsiva-26
• Generación secuencial de números aleatorios:
Xi+1 = (aXi + c) mod m
a = 16.807
m = 231-1
c=0
Xi = (Xi-63 Θ Xi-127) mod 231
http://sprng.cs.fsu.edu/
• Generación paralela de números aleatorios: (sean 4 procesos)
X0 X1 X2 X3 X4 X5 X6 X7
Xi+4 = (AXi + C) mod m
P0
P1
P2
P3
A = a4
C = c(a3+a2+a1+a0) mod m
proPar
Los métodos de Monte Carlo
Compulsiva-27
Otra forma de calcular  mediante una integral (Sumatorio)
Área del semicírculo = /4
y=F(x)
1
y
1
0
1
x
1
1-x2 dx
1 N
 F(xr) (1 - 0)
N r=1
Xr => Números aleatorios [0..1]
proPar
Los métodos de Monte Carlo
Compulsiva-28
Otra forma de calcular  mediante una integral (Sumatorio)
Fx = 0.0;
for (i=1; i<M; i++) {
x = (double) random() / (double) RAND_MAX;
fx = sqrt (1.0 – x*x);
Fx + = fx;
}
PI = (Fx / (double) M) * 4.0;
M
Error Moneda
100.000
0,000104
1.000.000
0,000068
10.000.000
0,000463
100.000.000
0,000105
1.000.000.000
0,000011
Error Integral
0,000021
0,000024
0,000010
0,000017
0,000029
FIN
Descargar

Compulsiva