Parallelism

Increase bandwidth at (often times) the cost of increased Latency. There are problems that are very easy to parallelize, but there is often some sort of overhead. There are problems that are “inherently sequential” (if an iteration’s execution depends directly on the previous execution). There’s also always going to be some cognitive overhead writing parallel code (partial ordering etc).

Parallelism can lead to data race (which is solved with primatives, but when too constrained can lead to deadlock.

Amdahl’s Law

In 1967 Gene Amdahl argued that improvements in processor design for single processors would be more effective than designing multi-processor systems.

Assumptions:

• Problem size is fixed
• The program or the underlying implementation behaves the same on 1 vs N processors
• We can accurately measure runtimes and overhead doesn’t matter

$T_p=T_s\cdot \left(S+\frac{P}{N}\right)$
Where:

• $T_p$: Parallel time
• $T_s$: Total time in single processor system
• $S$: Serial part
• $P$: Parallelizable part

Here, as N increases, $T_p$ is dominated by S, limiting potential speedups

We can also define max speedup as $\text{max speedup}=\frac{1}{(1-P)}$ Where as P increases, we can get up to an 18x speedup. We can use this information to figure out our runtimes relative to how many processors we have.

To empirically estimate parallel speedup: $P_{estimated}=\frac{\frac{1}{\text{speedup}}-1}{\frac{1}{N}-1}$.
If we generalize Amdahl’s law, lets have:

• $f_1,f_2,\dots ,f_n$ which is the fraction of time in part n
• $S_{f_1},S_{f_2},\dots ,S_{f_n}$ which is the speedup for part n

Then: $\text{speedup}=\frac{1}{\frac{f_1}{S_{f_1}}+\cdots +\frac{f_n}{S_{fn}}}$.