Grafos de dependencias + Espacio de iteraciones do i = 2, N-1 do j = 1, N-2 1 A(i,j) = A(i,j-1) * 2 2 C(i,j) = A(i-2,j+1) + 1 enddo enddo (Gp:) 1 (Gp:) 2 (Gp:) A 2,-1 (Gp:) A 0,1
(Gp:) i (Gp:) j
Dependencias ? Test de dependencias: únicamente para funciones lineales del índice del bucle. (Gp:) do i = L1, L2 X(a*i+b) = = X(c*i+d) enddo (Gp:) ?
(Gp:) L1 (Gp:) L2 (Gp:) i
(Gp:) a*i+b
(Gp:) c*i+d
i1 i2 (Gp:) d – b (Gp:) MCD(c,a) (Gp:) ? Z ? no hay depend.
? Paralelizar el código significa repartir tareas (iteraciones de un bucle) a procesadores. Pero hay que respetar las dependencias de datos. El problema principal son las dependencias de distancia > 0, y sobre todo aquellas que forman ciclos en el grafo de dependencias.
? Siempre es posible ejecutar un bucle en P procesa-dores, añadiendo sincronización para respetar las dependencias de datos… … lo que no significa que siempre sea sensato hacerlo, pues hay que tener en cuenta el coste global: cálculo + sincronización (comunicación). Dependencias
Paralelización de bucles Objetivos: ? Repartir las iteraciones de un bucle entre los procesadores, para que se ejecuten “a la par”. ? Siempre que se pueda, que se ejecuten de manera independiente, sin necesidad de sincronizar (dependencias de distancia 0). ? En función de las características del sistema (comunicación, reparto de tareas…) intentar que las tareas tengan un cierto tamaño.
Paralelización de bucles Objetivos: ? Tal vez sólo se pueda utilizar un número limitado de procesadores. ? Atención al rendimiento (p. e., problemas en la cache).
Objetivos: ? En los bucles de más de una dimensión, paralelizar aquella dimensión que minimice la necesidad de sincronización entre procesadores y aumente el tamaño de grano. Paralelización de bucles do i = 0, N-1 do j = 1, M-1 A(i,j) = A(i,j-1) + 1 enddo enddo (Gp:) P0 (Gp:) P1 (Gp:) P2 (Gp:) P3
Paralelización de bucles (Gp:) P0 (Gp:) P1 (Gp:) P2 (Gp:) P3
do i = 0, N-1 do j = 1, M-1 A(i,j) = A(i,j-1) + 1 enddo enddo Objetivos: ? En los bucles de más de una dimensión, paralelizar aquella dimensión que minimice la necesidad de sincronización entre procesadores y aumente el tamaño de grano.
? Si todas las dependencias son de distancia 0, las iteraciones se pueden repartir como se quiera entre los procesadores.
? Si no es así: ? si todas las dependencias son hacia adelante, sincronizarlas mediante barreras. ? si van hacia adelante y hacia atrás, sincronizarlas punto a punto (contadores o vectores de eventos). ? intentar alguna transformación del bucle para llevar a distancia 0 las dependencias. Bucles con y sin sincron.
Ejemplos do i = 0, N-1 C(i) = C(i) * C(i) A(i) = C(i) + B(i) D(i) = C(i) / A(i) enddo doall i = 0, N-1 C(i) = C(i) * C(i) A(i) = C(i) + B(i) D(i) = C(i) / A(i) enddoall (Gp:) 1 (Gp:) 2 (Gp:) 3 (Gp:) C, 0 (Gp:) A, 0
(Gp:) i=0 1 2 3
Ejemplos do i = 1, N-1 C(i) = C(i) * C(i) A(i) = C(i) + B(i) D(i) = C(i-1) / A(i) enddo forall i = 1, N-1 C(i) = C(i) * C(i) A(i) = C(i) + B(i) BARRERA (…) D(i) = C(i-1) / A(i) endforall (Gp:) i=1 2 3 4
(Gp:) barrera
(Gp:) 1 (Gp:) 2 (Gp:) 3 (Gp:) C, 0 (Gp:) A, 0 (Gp:) C, 1
Ejemplos do i = 1, N-1 C(i) = C(i) * C(i) A(i) = C(i) + B(i) D(i) = C(i-1) / A(i) enddo (Gp:) i=1 2 3 4
(Gp:) barrera
doall i = 1, N-1 C(i) = C(i) * C(i) A(i) = C(i) + B(i) enddoall [ BARERRA (…) ] doall i = 1, N-1 D(i) = C(i-1) / A(i) enddoall (Gp:) 1 (Gp:) 2 (Gp:) 3 (Gp:) C, 0 (Gp:) A, 0 (Gp:) C, 1
Vectores de eventos no ordena las dependencias mucho espacio en memoria Ejemplos do i = 2, N-2 A(i) = B(i-2) + 1 B(i+1) = A(i-2) * 2 enddo (Gp:) 1 (Gp:) 2 (Gp:) A,2 (Gp:) B,3
(Gp:) 1 1 1 . . .
2 2 2 . . .
1 1 1
2 2 2 (Gp:) i=2 3 4 5 6 7
doacross i = 2, N-2
wait (vB,i-3) A(i) = B(i-2) + 1 post (vA,i)
wait (vA,i-2) B(i+1) = A(i-2) * 2 post (vB,i)
enddoacross
Ejemplos do i = 2, N-2 A(i) = B(i-2) + 1 B(i+1) = A(i-2) * 2 enddo doacross i = 2, N-2
wait (vB,i-3) A(i) = B(i-2) + 1 post (vA,i)
wait (vA,i-2) B(i+1) = A(i-2) * 2 post (vB,i)
enddoacross (Gp:) 1 (Gp:) 2 (Gp:) A,2 (Gp:) B,3
(Gp:) , 3
(Gp:) 12 13 14
22 23 24
15 16 17
25 26 27
… (Gp:) P0 P1 P2
Ejemplos do i = 2, N-2 A(i) = B(i-2) + 1 B(i+1) = A(i-2) * 2 enddo (Gp:) 1 (Gp:) 2 (Gp:) A,2 (Gp:) B,3
(Gp:) 12 13 14
22 23 24
15 16 17
25 26 27
… (Gp:) P0 P1 P2
doacross i = 2, N-2,3
A(i) = B(i-2) + 1 wait (KA, i-1) post (KA)
B(i+1) = A(i-2) * 2
enddoacross Contadores ordena las dependencias sin problemas de espacio en memoria
1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 ? En general, los bucles de dependencias siempre son problemáticos y hay que analizar detenidamente qué se gana y qué se pierde (coste de la sincronización, problemas de acceso a cache…). (Gp:) 1 (Gp:) 2 (Gp:) C,1 (Gp:) D,2
> Alternativas para el ejemplo — wait / post ?? — 3 procesos independientes ?? — ejecución serie ?? Ejemplos
Optimizaciones 0. Deshacer la definición de constantes y las variables de inducción.
1. Eliminar todas las dependencias que no son intrínsecas al bucle. Por ejemplo: do i = 0, N-1 X = A(i) * B(i) C(i) = SQRT(X) D(i) = X – 1 enddo doall i = 0, N-1 X(i) = A(i) * B(i) C(i) = SQRT(X(i)) D(i) = X(i) – 1 enddoall (Gp:) convertir X en una variable privada
Optimizaciones 2. Fisión del bucle. Si una parte del bucle hay que ejecutarla en serie, romper el bucle convenientemente y ejecutar lo que sea posible en paralelo. do i = 1, N-1 A(i) = A(i-1) / 2 D(i) = D(i) + 1 enddo do i = 1, N-1 A(i) = A(i-1) / 2 enddo
doall i = 1, N-1 D(i) = D(i) + 1 enddoall
Optimizaciones 3. Ordenar las dependencias (hacia adelante). do i = 1, N-1 A(i) = D(i-1) / 2 D(i) = C(i) + 1 enddo forall i = 1, N-1 D(i) = C(i) + 1 BARRERA (…) A(i) = D(i-1) / 2 endforall (Gp:) 1 (Gp:) 2 (Gp:) D, 1
(Gp:) 2………….1 2………1 2…….1
(Gp:) 1…2.. 1…2.. 1…2.. (Gp:) ??
Optimizaciones 4. Alinear las dependencias: peeling. do i = 1, N-1 A(i) = B(i) C(i) = A(i-1) + 2 enddo (Gp:) 1 (Gp:) 2 (Gp:) A, 1
doall i = 1, N-2 A(i) = B(i) C(i+1) = A(i) + 2 enddoall C(1) = A(0) + 2 A(N-1) = B(N-1)
Optimizaciones do i = 2, N-1 A(i) = B(i) C(i) = A(i-1) + A(i-2) enddo (Gp:) 1 (Gp:) 2 (Gp:) A, 2 (Gp:) A, 1
C(2) = A(1) + A(0) C(3) = B(2) + A(1)
doall i = 2, N-3 A(i) = B(i) X(i+1) = B(i+1) C(i+2) = X(i+1) + A(i) enddoall
A(N-2) = B(N-2) A(N-1) = B(N-1) do i = 2, N-1 A(i) = B(i) X(i) = B(i) C(i) = X(i-1) + A(i-2) enddo (Gp:) 1’ (Gp:) 2 (Gp:) A, 2 (Gp:) X, 1 (Gp:) 1
Optimizaciones 5. Generar hilos independientes do i = 0, N-3 A(i+1) = B(i) + 1 B(i+2) = A(i) * 3 C(i) = B(i+2) – 2 enddo B(2) = A(0) * 3 C(0) = B(2) – 2
doall k = 0, 2 do i = pid, N-4, 3 A(i+1) = B(i) + 1 B(i+3) = A(i+1) * 3 C(i+1) = B(i+3) – 2 enddo enddoall
A(N-2) = B(N-3) + 1 (Gp:) 1 (Gp:) 2 (Gp:) 3 (Gp:) B,0 (Gp:) B,2 (Gp:) A,1
1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3
Optimizaciones 6. Minimizar la sincronización do i = 2, N-1 B(i) = B(i) + 1 C(i) = C(i) / 3 A(i) = B(i) + C(i-1) D(i) = A(i-1) * C(i-2) E(i) = D(i) + B(i-1) enddo (Gp:) 1 (Gp:) 2 (Gp:) 3 (Gp:) B,0 (Gp:) B,1 (Gp:) A,1 (Gp:) 4 (Gp:) 5 (Gp:) C,1 (Gp:) C,2 (Gp:) D,0
doacross i = 2, N-1 B(i) = B(i) + 1 C(i) = C(i) / 3 post (vC,i)
wait (vC,i-1) A(i) = B(i) + C(i-1) post (vA,i)
wait (vA,i-1) D(i) = A(i-1) * C(i-2) E(i) = D(i) + B(i-1) enddoacross (Gp:) 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 (Gp:) i=2
3
4 …
Optimizaciones 7. Tratamiento de bucles: intercambio. (Gp:) do i do_par j
(Gp:) do_par i do j
(Gp:) do j do_par i
(Gp:) do_par j do i
Optimizaciones Ejemplo: do i = 1, N-1 do j = 0, N-1 A(i,j) = A(i-1,j) + 1 enddo enddo (Gp:) do i = 1, N-1
doall j = 0, N-1 A(i,j) = A(i-1,j) + 1 enddoall
enddo
(Gp:) j=0 1 2 3 (Gp:) i=1
2
3
4
Optimizaciones Ejemplo: (Gp:) doall j = 0, N-1
do i = 1, N-1 A(i,j) = A(i-1,j) + 1 enddo
enddoall
do i = 1, N-1 do j = 0, N-1 A(i,j) = A(i-1,j) + 1 enddo enddo (Gp:) j=0 1 2 3 (Gp:) i=1
2
3
4
Optimizaciones 8. Tratamiento de bucles: cambio de sentido. (Gp:) j=0 1 2 (Gp:) i=1
2
3
4
do i = 1, 100 do j = 0, 2 A(i,j) = A(i,j) – 1 D(i) = A(i-1,j+1) * 3 enddo enddo do j = 2, 0, -1
doall i = 1, 100 A(i,j) = A(i,j) – 1 D(i) = A(i-1,j+1) * 3 enddoall
enddo
Optimizaciones do j = 1, 2N-1 doall i = max(1,j-N+1), min(j,N) A(i,j-(i-1)) = A(i-1,j-(i-1)) + A(i,j-1-(i-1)) enddoall enddo 9. Skew do i = 1, N do j = 1, N A(i,j) = A(i-1,j) + A(i,j-1) enddo enddo
Optimizaciones 10. Otras optimizaciones típicas
Aumento del tamaño de grano y reduccción del overhead de la paralelización.
– Juntar dos bucles en uno (¡manteniendo la semántica!): fusión. – Convertir un bucle de dos dimensiones en otro de una sola dimensión: colapso o coalescencia. …
Reparto de tareas / iterac. ? ¿Cómo se reparten las iteraciones de un bucle entre los procesadores? Si hay tantos procesadores como iteraciones, tal vez una por procesador.
? Pero si hay menos (lo normal), hay que repartir. El reparto puede ser:
estático: en tiempo de compilación. dinámico: en ejecución.
Reparto de tareas / iterac. ? El objetivo: intentar que el tiempo de ejecución de los trozos que se reparten a cada procesador sea similar, para evitar tiempos muertos (load balancing). ? En todo caso, OJO con las dependencias (sincronización), el tamaño de grano, la localidad de los accesos y el coste del propio reparto.
Reparto de tareas / iterac. ? Planificación estática Qué ejecuta cada procesador se decide en tiempo de compilación. Es por tanto una decisión prefijada.
Cada proceso tiene una variable local que lo identifica, pid [0..P-1].
Dos opciones básicas: reparto consecutivo y reparto entrelazado.
Reparto de tareas / iterac. – No añade carga a la ejecución de los threads. – Pero no asegura el equilibrio de la carga entre los procesos. – Permite cierto control sobre la localidad de los accesos a cache. ? Consecutivo
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3 ? Entrelazado
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 principio = pid * N/P fin = (pid+1) * N/P – 1
do i = principio, fin … enddo do i = pid, N, P … enddo
Reparto de tareas / iterac. ? Equilibrio en el reparto de carga (Gp:) 1-20 (Gp:) 21-40 (Gp:) 41-60 (Gp:) 61-80 (Gp:) estático (fijo)
(Gp:) Tej
(Gp:) asignación dinámica de una nueva tarea
(Gp:) 1-10 (Gp:) 21-30 (Gp:) 11-20 (Gp:) 31-40
(Gp:) Tej
do i = 1, 80 if (A(i) > 0) calcular() enddo
Reparto de tareas / iterac. ? Planificación dinámica Para intentar mantener la carga equilibrada, las tareas se van escogiendo en tiempo de ejecución de un cola de tareas. Cuando un proceso acaba con una tarea (un trozo del bucle) se asigna un nuevo trozo.
Dos opciones básicas: los trozos que se van repartiendo son de tamaño constante o son cada vez más pequeños.
Reparto de tareas / iterac. Las iteraciones se reparten una a una o por trozos ? Self / Chunk scheduling Añade carga a la ejecución de los threads. Hay que comparar ejecución y reparto. LOCK (C); mia = i; i = i + Z; Z = 1 ? self UNLOCK (C); while (mia <= N-1)
endwhile do j = mia, min(mia+Z-1, N-1) … enddo LOCK (C) mia = i; i = i + Z; UNLOCK (C)
Reparto de tareas / iterac. Los trozos de bucle que se reparten son cada vez más pequeños según nos acercamos al final. ? Guided / Trapezoidal ? Guided : parte proporcional de lo que queda por ejecutar:
Zs = (N – i) / P (entero superior)
que equivale a:
Zi = Zi-1 (1 – 1/P)
Reparto de tareas / iterac. ? Trapezoidal: reduciendo el trozo anterior en una constante: Zi = Zi-1 – k (Gp:) op. de planificación (Gp:) Z1 (Gp:) Zn (Gp:) 1 (Gp:) n (Gp:) 2 (Gp:) i (Gp:) k (Gp:) Z2
Reparto de tareas / iterac. ? En general, el reparto dinámico busca un mejor equilibrio en el reparto de carga, pero:
– hay que considerar la carga que se añade (overhead), en relación al coste de las tareas que se asignan.
– hay que considerar la localidad en los accesos a los datos y los posibles problemas de falsa compartición.
Reparto de tareas / iterac. ? Ejemplo de reparto (1.000 iteraciones, 4 procesadores):
? chunk (Z = 100) 100 100 100 100 100 100 100 100 100 100 (10) ? guided quedan: 1000 750 562 421 … 17 12 9 6 4 3 2 1 se reparten: 250 188 141 106 … 5 3 3 2 1 1 1 1 (22)
? trapezoidal (Z1 = 76, Zn = 4 >> k = 3) 76 73 70 67 … 16 13 10 7 4 (25)
Paralelismo de función ? Paralelismo a nivel de procedimiento o función:
(Gp:) F2 (Gp:) F3 (Gp:) F1 (Gp:) F4 (Gp:) F5
– modelo Fork / Join – Parallel sections
Fork F1 F2 Join
Fork F3 F4 Join F5 doall k = 0, 1 if (pid = 0) then F1 if (pid = 1) then F2 endoall [barrera]
doall k = 0, 1 if (pid = 0) then F3 if (pid = 1) then F4 endoall F5
? El objetivo de un sistema de P procesadores es ejecutar el código P veces más rápido. ? Problemas (algunos): – ¿puede ejecutarse todo el código en paralelo? ¿está bien repartida la carga? – ¿dónde están los datos? ¿cuál es el coste de la transmisión de datos? – ¿cuál es el coste de la sincronización? – ¿es eficiente el uso de la memoria cache? Rendimiento
? Ejecución en un procesador (código serie, no la versión paralela de 1 procesador) ? Ts
Ejecución en P procesadores ? Tp fa = Ts / Tp ? límite P ideal: crecer linealmente con P
efic = fa / P ? límite 1 ideal: constante Rendimiento
La parte más lenta (serie) en la ejecución de un pro-grama marcará la velocidad de ejecución del mismo. Serie Ts ? Paralelo Ts / P Parte en paralelo (f), pero parte en serie (1-f) fa (speed-up) = Ts / Tp = Ts / (f*Ts/P + (1-f)Ts) = 1 / (1-f) (máximo) = independiente de P! ? ¿Es todo el código paralelizable? En general, no.
– Ley de Amdahl (tamaño constante) Rendimiento
Rendimiento
– Ley de Gustafson (tiempo constante) En muchos casos, se utiliza el paralelismo no para ir más rápido, sino para ejecutar tareas de mayor tamaño. fa = (1-f) + f*p (Gp:) f*Ts (Gp:) (1-f)*Ts (Gp:) f*Ts*p (Gp:) (1-f)*Ts (Gp:) (1-f)*Ts (Gp:) mayor tamaño (Gp:) p procesadores (Gp:) f*Ts
Rendimiento
? A la fracción de código en paralelo, hay que añadirle una serie de overheads; por ejemplo, la comunicación debida al reparto o recolección de datos en unos casos y a la sincronización de procesos en otros. (Gp:) T_ej
(Gp:) T_com
(Gp:) n. de procesadores (Gp:) T_total
Tp = Ts / P + Tcom(P) Rendimiento
? Load balancing
Otra fuente típica de perdida de eficiencia en la ejecución en paralela es el reparto no equilibrado de tareas. Ejemplo: 6 tareas independientes, de peso equivalente, ? entre 3 procesadores Tp = Ts/3 ? entre 4 procesadores Tp = Ts/3 Rendimiento
? No podemos olvidarnos de la memoria cache. Para que su uso sea eficiente, se necesita reutilizar los datos que se cargan (un bloque o line). Por ejemplo, si A(1) y A(2) están en posiciones consecutivas de memoria, tal vez sea conveniente que se procesen en el mismo procesador para aumentar la tasa de aciertos de la cache. ? Por otra parte, todos los overheads que añada la ejecución paralela hay que valorarlos en función del tamaño de grano, es decir en relación al tiempo de ejecución. Rendimiento
| Página siguiente |