One job, a great many pieces
Brightening a photograph means adding the same small number to millions of pixels. Nothing about one pixel depends on another, so thousands of tiny workers can each take a few. A graphics card is built for exactly that. This lab has no graphics card, but it lets you see the ideas it is built on.
By the end of this lesson
Note
I can explain how doing one job on many pieces of data at once differs from a loop, and why more workers do not always mean a proportionally faster job.
Key words
- Parallel: several parts of a job being done at the same time.
- Worker: one process or thread doing a share of the job.
- Serial part: the share of a job that cannot be split and must be done in order.
- Speed-up: how many times faster a job is than with one worker.
- Thread: one small worker; a GPU runs thousands at once.
- Kernel: the small function every thread runs, each on its own element.
Starter: what you already know
Note
Answer in your head. 1. What does a for loop do? 2. If one person takes 8 minutes to fold 80 leaflets, how long would 4 people take if they split the pile evenly? 3. What if one of the 8 minutes is spent writing the address list, which only one person can do? Answers: it repeats the same steps one after another; 2 minutes; more than 2, because the address list still takes 1 minute for one person.
Before you start
Note
Press Start the lab on the bar at the top of this lesson and wait until it says it is running. There is one container, jupyter, and the terminal reaches its Python with docker exec jupyter, which runs one command inside it. The JupyterLab link opens its web page, port 8888. There is no GPU here. Each Run button below types its command into your lab's terminal, one after another in the same session. To watch them, or to type your own, press Open terminal on the bar.
A parallel project is a folder of small scripts
ls lists the work folder: the notebook start.ipynb and the folder steps. cat prints the first script. It adds up the squares of 1 to 1000 twice: once with a Python loop, and once with a single NumPy operation, which does the same work over the whole array at once.
docker exec jupyter lsShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
docker exec jupyter cat steps/vectors.pyShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
One operation on a whole array
Both ways give 333833500, and the script says the two results are equal. The loop takes 2000 Python-level operations, a multiply and an add for each of 1000 numbers. NumPy takes 1, because one call does all the work in fast compiled code. Nothing is timed, so the script prints the same every time. A GPU goes further: one instruction, thousands of elements.
docker exec jupyter python3 steps/vectors.pyShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Splitting a job between workers
The numbers 1 to 40 are cut into 4 chunks of 10 and two workers share them. Each chunk gives a partial sum, 55, 155, 255 and 355, always listed in chunk order, and adding them gives 820, the same as summing the whole list in one piece. Splitting works because each chunk can be summed without knowing the others.
docker exec jupyter python3 steps/chunks.pyShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
The limit on a speed-up
Some of every job cannot be split. The table works out the speed-up from 1, 2, 4 and 8 workers when 10, 25 and 50 percent cannot. With 10 percent serial, 8 workers give 4.71 times, not 8, and even endless workers give at most 10.0. With 50 percent serial, 8 workers give only 1.78.
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
Tip
In the table, how much faster is the job with 8 workers if 25 percent of it cannot be split? Answer: 2.91 times, not 8, because the serial quarter is still done by one worker.
A launch of blocks of threads
A GPU runs a function called a kernel once for every thread. Threads come in blocks, and each works out which element is its own with block * block size + thread. This script simulates a launch of 3 blocks of 4 threads over 10 elements, adding two vectors. It prints each thread's global index, 0 to 11, and the result 11, 22, and so on to 110. The last two threads, 10 and 11, are past the end and do nothing.
docker exec jupyter python3 steps/kernel.pyShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Moving data costs time too
A device has two limits: how fast it moves bytes and how fast it does sums. This script is arithmetic on a made-up device that moves 500 gigabytes a second and does 10 teraflops a second. A vector add of 10 million elements moves 120000000 bytes for 10000000 sums, so it is limited by memory. A 1000 by 1000 matrix multiply moves 12000000 bytes for 2000000000 sums, so it is limited by compute.
docker exec jupyter python3 steps/transfer.pyShown 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 8 workers make a job 8 times faster. They do only if none of the job has to be done in order. Whatever must stay serial sets a ceiling, and moving the data can cost more than the sums. Ask two questions before adding workers: how much cannot be split, and is the job waiting on memory or on compute?
The same work in a notebook
Open JupyterLab from the bar and double-click start.ipynb. Each cell runs one script, so it shows what the six scripts did, one idea at a time. Click a cell and press Shift and Enter to run it. To explore, open a script in the file list, change one number, such as the number of chunks or the share that cannot be split, and run it again.
Exit check
Tip
Answer without looking back. 1. How many Python-level operations did the loop take for the sum of squares, and how many did NumPy take? 2. What did the four partial sums add up to? 3. With 10 percent serial, what is the most speed-up any number of workers can give? 4. What does each thread in a kernel work out first? Answers: 2000 and 1; 820; 10.0 times; which element is its own, its global index.
For teachers
Tip
This lesson is a small example of a lesson worked in a lab: the steps and the Run buttons are the lesson, and the lab is each student's own copy. The lab is one service, JupyterLab with NumPy, and has no GPU: it teaches the model a GPU is built on, and nothing here marks itself. The student hands in a short change of their own to one script and a sentence on what moved. Key learning points: 1. One operation on a whole array replaces a loop. 2. A job split between workers still has a serial part that sets a ceiling. 3. A kernel runs once per thread, and each thread works out its own element. Common mistake: believing 8 workers give 8 times the speed. Equipment: the lab and a browser. Tip: ask students to predict each table entry before they press Run. Every script prints the same each time, because nothing is timed. Copy it into your own module and change it, or build one from scratch with the Lab menu in the lesson builder.