Art of MP Ch 1 - Introduction

Amdahl’s Law

Suppose a task has $1$ unit of work to do. $p$ part of it can be done in parallel by $n$ workers and the remaining $1-p$ is to be done sequentially.

Define speedup $S$ as the ratio of time taken by a task done sequentially vs done parallelly.

In this case, the maximum speedup we can get is $S=\frac{1}{1-p+\frac{p}{n}}$

Example

90% of the task can be paralellised, we have 10 workers. Then speedup will be 1/(0.1 + 0.9/10) ≈ 5! We get a 5X speedup even with 10 workers!

The part that can’t be paralellised significantly affects the speedup we get.