proparcurso 14/15 1computadores paralelos 2programación basada en paso de mensajes 3técnicas...

proPar 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, …

5

5

2, 3, 2

2, 2

4

3

proPar Temario síncrona-2

5 Computación Síncrona

1 Sincronización (Barrera y su implementación)

• Contador

• Árbol

• Mariposa “Butterfly”

• Problemática de interbloqueo

2 Cálculos sincronizados (PRAM)

• Modelo Hardware / Software

• Algunos ejemplos simples

3 Ejemplo adaptado a CLUSTER

• Problema de la distribución del calor

proPar Sincronización BARRERA síncrona-3

Muchas aplicaciones presentan sincronismo

----------MPI_Comm_size (MPI_COMM_WORLD, &numProcesos);----------// Computar todos paso 1

MPI_Barrier (MPI_COMM_WORLD);

// Computar todos paso 2

6

int pvm_barrier( char *group, int count )

PVM

(75% según Fox, … 1994)


Princeton Application Repository for Shared-Memory Computers

yo = …; // 0..15

datos.total[yo] = misPrimos(yo);

load (“primopar”,4,4, …);

read (&datos);for (i=1; i<16; i++) total[0] += total[i];

proPar Sincronización BARRERA (Ejemplo) síncrona-6

ARM A9Dual Core

Epiphany 16

1GB SDRAM

primopar

struct { int total[16]; } datos;


sleep(10);// ¿Funcionará?read (&datos);for (i=1; i<16; i++) total[0] += total[i];


read (&datos);for (i=1; i<16; i++) total[0] += total[i];

yo = …; // 0..15

datos.total[yo] = misPrimos(yo);

if (yo==0) datos.computando = 0;

struct { int total[16]; int computando;} datos;

datos.computando = 1;


while (datos.computando) read (&datos);for (i=1; i<16; i++) total[0] += total[i];

yo = …; // 0..15

barrier_init(…);datos.total[yo] = misPrimos(yo);barrier (…);if (yo==0) datos.computando = 0;

datos.computando = 1;


while (datos.computando) read (&datos);for (i=1; i<16; i++) total[0] += total[i];

proPar Sincronización BARRERA (Escalabilidad) síncrona-7

for (i=0; i<100.000; i++) MPI_Barrier (MPI_COMM_WORLD);

PC #Pi µseg12345678

10119

48

121620242832364048

80146319395372

10261104664661744619

0

200

400

600

800

1000

1200

4 8 12 16 20 24 28 32 36 40 48

MPI_Barrier

Parallella => 16Pi => 0,994 µseg

PC9 => 4Pi [104] y 8Pi[385]

proPar BARRERA (Contador) síncrona-8

• Idea: Un contador cuenta los procesos que llegan a la barrera

//barrier(4)

P2

//barrier(4)

P1

//barrier(4)

P3

//barrier(4)

P0

0 1 2 3 4 50

Pg

¿Dónde reside? Proceso gestor de grupos

send(Pg, 4)

recv(Pg)

3 X

send(Pg, 4)

recv(Pg)

2 X

send(Pg, 4)

recv(Pg)

1 X

send(Pg, 4)

recv(Pg)

0

¿Código de Pg? Latencia O(n)

proPar BARRERA (Árbol) síncrona-9

• Idea: Fases de sincronismo parcial por parejas (Sean 8 Pi)

P0P1 P2 P3 P4 P5 P6 P7

Llegada a la Barrera

Salida de la Barrera

¿Código de cada Pi?

Latencia (2 log n)


void barrera (int yo, int dist) { if (((yo/dist)%2) == 0) { recibir (yo+dist, &msj); if (dist<N/2) barrera (yo, dist*2); enviar (yo+dist, &msj); } else { enviar (yo-dist, &msj); recibir (yo-dist, &msj); }}

//barrera (yo, 1);

¿ Sin recursividad ?

proPar BARRERA (Butterfly) síncrona-12

• Idea: Barreras parciales por parejas (Enlaces Full Duplex)

P0 P1 P2 P3 P4 P5 P6 P7

Latencia (log n)

¿Código de cada Pi?

proPar BARRERA (Butterfly) síncrona-13

void barrera (void) { for (dist=1; dist<N; dist*=2) if ( (yo%(dist*2)) < dist) { enviar (yo+dist, &msj); recibir (yo+dist, &msj); } else { recibir (yo-dist, &msj); enviar (yo-dist, &msj);} }

?

P0 P1 P2 P3 P4 P5 P6 P7

0 1 2 3 0 1 2 3

0 1 2 3 4 5 6 7

0 1 0 1 0 1 0 1dist

1

2

4

grupos2

4

8

proPar BARRERA (Problemática de Interbloqueo) síncrona-14

• Ojo en situaciones tipo Butterfly:

P0 P1 P2 P3 P4 P5 P6 P7

Pi Pi+1

------------------- ------------------enviar (Pi+1, &msj); enviar (Pi, &msj);recibir(Pi+1, &msj); recibir(Pi, &msj);------------------- ------------------

¡ Potencial interbloqueo ! Pi Pi+1

------------------- ------------------enviar (Pi+1, &msj); recibir(Pi, &msj);recibir(Pi+1, &msj); enviar (Pi, &msj);------------------- ------------------

Escritura cuidadosa

enviarRecibir

proPar BARRERA (Problemática de Interbloqueo) síncrona-15

• MPI_Sendrecv

------envRec(Pi+1, &msjIda, &msjVuelta);------

------envRec(Pi, &msjIda, &msjVuelta);------

¡ 12 parámetros !

• MPI_Sendrecv_replace

-------envRecR(Pi+1, &msj);-------

------- envRecR(Pi, &msj); -------

Pi-1 Pi Pi+1

envRecR(Pi-2,…); envRecR(Pi-1,…) envRecR(Pi, …);envRecR(Pi, …); envRecR(Pi+1,…); envRecR(Pi+2,…);

¡ Ojo !

proPar Cálculos sincronizados (PRAM) síncrona-16

• Modelo Hardware (SIMD)

Programa

P0 P1 Pn

RelojInstrucciones

Memoria Común

• Los Pi trabajan síncronamente

• Los Pi activos ejecutan misma instrucción sobre distintos datos

• La instrucción: move, add, función

• La propia inst. dice qué Pi activo

• No se pasa a siguiente instrucción hasta que todos acaban

EREW Lectura y escritura ExcluyenteCREW Lectura Concurrente y escritura ExcluyenteERCW Lectura Excluyente y escritura ConcurrenteCRCW Lectura y escritura Concurrente


• Modelo Software (operador: forall)

forall (i=j to k [by delta]) {operaciones ejecutadas por Pi[P0..Pn]}

s=0;for (i=0; i<10; i++) s = s + v[i];

forall (i=0; i<4; i++) t[i] = s + v[i];

forall (i=2; i<4; i++) Q(i);

forall (i=0; i<4; i++) s = s + v[i];

fuera del forall secuencial P0

P0, P1, P2 y P3

P2 y P3

Sólo válido si CRCW


• Algunos ejemplos simples (Difusión de un dato):

¿ D = 5, N Pi quieren leerlo y máquina EREW ( N = 2i ) ?

5

P0 P1 Pn-1

P0 P1 Pn-1

int A[N];

5Replicar D

5 5 5

forall (i=0;i<N;i++) if (D==0) ...

for (i=0;i<N;i++) A[i] = D;

forall (i=0;i<N;i++) if (A[i]==0) ...

Muy lento O(N)

Puedo hacerlo en paralelo


• Idea: Usar más Pi según se van teniendo copias nuevas en A

5

P0

inicio

5 5

P0

paso 0

5

P1

555

P0

paso 1

5

P1 P2 P3

555

P0

paso 2 (con N=8)

5

P1 P2 P3

5555

P4 P5 P6 P7

A[0] = D; // Inicio

for (i=0;i< ? ;i++) // Pasos

forall (j= ? ;j< ? ;j++) // Difusión A[ ? ] = A[ ? ]; // paralela

logN

2i 2i+1

j-2ij

Complejidad (log N)


• Algunos ejemplos simples (Suma de un vector):

Restricción: |V| = 2i <= N

V0 V1 V2 V3 V4 V5 V6 V7

V01 V23 V45 V67

V03 V47

V07

Idea: Usar un vector auxiliar (A)

¿ Código paralelo ?

1 2 3 4 5 6 7 8 V

1 2 3 4 5 6 7 8 AP0 P7

3 7 11 15 A

P1 P3 P5 P7

10 26 A

P3 P7

36 A

P7


• Algunos ejemplos simples (Suma de un vector):

Restricción: |V| = 2i <= N

1 2 3 4 5 6 7 8 V

1 2 3 4 5 6 7 8 AP0 P7

3 7 11 15 A

P1 P3 P5 P7

10 26 A

P3 P7

36 A

P7

forall (i=0;i<N;i++) A[i] = V[i];

for (i=1;i<=logN;i++) forall (j=2i-1; j<N; j+=2i) A[j]=A[j]+A[j-2i-1];

¿ Código definitivo ?


• ¿Cómo simular el forall con modelo de paso de mensajes?

--------------------forall (P0..Pn)

Q(i);--------------------

--------------------//forall (P0..Pn)Bcast(… 0, grupo); Q(i);Barrier(grupo);--------------------

Pi

?

proPar Problema de la distribución del calor síncrona-23

• Barra con temperatura en los extremos (1D): ¿Temperatura interior?

20º 100º

¿Calor o Tibieza?

¿Modelo de difusión del calor?

Ta Tb Tc

Tb se ve influido por Ta y Tc

Tb (Ta + Tc) / 20

1

2

3

N

N-1

¿Cuándo terminar?:

• NumIteraciones

• cotaError <


#define N 100000#define P 100 int main (int argc, char *argv[]) { int i, t; float x[P], y[P]; x[0] = y[0] = 20.0; x[P-1] = y[P-1] = 100.0; for (i=1; i<P-1; i++) x[i] = 0.0; for (t=1; t<=N; t+=2) { for (i=1; i<P-1; i++) y[i] = 0.5 * (x[i-1]+x[i+1]); for (i=1; i<P-1; i++) x[i] = 0.5 * (y[i-1]+y[i+1]); } // imprimir los valores de temperaturas exit (0);}


20.0000000 18.4082146 16.8476410 15.2870674 13.8165274 12.3459873 11.0141773 9.6823673 8.5232000 7.3640323 6.3945465 5.4250607 4.6460094 3.8669584 3.2655854 2.6642127 2.2183673 1.7725219 1.4551404 1.1377589 0.9208815 0.7040040 0.5617894 0.4195748 0.3301172 0.2406595 0.1867010 0.1327424 0.1015476 0.0703528 0.0530757 0.0357986 0.0266365 0.0174744 0.0128250 0.0081755 0.0059192 0.0036629 0.0026165 0.0015701 0.0011067 0.0006435 0.0004478 0.0002526 0.0001743 0.0000974 0.0000691 0.0000452 0.0000404 0.0000485 0.0000638 0.0001152 0.0001691 0.0003191 0.0004700 0.0008639 0.0012581 0.0022370 0.0032161 0.0055331 0.0078502 0.0130822 0.0183143 0.0295960 0.0408777 0.0641248 0.0873720 0.1331825 0.1789930 0.2653786 0.3517642 0.5077381 0.6637121 0.9335048 1.2032976 1.6505858 2.0978739 2.8089471 3.5200205 4.6044073 5.6887941 7.2757010 8.8626080 11.0918350 13.3210621 16.3279266 19.3347893 23.2300453 27.1253014 31.9727325 36.8201637 42.6160049 48.4118423 55.0708923 61.7299461 69.0826492 76.4353485 84.2382126 92.0410767 100.0000000

100iteraciones

20.0000000 20.8079491 21.6158981 22.4238491 23.2318001 24.0397530 24.8477058 25.6556606 26.4636154 27.2715721 28.0795307 28.8874893 29.6954498 30.5034122 31.3113747 32.1193390 32.9273071 33.7352791 34.5432510 35.3512268 36.1592064 36.9671860 37.7751694 38.5831566 39.3911438 40.1991348 41.0071297 41.8151245 42.6231232 43.4311256 44.2391281 45.0471344 45.8551445 46.6631546 47.4711685 48.2791862 49.0872040 49.8952255 50.7032509 51.5112762 52.3193054 53.1273384 53.9353714 54.7434082 55.5514488 56.3594894 57.1675339 57.9755821 58.7836304 59.5916824 60.3997383 61.2077942 62.0158539 62.8239174 63.6319809 64.4400482 65.2481232 66.0562057 66.8642883 67.6723785 68.4804764 69.2885742 70.0966797 70.9047928 71.7129059 72.5210266 73.3291550 74.1372833 74.9454193 75.7535553 76.5616989 77.3698425 78.1779938 78.9861526 79.7943115 80.6024780 81.4106522 82.2188263 83.0270081 83.8351974 84.6433868 85.4515839 86.2597885 87.0679932 87.8762054 88.6844254 89.4926453 90.3008728 91.1091080 91.9173431 92.7255859 93.5338364 94.3420868 95.1503448 95.9586105 96.7668762 97.5751495 98.3834305 99.1917114 100.0000000

100.000iteraciones


• Placa con temperatura en los bordes (2D): ¿Temperatura interior?


• Placa con temperatura en los bordes (2D): ¿Temperatura interior?

• 200 x 200 puntos

• cambiosColor < 21

• 164.000 iteraciones

• 457:883 (seg:mseg)


• Zona con temperatura en los bordes (2D): ¿Puedo pasar?

¿Código

paralelo?

Aguanto hasta 71º

Aguantohasta 71,5º

Aguanto hasta 71,25º¿Seguro? Cambios<6


for (i=1; i<numIter; i++){ T = (TN + TS + TE + TO) * 0.25; send (PN, T); // send (PS, T); // Envios no send (PE, T); // bloqueantes send (PO, T); // recv (PN, &TN); recv (PS, &TS); recv (PE, &TE); recv (PO, &TO);}

Barrera

Local

¿ Terminación por cota de Error ?


• Particionamiento

P0 P1 P2 P3

P4 P5 P6 P7

P8 P9 P10 P11

P12 P13 P14 P15

P0 P15

P9

¡ Comunicación con 4 vecinos ! ¡ Comunicación con 2 vecinos !


• Particionamiento


• ¡ Ojo al partir ! (Fila de puntos fantasma)

Proceso Pi

Proceso Pi+1

Puntos

fantasmas

FIN

proparcurso 14/15 1computadores paralelos 2programación basada en paso de mensajes 3técnicas...

Documents