Problemas de aula resueltos

Teoría: Tema 1 - Evaluación de las prestaciones · Tema 2 - Diseño de algoritmos paralelos · Exámenes: Problemas de examen resueltos

Receta para cualquier problema de prestaciones

$T(n)$ secuencial: contar FLOPs × $t_c$ .
$T(n,p)$ : lo que tarda el procesador más cargado: su cálculo + sus comunicaciones. Cada mensaje cuesta $t_s + (\text{tamaño})\,t_w$ ; un envío y una recepción cuentan como dos mensajes (en el curso se suman, no se solapan).
Coste: $C = p\,T(n,p)$ .
Sobrecarga: $T_0 = C - T(n)$ . El término de cálculo se cancela si el reparto es perfecto: lo que queda en $T_0$ es lo que "sobra" (comunicaciones, desequilibrio, cálculo redundante).
Speedup y eficiencia: $S = T(n)/T(n,p)$ , $\;E = S/p$ . Truco: dividir numerador y denominador para dejar $E = \dfrac{1}{1 + T_0/T(n)}$ .
Escalabilidad (isoeficiencia): $W \propto K\,T_0$ , término a término ( $t_c$ , $t_s$ , $t_w$ ). Para cada uno despejar $W$ en función de $p$ :
- Si sale $W \in \theta(p)$ : óptima. $\theta(p\log p)$ : buena. $\theta(p^2)$ o peor: pobre.
- Si $n$ aparece igual en los dos lados y se cancela ( $1 \propto Kp$ ): no escala.
- Si el término no depende de $p$ : no afecta.
Ojo con las restricciones entre $n$ y $p$ (p. ej. $p = n$ o $p = n^2$ ): aunque $T_0$ sea 0, si $p$ no puede pasar de $n$ , el problema tiene que crecer como $W \ge p^2$ para usar más procesadores.

Evaluación de las prestaciones

Todos los problemas usan el mismo dominio: una matriz $n \times n$ , 1 FLOP por elemento, y cada elemento depende solo de sus vecinos de arriba y de abajo (la figura del enunciado es una malla con aristas solo verticales). Por tanto:

T(n) = n^2 t_c

Problema 1: una tarea por elemento ( $p = n^2$ )

Cada procesador actualiza un elemento (1 FLOP) e intercambia su valor con el vecino de arriba y el de abajo: 2 envíos + 2 recepciones = 4 mensajes de 1 dato.

T(n,p) = t_c + 4(t_s + t_w)

C(n,p) = p\,t_c + 4p(t_s + t_w) \qquad T_0(n,p) = \underbrace{p\,t_c - n^2 t_c}_{=0 \text{ porque } p = n^2} + 4p(t_s + t_w) = 4p(t_s + t_w)

S(n,p) = \frac{n^2 t_c}{t_c + 4(t_s + t_w)} \qquad E(n,p) = \frac{n^2 t_c}{n^2\big(t_c + 4(t_s+t_w)\big)} = \frac{t_c}{t_c + 4(t_s + t_w)}

Interpretación:

$T_0$ no tiene término en $t_c$ : el cálculo está perfectamente repartido.
La eficiencia no depende ni de $n$ ni de $p$ : es constante, así que el algoritmo es escalable sin hacer más cálculos (en isoeficiencia: $W \propto KW \Rightarrow 1 \propto K$ , no depende de $p$ ). El tiempo paralelo también es constante.
Pero la eficiencia es malísima: con $t_s = 10^{-5}$ , $t_w = 10^{-6}$ , $t_c = 10^{-7}$ sale $E = \frac{10^{-7}}{4.41 \cdot 10^{-5}} \approx 2.27 \cdot 10^{-3}$ y $T(n,p) = 4.41 \cdot 10^{-5}$ s. Cada tarea hace 1 FLOP y 4 mensajes: la granularidad es demasiado fina. Hay que agrupar.

Escalable no significa eficiente

Una eficiencia constante pero de 0.002 es escalable y, aun así, un diseño inútil.

Problema 2: agrupar por filas y por columnas ( $p = n$ )

Por filas. Cada procesador tiene una fila completa ( $n$ elementos). Las dependencias son verticales, así que necesita la fila de arriba y la de abajo: 4 mensajes de $n$ datos.

T(n,p) = n\,t_c + 4(t_s + n\,t_w)

C = p\,n\,t_c + 4p(t_s + n\,t_w) \qquad T_0 = 4p(t_s + n\,t_w)

E = \frac{1}{1 + \dfrac{4p(t_s + n t_w)}{n^2 t_c}} \overset{p=n}{=} \frac{1}{1 + \dfrac{4(t_s + n t_w)}{n\,t_c}} \;\xrightarrow{\;n\to\infty\;}\; \frac{1}{1 + \dfrac{4t_w}{t_c}}

La eficiencia sube con $n$ pero se estanca en $1/(1 + 4t_w/t_c)$ (con los valores de antes, $1/41 \approx 0.0244$ ). En términos de Kumar escala pobremente: $W = n^2 = p^2$ .

Por columnas. Cada procesador tiene una columna completa. Como las dependencias son verticales, todas quedan dentro de la columna: no hay comunicaciones.

T(n,p) = n\,t_c \qquad C = p\,n\,t_c = n^2 t_c \qquad T_0 = 0 \qquad S = n = p \qquad E = 1

Es el diseño ideal en cuanto a eficiencia, pero como $p = n$ y $W = n^2$ , para usar más procesadores el problema tiene que crecer como $W = O(p^2)$ .

La lección del problema 2

Agrupa en la dirección de las dependencias. Si las dependencias van en vertical, las columnas las contienen enteras y la relación superficie/volumen es 0. Por filas cortas justo las dependencias.

En la gráfica de eficiencia escalada de clase (diapositiva 7), con $p = n$ las dos curvas caen, y la de filas queda por encima de la de columnas. Con $p = n$ atado, ninguna de las dos mantiene el tiempo al multiplicar $W$ y $p$ por el mismo factor. El arreglo es el problema 4: desatar $p$ de $n$ .

Problema 3: columnas + carga/descarga de datos ( $p = n$ )

Ahora se cuenta repartir la matriz y recogerla. Un procesador envía a los otros $p-1$ su columna ( $n$ datos) uno a uno (P2P no optimizado), y al final se recoge igual: $2(p-1)$ mensajes de $n$ datos.

T(n,p) = 2(p-1)(t_s + n\,t_w) + n\,t_c \cong 2p(t_s + n\,t_w) + n\,t_c

C \cong 2p^2(t_s + n\,t_w) + p\,n\,t_c \qquad T_0 \cong 2p^2(t_s + n\,t_w)

E \cong \frac{n^2 t_c}{p\big(2p(t_s + nt_w) + nt_c\big)} \overset{p=n}{=} \frac{t_c}{2(t_s + n\,t_w) + t_c}

Isoeficiencia (con $W = n^2$ ):

$t_s$ : $n^2 = W \propto Kp^2$ → escalable pero no óptimo (cuadrática).
$t_w$ : $n^2 = W \propto K\,p^2 n = K\,W^{1/2}p^2 \Rightarrow W^{1/2} \propto Kp^2 \Rightarrow W \propto K^2 p^4$ → escalabilidad muy pobre.

Lección: la distribución secuencial desde un nodo arruina un diseño que sin ella era perfecto. En la comparativa de clase, "columnas + E/S" es con diferencia la peor curva.

Problema 4: columnas con $p < n$

Cada procesador tiene $n/p$ columnas (bloques de columnas consecutivas). Sigue sin haber comunicaciones:

T(n,p) = \frac{n^2}{p}t_c \qquad C = n^2 t_c \qquad T_0 = 0 \qquad S = p \qquad E = 1

Es la generalización del caso por columnas. Ahora $p$ ya no está atado a $n$ : mientras $p \le n$ , es perfecto.

Problema 5: filas con $p < n$

Cada procesador tiene $n/p$ filas consecutivas. Solo las filas de los bordes del bloque tienen que comunicarse (con el bloque de arriba y el de abajo): siguen siendo 4 mensajes de $n$ datos, pero ahora con mucho más cálculo por procesador.

T(n,p) = \frac{n^2}{p}t_c + 4(t_s + n\,t_w) \qquad C = n^2 t_c + 4p(t_s + n\,t_w) \qquad T_0 = 4p(t_s + n\,t_w)

E = \frac{n^2 t_c}{n^2 t_c + 4p(t_s + n\,t_w)} = \frac{1}{1 + 4p\left(\dfrac{t_s}{n^2 t_c} + \dfrac{t_w}{n\,t_c}\right)}

$t_s$ : $n^2 = W \propto Kp$ → escalable óptimo.
$t_w$ : $n^2 = W \propto K\,p\,n = K W^{1/2} p \Rightarrow W \propto K^2 p^2$ → no óptimo, isoeficiencia cuadrática.

La eficiencia escalada baja despacio (≈ 0.55 con $p = 512$ ): mucho mejor que con $p = n$ .

Problema 6: el problema 4 + carga/descarga

Repartir los bloques de $n^2/p$ datos desde un nodo y recogerlos, P2P no optimizado:

T(n,p) = 2(p-1)\left(t_s + \frac{n^2}{p}t_w\right) + \frac{n^2}{p}t_c \cong 2p\left(t_s + \frac{n^2}{p}t_w\right) + \frac{n^2}{p}t_c

C \cong 2p^2 t_s + 2p\,n^2 t_w + n^2 t_c \qquad T_0 \cong 2p^2 t_s + 2p\,n^2 t_w

E \cong \frac{n^2 t_c}{2p^2 t_s + 2p\,n^2 t_w + n^2 t_c}

$t_s$ : $W \propto Kp^2 \in O(p^2)$ .
$t_w$ : $W = n^2 \propto K\,p\,n^2 \Rightarrow 1 \propto Kp$ → $n$ se cancela: no es escalable. Por mucho que crezca la matriz, el reparto cuesta tanto como el propio problema.

(En la diapositiva hay una errata en el paso intermedio de $E$ , que pone $n\,t_c$ donde debería poner $n^2 t_c$ ; el resultado final es el correcto.)

Problema 7: el problema 5 + carga/descarga

T(n,p) = 2(p-1)\left(t_s + \frac{n^2}{p}t_w\right) + \frac{n^2}{p}t_c + 4(t_s + n\,t_w) \cong \frac{n^2}{p}t_c + 2t_s(p+2) + 2t_w(n^2 + 2n)

T_0 = 2p\,t_s(p+2) + 2p\,t_w(n^2 + 2n)

E \cong \frac{1}{1 + \dfrac{2p^2 t_s}{n^2 t_c} + \dfrac{4p\,t_w}{n\,t_c} + \dfrac{2p\,t_w}{t_c}}

$t_s$ : $W \propto Kp^2$ .
$t_w$ : $W \propto K\,W\,p \Rightarrow 1 \propto Kp$ → no escala (el término $2p\,t_w/t_c$ de $E$ no depende de $n$ ).

Comparativa final (eficiencia escalada)

Diseño	Comportamiento
Bloques de columnas, $p < n$	$E_{sca} = 1$ : perfecto
Bloques de filas, $p < n$	Baja muy despacio
Filas, $p = n$	Baja más rápido
Columnas, $p = n$	Baja todavía más
Cualquiera + E/S	Se desploma: no escala

Diseño de algoritmos paralelos

Problema 1: procesado de $n$ imágenes en 5 fases

Enunciado: $n \gg 1$ imágenes; cada una pasa, en orden, por lectura, corrección de brillo, detección de bordes, compresión y almacenamiento. $p$ procesadores. Aplicar las dos primeras etapas de Foster y decir qué patrón describe la solución.

1. Descomposición: funcional. El trabajo sobre cada imagen se divide en fases que hacen operaciones distintas. Se definen 5 tipos de tareas: $T_L$ (lectura), $T_B$ (brillo), $T_E$ (bordes), $T_C$ (compresión) y $T_A$ (almacenamiento). Para cada imagen $I_i$ :

T_L(I_i) \to T_B(I_i) \to T_E(I_i) \to T_C(I_i) \to T_A(I_i)

2. Comunicaciones: locales, estáticas y regulares: cada fase envía la imagen procesada solo a la siguiente. No hay dependencias entre imágenes distintas.

Patrón: pipeline (segmentación). Mientras $T_B$ trata la imagen 1, $T_L$ ya lee la imagen 2, etc. Una vez lleno el cauce, sale una imagen por "ciclo".

¿Y si $n$ es pequeño o las fases tienen costes muy distintos?

$n$ pequeño: el tiempo de llenado y vaciado del pipeline pesa mucho; con pocas imágenes casi nunca están las 5 fases trabajando a la vez.
Costes desiguales: la fase más lenta marca el ritmo y las demás esperan (falta de equidad en la granularidad).
Alternativas: descomposición del dominio sobre las imágenes (granja de procesos / trabajadores replicados: cada procesador hace las 5 fases de imágenes distintas, con reparto dinámico si los costes varían); replicar la fase lenta; agrupar fases baratas en un mismo procesador para equilibrar.

Problema 2: índice invertido sobre $n$ documentos

Enunciado: construir, para cada palabra, la lista de documentos donde aparece (p. ej. $casa \to \{D_0, D_7, D_{100}\}$ ). Dos primeras etapas y patrón.

1. Descomposición del dominio sobre los datos de entrada: se reparten los $n$ documentos entre las tareas.

2. Comunicaciones en tres fases:

Map: cada tarea procesa sus documentos de forma independiente y genera pares $(palabra, documento)$ . Sin comunicación.
Shuffle (redistribución): se reúnen todos los pares con la misma clave (palabra) en la misma tarea. Es una comunicación global, todos con todos (cada tarea puede tener pares para cualquier otra).
Reduce: cada tarea combina las listas de sus palabras y obtiene la parte del índice global (nuevo reparto de trabajo: ahora por palabras).

Patrón: MapReduce.

¿Problemas?

Desequilibrio: documentos de tamaños muy distintos y palabras con frecuencias muy desiguales (unas pocas palabras aparecen en casi todos los documentos), así que algunas tareas de reduce reciben muchísimo más trabajo.
Coste del shuffle: comunicación todos con todos, la más cara.
Mitigaciones: asignación dinámica (bolsa de tareas), repartir las claves con una función hash, combinar localmente antes del shuffle (enviar una lista por palabra y no un par por aparición: menos mensajes y más grandes).

Problema 3

Es el problema 22 del boletín de exámenes (normalización por filas). Está resuelto en Problemas de examen resueltos.

Problemas de aula resueltos

Receta para cualquier problema de prestaciones

Evaluación de las prestaciones

Problema 1: una tarea por elemento (p=n2p = n^2p=n2)

Problema 2: agrupar por filas y por columnas (p=np = np=n)

Problema 3: columnas + carga/descarga de datos (p=np = np=n)

Problema 4: columnas con p<np < np<n

Problema 5: filas con p<np < np<n