Tema 2: Diseño de algoritmos paralelos

Motivación

Paralelizar es dividir el problema en subproblemas que se puedan resolver a la vez (concurrentes).

Objetivos del tema:

Desarrollar algoritmos paralelos de forma sistemática y metódica.
Depender menos de la "inspiración" del programador.
Partir de la definición del problema, no solo de "transformar el secuencial".

Es más complejo que el secuencial: hay que gestionar la concurrencia (comunicar y sincronizar), la asignación de datos y programas a procesadores, la escalabilidad… El rendimiento dependerá, entre otras cosas, de:

Balanceado: que todas las tareas tengan el mismo tamaño (misma carga por procesador).
Concurrencia: que se ejecuten todas a la vez.
Dependencias: minimizarlas.

Ejemplo ilustrativo

Cuatro bucles con coste por iteración de 1, 1, 3 y 2 FLOPs:

<span><span style="color: var(--shiki-color-text)">a </span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)"> </span><span style="color: var(--shiki-token-constant)">0.0</span><span style="color: var(--shiki-color-text)">; b </span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)"> </span><span style="color: var(--shiki-token-constant)">0.0</span><span style="color: var(--shiki-color-text)">;</span></span>
<span><span style="color: var(--shiki-token-keyword)">for</span><span style="color: var(--shiki-color-text)"> (i</span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-token-constant)">0</span><span style="color: var(--shiki-color-text)">; i</span><span style="color: var(--shiki-token-keyword)">&lt;</span><span style="color: var(--shiki-color-text)">n; i</span><span style="color: var(--shiki-token-keyword)">++</span><span style="color: var(--shiki-color-text)">) a </span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)"> a </span><span style="color: var(--shiki-token-keyword)">+</span><span style="color: var(--shiki-color-text)"> x[i];</span><span style="color: var(--shiki-token-comment)">                 // 1 FLOP</span></span>
<span><span style="color: var(--shiki-token-keyword)">for</span><span style="color: var(--shiki-color-text)"> (i</span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-token-constant)">0</span><span style="color: var(--shiki-color-text)">; i</span><span style="color: var(--shiki-token-keyword)">&lt;</span><span style="color: var(--shiki-color-text)">n; i</span><span style="color: var(--shiki-token-keyword)">++</span><span style="color: var(--shiki-color-text)">) b </span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)"> b </span><span style="color: var(--shiki-token-keyword)">+</span><span style="color: var(--shiki-color-text)"> y[i];</span><span style="color: var(--shiki-token-comment)">                 // 1 FLOP</span></span>
<span><span style="color: var(--shiki-token-keyword)">for</span><span style="color: var(--shiki-color-text)"> (i</span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-token-constant)">0</span><span style="color: var(--shiki-color-text)">; i</span><span style="color: var(--shiki-token-keyword)">&lt;</span><span style="color: var(--shiki-color-text)">n; i</span><span style="color: var(--shiki-token-keyword)">++</span><span style="color: var(--shiki-color-text)">) z[i] </span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)"> x[i]</span><span style="color: var(--shiki-token-keyword)">/</span><span style="color: var(--shiki-color-text)">b </span><span style="color: var(--shiki-token-keyword)">+</span><span style="color: var(--shiki-color-text)"> y[i]</span><span style="color: var(--shiki-token-keyword)">/</span><span style="color: var(--shiki-color-text)">a;</span><span style="color: var(--shiki-token-comment)">       // 3 FLOPs</span></span>
<span><span style="color: var(--shiki-token-keyword)">for</span><span style="color: var(--shiki-color-text)"> (i</span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-token-constant)">0</span><span style="color: var(--shiki-color-text)">; i</span><span style="color: var(--shiki-token-keyword)">&lt;</span><span style="color: var(--shiki-color-text)">n; i</span><span style="color: var(--shiki-token-keyword)">++</span><span style="color: var(--shiki-color-text)">) y[i] </span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)"> (a</span><span style="color: var(--shiki-token-keyword)">+</span><span style="color: var(--shiki-color-text)">b)</span><span style="color: var(--shiki-token-keyword)">*</span><span style="color: var(--shiki-color-text)">y[i];</span><span style="color: var(--shiki-token-comment)">            // 2 FLOPs</span></span>
<span></span>

Secuencial: $T(n) = (2 + n + n + 3n + 2n)\,t_c \approx 7n\,t_c$ .

Con $p = 2$ se prueban varios repartos:

Reparto	$T(n, 2)$	Comentario
`a` y `b` en paralelo; después `z` y luego `y`, enteros	$\approx (1 + n + 3n + 2n)t_c \approx 6n\,t_c$	`z` necesita `a` y `b`, e `y` no puede modificarse hasta que `z` lo haya leído: solo se paralelizan las dos sumas
Además, `z` partido en dos mitades	$\approx \left(1 + n + \frac{3n}{2} + 2n\right)t_c \approx \frac{9n}{2}t_c$	El bucle de `y` sigue esperando a las dos mitades de `z`
`z[i]` e `y[i]` fusionados en el mismo bucle y partido en dos mitades	$\approx \left(1 + n + \frac{5n}{2}\right)t_c \approx \frac{7n}{2}t_c$	Mejor reparto: carga balanceada y sin espera entre `z` e `y`

La moraleja: hay que mirar a la vez el balanceo, la concurrencia y las dependencias. Esto se cuantifica con el grafo de dependencias (más abajo).

Estrategias

Esquemas o patrones algorítmicos. Un esquema sirve para muchos problemas y un problema puede combinar varios. De Algoritmia ya se conocen divide y vencerás, programación dinámica… Otros más específicos de paralelo:

Paralelismo de datos: Map, Reduce, Scan/Prefix, Stencil.
Pipeline (segmentación).
Task graph / DAG.
Granja de procesos / trabajadores replicados.

También grafos de dependencias y un enfoque metodológico (Foster).

Segmentación (pipeline) y sistólicos

Pipeline: conjunto ordenado de segmentos en el que la salida de uno es la entrada del siguiente. Varios segmentos pueden ejecutarse a la vez si sus salidas no afectan a las entradas de los otros.

Útil cuando:

Se ejecuta más de una instancia del problema.
Una serie de datos debe pasar por varias operaciones.
La información para el siguiente proceso está disponible antes de que la necesite.

Equidad en la granularidad

Todos los segmentos deben tener un coste parecido; el más lento marca el ritmo.

Sistema triangular

Secuencial:

para i=1 hasta n
  suma = 0
  para j=1 hasta i-1
    suma = suma + a[i][j]*x[j]
  x[i] = (b[i] - suma) / a[i][i]

\sum_{i=1}^{n}\Big(2 + \sum_{j=1}^{i-1} 1\Big) \approx \frac{1}{2}n^2 + \frac{3}{2}n

En pipeline, el proceso $P_i$ calcula $x[i]$ y necesita las salidas de $P_1, \dots, P_{i-1}$ :

Proceso pipeline(i)
  suma = 0
  para j=1 hasta i-1
    recibir x[j] de la izquierda; enviar x[j] a la derecha
    suma = suma + a[i][j]*x[j]
  x[i] = (b[i] - suma) / a[i][i]
  enviar x[i] a la derecha

Complejidad $O(n)$ : las comunicaciones y el cálculo del proceso más lento son de orden $n$ . El speedup es solo $\approx 0.37n$ (Lester) porque la granularidad no es equitativa (el último proceso trabaja mucho más que el primero).

Ordenación en pipeline

Cada $P_i$ guarda el mayor número que ha visto y pasa el resto a la derecha:

recibir(P(i-1), numero)
si (numero > x)
  enviar(P(i+1), x)
  x = numero
si no
  enviar(P(i+1), numero)

Complejidad $O(n)$ con $n$ procesadores. Comparado con el secuencial $O(n^2)$ equivalente, la eficiencia máxima es 0.5 (el óptimo secuencial es $O(n\log n)$ ).

Grafos de dependencias

Dependencias y condiciones de Bernstein

Las dependencias se obtienen analizando los datos que lee y escribe cada tarea. Sea $T_i$ anterior a $T_j$ , con $I$ el conjunto de variables leídas y $O$ el de escritas. $T_i$ y $T_j$ son independientes si y solo si:

I_j \cap O_i = \emptyset, \qquad I_i \cap O_j = \emptyset, \qquad O_j \cap O_i = \emptyset

Tipo	Condición	Significado
De flujo (verdadera)	$I_j \cap O_i \ne \emptyset$	$T_j$ lee lo que escribe $T_i$
Antidependencia	$I_i \cap O_j \ne \emptyset$	$T_j$ escribe algo que $T_i$ lee
De salida	$O_j \cap O_i \ne \emptyset$	Las dos escriben lo mismo

Dependencia de flujo entre iteraciones

<span><span style="color: var(--shiki-token-keyword)">for</span><span style="color: var(--shiki-color-text)"> (i</span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-token-constant)">1</span><span style="color: var(--shiki-color-text)">; i</span><span style="color: var(--shiki-token-keyword)">&lt;=</span><span style="color: var(--shiki-color-text)">n; i</span><span style="color: var(--shiki-token-keyword)">++</span><span style="color: var(--shiki-color-text)">) {</span></span>
<span><span style="color: var(--shiki-color-text)">  b[i] </span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)"> b[i] </span><span style="color: var(--shiki-token-keyword)">+</span><span style="color: var(--shiki-color-text)"> a[i</span><span style="color: var(--shiki-token-keyword)">-</span><span style="color: var(--shiki-token-constant)">1</span><span style="color: var(--shiki-color-text)">];</span></span>
<span><span style="color: var(--shiki-color-text)">  a[i] </span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)"> a[i] </span><span style="color: var(--shiki-token-keyword)">+</span><span style="color: var(--shiki-color-text)"> c[i];</span></span>
<span><span style="color: var(--shiki-color-text)">}</span></span>
<span></span>

La iteración $i$ modifica a[i], que lee la iteración $i+1$ . Reordenando el bucle (calcular a[i] y justo después b[i+1], sacando el primer y último término fuera) la dependencia queda dentro de cada iteración y las iteraciones pasan a ser independientes:

<span><span style="color: var(--shiki-color-text)">b[</span><span style="color: var(--shiki-token-constant)">1</span><span style="color: var(--shiki-color-text)">] </span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)"> b[</span><span style="color: var(--shiki-token-constant)">1</span><span style="color: var(--shiki-color-text)">] </span><span style="color: var(--shiki-token-keyword)">+</span><span style="color: var(--shiki-color-text)"> a[</span><span style="color: var(--shiki-token-constant)">0</span><span style="color: var(--shiki-color-text)">];</span></span>
<span><span style="color: var(--shiki-token-keyword)">for</span><span style="color: var(--shiki-color-text)"> (i</span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-token-constant)">1</span><span style="color: var(--shiki-color-text)">; i</span><span style="color: var(--shiki-token-keyword)">&lt;=</span><span style="color: var(--shiki-color-text)">n</span><span style="color: var(--shiki-token-keyword)">-</span><span style="color: var(--shiki-token-constant)">1</span><span style="color: var(--shiki-color-text)">; i</span><span style="color: var(--shiki-token-keyword)">++</span><span style="color: var(--shiki-color-text)">) {</span></span>
<span><span style="color: var(--shiki-color-text)">  a[i] </span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)"> a[i] </span><span style="color: var(--shiki-token-keyword)">+</span><span style="color: var(--shiki-color-text)"> c[i];</span></span>
<span><span style="color: var(--shiki-color-text)">  b[i</span><span style="color: var(--shiki-token-keyword)">+</span><span style="color: var(--shiki-token-constant)">1</span><span style="color: var(--shiki-color-text)">] </span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)"> b[i</span><span style="color: var(--shiki-token-keyword)">+</span><span style="color: var(--shiki-token-constant)">1</span><span style="color: var(--shiki-color-text)">] </span><span style="color: var(--shiki-token-keyword)">+</span><span style="color: var(--shiki-color-text)"> a[i];</span></span>
<span><span style="color: var(--shiki-color-text)">}</span></span>
<span><span style="color: var(--shiki-color-text)">a[n] </span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)"> a[n] </span><span style="color: var(--shiki-token-keyword)">+</span><span style="color: var(--shiki-color-text)"> c[n];</span></span>
<span></span>

Algunas dependencias se pueden eliminar así; otras son difíciles.

Grafo de dependencias

Abstracción que expresa las dependencias entre tareas y, por tanto, su orden relativo de ejecución.

Es un grafo dirigido acíclico (DAG): nodos = tareas, aristas = de una tarea fuente a una destino.
Una arista significa "para ejecutar la tarea destino, antes tiene que haberse ejecutado la fuente".
A veces las aristas representan comunicaciones y se etiquetan con el volumen de datos.
Cada nodo se etiqueta con un valor proporcional a su coste computacional.
El mismo problema puede tener varios grafos según cómo se plantee.

Métricas:

Longitud de un camino: suma de los costes de sus nodos (y/o aristas).
Camino crítico $L(G)$ : el camino más largo (más costoso) entre cualquier nodo inicial y cualquier final. Es una cota inferior del tiempo paralelo.
Grado medio de concurrencia: número medio de tareas que se pueden ejecutar en paralelo.

M(G) = \sum_{i=1}^{N}\frac{c_i}{L(G)} = \frac{1}{L(G)}\sum_{i=1}^{N} c_i

con $N$ el número de nodos y $c_i$ el coste del nodo $i$ .

Máximo grado de concurrencia: número máximo de tareas que se pueden ejecutar simultáneamente.

Mínimo de 4 valores

Cuatro tareas $f^0(a), \dots, f^3(a)$ de coste 3 y tres tareas min de coste 1. Coste total $= 4 \cdot 3 + 3 \cdot 1 = 15$ .

Grafo (a), en árbol: dos min en paralelo y uno final. $L_a = 3 + 1 + 1 = 5$ , $M_a = 15/5 = 3$ .
Grafo (b), en cadena: cada min combina el resultado anterior con un valor nuevo. $L_b = 3 + 1 + 1 + 1 = 6$ , $M_b = 15/6 = 2.5$ .

El árbol tiene más concurrencia.

Aplicado al ejemplo ilustrativo de los cuatro bucles (coste total $7n$ ):

Versión	Camino crítico $L$	$M = 7n/L$
`z` y `y` enteros en tareas separadas	$n + 3n + 2n = 6n$	$7/6$ (≈ 14 % mejor que secuencial)
`z` partido en dos mitades	$n + \frac{3n}{2} + 2n = 4.5n$	$7/4.5$ (≈ 35 %)
`z` e `y` fusionados y partidos en dos	$n + \frac{5n}{2} = 3.5n$	$7/3.5 = 2$ (50 %)

Ejemplos

Evaluar $m$ polinomios y quedarse con el máximo: $s = \max_{i} P_i(b)$ con los coeficientes en las filas de una matriz $A$ . Una solución: (1) una tarea por polinomio, $c_i = P_i(b)$ ; (2) combinar los $c_i$ con una reducción.

Suma de vectores $x = v + w$ : no hay dependencias entre elementos. Con $p = n$ , cada procesador $i$ hace x[i] = v[i] + w[i]. Con $p < n$ , cada uno se encarga de un bloque.

Suma de un vector $s = \sum v_i$ (operador de reducción): con $p \le n$ y $n$ divisible entre $p$ , cada procesador suma su bloque de $n/p$ elementos, se espera a todos y uno combina las sumas parciales:

<span><span style="color: var(--shiki-token-comment)">// En cada procesador Proc = 0..p-1</span></span>
<span><span style="color: var(--shiki-color-text)">s[Proc] </span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)"> </span><span style="color: var(--shiki-token-constant)">0</span><span style="color: var(--shiki-color-text)">;</span></span>
<span><span style="color: var(--shiki-token-keyword)">for</span><span style="color: var(--shiki-color-text)"> (i </span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)"> n</span><span style="color: var(--shiki-token-keyword)">/</span><span style="color: var(--shiki-color-text)">p</span><span style="color: var(--shiki-token-keyword)">*</span><span style="color: var(--shiki-color-text)">Proc; i </span><span style="color: var(--shiki-token-keyword)">&lt;</span><span style="color: var(--shiki-color-text)"> n</span><span style="color: var(--shiki-token-keyword)">/</span><span style="color: var(--shiki-color-text)">p</span><span style="color: var(--shiki-token-keyword)">*</span><span style="color: var(--shiki-color-text)">(Proc</span><span style="color: var(--shiki-token-keyword)">+</span><span style="color: var(--shiki-token-constant)">1</span><span style="color: var(--shiki-color-text)">); i</span><span style="color: var(--shiki-token-keyword)">++</span><span style="color: var(--shiki-color-text)">)</span></span>
<span><span style="color: var(--shiki-color-text)">  s[Proc] </span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)"> s[Proc] </span><span style="color: var(--shiki-token-keyword)">+</span><span style="color: var(--shiki-color-text)"> v[i];</span></span>
<span><span style="color: var(--shiki-token-comment)">// &quot;esperar por todos aquí&quot;</span></span>
<span><span style="color: var(--shiki-token-keyword)">if</span><span style="color: var(--shiki-color-text)"> (Proc </span><span style="color: var(--shiki-token-keyword)">==</span><span style="color: var(--shiki-color-text)"> </span><span style="color: var(--shiki-token-constant)">0</span><span style="color: var(--shiki-color-text)">) {</span></span>
<span><span style="color: var(--shiki-color-text)">  sf </span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)"> s[</span><span style="color: var(--shiki-token-constant)">0</span><span style="color: var(--shiki-color-text)">];</span></span>
<span><span style="color: var(--shiki-color-text)">  </span><span style="color: var(--shiki-token-keyword)">for</span><span style="color: var(--shiki-color-text)"> (i</span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-token-constant)">1</span><span style="color: var(--shiki-color-text)">; i</span><span style="color: var(--shiki-token-keyword)">&lt;</span><span style="color: var(--shiki-color-text)">p; i</span><span style="color: var(--shiki-token-keyword)">++</span><span style="color: var(--shiki-color-text)">) sf </span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)"> sf </span><span style="color: var(--shiki-token-keyword)">+</span><span style="color: var(--shiki-color-text)"> s[i];</span></span>
<span><span style="color: var(--shiki-color-text)">}</span></span>
<span></span>

En OpenMP, a mano o con la cláusula de reducción:

<span><span style="color: var(--shiki-color-text)">sum </span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)"> </span><span style="color: var(--shiki-token-constant)">0</span><span style="color: var(--shiki-color-text)">;</span></span>
<span><span style="color: var(--shiki-token-keyword)">#pragma</span><span style="color: var(--shiki-color-text)"> </span><span style="color: var(--shiki-token-function)">omp</span><span style="color: var(--shiki-color-text)"> </span><span style="color: var(--shiki-token-function)">parallel</span><span style="color: var(--shiki-color-text)"> </span><span style="color: var(--shiki-token-function)">private</span><span style="color: var(--shiki-color-text)">(</span><span style="color: var(--shiki-token-function)">local_sum</span><span style="color: var(--shiki-color-text)">)</span></span>
<span><span style="color: var(--shiki-color-text)">{</span></span>
<span><span style="color: var(--shiki-color-text)">  local_sum </span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)"> </span><span style="color: var(--shiki-token-constant)">0</span><span style="color: var(--shiki-color-text)">;</span></span>
<span><span style="color: var(--shiki-color-text)">  </span><span style="color: var(--shiki-token-keyword)">#pragma</span><span style="color: var(--shiki-color-text)"> </span><span style="color: var(--shiki-token-function)">omp</span><span style="color: var(--shiki-color-text)"> </span><span style="color: var(--shiki-token-function)">for</span></span>
<span><span style="color: var(--shiki-color-text)">  </span><span style="color: var(--shiki-token-keyword)">for</span><span style="color: var(--shiki-color-text)"> (i</span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-token-constant)">0</span><span style="color: var(--shiki-color-text)">; i</span><span style="color: var(--shiki-token-keyword)">&lt;</span><span style="color: var(--shiki-color-text)">n; i</span><span style="color: var(--shiki-token-keyword)">++</span><span style="color: var(--shiki-color-text)">) local_sum </span><span style="color: var(--shiki-token-keyword)">+=</span><span style="color: var(--shiki-color-text)"> v[i];</span></span>
<span><span style="color: var(--shiki-color-text)">  </span><span style="color: var(--shiki-token-keyword)">#pragma</span><span style="color: var(--shiki-color-text)"> </span><span style="color: var(--shiki-token-function)">omp</span><span style="color: var(--shiki-color-text)"> </span><span style="color: var(--shiki-token-function)">atomic</span></span>
<span><span style="color: var(--shiki-color-text)">  sum </span><span style="color: var(--shiki-token-keyword)">+=</span><span style="color: var(--shiki-color-text)"> local_sum;</span></span>
<span><span style="color: var(--shiki-color-text)">}</span></span>
<span></span>
<span><span style="color: var(--shiki-color-text)">sum </span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)"> </span><span style="color: var(--shiki-token-constant)">0</span><span style="color: var(--shiki-color-text)">;</span></span>
<span><span style="color: var(--shiki-token-keyword)">#pragma</span><span style="color: var(--shiki-color-text)"> </span><span style="color: var(--shiki-token-function)">omp</span><span style="color: var(--shiki-color-text)"> </span><span style="color: var(--shiki-token-function)">parallel</span><span style="color: var(--shiki-color-text)"> </span><span style="color: var(--shiki-token-function)">for</span><span style="color: var(--shiki-color-text)"> </span><span style="color: var(--shiki-token-function)">reduction</span><span style="color: var(--shiki-color-text)">(+: </span><span style="color: var(--shiki-token-function)">sum</span><span style="color: var(--shiki-color-text)">)</span></span>
<span><span style="color: var(--shiki-token-keyword)">for</span><span style="color: var(--shiki-color-text)"> (i</span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-token-constant)">0</span><span style="color: var(--shiki-color-text)">; i</span><span style="color: var(--shiki-token-keyword)">&lt;</span><span style="color: var(--shiki-color-text)">n; i</span><span style="color: var(--shiki-token-keyword)">++</span><span style="color: var(--shiki-color-text)">) sum </span><span style="color: var(--shiki-token-keyword)">+=</span><span style="color: var(--shiki-color-text)"> v[i];</span></span>
<span></span>

Metodología de Foster

Referencia: I. Foster, Designing and Building Parallel Programs. Cuatro fases:

Descomposición (particionado): qué cálculos se paralelizan. Busca concurrencia y escalabilidad.
Comunicaciones: qué tienen que intercambiar las tareas.
Agrupación: juntar tareas para mejorar la localidad y el rendimiento.
Asignación (mapping): a qué procesador va cada tarea.

Las dos primeras piensan en concurrencia y escalabilidad (independientes de la máquina); las dos últimas en localidad y rendimiento.

1. Descomposición

Dividir en muchas tareas con un grado de concurrencia alto, pensando en un computador ideal sin limitaciones (flexibilidad). Puede ser estática (tareas creadas al inicio) o dinámica (en tiempo de ejecución).

Interesa:

Conjuntos disjuntos de cálculos y datos.
Que el número de tareas escale con el tamaño del problema.
Tareas de peso parecido que compartan pocos datos o cálculos.

Tipos:

Generales: del dominio, funcional y recursiva.
Específicos: explorativa, especulativa…
Mixtos: combinaciones.

Descomposición del dominio

Cuándo: cuando se puede aplicar el mismo conjunto de operaciones a los datos de cada subdominio.
Cómo: dividir los datos en subconjuntos pequeños y homogéneos y ver qué cálculo se aplica a cada uno. Cada tarea gestiona el cálculo sobre sus datos.
Dónde: datos de entrada, de salida, intermedios, por bloques… en 1-D, 2-D o 3-D.
Consejos: fijarse en los datos de mayor dimensión, más accedidos o que reflejen la evolución del problema. Subconjuntos disjuntos y de igual tamaño.

Ejemplos

Iteración sobre un vector (centrada en la salida): $X_i^{(k+1)} = \frac{X_{i-1}^{(k)} + X_i^{(k)} + X_{i+1}^{(k)}}{3}$ con extremos circulares ( $X_{-1} = X_{n-1}$ , $X_n = X_0$ ). La tarea $i$ calcula $X_i$ . Hay dependencias de flujo (necesita los vecinos de la iteración anterior) y antidependencias (no se puede sobrescribir antes de que los vecinos lean).
Producto escalar (centrada en la entrada): con $t$ tareas, cada tarea $i$ calcula $\sum_{j=in/t}^{(i+1)n/t - 1} x_j y_j$ y al final se hace una reducción.
Matriz por vector $x = A b$ con $p = n$ : por bloques centrado en la salida, la tarea $i$ calcula $X_i = \sum_j A_{ij} b_j$ ; o centrado en resultados intermedios, cada tarea calcula un $A_{ij} b_j$ y luego se suman en pipeline.

Descomposición funcional

Cuándo: cuando la resolución se divide en fases y cada fase ejecuta un algoritmo distinto.
Cómo: cada fase es una tarea. Después se reparten los datos que necesita cada tarea.
Consejo: si los conjuntos de datos son disjuntos, listo; si no (solapamiento, dependencias), mejor otro tipo de descomposición.
Ventajas: útil en problemas muy complejos; reduce la complejidad al paralelizar estructuras grandes con accesos múltiples.
Inconvenientes: menos flexible y menos escalable; una división no disjunta implica comunicaciones complejas.

Ejemplo: dados $m$ primos y una lista de $n$ enteros, quedarse con los múltiplos de todos los primos. Una cadena de filtros: "múltiplos de 2" → "múltiplos de 3" → … → "múltiplos de $p_m$ ".

Descomposición recursiva

Basada en divide y vencerás: la generación recursiva de subproblemas crea la concurrencia.

Cómo: dividir recursivamente hasta el caso base y combinar los resultados parciales (salvo en recursión final).
Dónde: trabajadores replicados con bolsa de tareas (tareas que cogen subproblemas de una estructura compartida), algoritmos recursivos, todo lo visto en Algoritmia.

Ejemplo, mínimo de una secuencia:

\text{MIN}(a_1, \dots, a_m) = \min\big(\text{MIN}(a_1, \dots, a_{m/2}),\; \text{MIN}(a_{m/2+1}, \dots, a_m)\big)

que da justo el grafo en árbol del ejemplo anterior.

Descomposición explorativa

Cuándo: búsqueda de soluciones en un espacio de estados.
Cómo: dividir dinámicamente el espacio de búsqueda y explorar cada parte con una tarea distinta (estructura de árbol).
Estrategia: generar niveles de estados desde el inicial y, cuando haya suficientes nodos, que cada tarea explore un conjunto distinto.
Casos: búsqueda exhaustiva (termina cuando no quedan nodos) o de primera solución (quien la encuentra avisa al resto y se acaba).

2. Comunicaciones

Las tareas pueden ejecutarse concurrentemente, pero no de forma independiente.

Etapas:

Definir, según la tecnología, la estructura de los canales y las tareas productoras y consumidoras.
Definir los tipos de mensajes de cada canal.

Particionado y comunicaciones van al revés:

Funcional: particionado complejo, comunicaciones simples.
Dominio: particionado simple, comunicaciones complejas.

Puede haber relaciones de sincronización y comunicación entre tareas que no aparecen en el grafo de dependencias.

Tipos de comunicaciones

Tipo	Descripción
Locales	Cada tarea solo habla con unas pocas "vecinas". Fáciles de definir: aristas + envío/recepción (paso de mensajes) o sincronización (memoria compartida)
Globales	Muchas tareas aportan datos a un cálculo común
Estáticas / dinámicas	Los interlocutores no cambian / sí cambian con el tiempo
Regulares	La estructura espacial permite una implementación eficiente
Otras	Síncronas/asíncronas, unilaterales/bilaterales, lectura/lectura-escritura

Ejemplo de comunicaciones locales: stencil en una malla

En cada iteración todos los elementos de una matriz se actualizan con sus 4 vecinos (descomposición del dominio, una tarea por elemento):

X[i,j]^{t+1} = \frac{4X[i,j]^t + X[i-1,j]^t + X[i+1,j]^t + X[i,j-1]^t + X[i,j+1]^t}{8}

Jacobi (todo con valores de la iteración $t$ ):

En cada tarea X[i,j]
  para t=1 hasta k
    enviar valor a cada vecino afectado
    recibir datos de los vecinos afectados
    actualizar valor

Fácil de paralelizar, todas las tareas concurrentes y carga balanceada:

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

(4 envíos, 4 recepciones y 6 FLOPs). Para simplificar la implementación en memoria compartida se puede usar padding (bordes extra).

Gauss-Seidel: usa los valores ya actualizados de arriba y de la izquierda:

X[i,j]^{t+1} = \frac{4X[i,j]^t + X[i-1,j]^{t+1} + X[i+1,j]^t + X[i,j-1]^{t+1} + X[i,j+1]^t}{8}

Ahora hay dependencias dentro de la iteración y las actualizaciones avanzan en diagonal:

Variante	Tiempo
Frente de onda (cada iteración espera a que termine la anterior)	$T \cong k'(n+m)\big(4(t_s+t_w) + 4(t_s+t_w) + 6t_c\big)$
Frente de onda encauzado (la iteración siguiente arranca detrás de la actual, en pipeline)	$T \cong (n+m)(\dots) + k'(\dots)$
Red-black (dos grupos de $n/2$ tareas sin dependencias internas, tipo tablero de ajedrez, que se actualizan alternativamente)	$T \cong 2k'\big(4(t_s+t_w) + 4(t_s+t_w) + 6t_c\big)$

El encauzado pasa de multiplicar a sumar el término $(n+m)$ ; red-black elimina ese término.

Ejemplo de comunicaciones globales: reducción

$S = \sum_{i=0}^{N-1} X_i$ :

Centralizado: una tarea recibe todo y suma. $\theta(n)$ , con gran componente secuencial: muy ineficiente. No basta con identificar pares productor-consumidor sueltos.
Distribuido en cadena: reparte el cálculo, pero sigue siendo $\theta(n)$ .
Divide y vencerás (árbol): $\theta(\log n)$ . El inconveniente es que el grado de concurrencia va disminuyendo en cada nivel.

3. Agrupación

Las prestaciones se degradan por dependencias, mucho tiempo secuencial, comunicaciones, mala distribución de la carga… Aumentar la granularidad de las tareas puede mejorar la eficiencia.

Agrupar vs. asignar

Comparten objetivos, pero en la agrupación se puede (o se debe) modificar el diseño; en la asignación solo se reparten las tareas entre procesadores físicos sin tocar el diseño.

Al agrupar se reducen las tareas para:

Limitar los costes de crear y destruir tareas.
Minimizar los retardos por interacción entre tareas (acceso local frente a remoto).

Qué maximizar y minimizar:

Maximizar el cálculo concurrente: tareas independientes en procesos distintos.
Minimizar la comunicación: tareas que se comunican mucho en el mismo proceso.
Minimizar el ocio: evitar fuentes de inactividad.

Estrategias:

Reducir el volumen de datos transferidos: distribución por bloques, agrupar tareas no concurrentes, guardar resultados temporales…
Reducir la frecuencia de interacciones: menos transferencias y más grandes. En paso de mensajes, menos mensajes y más largos; en memoria compartida, menos fallos de caché.

Preguntas abiertas: ¿cómo mantener la flexibilidad (escalabilidad)? ¿cómo aumentar la granularidad reduciendo comunicaciones? ¿qué tareas a qué procesos y en qué orden? El grafo de dependencias y el análisis de eficiencia son buenos puntos de partida.

Relación superficie / volumen

Las comunicaciones de una tarea son proporcionales a la superficie de su dominio.
El cálculo es proporcional a su volumen.

Objetivo: poca superficie y mucho volumen. Aparece en la descomposición del dominio. Aumentar la granularidad sin reducir la dimensionalidad del problema (con excepciones).

\frac{T_{\text{comunicación}}}{T_{\text{cálculo}}}

Malla 8×8 del stencil (6 FLOPs por punto)

Agrupación	Comunicaciones por iteración	Relación por tarea
64 tareas de 1 punto	$64 \times 8(t_s + t_w) = 512t_s + 512t_w$	$\dfrac{8(t_s+t_w)}{6t_c}$
4 bloques 2-D de 4×4	$4 \times 8(t_s + 4t_w) = 32t_s + 128t_w$	$\dfrac{8t_s + 32t_w}{96t_c}$
4 franjas 1-D de 2×8	$4 \times 4(t_s + 8t_w) = 16t_s + 128t_w$	$\dfrac{4t_s + 32t_w}{96t_c}$

Agrupar reduce mucho la comunicación. Las franjas envían menos mensajes (menos $t_s$ ), pero reducen la dimensionalidad: con más procesadores escalan peor que los bloques 2-D.

Replicación

Se puede replicar datos (en paso de mensajes) o cálculo y comunicaciones para ahorrar esperas. Por ejemplo, si varias tareas en distintos procesadores dependen de una tarea inicial $T_1$ , cada procesador puede ejecutar su propia copia de $T_1$ en lugar de esperar a recibir el resultado. En una reducción, replicar el cálculo permite que todos acaben con el resultado (ver hipercubo).

Tareas no concurrentes y flexibilidad

Agrupar tareas que no pueden ejecutarse a la vez reduce comunicaciones sin perder paralelismo.
Agrupar datos en bloques contiguos, agrupar tareas que se comunican mucho, usar datos locales para resultados intermedios.
Preservar la flexibilidad: agrupar solo pensando en el rendimiento puede limitar la escalabilidad (p. ej., pasar de una descomposición multidimensional a una sola dimensión). El número óptimo de tareas depende de $n$ , $p$ , el análisis teórico y el empírico.

4. Asignación

Decidir dónde y en qué orden se ejecuta cada cosa:

En el diseño: asignar o planificar tareas en procesos.
En ejecución: asignar procesos a procesadores.

Objetivo: minimizar el tiempo total de ejecución.

Cálculo: tareas concurrentes en procesadores distintos.
Comunicación: tareas que se comunican mucho en el mismo procesador o en vecinos.
Inactividad: minimizar el desequilibrio de carga y las esperas.

Estas estrategias entran en conflicto entre sí.

Desequilibrio de carga y esperas

Hay que equilibrar tanto cálculo como comunicaciones. Las esperas son dependencias que se ven en el grafo: asignar de forma balanceada no basta. En el ejemplo de clase, un reparto perfectamente balanceado de 9 tareas en 3 procesadores tarda más (16 unidades) que otro que respeta las dependencias y replica la tarea inicial (13 unidades).

Estrategias generales

	Estática (planificación determinista)	Dinámica
Cuándo se decide	Antes de ejecutar	En ejecución, centralizada o distribuida
Ventajas	Sencilla, sin sobrecarga en ejecución	Flexible, válida para arquitecturas heterogéneas, no hace falta conocer el comportamiento a priori
Inconvenientes	NP-completo en el caso general (mapping problem, Bokhari 1981)	Sobrecarga por las transferencias para tomar decisiones

Asignación estática en descomposición del dominio

Distribución por bloques: para estructuras regulares (vectores, matrices). Por filas, columnas, bloques de filas o columnas, bloques 2-D…
Subdivisión de grafos: para estructuras irregulares (mallas). Agrupar vértices de forma que cada subdominio tenga aproximadamente el mismo número y que haya el mínimo de aristas entre subdominios. Es NP-completo: se usan heurísticos.

Bisección recursiva: divide y vencerás sobre el cálculo para reducir las comunicaciones. Muy buen rendimiento en mallas.

Variante	Estrategia	Ventajas	Inconvenientes
Por coordenadas	Corta según las coordenadas físicas, por la mitad de una dimensión en cada paso	Barata; reparte bien el cálculo	No minimiza necesariamente las comunicaciones
No balanceada	Prueba las $p-1$ particiones $\left(\frac{1}{p}, \frac{p-1}{p}\right), \left(\frac{2}{p}, \frac{p-2}{p}\right), \dots$ y elige la menos costosa	Mejores comunicaciones	Más cara
De grafos	Usa la conectividad: identifica los vértices extremos y asigna el resto según la distancia; se repite hasta tener las tareas deseadas	Para mallas complejas y comunicaciones no estructuradas; reduce canales entre subdominios

Balanceo probabilístico: asignación aleatoria buscando equilibrar el cálculo. Simple, barato y escalable, pero puede ser malo para las comunicaciones. Para pocas comunicaciones locales.

Distribuciones cíclicas: variante del probabilístico que parte de una numeración. Asigna la tarea $i$ al proceso $i \bmod \text{dimensión}$ (dimensión = nodos de la malla, filas, columnas…).

Asignación estática en descomposición funcional

Con un grafo de dependencias estático y costes conocidos el problema vuelve a ser NP-completo, pero hay casos con soluciones óptimas o heurísticas conocidas.

Árbol binomial:

Un árbol binomial de orden $k$ tiene $2^k$ nodos y profundidad $k$ ; se forma uniendo dos de orden $k-1$ (la raíz es una de las dos raíces).
En un árbol binario con $p = 2^k$ hojas, la asignación óptima es un árbol binomial de $p$ procesos: se agrupan nodos de distintos niveles que tienen relación de dependencia.
Permite sumar $p$ valores en $\log p$ pasos (p. ej., la reducción final de un producto escalar).

Hipercubo: ¿y si todos deben acabar con el resultado (reducción con réplica)?

Método 1: subir por el árbol binomial hasta la raíz y bajar para difundir: $2\log p$ pasos.
Método 2: replicar comunicaciones y cálculo. Hipercubo de grado $d$ : $2^d$ nodos, cada uno con $d$ vecinos y distancia máxima $d$ . En cada paso cada nodo intercambia su valor con el vecino de una dimensión distinta y suma. En $\log p$ pasos todos tienen la suma.

Asignación dinámica

Puede ser centralizada o distribuida y necesita un mecanismo de detección de fin.

Basada en información local:

Para problemas en los que la carga cambia constantemente; no necesita conocimiento global.
Cada procesador compara periódicamente su carga con la de sus vecinos y les transfiere el exceso.
Barata, pero rinde peor que las anteriores.

Basada en algoritmos de planificación:

Para descomposición funcional con pocas comunicaciones locales.
Se mantiene una lista de tareas (centralizada o distribuida); las nuevas esperan a que se les asigne un procesador.
Modelos: gestor-trabajador (bien con pocos trabajadores), jerarquía de gestores-trabajadores (con gestores intermedios para evitar conflictos) y esquemas distribuidos (cada procesador con su lista).
Inconvenientes: complejidad al repartir el cálculo y el problema de detectar la parada en algoritmos totalmente distribuidos.