proPar
Curso 15/16
5
1 Computadores Paralelos
5
2 Programación basada en paso de mensajes
3 Técnicas básicas de programación paralela
2, 2, 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
4 Particionamiento y Divide y Vencerás
1 Particionamiento
2 Divide y Vencerás
3 Ordenación mediante cubetas
4 Integración numérica
5 Problema de los N-cuerpos
diviVence-2
proPar
Particionamiento
diviVence-3
Particionar: Dividir el problema en partes (Ej: Fractal Mandelbrot)
datos
funcional
cuentaM
MPEG
f1
cuentaE1
cuentaEn
f2
Huffman
Quantizar
IDCT
PB
Componer resultado final:
scatter + reduce
Mucho menos
frecuente
fn
YCbCr  RGB
proPar
Divide y Vencerás
diviVence-4
Divide y Vencerás: Particionar de forma recursiva, combinando
resultados (Ej: QuickSort, SumarNúmeros)
int sumar(int *s) {
if (card(s) <= 2)
return (n1 + n2);
else {
dividir (s, s1, s2);
suma1 = sumar(s1);
suma2 = sumar(s2);
return (suma1 + suma2);
}
}
¿ Paralelización ?
+
+
+
+
+
+
+
proPar
Divide y Vencerás (paralelización)
Recolectar
sumas
P0
P1
P2
P3
P7
P4
P8
P9
diviVence-5
P5
P10 P11
P6
P12
Dividir
No trabajan todos los
procesos todo el tiempo
P13
P14
proPar
Divide y Vencerás (paralelización)
Nivel
4
P0
2
P0
1
0
diviVence-6
P4
P0
P0
P2
P1
P0 => 4, 2, 1
P4 => 6, 5
P2 => 3
P6 => 7
P2
P4
P3
P4
P6
P5
P6
P7
¿ Cómo programarlo ?
Recibir_Mi_Trozo
Distribuir_A_Descendientes
¿Cuáles?
Procesar_Mi_Trozo
Recolectar_Sumas_De_Mis_Descendientes
Enviar_Mi_Suma_Total_A_Mi_Ancestro
proPar
Divide y Vencerás (paralelización)
diviVence-7
//Recibir_Mi_Trozo
if (yo == 0) nivel = numProcesos / 2;
else recibir (-1, {&padre, &nivel, &miTrozo});
//Distribuir_A_Descendientes
for (i=nivel; i>0; i=i/2)
enviar(yo+i, {yo, i/2, trozo(i)});
//Procesar_Mi_Trozo
//Recolectar_Sumas_De_Mis_Descendientes
//Enviar_Mi_Suma_Total_A_Mi_Ancestro
if (yo == 0) printf(“Total = %d\n”, Total);
else enviar(padre, Total);
proPar
Divide y Vencerás (paralelización)
diviVence-8
//Recibir_Mi_Trozo
if (yo == 0) {
for (i=0; i<N; i++) v[i] = random();
nivel = numProcesos / 2;
longRodaja = N;
} else {
MPI_Recv (v, N/2, MPI_INT, MPI_ANY_SOURCE,
MPI_ANY_TAG, MPI_COMM_WORLD, &estado);
padre = estado.MPI_SOURCE;
nivel = estado.MPI_TAG;
MPI_Get_count (&estado, MPI_INT, longRodaja);
}
¿ scatter ?
//Distribuir_A_Descendientes
for (i=nivel; i>0; i=i/2) {
longRodaja = longRodaja / 2;
MPI_Send (&v[longRodaja], longRodaja, MPI_INT,
yo+i, i/2, MPI_COMM_WORLD);
}
proPar
Divide y Vencerás (paralelización)
diviVence-9
//Procesar_Mi_Trozo
suma = 0;
for (i=0; i<longRodaja; i++) suma += v[i];
//Recolectar_Sumas_De_Mis_Descendientes
for (i=nivel; i>0; i=i/2) {
MPI_Recv (&sumaBis, 1, MPI_INT,
MPI_ANY_SOURCE, 1, MPI_COMM_WORLD, &estado);
suma += sumaBis
¿ reduce?
}
//Enviar_Mi_Suma_Total_A_Mi_Ancestro
if (yo>0) MPI_Send (&sumaBis, 1, MPI_INT, padre, 1, …);
else
printf (“Suma = %d\n”, suma);
proPar
Divide y Vencerás (paralelización)
diviVence-10
32.000.000 números int  sumaSec => 0,033
*500
17,021
Procesos sumaPar
2
0,152
4
0,222
8
0,996
16
1,382
32
1,626
2
4
8
16
32
11,388
10,279
6,320
3,985
2,675
sumaParBis
0,161
0,234
1,006
1,385
1,632
0,75
0,41
0,34
0,27
0,20
Scatter +
Reduce
?
proPar
Ordenación mediante cubetas
diviVence-11
• ¿Ordenar exámenes?
¿Cuánto tardará en
ordenar 600 exámenes?
Un montón por letra
De uno en uno
A
B
Z
¡ Lentísimo !
¡ Más rápido !
¿ Paralelo ?
ordenar
juntar
proPar
Ordenación mediante cubetas
diviVence-12
M números (10.000.000) en un rango (sea: 0..99.999)
Uniformemente distribuidos en N intervalos regulares (sean: 10)
1.000.000  [0..9.999], 1.000.000  [10.000..19.999], .............
M-1
0
Distribuir
en cubetas
0
9.999
Ordenar
cubetas
¡ No todas
iguales !
Juntar
10.000
19.999
90.000
99.999
¿Programa paralelo?
proPar
Ordenación mediante cubetas
diviVence-13
Versión 1: Asociar una cubeta por proceso
M-1
0
Para todo Pi
Recolectar
en mi cubeta P0
0
9.999
P1
P9
10.000
19.999
90.000
99.999
Ordenar mi
cubeta
Todos los Pi necesitan el array completo
proPar
Ordenación mediante cubetas
diviVence-14
static int *vector, elemCubeta;
vector = malloc (CARDINALIDAD * 4);
enterosCubeta = MAX_ENTERO / numCubetas;
if (yo == 0) // Inicializar vector
MPI_Bcast (vector, CARDINALIDAD, MPI_INT, 0, MPI_COMM_WORLD);
// Coger los de mi cubeta
elemCubeta = 0;
for (i=0; i<CARDINALIDAD; i++)
if ((vector[i] / enterosCubeta) == yo)
vector[elemCubeta++] = vector[i];
ordenarCubeta ( );
// Enviar y Recoger cubetas
if (yo == 0) {
j = elemCubeta;
for (i=1; i<numCubetas; i++) {
MPI_Recv (&vector[j], CARDINALIDAD, MPI_INT,
i, 1, MPI_COMM_WORLD, &estado);
MPI_Get_count (&estado, MPI_INT, &elemCubeta);
j+=elemCubeta;
}
} else
MPI_Send (vector, elemCubeta, MPI_INT, 0, 1, MPI_COMM_WORLD);
proPar
Ordenación mediante cubetas
diviVence-15
Versión 2: Asignar un trozo del array original a cada proceso
M-1
0
Para todo Pi
Recolectar en
miniCubetas
P0
P1
Env/Rec
miniCubetas
Ordenar mi
cubeta
P9
MPI_Alltoall
0
9.999
10.000
19.999
90.000
99.999
proPar
Ordenación mediante cubetas
diviVence-16
MPI_Alltoall (BufferEnvio, BufferRecepcion, MPI_Comm)
P0
Pn-1
buffer
enviar
buffer
recibir
gather
(receptorP0)
buffer
enviar
0
n-1
P1
gather
(receptorPn-1)
0
n-1
Pn-1
0
n-1
P0
¿Todas las minicubetas iguales?
0
n-1
Pn-2
proPar
Tiempos ordenar Cubetas
diviVence-17
480.000 números, 2..16 cubetas/Pi y Selección Directa
puro
97,208
proPar
Integración numérica
diviVence-18
b
a F(x) dx
¿Mejor trapecios?

a
 = (b – a) / N
b
a

b
Precisión
b-
I =   F(x)
x=a
¿Cómo puede ser el programa paralelo?
proPar
Integración numérica
diviVence-19
a) Particionamiento y
Asignación Estática (4Pi)
P0
a
b
 = (b – a) / N (N=1.000.000)
P1
P2
a
P3
b
 = (b – a) / P (P=4)
Cada Pi calculará su trozo:
¿Esbozo del programa paralelo?
250.000 rectángulos ()
Conocimiento previo del N razonable
proPar
Integración numérica
diviVence-20
b) Divide y Vencerás y
Asignación Estática (4Pi)
P0
a
b
 = (b – a) / N (N=¿?)
N
Area
2
4
A2
A4
n
2n
An
A2n
a
P1
P2
P3
b
¿Esbozo del programa paralelo?
Reparto no equilibrado de trabajo
|A2n-An| < cotaError
proPar
•
Problema de los N-cuerpos
diviVence-21
“N-body” Interacción de astros en el espacio (galaxia)
m4
m1
m2
i m3
(xi,yi)
Vi
i
m2
ti
F=
G mp mq
Fp=
r2
q
F=ma
composición
t
(xi+1,yi+1)
Vi+1
i+1
ti+1
m (Vi+1-Vi)
t
Vi+1 = Vi + (F t / m)
dist = Vi t
i+1
(xi+1,yi+1) = f (dist, i, Xi, Yi)
t
proPar
Problema de los N-cuerpos
diviVence-22
for (t=0; t<tMax; t++)
/* Para cada periodo */
for (i=0; i<N; i++) {
/* Para cada cuerpo */
FNew[i] = NuevaFuerza(i);
VNew[i] = NuevaVelocidad(i);
PNew[i] = NuevaPosicion(i);
}
for (i=0; i<N; i++){ /*Actualizar estado global*/
F[i] = Fnew[i]
V[i] = VNew[i];
P[i] = PNew[i];
}
}
¿Esbozo del programa paralelo?
No computable eficientemente O(N2)
proPar
Algoritmo de Burnes-Hut
diviVence-23
Idea: Disminuir N agrupando cuerpos próximos
Centro
de masa
r
¿ Cómo determinar las agrupaciones ?
proPar
Algoritmo de Burnes-Hut
diviVence-24
Idea: Dividir el espacio en (8 ó 4) regiones (cubos o cuadrados)
que contengan un único cuerpo y luego .........
QuadTree: Árbol cuaternario
En cada nodo:
Masa total
Centro de masa
proPar
Algoritmo de Burnes-Hut
diviVence-25
Idea: ..... y luego calcular (F,V,X,Y) recorriendo árbol
Sigue
r
d
Para
¿ Parar ?
r >= d / 
tal que  = 1.0 o menor
proPar
Algoritmo de Burnes-Hut
diviVence-26
proPar
Algoritmo de Burnes-Hut
for (t=0; t<tMax; t++) {
formarArbol;
CalcularMasasYCentros;
CalcularNuevasFuerzas;
Actualizar;
}
Complejidad = O(NlogN)
Asignar nodos a procesos
Árbol muy poco equilibrado
Bisección recursiva ortogonal
diviVence-27
/* Para cada periodo */
???
¿Programa paralelo?
proPar
Algoritmo de Burnes-Hut
9
diviVence-28
21
Media = 10,25
10
1
proPar
Algoritmo de Burnes-Hut
diviVence-29
• Bisección recursiva ortogonal
FIN
Descargar

Sistemas Operativos I