Tema 1: Evaluación de las prestaciones

Antecedentes

En Algoritmia se analizaba la eficiencia de algoritmos secuenciales con un enfoque monovariable (solo la talla $n$ ). Aquí se reutilizan esos modelos y se amplían a algoritmos paralelos, donde el tiempo depende también del número de procesadores $p$ .

Tiempo de ejecución secuencial: tiempo que tarda el programa en una sola unidad de proceso (procesador o core). Depende de la entrada, el compilador, el programador… pero se ignoran las constantes del sistema y se asume que solo depende de la talla: $T(n)$ .

En el análisis a priori se cuentan FLOPs (no pasos).
En el análisis a posteriori se mide tiempo (segundos).

Sumatorios que aparecen continuamente:

\sum_{i=1}^{n} 1 = n \qquad \sum_{i=1}^{n} i \approx \frac{n^2}{2} \qquad \sum_{i=1}^{n} i^2 \approx \frac{n^3}{3} \qquad \sum_{i=1}^{\log_b n} k \approx k\log_b n = k\frac{\log n}{\log b}

Ejemplos de conteo (1 FLOP por iteración interna):

<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)">)</span><span style="color: var(--shiki-token-comment)">            // T(n) = n^2 FLOPs</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)"> (j</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)">; j</span><span style="color: var(--shiki-token-keyword)">&lt;</span><span style="color: var(--shiki-color-text)">n; j</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 </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][j];</span></span>
<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)">)</span><span style="color: var(--shiki-token-comment)">            // T(n) ≈ n^2/2 + n/2 ≈ n^2/2 FLOPs</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)"> (j</span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)">i; j</span><span style="color: var(--shiki-token-keyword)">&lt;</span><span style="color: var(--shiki-color-text)">n; j</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 </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][j];</span></span>
<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)">)</span><span style="color: var(--shiki-token-comment)">            // T(n) ≈ n^3/3 FLOPs</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)"> (j</span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)">i; j</span><span style="color: var(--shiki-token-keyword)">&lt;</span><span style="color: var(--shiki-color-text)">n; j</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)">    </span><span style="color: var(--shiki-token-keyword)">for</span><span style="color: var(--shiki-color-text)"> (k</span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)">i; k</span><span style="color: var(--shiki-token-keyword)">&lt;</span><span style="color: var(--shiki-color-text)">n; k</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 </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][k];</span></span>
<span></span>

Por qué hace falta un modelo

El objetivo de un algoritmo paralelo es reducir el tiempo de ejecución: si el secuencial tarda $t(n)$ , con $p$ procesadores se busca (como máximo teórico) $t(n)/p$ . El rendimiento real es un conjunto de aspectos muy distintos (tiempo, productividad o throughput, latencia, portabilidad, escalabilidad…), $R(p, n, u, \dots)$ ; en este curso se simplifica a $R(p, n)$ .

Extrapolar observaciones no sirve

"Con 12 procesadores y $n = 100$ el speedup fue 10.8". ¿Y con 1000 procesadores? ¿Y con $n = 10$ ? ¿Y si las comunicaciones cuestan 10 veces más? Una medida aislada no responde. Con ecuaciones sí: dados $T_1 = n + \frac{n^2}{p}$ , $T_2 = n + \frac{n^2}{p} + 100$ y $T_3 = n + \frac{n^2}{p} + p^2$ , se puede estudiar cuál es mejor según $n$ y $p$ (el término $p^2$ de $T_3$ acaba dominando cuando crece $p$ ).

	Análisis a priori (teórico)	Análisis a posteriori (empírico)
Cuándo	En el diseño, independiente de la máquina	Sobre una implementación y máquina concretas
Sirve para	Elegir la mejor opción y descubrir las tallas adecuadas	Encontrar cuellos de botella, dependencias, conflictos… no vistos en el diseño
Herramientas	Las de Algoritmia ( $\theta$ , $O$ , $\Omega$ ) ampliadas	Medidas de tiempo

Lo recomendable es combinar ambos: saber modelizar y saber medir.

Parámetros absolutos y relativos

Absolutos: dan el coste real (muy importantes en tiempo real). Hay que normalizarlos y aun así no sirven para comparar algoritmos. Se usará el tiempo de ejecución, que es la base de los relativos.
Relativos: miden lo bien que el algoritmo aprovecha los recursos y permiten comparar algoritmos (paralelos y secuenciales). Se estudian coste, sobrecarga (overhead), eficiencia, speedup y escalabilidad.

Tiempo de ejecución paralelo

Definición: tiempo transcurrido desde que empieza el primer procesador hasta que termina el último.

Saber cuándo empieza o termina cada procesador no es trivial (es un orden parcial). Como en secuencial, admite análisis a priori y a posteriori. El modelo simplificado depende de la talla y del número de procesadores: $T(n, p)$ .

Primera aproximación:

T(n,p) = T_{ar}(n,p) + T_{co}(n,p)

con $T_{ar}$ el tiempo de cálculo (aritmético) y $T_{co}$ el de comunicaciones. En un diagrama de Gantt, cada procesador alterna computación, comunicación e inactividad; $T(n,p)$ es lo que tarda el más lento.

Segunda aproximación:

T(n,p) = T_{ar}(n,p) + T_{co}(n,p) - T_{sol}(n,p) + T_{ov}(n,p)

$T_{sol}$ : tiempo de solapamiento entre cálculo y comunicación.
$T_{ov}$ : tiempo de sobrecarga (esperas, creación de procesos…).

Tipo de algoritmo	Tiempo
Síncrono ( $T_{sol} = 0$ )	$T(n,p) = T_{ar} + T_{co} + T_{ov}$
Asíncrono	$T(n,p) = \max(T_{ar}, T_{co}) + T_{ov}$ , con $\frac{T_{ar}+T_{co}}{2} \le \max(T_{ar}, T_{co}) \le T_{ar}+T_{co}$

$T_{ov}$ y $T_{sol}$ son difíciles de estimar, así que en el curso se admite:

T(n,p) \cong T_{ar}(n,p) + T_{co}(n,p)

Para calcularlo: estudiar $T_{ar}$ y $T_{co}$ por separado y luego combinar, suponiendo una arquitectura paralela ideal.

Tiempo de cálculo $T_{ar}$

Tiempo que el algoritmo pasa haciendo cálculos. Se expresa en FLOPs (en segundos en el modelo empírico):

T_{ar}(n,p) = n\, t_c

donde $n$ es el número de FLOPs y $t_c$ el tiempo por FLOP.

Tiempo de comunicaciones $T_{co}$

Tiempo que pasa enviando mensajes (memoria distribuida, MD) o sincronizándose (memoria compartida, MC). Por simplicidad se usa el mismo modelo para ambos, y también para comunicaciones internas y externas.

Un intercambio entre dos procesos vecinos (P2P) cuesta:

T_{co}(n,p) = t_s + L\, t_w \qquad \text{(en la práctica } t_s + n\, t_w\text{)}

$L$ : tamaño del mensaje.
$t_s$ : latencia (start-up time).
$t_w$ : inversa del ancho de banda (tiempo por palabra).

$t_s \gg t_w$

Como la latencia domina, es mejor enviar un mensaje grande que muchos pequeños:

t_s + n\,t_w \ll n\,(t_s + t_w) = n\,t_s + n\,t_w

$t_s$ y $t_w$ pueden variar con la red o el tráfico; ese efecto no se considera.
El modelo P2P no vale para operaciones colectivas (difusiones, recolecciones…): se expresan en función de operaciones P2P.
En MC la sincronización se puede modelizar como mensajes de tamaño constante (coste constante) o en función de $p$ .

FLOP y rendimiento teórico

FLOP: una operación en coma flotante básica (suma, resta, multiplicación, división). El coste de otras operaciones en coma flotante se expresa en FLOPs, y el resto (aritmética entera, etc.) normalmente no se cuenta.

FLOPS (o FLOP/s, para no confundir): FLOPs por segundo.

Theoretical Peak Performance en doble precisión ( $TPP_{dp}$ ), en GFLOPS. Es una estimación muy optimista, pero útil en el diseño. Se acepta $TPP_{sp} = 2\, TPP_{dp}$ (simple precisión).

TPP_{dp} = \text{sockets} \times \text{cores}_{\text{socket}} \times \text{ciclos}_{\text{GHz}} \times \frac{\text{FLOPs}}{\text{ciclo}}

(con varios nodos se multiplica también por chasis y nodos por chasis). Los FLOPs por ciclo dependen de las extensiones vectoriales (SIMD):

Extensión	Factor (doble precisión)	Ejemplo
FMA (Fused Multiply-Add, $A = A \cdot B + C$ )	2
SSE (128 bits)	2 × nº unidades	Nehalem / Westmere: 4 FLOPs/ciclo
SSE2, AVX (256 bits)	4 × nº unidades	Sandy/Ivy Bridge: 8 FLOPs/ciclo
AVX2 (AVX + FMA)	8 × nº unidades	Haswell / Broadwell: 16 FLOPs/ciclo
AVX-512	8 × nº unidades	Knights Landing: 8 y 16 FLOPs/ciclo
AVX-512 + FMA	16 × nº unidades	Skylake-SP / Cascade Lake: 32 FLOPs/ciclo

Ejemplos (frecuencia base):

Modelo	Sockets	Cores/socket	GHz	FLOPs/ciclo (DP–SP)	$TPP_{dp}$ (GFLOPS)	$TPP_{sp}$
Xeon E5-2603 v4	2	6	1.7	16–32	326.4	652.8
Xeon E5620	2	4	2.4	4–8	76.8	153.6
i3-2100	1	2	3.1	8–16	49.6	99.2
Ryzen 7 3700X	1	8	2.2	16–32	281.6	563.2
AMD EPYC 7413	1	24	2.65	16–32	1017.6	2035.4

Por ejemplo, Xeon E5620: $2 \times 4 \times 2.4 \times 4 = 76.8$ GFLOPS.

Pico anunciado vs. rendimiento real

En el ejemplo de clase: pico anunciado (PAP) 5.00 TFLOPs, LINPACK 3.05 TFLOPs y rendimiento medio sostenido en aplicaciones reales (ASAP) solo 0.40 TFLOPs. Y la distancia entre PAP y ASAP ha ido creciendo con los años. Usar un sistema de forma eficiente es justo el objetivo de la asignatura.

Coste y sobrecarga

Coste:

C(n,p) = p\, T(n,p)

Un algoritmo es de coste óptimo si $C(n,p)$ es proporcional a $T(n)$ . Ejemplo: $T(n) = 100$ , $p = 10$ , $T(n,p) = 10 \Rightarrow C(n,p) = 100 = T(n)$ .

Sobrecarga (overhead): tiempo extra que los procesadores consumen entre todos respecto al mejor algoritmo secuencial.

T_0(n,p) = C(n,p) - T(n)

Speedup y eficiencia

Speedup: ganancia de velocidad del paralelo frente al secuencial.

S(n,p) = \frac{T(n)}{T(n,p)}

Cualquier algoritmo paralelo se puede simular en una máquina secuencial ejecutando sus pasos en serie (ignorando comunicaciones), así que:

T(n) \le p\, T(n,p) \;\Longrightarrow\; S(n,p) \le p

Si se usa como $T(n)$ el paralelo con un procesador, $T(n,1)$ , el speedup mide la bondad del diseño paralelo.
Si se usa el mejor secuencial conocido, mide la eficacia (prestaciones) real del algoritmo paralelo.

Speedup	Nombre	Causa
$S = p$	Lineal	Sin penalización por comunicaciones, sin dependencias, todos trabajan a la vez, carga balanceada
$S < p$	Sublineal	Dependencias de datos, el problema no se divide en $p$ partes concurrentes…
$S > p$	Superlineal	El secuencial no era óptimo, hay un error de cálculo o efectos colaterales (p. ej., cachés)

Eficiencia: grado de aprovechamiento del sistema (fracción de trabajo útil).

0 \le E(n,p) = \frac{S(n,p)}{p} = \frac{T(n)}{p\,T(n,p)} \le 1

Ejemplos

1. Producto de matrices secuencial

<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)">)</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)"> (j</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)">; j</span><span style="color: var(--shiki-token-keyword)">&lt;</span><span style="color: var(--shiki-color-text)">m; j</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)">    c[i][j] </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-color-text)">    </span><span style="color: var(--shiki-token-keyword)">for</span><span style="color: var(--shiki-color-text)"> (r</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)">; r</span><span style="color: var(--shiki-token-keyword)">&lt;</span><span style="color: var(--shiki-color-text)">k; r</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)">      c[i][j] </span><span style="color: var(--shiki-token-keyword)">+=</span><span style="color: var(--shiki-color-text)"> a[i][r] </span><span style="color: var(--shiki-token-keyword)">*</span><span style="color: var(--shiki-color-text)"> b[r][j];</span></span>
<span><span style="color: var(--shiki-color-text)">  }</span></span>
<span></span>

T(n,m,k) = \sum_{i=1}^{n}\sum_{j=1}^{m}\Big(1 + \sum_{r=1}^{k} 2\Big) t_c = nm\,t_c + 2nmk\,t_c \in \theta(nmk)

Con FMA la multiplicación y la suma cuentan como una sola operación: $nm\,t_c + nmk\,t_c$ .

2. Grafo de tareas

Cuatro tareas independientes $T_1$ – $T_4$ de coste 50 y una tarea final $T_5$ de coste 20 que depende de las cuatro. Secuencial: $T(n) = 4 \cdot 50 + 20 = 220$ .

$p$	$T(n,p)$	$C = pT(n,p)$	$T_0 = C - 220$	$S$	$E$
2	$100 + 20 = 120$	240	20	1.83	0.916
3	$100 + 20 = 120$	360	140	1.83	0.61
4	$50 + 20 = 70$	280	60	3.14	0.786
5	$50 + 20 = 70$	350	130	3.14	0.629

Con 3 procesadores una de las tareas de 50 sigue necesitando una segunda "ronda", así que no mejora respecto a 2. A partir de $p > 4$ : el tiempo y el speedup quedan constantes, el coste y la sobrecarga crecen y la eficiencia decrece ( $\lim_{p\to\infty} E = \lim \frac{cte}{p} = 0$ ). No compensa usar más de 4 procesadores. El área en la que los procesadores están parados es justo la sobrecarga.

Adelanto: cota de Brent

T(n,p) \lesssim \frac{T(n)}{p} + T_\infty(n,p)

donde $T_\infty$ es el tiempo del camino crítico (se ve en el tema siguiente).

3. Suma de un vector con $p = n/2$

<span><span style="color: var(--shiki-token-comment)">/* Secuencial */</span></span>
<span><span style="color: var(--shiki-color-text)">s </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)">) s </span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)"> s </span><span style="color: var(--shiki-token-keyword)">+</span><span style="color: var(--shiki-color-text)"> v[i];</span></span>
<span></span>
<span><span style="color: var(--shiki-token-comment)">/* Paralelo, en cada Pi con i = 0..(n/2)-1: reducción en árbol */</span></span>
<span><span style="color: var(--shiki-color-text)">in </span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)"> </span><span style="color: var(--shiki-token-constant)">2</span><span style="color: var(--shiki-token-keyword)">*</span><span style="color: var(--shiki-color-text)">i; des </span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)"> </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-token-keyword)">for</span><span style="color: var(--shiki-color-text)"> (k</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)">; k</span><span style="color: var(--shiki-token-keyword)">&lt;=</span><span style="color: var(--shiki-token-function)">log2</span><span style="color: var(--shiki-color-text)">(n) </span><span style="color: var(--shiki-token-keyword)">&amp;&amp;</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)"> des </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)">); k</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[in] </span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)"> a[in] </span><span style="color: var(--shiki-token-keyword)">+</span><span style="color: var(--shiki-color-text)"> a[in</span><span style="color: var(--shiki-token-keyword)">+</span><span style="color: var(--shiki-color-text)">des];</span></span>
<span><span style="color: var(--shiki-color-text)">  des </span><span style="color: var(--shiki-token-keyword)">=</span><span style="color: var(--shiki-color-text)"> des</span><span style="color: var(--shiki-token-keyword)">*</span><span style="color: var(--shiki-token-constant)">2</span><span style="color: var(--shiki-color-text)">;</span></span>
<span><span style="color: var(--shiki-color-text)">}</span></span>
<span></span>

$T(n) = (1 + n)\,t_c \cong n\,t_c$
$T(n,p) \cong 2\log_2 n\; t_c$
$C(n,p) = n\,t_c\log_2 n$ , $\quad T_0(n,p) = n\,t_c(\log_2 n - 1)$
$S(n,p) = \dfrac{n}{2\log_2 n}$ , $\quad E(n,p) = \dfrac{1}{\log_2 n}$

No es de coste óptimo: el coste crece como $n \log n$ frente a $n$ .

4. Suma con $2 \le p \le n/2$

Cada procesador suma primero su bloque de $n/p$ elementos y después se hace la reducción en árbol entre los $p$ resultados:

T(n,p) \cong \Big(\frac{n}{p} + 2\log_2 p\Big) t_c \qquad 2t_c\log_2 n \le T(n,p) \le \frac{n}{2}t_c

(los extremos son $p = n/2$ y $p = 2$ ). Con $n = 64$ , $p = 32$ : $T \cong 12\,t_c$ y $E \cong 1/6$ , la misma eficiencia que el algoritmo anterior. Con menos procesadores ( $p \ll n$ ) el término $n/p$ domina y la eficiencia mejora.

5. Algoritmo iterativo con matrices

Con $W, H, A \in \mathbb{R}^{n \times n}$ , cada producto de matrices cuesta $2n^3$ y $\circledast$ , $\oslash$ son producto y división elemento a elemento:

Repetir
  B = W^T W H
  C = W^T A
  H = H ⊛ C ⊘ B
  D = W H H^T
  E = A H^T
  W = W ⊛ E ⊘ D
Fin repetir

Hay 6 productos de matrices ( $2+1+2+1$ ) y 4 operaciones elemento a elemento:

T(n) = 2n^3(2+1+2+1)\,t_c + n^2(2+2)\,t_c = 12n^3 t_c + 4n^2 t_c

Modelos de rendimiento

Ley de Amdahl (tamaño fijo del problema)

Mide el speedup máximo alcanzable. El tiempo secuencial se divide en una parte no paralelizable $\alpha(n)$ y una paralelizable $\beta(n)$ :

T(n) = \alpha(n) + \beta(n) \qquad T(n,p) = \alpha(n) + \frac{\beta(n)}{p}

\lim_{p\to\infty}\frac{T(n)}{T(n,p)} = \lim_{p\to\infty}\frac{\alpha(n) + \beta(n)}{\alpha(n) + \frac{\beta(n)}{p}} = 1 + \frac{\beta(n)}{\alpha(n)}

Normalizando $\alpha(n) + \beta(n) = 1$ :

S(n,p) = \frac{p}{(p-1)\,\alpha(n) + 1} \le \frac{1}{\alpha(n)}

Paralelizable al 90 %: $S < 1/0.1 = 10$ , por muchos procesadores que se usen.
Paralelizable al 50 %: $S < 1/0.5 = 2$ .

Escrito con la fracción paralela $PF$ (en tantos por uno):

S(n,p) = \frac{1}{(1 - PF) + \dfrac{PF}{p}}

Rendimiento efectivo en doble precisión: el speedup de Amdahl por lo que da un solo core.

Re_{dp} = \frac{1}{(1 - PF) + \dfrac{PF}{p}} \times \text{ciclos}_{\text{GHz}} \times \frac{\text{FLOPs}}{\text{ciclo}}

Modelo	$TPP_{dp}$	$Re_{dp}$ ( $PF=0.99$ )	$PF = 0.95$	$PF = 0.90$	$PF = 0.75$
Xeon E5-2603 v4	326.4	294.1	210.6	155.4	87.0
Xeon Phi 31S1P	1003.0	306.8	81.2	42.3	17.4
i3-2100	49.6	49.1	47.2	45.1	39.7
AMD EPYC 7413	1017.6	827.3	473.3	308.4	150.8

Por ejemplo, Xeon E5-2603 v4 ( $p = 12$ , $PF = 0.99$ ): $S = 1/(0.01 + 0.99/12) \approx 10.81$ y $10.81 \times 1.7 \times 16 \approx 294.1$ .

Consecuencias de Amdahl

Con el tamaño del problema fijo (strong scaling), la eficiencia decrece al aumentar $p$ .
En programas reales el tiempo puede incluso aumentar al crecer $p$ (overhead, comunicaciones…), aunque el modelo teórico no lo refleje.
Para un tamaño fijo, a partir de cierto número de procesadores no compensa añadir más.
Una máquina con muchos cores lentos (Xeon Phi) se hunde en cuanto la fracción secuencial no es mínima.
Speedup y eficiencia dependen de $n$ y $p$ : las conclusiones pueden cambiar si cambia cualquiera de ellos.

Ley de Gustafson–Barsis

Speedup escalado:

S_G(W,p) = p - (p-1)\,f_s \qquad f_s = 1 - PF

donde $W$ es el tamaño computacional del problema.

Amdahl responde: ¿cuánto se puede acelerar un problema de tamaño fijo?
Gustafson responde: con más recursos, ¿cuánto más grande puede ser el problema manteniendo el tiempo aproximadamente constante?

Escalabilidad

Modelos de isorendimiento: caracterizan la escalabilidad manteniendo constante una métrica de rendimiento.

Isotiempo: se mantiene el tiempo; el recurso es el número de procesadores.
Isoeficiencia: se mantiene la eficiencia; el recurso es el número de procesadores.

Función de isoeficiencia: ¿cómo debe crecer el tamaño computacional $W$ en función de $p$ para que $E(n,p)$ sea constante?

Algoritmo escalable: aquel cuya función de isoeficiencia es lineal en $p$ . Cuanto menos tenga que crecer $W$ al aumentar $p$ , más escalable es.

Enfoque 1: fijar la eficiencia y despejar $W$

Ejemplo, con $W = n^3$ y $T(n) = c\,n^3 t_c$ :

Algoritmo	$T(n,p)$
A	$\left(\dfrac{c\,n^3}{p} + \dfrac{b\,n^2}{\sqrt{p}}\right)t_c$
B	$\left(\dfrac{2c\,n^3}{p} + \dfrac{b\,n^2}{2\sqrt{p}}\right)t_c$

E_A = \frac{1}{1 + \dfrac{b\sqrt{p}}{n\,c}} \qquad E_B = \frac{1}{2 + \dfrac{b\sqrt{p}}{2n\,c}}

Con $E = 1/3$ : ambos dan $n = \dfrac{b\sqrt{p}}{2c}$ , es decir, $W = \dfrac{b^3}{(2c)^3}\,p\sqrt{p}$ . Iguales.
Con $E = 1/4$ : A da $W = \dfrac{b^3}{(3c)^3}\,p\sqrt{p}$ y B da $W = \dfrac{b^3}{(4c)^3}\,p\sqrt{p}$ . Analíticamente distintos, pero asintóticamente equivalentes ( $\theta(p^{3/2})$ ).

Enfoque 2: Kumar et al.

Partiendo de la sobrecarga:

T_0(n,p) = p\,T(n,p) - T(n) \;\Rightarrow\; T(n,p) = \frac{T(n) + T_0(n,p)}{p}

E(n,p) = \frac{T(n)}{T(n) + T_0(n,p)} \;\Rightarrow\; T(n) = \frac{E}{1 - E}\,T_0(n,p)

Llamando $K = \dfrac{E}{1-E}$ (constante si $E$ lo es), la función de isoeficiencia es:

W = K\,T_0(W,p) \;\Rightarrow\; W = f(p)

Cómo se usa: se calcula $T_0$ y se analiza cada término por separado (el de $t_c$ , el de $t_s$ , el de $t_w$ ); la isoeficiencia del algoritmo es la del término que exige un crecimiento mayor. Los términos que no dependen de $p$ no afectan a la escalabilidad.

Ejemplo

$T(n) = \frac{2n^3}{3}t_c$ y $T_1(n,p) = \frac{n^3}{p}t_c + n\,t_s + \frac{n^2}{2}t_w$ , con $W = n^3$ .

T_{0}(n,p) = \frac{n^3}{3}t_c + t_s\,n\,p + \frac{n^2 p}{2}t_w

$t_c$ : no depende de $p$ → no afecta.
$t_s$ : $n^3 \propto Knp \Rightarrow W^{2/3} \propto Kp \Rightarrow W \propto (Kp)^{3/2} \in \theta(p^{3/2})$ .
$t_w$ : $n^3 \propto K\frac{n^2}{2}p \Rightarrow W^{1/3} \propto Kp \Rightarrow W \propto (Kp)^3 \in \theta(p^3)$ .

La isoeficiencia es $\theta(p^3)$ . Otras variantes del mismo problema dan $\theta(p^3)$ o $\theta((p\log p)^3)$ si las comunicaciones tienen un factor $\log p$ .

Ejemplo con dos casos

$T(n) = ZN^2 t_c$ y $T(n,p) = \frac{ZN^2}{p}t_c + 4(t_s + ZN\,t_w)$ :

T_0 = 4p\,t_s + 4p\,ZN\,t_w

$t_s$ : $W = ZN^2 \propto Kp \in \theta(p)$ .
$t_w$ con $Z = 1$ : $W = N^2 \propto KNp \Rightarrow W^{1/2} \propto Kp \Rightarrow W \in \theta(p^2)$ .
$t_w$ con $Z = N$ : $W = N^3 \propto KN^2p \Rightarrow W^{1/3} \propto Kp \Rightarrow W \in \theta(p^3)$ .

Enfoque 3: sobrecarga relativa

Mira cómo crece la sobrecarga respecto al mejor secuencial:

\frac{T_0(n,p)}{T(n)} = \frac{p\,T(n,p) - T(n)}{T(n)} \in O\!\left(\frac{p^r}{T(n)^s}\right) = O\!\left(\frac{p^r}{W^s}\right)

Si $r \le s$ el algoritmo escala óptimamente. Manteniendo constante la eficiencia sale $W \in O(p^{r/s})$ ; si $r/s \le 1$ la sobrecarga no obliga a que $W$ crezca más que linealmente. Como además el límite de concurrencia impone $W \in \Omega(p)$ , el mejor crecimiento posible es $W \in \theta(p)$ : exactamente la escalabilidad óptima del enfoque 2.

Interpretación de la isoeficiencia

Función de isoeficiencia	Escalabilidad
$W \in \theta(p)$	Óptima
$W \in \theta(p\log p)$	Buena, pero no óptima
$W \in \theta(p^2)$	Peor
$W \in \theta(p^3)$	Mala: exige que el problema crezca muy rápido

Siempre que se pueda mantener constante la eficiencia haciendo crecer $W$ , el algoritmo es escalable, por mala que sea su escalabilidad. Si no se puede (el término se cancela), no escala.

Eficiencia escalada

Otra forma de medir la escalabilidad: se multiplican el tamaño del problema y el número de procesadores por el mismo factor $r$ y se compara el tiempo.

E_{sca}(W,r) = \frac{T_{par}(W_0, p_0)}{T_{par}(r\,W_0,\; r\,p_0)}

Si el tiempo se mantiene aproximadamente constante, $E_{sca} \approx 1$ : comportamiento ideal de escalado débil (weak scaling).
Algunos autores consideran cuasi-escalable un algoritmo mientras $E_{sca} > 0$ (Prieto et al., 2003).
Multiplicar por 2 es buena estrategia, pero un intervalo de observación mal elegido puede llevar a conclusiones erróneas.

Ejemplo

$T(n) = n^3 t_c$ , $T(n,p) = \frac{n^3}{p}t_c + n\,t_s + \frac{n^2}{2}t_w$ , $W = n^3$ , con $p_0 = 1$ , $n_0 = 1024$ y $r = 2$ .

$p_1 = 2$ , $W_1 = 2W_0 \Rightarrow n_1 = n_0\sqrt[3]{2} \approx 1290.16$ → $E_{sca} \approx 0.997$
$p_2 = 4$ , $W_2 = 4W_0 \Rightarrow n_2 = n_0\sqrt[3]{4} \approx 1625.50$ → $E_{sca} \approx 0.993$

Sistemas híbridos / heterogéneos

Sistemas formados por elementos de distinta naturaleza: CPU + GPU, ordenadores con distintas prestaciones, etc. Los grupos suelen (no necesariamente) hacer los mismos cálculos y comunicaciones.

El modelo se generaliza con varias constantes de cálculo y comunicación. Se obtiene el $T_i(n,p)$ de cada grupo por separado y luego se compone $T(n,p)$ . El resto del análisis es igual, solo que más complejo algebraicamente.

Clúster con CPU + GPU

$p$ ordenadores iguales en red ( $t_s$ , $t_w$ ). Cada uno tiene una CPU con $k$ núcleos ( $t_c$ ) y una GPU 9 veces más potente (constantes $t_{c_{GPU}}$ , $t_{s_{GPU}}$ , $t_{w_{GPU}}$ ). $T(n) = n^2 t_c$ , sin dependencias externas y todos hacen el mismo cálculo.

a) Tiempo de cada ordenador. Cada ordenador recibe $n^2/p$ . Dentro, el reparto es proporcional a la potencia: $\frac{n^2}{p} = x + 9x \Rightarrow$ $\frac{n^2}{10p}$ a la CPU y $\frac{9n^2}{10p}$ a la GPU. Se envía y recibe lo mismo a/de la GPU y la carga está balanceada ( $T_{ar_{GPU}} = T_{ar_{CPU}}$ ):

T(n,p,k) = 2\left(t_{s_{GPU}} + \frac{9n^2}{10p}t_{w_{GPU}}\right) + \frac{n^2 t_c}{10pk}

b) Sistema completo, con coste CPU/GPU nulo. Distribuir y recolectar entre los ordenadores con P2P (no óptimo):

T(n,p,k) = 2p\left(t_s + \frac{n^2}{p}t_w\right) + \frac{n^2 t_c}{10pk}

c) Escalabilidad.

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

$t_c$ : no depende de $p$ .
$t_s$ : $W \propto Kp^2 \in O(p^2)$ .
$t_w$ : $W = n^2 \propto Kpn^2 \Rightarrow 1 \propto Kp$ . $n$ aparece en los dos lados y se cancela: aumentar el problema no compensa el crecimiento de $p$ . No escala.

Resumen de fórmulas

Concepto	Fórmula
Tiempo paralelo	$T(n,p) = T_{ar} + T_{co} - T_{sol} + T_{ov} \cong T_{ar} + T_{co}$
Síncrono	$T(n,p) = T_{ar} + T_{co} + T_{ov}$
Asíncrono	$T(n,p) = \max(T_{ar}, T_{co}) + T_{ov}$
Cálculo	$T_{ar} = n\,t_c$
Comunicación P2P	$T_{co} = t_s + n\,t_w$
Coste	$C(n,p) = p\,T(n,p)$
Sobrecarga	$T_0(n,p) = C(n,p) - T(n)$
Speedup	$S(n,p) = T(n)/T(n,p) \le p$
Eficiencia	$E(n,p) = S/p = T(n)/(p\,T(n,p)) \in [0,1]$
Amdahl	$S = \dfrac{1}{(1-PF) + PF/p} \le \dfrac{1}{\alpha}$
Gustafson–Barsis	$S_G(W,p) = p - (p-1)f_s$ , $\;f_s = 1 - PF$
Rendimiento teórico	$TPP_{dp} = \text{sockets} \times \text{cores} \times \text{GHz} \times \text{FLOPs/ciclo}$
Rendimiento efectivo	$Re_{dp} = S_{\text{Amdahl}} \times \text{GHz} \times \text{FLOPs/ciclo}$
Isoeficiencia	$W = K\,T_0(W,p)$ , $\;K = E/(1-E)$
Sobrecarga relativa	$T_0/T(n) \in O(p^r/W^s)$ ; escala óptimamente si $r \le s$
Eficiencia escalada	$E_{sca}(W,r) = T(W_0,p_0)/T(rW_0, rp_0)$
Grado medio de concurrencia	$M(G) = \frac{1}{L(G)}\sum_{i=1}^{N} c_i$ (ver Tema 2 - Diseño de algoritmos paralelos)
Relación superficie-volumen	$T_{\text{comunicación}} / T_{\text{cálculo}}$