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  |