D. Topics in Computer Science · Topics in Computer Science: Sustainability, Emerging Research and CareersParallel and Distributed Computing: Many Processors, One Problem
D2.1About 65 minutes
Learning goals- I can explain parallel processing and why modern processors have many cores.
- I can describe distributed computing, including cloud computing, supercomputers and volunteer computing.
- I can calculate speedup and use Amdahl's law to explain the limits of parallelism.
- I can describe challenges researchers work on: communication, coordination and failures.
Words to know
core
One processing unit inside a CPU. A multicore processor can run several streams of instructions at the same time.
parallel processing
Splitting a task into parts that run at the same time on several cores or processors.
distributed computing
Many separate computers connected by a network working together on one problem.
speedup
How many times faster a task runs in parallel: time on one processor ÷ time on many.
Amdahl's law
A formula showing that the part of a program that must run one step at a time limits the total speedup.
GPU
Graphics processing unit: a processor with thousands of simple cores, used for graphics and for AI and science calculations.
cloud computing
Using computing power and storage in large data centres over the internet instead of on your own machine.
The pizza problem
You have to cut and serve 40 pizzas for a school event. Alone, it takes all afternoon. With four friends, each taking 8 pizzas, it goes much faster, but someone still has to collect the money and stack the boxes at the end.
That is exactly the idea behind parallel and distributed computing, two research areas the curriculum names. When one processor is not fast enough, use many.
Why many cores?
For decades processors got faster mostly by running their clock faster. In the mid-2000s this became hard, because faster clocks produced too much heat. Chip makers started putting several cores on each chip instead. Today a phone or laptop CPU often has 4 to 16 or more cores, and a GPU has thousands of small cores. (You learn about the CPU and its specifications in the unit Computer Environments and Systems.)
Extra cores only help if the software splits the work among them. Writing programs that do this correctly is a major research and engineering area.
Parallel processing: split, work, combine
Many parallel programs follow one pattern:
- Split the data or task into chunks.
- Work: each core processes its chunk at the same time.
- Combine the partial results into the final answer.
data = list(range(1, 101)) # the numbers 1 to 100
chunks = [data[i:i + 25] for i in range(0, 100, 25)]
partial = [sum(c) for c in chunks] # each "worker" sums one chunk
print("Partial sums:", partial)
print("Combined:", sum(partial))
The split, work, combine pattern. Here one computer plays all four workers, but on a real system each chunk could go to a different core or computer. Output (one line each): Partial sums: [325, 950, 1575, 2200] / Combined: 5050
Measuring the benefit: speedup
Speedup = time with one processor ÷ time with many processors.
In the diagram, 40 s ÷ 13 s ≈ 3.1. Four cores did not give a speedup of 4, because the combine step could not be split.
Amdahl's law turns this into a formula. If a fraction p of the work can run in parallel and the rest (1 − p) cannot, then with n processors:
speedup = 1 ÷ ((1 − p) + p ÷ n)
As n gets very large, p ÷ n gets close to 0, so the speedup can never be more than 1 ÷ (1 − p).
Worked exampleExample 1: Using Amdahl's law
A photo-editing filter spends 80% of its time on work that can be split among cores (p = 0.8). (a) Find the speedup with 4 cores. (b) What is the largest possible speedup with any number of cores?
- (a) speedup = 1 ÷ ((1 − 0.8) + 0.8 ÷ 4) = 1 ÷ (0.2 + 0.2) = 1 ÷ 0.4 = 2.5.
- (b) As n grows, 0.8 ÷ n → 0, so speedup → 1 ÷ 0.2 = 5.
- Interpretation: the 20% that must run in order is the bottleneck. To go faster, programmers must find ways to parallelize that part too.
def speedup(p, n):
return 1 / ((1 - p) + p / n)
for n in [1, 2, 4, 8, 16, 1000]:
print(n, "cores:", round(speedup(0.9, n), 2))
Amdahl's law with p = 0.9 (90% parallel). Output (one line each): 1 cores: 1.0 / 2 cores: 1.82 / 4 cores: 3.08 / 8 cores: 4.71 / 16 cores: 6.4 / 1000 cores: 9.91
Distributed computing
In distributed computing, separate computers connected by a network share a problem.
- Cloud computing: companies run huge data centres, and a single web search or streaming service may involve many machines working together.
- Supercomputers link thousands of processors with very fast networks for weather forecasting, climate models, medicine and physics. In Canada, the Digital Research Alliance of Canada coordinates national advanced research computing for university researchers.
- Volunteer computing: projects such as Folding@home use spare computing time on volunteers' home computers to simulate how proteins fold, which helps disease research.
What makes it hard
- Communication: sending data between computers takes time; sometimes more time than the computing itself.
- Coordination: if two workers update the same value at the same time, the result can be wrong (a race condition).
- Failures: with thousands of machines, some are always failing; the system must keep going.
- Energy: more machines use more power (remember Lesson 1).
Researchers work on new algorithms, programming tools and hardware to deal with all four.
Just for funIf one person can mix, scoop and bake a tray of cookies in 30 minutes, can 30 people bake it in 1 minute?
No. Even if the mixing and scooping are shared, the tray still needs its 12 minutes in the oven. That's Amdahl's law in the kitchen: some steps just can't be split.
Hands-on activityParallel card sorting
You need: a deck of playing cards, a timer, and two to four helpers.
- Sequential: shuffle the deck. One person sorts it into the four suits, each suit in order from ace to king. Time it.
- Parallel: shuffle again and deal the deck into equal piles, one per person. Each person sorts their pile by suit. Then combine: each person hands over their cards suit by suit to the person responsible for that suit, who puts them in order. Time the whole thing, including combining.
- Calculate the speedup: sequential time ÷ parallel time.
- Use Amdahl's law in reverse: if you got a speedup S with n people, what fraction p seems to have been parallel? (Try values of p in the Python program until the speedup matches.)
- Write two sentences on where time was lost (handing cards over, waiting, getting in each other's way).
What to look for: two measured times, a correct speedup (less than the number of people), and a sensible explanation of the overhead.
Your turn
One processing unit inside a CPU that can run its own stream of instructions.
2Name the three steps of the split–work–combine pattern.
Split the task into chunks, process the chunks at the same time, combine the partial results.
3A task takes 60 s on one core and 20 s on four cores. What is the speedup?
4Use Amdahl's law to find the speedup with p = 0.5 and n = 2.
1 ÷ (0.5 + 0.25) = 1 ÷ 0.75 ≈ 1.33.
5What is the maximum speedup if 25% of a program cannot be parallelized?
6Give two examples of distributed computing.
Any two: cloud services, supercomputers, volunteer computing like Folding@home, web search.
7What is a race condition?
An error that happens when two workers update the same data at the same time and the result depends on timing.
More practice: warm-up
Graphics processing unit.
2Why did chip makers start adding more cores instead of raising clock speed?
Faster clocks produced too much heat.
Using computing power and storage in data centres over the internet.
4What does Folding@home use?
Spare computing time on volunteers' computers, to simulate protein folding for disease research.
5If the speedup is 1, what does that mean?
No improvement: the parallel version is just as fast as the sequential one.
More practice: on your own
1Using the program's partial sums, what would the chunks and partial sums be if the numbers 1 to 100 were split into 2 chunks?
Chunks 1–50 and 51–100; partial sums 1275 and 3775, combined 5050.
2A program is 95% parallel. Find the speedup on 10 cores, to two decimal places.
1 ÷ (0.05 + 0.095) = 1 ÷ 0.145 ≈ 6.90.
3Explain why the speedup in the card-sorting activity is less than the number of people.
Splitting and combining take time and can't be fully shared, and people wait for each other, so some of the work is not parallel.
4Why is communication time a bigger problem for distributed computing than for parallel cores on one chip?
Cores on one chip share memory and are millimetres apart; separate computers must send data over a network, which is much slower.
5A video game runs at the same speed on a 4-core and an 8-core processor. Give a likely reason.
The game's code is not split into enough parallel parts (or another part, such as the GPU, is the bottleneck), so extra cores sit idle.
Challenge
1Show algebraically that Amdahl's speedup approaches 1 ÷ (1 − p) as n becomes very large, and find how many cores are needed to reach a speedup of 8 when p = 0.9.
As n → ∞, p ÷ n → 0, so speedup → 1 ÷ (1 − p). For speedup 8: 1 ÷ (0.1 + 0.9/n) = 8 → 0.1 + 0.9/n = 0.125 → 0.9/n = 0.025 → n = 36 cores.
2Write a Python function parallel_max(data, workers) that splits a list into workers roughly equal chunks, finds the max of each chunk, and combines them. What does parallel_max([4, 17, 9, 2, 23, 8, 15], 3) return?
Example: size = math.ceil(len(data) / workers), chunks = [data[i:i + size] for i in range(0, len(data), size)], return max(max(c) for c in chunks). Chunks [4, 17, 9], [2, 23, 8], [15]; partial maxima 17, 23, 15; it returns 23.
3Two workers each add 1 to a shared counter that starts at 10. Each one reads the counter, adds 1, and writes it back. Explain how the final value could be 11 instead of 12.
Both read 10 before either writes. Each computes 11 and writes 11, so one update is lost. This is a race condition; it is prevented with locks or by giving each worker its own partial counter and combining at the end.
Quiz
1. A task takes 80 s on one processor and 25 s on four. What is the speedup?
2. According to Amdahl's law, what limits the speedup of a program?
3. A program is 75% parallel (p = 0.75). What is its maximum possible speedup?
4. Which is an example of distributed computing?
5. What is a race condition?
6. Why do modern CPUs have many cores?
Big idea: Expectation D2.1 names parallel processing and distributed computing as emerging research areas. Students learn the split–work–combine pattern, calculate speedup, and use Amdahl's law to explain why more processors do not always mean proportionally faster results.
How to help: Join the card-sorting activity. Afterwards, ask where the time went. Everyday parallels (group projects, kitchen prep, moving day) are great for discussing which steps can be shared and which cannot.
Common difficulties:
- Expecting n processors to give n times the speed.
- Order of operations in Amdahl's formula: compute p ÷ n first, add (1 − p), then take 1 ÷ the result.
- Confusing parallel computing (many cores, usually in one machine) with distributed computing (many machines over a network).