06 Scalability

How does performance improve with additional cores? More cores/hardware do not always result in a linear speedup.

Limiting factors

• parts of a program that cannot be executed parallelly
• data strcutres that require sequential access (f.ex. linked list)
• Verteilung auf Cores und Threads
• Overhead and time for synchronization/locking
• Memory bandwidth, cache misses

---

Speedup

S: Speedup, How performance improves with additional cores

T: Execution time

Success

$T_1$: sequential execution time $T_p$: Execution time on p CPUs.

$T_p=\frac{T_1}{p}$: linear speedup

$T_p>\frac{T_1}{p}$: normal speedup

Parallel speedup on p CPUs

$$S_p=\frac{T_1}{T_p}$$

• $S_p=p$ : linear
• $S_p<p$ (sub-linear, performance loss)

Efficiency

$$E=\frac{S_p}{p}$$

---

Beispiel

80% parallelisierbar, 20% sequenziell.

• $T_1=10$
• $T_{seq}=10\cdot 0.2$
• $T_p=10\cdot 0.8$
• $p=8$ CPUs

$T_8=?$

$$\begin{array}{rl}{T}_8& =T_{seq}+T_{par}\\ & =10\cdot 0.2+\frac{10\cdot 0.8}{8}\\ & =2+1\\ & =3\end{array}$$

$S_8=?$

$$S_8=\frac{T_1}{T_8}=\frac{10}{3}=3.33$$

$E=?$

$$E=\frac{3.33}{8}\approx 0.4⟹40\%$$

---

Amdahl’s Law

The speedup from parallelization is limited by the part that must run sequentially.

$W_{ser}$ … time spend on non-parallelizable work $W_{par}$ … time spend on parallelizable work

$$T_1=W_{ser}+W_{par}$$ $$T_p\ge W_{ser}+\frac{W_{par}}{p}$$

So in the definition of speedup:

$$S_p=\frac{T_1}{T_p}\le \frac{W_{ser}+W_{par}}{W_{ser}+\frac{W_{par}}{p}}$$

Formula with percentage

$f$ is the percentage of how much is sequential

$$S_p=\frac{1}{f+\frac{1-f}{P}}$$

---

Gustafson’s Law

Parallel part of a program scales with the problem size.

Wie viel Arbeit können wir in einem fixen Zeitfenster ausführen, wenn wir mehr Hardware hinzufügen?

Formulas

• $f$: Percentage of sequential part
• $1-f$: parallelizable part
• $P$: number of cores
• $T_{wall}$: total time allowed for execution
• $W$: amount of work
• $S_p$: speedup achieved by $p$ processors

$$W=P\cdot (1-f)\cdot T_{wall}+f\cdot T_{wall}$$ $$\begin{array}{rl}{S}_p& =f+P\cdot (1-f)\\ & =P-f\cdot (P-1)\end{array}$$

Gustafson’s Law can be seen as more work in the same time, Amdahl’s Law would be same work but faster need to happen.

Siehe exam , Kosten-Nutzen Analyse, lohnt es sich, mehr Hardware hinzuzufügen?