Why eight workers are not eight times faster
Parallel computing means splitting one job into parts and doing several parts at the same time. Amdahl's law tells you how much faster a job can get, and why the answer is rarely as much as you hoped.
Think of a bakery that gets a rush order of 100 loaves. Extra bakers shorten the baking, but the oven still has to be loaded first by one person.
By the end of this lesson
Note
I can estimate the speed-up from using more workers.
Key words
| Word | What it means | Example |
|---|---|---|
| Parallel | several parts of a job done at the same time | |
| Worker | one process or thread that does a share of the job | |
| Speed-up | how many times faster than one worker | 100 units / 40 units = 2.5 |
| Serial part | the work that must be done in order, by one worker | |
| Parallel part | the work that can be split between workers | |
| Amdahl's law | the serial part sets the most speed-up you can get |
The cells students fill in are left blank in this preview.
There is no GPU in this lab
Important
A GPU is a graphics processing unit, a chip with thousands of small workers. This lab has none. It teaches the model a GPU is built on, using Python and NumPy, so every result is the same each time. A GPU launch is simulated in plain Python.
Speed-up compares the old time with the new
Speed-up is the time with one worker divided by the time with more. If a job takes 100 units with one worker and 40 with four, the speed-up is 100 / 40 = 2.5.
A perfect speed-up equals the number of workers. Real jobs fall short, because some of the work is a serial part: it must happen in order, and only one worker can do it.
Worked example: 20 serial units, 80 parallel
| Workers | Serial time | Parallel time | Total time | Speed-up |
|---|---|---|---|---|
| 1 | 20 | 80 | 100 | 1.0 |
| 2 | 20 | 40 | 60 | 1.67 |
| 4 | 20 | 20 | 40 | 2.5 |
| 8 | 20 | 10 | 30 | 3.33 |
The cells students fill in are left blank in this preview.
The serial part sets a ceiling
Let s be the share that cannot be split, as a fraction. With n workers the speed-up is 1 / (s + (1 - s) / n). This is Amdahl's law.
As n grows, the second part shrinks towards zero, and the speed-up approaches 1 / s. With a serial share of 20 percent, s is 0.2, so no number of workers gives more than 5 times.
Run the worked example
# A job of 100 units of work: 20 cannot be split, 80 can.
serial = 20
parallel = 80
for workers in [1, 2, 4, 8]:
time = serial + parallel / workers
print(workers, "workers: time", time, "units, speed-up", round(100 / time, 2))
# Change serial to 50 and parallel to 50, then run again.
The lab prints one table for three shares
The lab's amdahl.py script prints the speed-up for 1, 2, 4 and 8 workers. It does so when 10, 25 and 50 percent of the job cannot be split. Read down one column: a bigger serial share gives a smaller speed-up for the same number of workers.
The script ends with the ceiling for 10 percent serial, which is 10.0. The second Run checks one cell by hand: 20 percent serial and 4 workers.
Print the speed-up table
docker exec jupyter python3 steps/amdahl.pyShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Check one cell by hand
docker exec jupyter python3 -c "print(round(1 / (0.2 + 0.8 / 4), 2))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A common mistake
Warning
Many people think that eight workers make a job eight times faster. They do only if none of the job must be done in order. Whatever stays serial sets the ceiling, so ask first how much of the job cannot be split.