View
217
Download
0
Embed Size (px)
Citation preview
Procesamiento Paralelo Curso 14/15
1 Computadores Paralelos
2 Programación basada en paso de mensajes
3 Técnicas básicas de programación paralela
Compulsiva, Divide y Vencerás, Pipeline,
Síncrona, Equilibrado de carga y Terminación
4 Programación basada en memoria común
5 Algoritmos y aplicaciones
Ordenación, …
4
4
2, 3, 2
2+, 2
4
3
proPar Temario equilibrado-2
6 Equilibrado de carga y Terminación
1 Equilibrado de carga (estática vs dinámica)• Dinámico y centralizado• Dinámico y distribuído• Aplicado a arquitectura “pipeline”
2 Terminación distribuída (condición)• Mensajes de ACK• Modo anillo• Modo árbol
3 Ejemplo “Camino más corto”
proPar Equilibrado de carga equilibrado-3
P0
P1
P2
P3
P4
P5
ideal
P0
P1
P2
P3
P4
P5
evitar
¿A qué se debe?
• División imperfecta del trabajo
• P4 más rápido y P1 más lento
• Equilibrado estático
• Equilibrado dinámico
¿Cómo se consigue?
proPar Equilibrado estático equilibrado-4
Decisión “a priori” sin tener en cuenta ejecución real de los Pi
Ejemplo 1 OK: cuentaPar1
A B C D
B C D
M0
E1 E2 E3
Ti31:80214:67910:548
7:9136:3225:2754:3213:784
Ei
1,081,001,001,011,001,051,05
Nodos12345678
mpirun –np N cuentaPar1 1680000
PC9
proPar Equilibrado estático equilibrado-5
Ejemplo 2 MAL: mandelpar “trozos”
• Difícil estimar tiempos de ejecución de las partes sin ejecutarlas
Ti30:12517:55220:61217:15812:60012:53411:342
9:214
Ei
0,880,490,440,480,400,380,41
Nodos12345678
mpirun –np N mandelparTrozos
PC9
proPar Equilibrado estático equilibrado-6
Ejemplo 3 MAL: primopar3
primosec
[3..5449]720
…. 5457, 5455, 5453, 5451 …. , 5477, 5471
primopar3
[3..5449]720
primopar3
[3..5449]720
primopar3
[3..5449]720
primopar3
[3..5449]720
…. 5475, 5467, 5459, 5451
…. 5477, 5469, 5461, 5453
…. 5479, 5471, 5463, 5455
…. 5481, 5473, 5465, 5457
Ti16:724
8:4524:2784:2832:1232:2162:2141:170
Ei
0,990,980,650,980,750,630,89
Nodos12468
101216
mpirun –np N primopar3 720
PC1..PC4
¿ Viable un reparto estático
mejor ?
proPar Equilibrado estático equilibrado-7
Ejemplo 4 MAL: mandelpar “filas fijas” Round Robin
E1 filas 0, 4, 8, 12, …E2 filas 1, 5, 9, 13, …E3 filas 2, 6, 10, 14, …E4 filas 3, 7, 11, 15, …
Ti58:03028:88314:453
9:76616:05012:70110:669
9:223
Ei
1,001,000,990,450,460,450,45
Nodos12468
101214
mpirun –np N mandelparFilas
PC1..PC8 duales heterogéneos
8:908 0,4315
Se usan PCs lentos
proPar Equilibrado estático equilibrado-8
proPar Equilibrado estático equilibrado-9
Ejemplo 5 MAL: primopar2
28:035 47:680
• Ojo con redes directas
Epiphany 16
?
Mapeo, planificación,
scheduling
proPar Equilibrado dinámico centralizado equilibrado-10
Idea: Maestro con tareas pendientes que reparte (en vivo) a los esclavos
maestro
e1
e2
e3
e4
0
1
2
3
4
Ejemplo 6 OK: mandelpar “reparto dinámico de filas”
PC1..PC8 duales heterogéneos
Ti58:03028:88314:453
9:76616:05012:70110:669
9:223
Ei
1,001,000,990,450,460,450,45
Nodos12468
101214
8:908 0,4315
estático
Ti
29:08614:670
9:8927:9787:0906:4395:876
Ei
1,000,990,980,910,820,750,71
5:617 0,69
dinámico
Se usan PCs lentos
cola de tareas
Pmaestro
Pesclavo
Granja de Procesadores: Fractal
proPar Equilibrado dinámico centralizado equilibrado-11
Idea: Maestro con tareas pendientes que reparte (en vivo) a los esclavos
Dame tarea
Toma tarea
for (fila=0; fila<FILAS; f++) enviar(proceso[fila%N], fila);
mandelpar ¿igual que estático?
• Tareas no homogéneas: Servir antes las grandes
• Creación dinámica de esclavos
• Creación dinámica de tareas
DETALLES
¿Cuándo terminar?
proPar Equilibrado dinámico centralizado equilibrado-12
• ¿Cuándo terminar?
cola de tareas
Pmaestro
Pesclavo
• No basta {tareas} =
• ¿Un esclavo detecta fin global?
M
e0 e1 ei en
• ¿Cada esclavo detecta su fin local?
Cuello de botella en el maestro
Sencillo y eficiente si: pocos esclavos y cálculo intensivo
proPar Equilibrado dinámico distribuido equilibrado-13
Idea: Distribuir la cola de tareas entre más procesos
A. Jerarquía de maestrosPmaestro
cola de tareas
Pesclavo
cola de tareas
PsubM0
Pesclavo
cola de tareas
PsubMn
proPar Equilibrado dinámico distribuido equilibrado-14
B. Totalmente descentralizado
Pi Pj
Pk Pm
Transferenciade tareas
• Iniciada por receptor
• Iniciada por emisor
Ri solicita a ¿Ej? si: {tareas} = o pocas
Ej envía a ¿Ri? si: {tareas} = demasiadas
Sistema muy cargado
Sistema poco cargado¿De quién recibo?¿A quién envío?
proPar Equilibrado dinámico distribuido equilibrado-15
B. Totalmente descentralizado ¿De quién recibo?¿A quién envío?
• Redes Directas (Pi recibe de ¿?)
Pi
Pi ¿Mejores candidatos los
vecinos?
• Solución más generalista
Pi• RoundRobin• Aleatorio• .......
Algoritmo local elige Pj
67%
¿Cuándo y cuánto doy?
proPar Aplicado a arquitectura “pipeline” equilibrado-16
MaestroEsclavo
0Esclavo
1Esclavo
N
tareas
resultados
ET
C
ER
T T
TL
RR
R
T : Tarea
ET: Encamina T
R : Resultado
ER: Encamina R
L: Libre
recibir(Eizq, &Tarea);if estoyLibre Resultado = computar(Tarea); enviar (Eizq, &Resultado);else enviar (Eder, &Tarea);
env(E0, &T);rec(E0, &R);
genera
dibuja
T
R
proPar Aplicado a arquitectura “pipeline” equilibrado-17
genera
dibuja
ET
C
ER
T
TL
RR
ET
C
ER
T
TL
RR
maestro E0 En
recibir(-1, &msj);if (msj == Tarea) if C.Libre enviar (C, &msj); C.Ocupado; else enviar (Eder, &msj);else C.Libre
ET
¿ Código ?
¡ Ojo !
if soyUltimo recibir(C, &Libre); enviar (C, &msj);else enviar (Eder, &msj);
¡ Autocontención !
?
proPar Terminación distribuida (condición) equilibrado-18
Pi Pj
Pk Pm
• Un Pi detecta fin global => fácil
• Cada Pi debe alcanzar fin local ?
Esclavos envían msjFin a maestro
Maestro
¡ Puede Fallar !Transferenciade tareas
¿Código?
rec(-1, <, );repeat eval (sacar(<), <); if muyGrande(LT) env (alguien, sacar(<), 0); if vacia(LT) rec (-1, <, 0);until vacia(LT);
• No hay mensajes en tránsito
+
proPar Terminación distribuida (condición) equilibrado-19
rec(-1, <, );repeat eval (sacar(<), <); if muyGrande(LT) env (alguien, sacar(<), 0); if vacia(LT) rec (-1, <, 0);until vacia(LT);
Pi Pj
Pi Pj
PjPi
Pi Pj
rec(-1, <, );repeat eval (sacar(<), <); if muyGrande(LT) env (alguien, sacar(<), 0); if vacia(LT) rec (-1, <, 0);until vacia(LT);
Pj
Pi
?
proPar Terminación ... (mensaje de ACK) equilibrado-20
inactivo
activo
Pi
Mi padre es Pj
Pj
T
T
Tack
T
Tack
Otros Procesos
FinLocal• No hay más tareas• Envié todos mis Tack (salvo a mi Padre)• Recibí todos los Tack
Tack
T
Tack ¿ Fin Global ?
proPar Terminación ... (mensaje de ACK) equilibrado-21
415826
518203
617992
818456
917924
1016598
1116990
115586
0
718272
218519
318575
1218477
1317002
1417610
1518210
proPar Terminación ... (modo Anillo) equilibrado-22
P0 P1 P2 Pn-1
Idea: Propagarse (recircular) un msjFin
¿ Fin global ?¡ No igual a modelo Primos !
and
fin local¿Código de P0?
Falla si reactivación de Procesos
proPar Terminación ... (modo Anillo) equilibrado-23
Solución: Dar dos o más vueltas al anillo => msjBlanco + msjNegro
P0 Pi Pj Pn-1
T
¡ Pi puede estar activo !
P0 Pi Pj Pn-1
T
PjPj
¡ P0 lo recircula como blanco ! ¿ Fin Global ?
proPar Terminación ... (modo Árbol)equilibrado-24
Idea: La misma del anillo aplicada a una estructura en árbol
and
fin local
and
fin local
and
fin local
Nodos Hoja yRaíz especiales
proPar Camino más corto equilibrado-25
Problema: Encontrar el mejor camino de un punto a otro
Escalada Cima
Campamento Base
proPar Camino más corto equilibrado-26
Representación: Grafo (nodos, arcos, pesos)
Escalada Cima
Campamento Base
10
5124
8
149
17
13
¿Qué estructura de datos?:
A. Matriz de adyacencia
10 8 13 24 51 14 9 17
A B C D E FABCDEF
origen
destino
B. Lista de adyacencia
B 10 •A
B
C
D
E
F
C 8 D 13 E 24 F 51 •
D 14 •
E 9 •
F 17 •
•
¿ Mejor ?
proPar Camino más corto equilibrado-27
Método de búsqueda: (Moore, 1957), (Dijkstra, 1959), ....
10 8 13 24 51 14 9 17
A B C D E FABCDEF
origen
destino
Vi
Vjdi wi,j
dj
Newdj = min(dj, di+wi,j)
Pila de Vértices
Distancias mínimas
0 A B C D E F
A
0 10 B
0 10 18 23 34 61C ED
0 10 18 23 34 51C D
0 10 18 23 32 51C E
0 10 18 23 32 49C
0 10 18 23 32 49•
¿Cómo se puede saber la ruta?
A
B B B B
E
D
E
proPar Camino más corto equilibrado-28
#Nodos Tiempo
1024
2048
4096
8192
1:371
12:796
42:528
357:343
radioC. ¿150?
proPar Camino más corto equilibrado-29
proPar Camino más corto equilibrado-30
• Código paralelo: Modelo centralizado
pila de vértices
Pmaestro
Pesclavo
• ¿Matriz de adyacencia?
• ¿Mínimos actuales?
Difundir todos vs cambios
inic (matriz, PV, dist);mcast (esclavos, &matriz);repeat Ei = rec(-1, &msj); if (msj == dameVertice) env (Ei, {sacar(&PV), dist}); else //msj == tomaVertices actualizar (&PV, &dist, msj);until condicionFin();mcast (esclavos, &msjFin);
maestro
• ¿ Condición de finalización ?
• ¿ Código de los esclavos ?
proPar Camino más corto equilibrado-31
• Código paralelo: Modelo distribuido
¿Seguimiento? 10 8 13 24 51 14 9 17
0 A B C D E F
proPar Camino más corto equilibrado-32
• Código paralelo: Modelo distribuido (Seguimiento)
∞
10
∞
B
A
8 13 24 51
∞
C D E F
B
14
∞
D
C
9
∞
E
D
17
∞
F
E
∞
F
Mm1[0]
0
m2[10]
10
m31[18]
m32[23] m3
4[61]
m33[34]
18 23 61
34
m4[32]
m5[32] m6[51]
32
51
m7[49]
49
• ¿ Código de los esclavos ?• ¿ Cuándo terminar ?• ¿ Agrupar ?
¿Resultados?
proPar Camino más corto equilibrado-33
#Nodos Tiempo
1024
2048
4096
8192
1:371
12:796
42:528
357:343
radioC. ¿150?
FIN
paralelo4
Tiempo
0:923
1:619
29:732
129:603
secRápido
Tiempo
0:005
0:022
0:088
0:347?