Escalabilidad e isoeficiencia

Un algoritmo es escalable si mantiene eficiencia constante al incrementar simultáneamente $p$ y el tamaño $n$.

	Qué se fija	Pregunta	Respuesta típica en el examen
Fuerte	$n$ constante	¿$E$ se mantiene al crecer $p$?	$E=O(1/p)$ o similar ⇒ no escala en forma fuerte
Débil	$n$ crece con $p$	¿qué $n=f(p)$ mantiene $E$ constante?	«escala si $p\propto n/\log n$» (o la relación que salga)

El patrón maestro (Brent → E)

Con $T_s=W$ y Brent $T_p=O(W/p+T_\infty)$:

$$S=\frac{W}{\frac Wp+T_\infty}\qquad E=\frac{S}{p}=\frac{1}{1+\dfrac{p\,T_\infty(n)}{W(n)}}$$

Débil: $E$ constante $\iff p\,T_\infty\propto W\iff p\propto\dfrac{W(n)}{T_\infty(n)}$ (el paralelismo disponible). Si se agrega comunicación, p. ej. $+\log p$:

$$E=\frac{1}{1+\dfrac{p\,T_\infty}{W}+\dfrac{p\log p}{W}}\;\Rightarrow\;\text{dos condiciones: }p\propto\frac{W}{T_\infty}\;\text{ y }\;p\log p\propto W$$

En el examen…

Lleva siempre $E$ a la forma $\dfrac{1}{1+p\cdot(\text{algo})}$. Lo que queda multiplicando a $p$ es exactamente lo que $n$ debe «compensar». Si aparecen dos términos, la condición dominante es la más restrictiva (la que exige que $n$ crezca más rápido).

Error común

Decir «escala» sin decir cómo. La respuesta completa es: «no escala fuerte; escala débil si $n$ crece como $f(p)$». Y comparar esquemas: el más escalable es el que, para un mismo $p$, necesita un $n$ menor para sostener la eficiencia (p. ej. $n\propto\sqrt{p\log p}$ gana a $n\propto p$).

Calculadora Brent → S, E y escalabilidad

Elige W(n) y T∞(n) (o un ejercicio previo). Se asume T_s = W (costo óptimo) y la cota de Brent T_p = W/p + T∞ .

P1.md: E = 1/(1 + p log n / n) ⇒ débil si p ∝ n / log n.

$$T_p(n,p)=O\!\left(\frac{n\log n}{p}+\log^2 n\right)\qquad S=\frac{n\log n}{T_p}\qquad E=\frac{1}{1+\dfrac{p\,\log^2 n}{n\log n}}$$

n = 2^16 = 65500Eficiencia objetivo E₀ = 0.5

Escalabilidad fuerte: n fijo, crece p

E(p), n = 65500E(p), n = 1.05e6

Speedup — se satura en W/T∞

S(p), n = 65500S = pW/T∞ (paralelismo) = 4100

Escalabilidad débil: n mínimo para sostener E ≥ 0.5 (función de isoeficiencia, numérica)

n(p) numéricoreferencia n ∝ p

Lectura para el examen. Fuerte (n constante): $E\to 0$ al crecer p ⇒ no escala en forma fuerte. Débil: E constante si $p\,\log^2 n\propto n\log n$, es decir $p\propto \frac{n}{\log n}$.

Isoeficiencia con overhead explícito

$$E=\frac{T_s}{T_s+T_o}\quad\Rightarrow\quad T_s=K\,T_o$$

Ejemplo PD01 (suavizado): $T_o=8\,p\,t\,t_w$ ⇒ $n=\dfrac{8Kt_w}{3t_c}\,p$: isoeficiencia lineal. Práctica 3 (filas, colectivas en árbol): $T_o=\Theta(p\log p)$ con $W=\Theta(N^2)$ ⇒ $N=\Theta(\sqrt{p\log p})$.

Ejercicio (P1): subsecuencia máxima con Divide y Vencerás

SubsecuenciaMaxima(A,l,r) hace dos llamadas recursivas sobre mitades y MaximoCentro recorre linealmente de $l$ a $r$. (a) Recurrencia secuencial. (b) Versión paralela, $W$ y $T_\infty$. (c) $T_p$, $S$, $E$ y escalabilidad.

Ver solución

(a) $T(n)=2T(n/2)+\Theta(n)$. Teorema maestro con $a=b=2$, $f(n)=\Theta(n)=n^{\log_2 2}$ ⇒ $T(n)=\Theta(n\log n)$.

(b) Las llamadas ML y MR son independientes ⇒ pardo. MaximoCentro se paraleliza con dos scans (prefix-sum con + y prefix-max con max), cada uno $O(n)$ trabajo y $O(\log n)$ span:

$$W(n)=2W(n/2)+O(n)=\Theta(n\log n)\qquad T_\infty(n)=T_\infty(n/2)+O(\log n)=O(\log^2 n)$$

(sin paralelizar MaximoCentro, el span sería $O(n)$).

(c) Brent:

$$T_p=O\!\left(\frac{n\log n}{p}+\log^2 n\right)\quad S=\frac{n\log n}{\frac{n\log n}{p}+\log^2n}\quad E=\frac{1}{1+\frac{p\log n}{n}}$$

Fuerte ($n$ cte): $E=O(1/p)$, no escala. Débil: $E$ constante si $p\propto n/\log n$. (Elige el preset «P1» en el playground.)

Autoevaluación

0/4 correctas · 0 respondidas Reiniciar

1. $E=\dfrac{1}{1+p\log n/n}$. Condición de escalabilidad débil:

a) $p\propto n$b) $p\propto n/\log n$c) $p\propto\log n$d) $n\propto\log p$

2. Mergesort con merge secuencial: $W=n\log n$, $T_\infty=n$. ¿$p$ máximo con E constante?

a) $p\propto n$b) $p\propto\log n$c) $p\propto n/\log n$d) $p\propto n^2$

3. Esquema A necesita $n\propto p$; esquema B, $n\propto\sqrt{p\log p}$. ¿Cuál es más escalable?

a) Ab) Bc) Igualesd) Depende de α

4. Con $n$ fijo, $E=O(1/(p\log p))$. Entonces…

a) escala fuerteb) no escala fuertec) escala débil siempred) es costo óptimo

Fuente ·P1.md · estudio/03_Amdahl_Gustafson.md §4 · estudio/08_Solvers_Examenes_Previos.md (Arquetipo E) · practica_3_ofi/executed/analisis_escalabilidad.md · PD01-Ejercicio1-Resolucion.md §6