Modelos de paralelismo ? Tipos de paralelismo (1) (a) Paralelismo de datos (Gp:) do i = 1, 1000 do i = 1001, 2000 do i = 2001, 3000 A(i) = func(i) A(i) = func(i) A(i) = func(i) enddo enddo enddo (Gp:) P0 (Gp:) P1 (Gp:) P2
do i = 1, 3000 A(i) = func(i) enddo
Modelos de paralelismo ? Tipos de paralelismo (1) (b) Paralelismo de función (Gp:) P0 (Gp:) P1
(Gp:) F1 (Gp:) F2 (Gp:) F3 (Gp:) F4
Modelos de paralelismo ? Tipos de paralelismo (2) ? grano fino (fine grain) tareas “pequeñas” / mucha comunicación
? grano medio
? grano grueso (coarse grain) tareas “grandes” / poca comunicación ? ? grado de paralelismo
Modelos de paralelismo ? Maestro-esclavo Un thread master genera P threads para ser ejecutados en paralelo, que “mueren” al terminar su tarea.
? SPMD (Single-Program-Multiple-Data) Se ejecutan P copias iguales independientes. Las tareas se diferencian mediante el pid del proceso.
? MPMD (Multiple-…) Se ejecutan P programas diferentes. ? Dos modelos
? Las tareas que se ejecutan en paralelo, bien sean iteraciones de un bucle o funciones, deben ser independientes, ya que se va a perder control global sobre la ejecución de las instrucciones. Análisis de dependencias Ejemplo:
do i = 0, N-1 A(i) = A(i) + 1 enddo (Gp:) P0: L0 +0 S0 P1: L1 +1 S1 P2: L2 +2 S2 … … (Gp:) En paralelo
(Gp:) L0 +0 S0 L1 +1 S1 L2 +2 S2 …
Análisis de dependencias ? ¿Dependencias entre tareas? Sincronización
– global (barreras) – punto a punto (eventos) (Gp:) P0 (Gp:) P1 (Gp:) F1 (Gp:) F2 (Gp:) F3 (Gp:) F4
Análisis de dependencias ? Salvo casos muy obvios, la paralelización del código (análisis de dependencias, reparto de tareas, etc.) sigue siendo responsabilidad del programador.
El análisis debe ser eficiente, ya que se necesita que una fracción importante del código sea ejecutada en paralelo.
Análisis de dependencias (Gp:) ? dependencia RAW
i: A = … j: = A
(Gp:) ? antidependencia WAR
i: = A … j: A =
(Gp:) ? dependen. de salida WAW
i: A = … j: A =
(Gp:) i j (Gp:) i j (Gp:) i j
dependencias verdaderas dependencias de nombre
Grafos de dependencias Bucles + Grafo de dependencias + Distancia de la dependencia do i = 2, N-2 1 A(i) = B(i) + 2 2 C(i) = A(i-2) + A(i+1) enddo A(2) = B(2) + 2 C(2) = A(0) + A(3)
A(3) = B(3) + 2 C(3) = A(1) + A(4)
A(4) = B(4) + 2 C(4) = A(2) + A(5)
A(5) = B(5) + 2 C(5) = A(3) + A(6) (Gp:) 1 (Gp:) 2
(Gp:) A, 2
(Gp:) A, 1
Grafos de dependencias do i = 2, N-31 1 A(i) = B(i) + 2 2 C(i) = A(i-2) 3 D(i+1) = C(i) + C(i+1) 4 B(i+1) = B(i) + 1 5 D(i+30) = A(i) enddo (Gp:) 1 (Gp:) 2 (Gp:) 3 (Gp:) 4 (Gp:) 5
(Gp:) A, 0
(Gp:) A, 2
(Gp:) C, 0
(Gp:) C, 1
(Gp:) D, 29
(Gp:) B, 1
(Gp:) B, 1
| Página siguiente |