Mesurar el paral·lelisme · 2.3

Escalabilitat

L'escalabilitat mesura si el programa continua millorant quan hi afegeixes recursos. Distingiràs la strong scalability (mida fixa) de la weak scalability (mida proporcional a $P$ ) i veuràs la llei de Gustafson.

Conceptes clau

Speedup $S_P = T_1 / T_P$
Strong scalability
Weak scalability
Llei de Gustafson

Prova-hoEscalabilitat forta i feble

Fracció paral·lela φ = 95%

feble (Gustafson): S = (1 − φ) + φ·p forta (Amdahl): S = 1 / ((1 − φ) + φ/p)

speed-up fort amb 256 processadors

speed-up feble amb 256 processadors

Amb escalabilitat forta, la part seqüencial pesa cada vegada més i el speed-up es planta. Amb escalabilitat feble, fas un problema més gran en el mateix temps: la part seqüencial queda petita al costat de la feina total.

L’escalabilitat (o scalability) és la capacitat d’un programa de seguir millorant el seu rendiment en augmentar els recursos. Mesurarem com varia l’speedup $S_P = \dfrac{T_1}{T_P}$ quan augmentem el nombre de processadors.

a) Strong scalability: en aquest model mantenim fixa la mida del problema i busquem disminuir $T_P$ incrementant $P$ . Com més proper estigui el speedup a l’ideal $S_P = P$ , millor strong scalability tindrà la nostra estratègia.

b) Weak scalability: aquí no busquem reduir el temps d’execució, sinó mantenir-lo mentre augmentem la mida del problema proporcionalment a $P$ . En el gràfic, l’ideal és mantenir-se a 1. Com més a prop d’1 es mantingui la corba, millor weak scalability.

(a) Strong scalability: speedup dels programes A i B fins a 64 processadors, amb la recta ideal $S_P = P$ . (b) Weak scalability: programes C i D, amb l’ideal a 1. (figura al dossier, p. 11)

En strong scaling, el programa A manté un comportament proper a l’ideal, mentre que el programa B es veu que es comença a estancar a partir de 32 processadors (limitacions per part seqüencial i/o overheads), reduint el guany per afegir més processadors.

En weak scaling, s’observa com l’overhead de comunicació i sincronització augmenta amb $P$ , fent que el rendiment es degradi progressivament en el programa D, mentre el programa C es manté més a prop de l’ideal.

Llei de Gustafson: encara que la strong scalability sigui dolenta (i, per tant, una part important no sigui paral·lelitzable), podem aplicar la llei de Gustafson, que contradiu la llei d’Amdahl: augmentar la mida del problema, per fer créixer la part paral·lelitzable, i així poder treure profit de la weak scalability.

Problema original ( $N$ ) amb un processador i problema escalat ( $4N$ ) amb $P = 4$ : cada processador fa un tram $T_{\text{par}}$ tan llarg com l’original. (figura al dossier, p. 11)

Al quadruplicar la mida del problema i usar $P = 4$ processadors, cada processador realitza la mateixa feina que l’únic processador original, mantenint $T_P \approx T_1$ .