Fracció paral·lelitzable i llei d'Amdahl

Separarem el temps d’execució en dues parts:

• $T_{\text{seq}}$: temps no paral·lelitzable (seqüencial).
• $T_{\text{par}}$: temps paral·lelitzable.

$$T = T_{\text{seq}} + T_{\text{par}}.$$

Definim la fracció paral·lelitzable del programa com:

$$\varphi = \frac{T_{\text{par}}}{T_1} \qquad \Rightarrow \qquad 1 - \varphi = \frac{T_{\text{seq}}}{T_1}.$$

Intuïtivament, $\varphi$ mesura quina part del codi podria beneficiar-se del paral·lelisme. $1 - \varphi$, en canvi, ens expressa quina fracció del programa ens frena d’obtenir un millor rendiment.

Model ideal amb $P$ processadors: si suposem un repartiment perfecte de la part paral·lelitzable (sense desbalanceig ni costos addicionals):

$$T_P = T_{\text{seq}} + \frac{T_{\text{par}}}{P} = (1 - \varphi), T_1 + \varphi, \frac{T_1}{P}.$$

▣Part paral·lelitzable ($\varphi$) gran: el tram $T_{\text{par}}$ es reparteix entre P0…P3 en quatre trossos de $T_{\text{par}}/4$, i els trams $T_{\text{seq}}$ es queden a P0. (figura al dossier, p. 10)

Llei d’Amdahl: el guany del paral·lelisme està limitat per la part seqüencial del programa:

• Si $\varphi$ és gran (quasi tot és paral·lelitzable), podem obtenir speedups elevats, però sempre acotats per $1 - \varphi$.
• Si $\varphi$ és petita (part seqüencial gran), encara que augmentem molt $P$, el speedup quedarà limitat.

▣$\varphi$ petit → $T_{\text{seq}}$ domina: de $P = 1$ a $P = 8$ el temps total gairebé no baixa. (figura al dossier, p. 10)