procesamiento paralelocurso 14/15 1computadores paralelos 2programación basada en paso de mensajes...

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


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


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 ?


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


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


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?


• ¿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


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?


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, &LT, );repeat eval (sacar(&LT), &LT); if muyGrande(LT) env (alguien, sacar(&LT), 0); if vacia(LT) rec (-1, &LT, 0);until vacia(LT);

• No hay mensajes en tránsito

+

proPar Terminación distribuida (condición) equilibrado-19


Pi Pj

Pi Pj

PjPi

Pi Pj


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


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 ?


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


#Nodos Tiempo

1024

2048

4096

8192

1:371

12:796

42:528

357:343

radioC. ¿150?


• 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 ?


• Código paralelo: Modelo distribuido

¿Seguimiento? 10 8 13 24 51 14 9 17

0 A B C D E F


• 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?


#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?

procesamiento paralelocurso 14/15 1computadores paralelos 2programación basada en paso de mensajes...

Documents