AP® Computer Science Principles review sheet from Aim for Five (aimforfive.com/csp/units/4/4-3)
Unit 4 · Topic 4.3
4.3 Parallel and Distributed Computing
Splitting work across processors or computers can make programs much faster, up to a point. This topic covers sequential, parallel and distributed computing, how to calculate the time a solution takes and its speedup, and why the steps that must happen in order limit the gains.
Key terms
- sequential computing
- parallel computing
- distributed computing
- speedup
Three ways to compute
Sequential computing runs a program's steps one after another, with only one step happening at any moment.
Parallel computing splits a job into smaller pieces and runs some of those pieces at once on different processors. A parallel solution always has a parallel portion (tasks that can run side by side) and usually a sequential portion (steps that must happen in order, like setting up before anything else can start).
Distributed computing uses multiple devices, often many computers connected over a network, to run a program. Large search engines and scientific projects spread work across thousands of machines.
Calculating time
To compare solutions, compare the time each takes to do the same task.
- Sequential time: add up the times of all the steps.
- Parallel time: the time of the sequential steps, plus the time of the slowest group of parallel work. Each processor works through its own tasks one after another, so the parallel part takes as long as the busiest processor.
- Speedup: sequential time divided by parallel time. A speedup of 2 means the parallel solution is twice as fast.
Assigning tasks to processors
When there are more tasks than processors, you have to decide which processor runs which task. To finish soonest, balance the work so the busiest processor has as little as possible.
With tasks of 50, 40, 30 and 20 seconds on two processors, pairing 50 with 20 and 40 with 30 gives each processor 70 seconds. The sequential time is 140 seconds, so the speedup is 140 ÷ 70 = 2. A worse split, like 50 + 40 on one processor and 30 + 20 on the other, takes 90 seconds.
Benefits and limits
Parallel solutions scale better than sequential ones: as the problem grows, adding processors keeps the time manageable. Distributed computing lets people solve problems that would take far too long, or need far too much storage, on any single computer.
But the sequential portion limits the gains. Steps that must happen in order take the same time no matter how many processors you add. Also, one task can't be split across processors unless the problem allows it. At some point, adding more processors no longer meaningfully speeds things up.
Worked examples
Try each one yourself first, then open the solution.
- Example 1
Speedup with a sequential step
A job has a 20-second setup step that must finish first. Then four independent tasks, each taking 30 seconds, can run in parallel. Find the time and speedup with 1, 2, 4 and 8 processors.
Show the solutionHide the solution
- Step 1: 1 processor (sequential): 20 + 30 + 30 + 30 + 30 = 140 seconds.
- Step 2: 2 processors: setup takes 20 seconds. Each processor then runs two tasks, 60 seconds. Total 20 + 60 = 80 seconds. Speedup 140 ÷ 80 = 1.75.
- Step 3: 4 processors: 20 + 30 = 50 seconds. Speedup 140 ÷ 50 = 2.8.
- Step 4: 8 processors: still 20 + 30 = 50 seconds. There are only four tasks, so four processors sit idle, and the 20-second setup can't be shortened. Speedup is still 2.8.
Answer: 1 processor: 140 s. 2 processors: 80 s (speedup 1.75). 4 processors: 50 s (2.8). 8 processors: 50 s (2.8, no further gain).
- Example 2
Choosing the best assignment
Three tasks take 60, 30 and 50 seconds and are independent. Two processors are available. What's the least time to finish all three, and what's the speedup over running them sequentially?
Show the solutionHide the solution
- Step 1: Sequential time: 60 + 30 + 50 = 140 seconds.
- Step 2: Try each way to split the tasks between two processors and take the busier processor's time: 60 + 30 versus 50 gives 90; 60 + 50 versus 30 gives 110; 60 versus 30 + 50 gives 80.
- Step 3: The best split is 60 on one processor and 30 + 50 on the other: 80 seconds.
- Step 4: Speedup: 140 ÷ 80 = 1.75.
Answer: 80 seconds, a speedup of 1.75.
Common mistakes
- Adding all the parallel task times together. Parallel tasks overlap, so you take the busiest processor's time, not the total.
- Forgetting the sequential portion when computing parallel time.
- Dividing parallel time by sequential time. Speedup is sequential ÷ parallel, so it's bigger than 1 when parallel is faster.
- Assuming more processors always help. Once every task has its own processor, extra processors do nothing.
On the exam
- Expect calculation questions: given task times and a number of processors, find the minimum time or the speedup. Try the possible assignments and keep the one where the busiest processor finishes soonest.
- Expect conceptual questions on why speedup levels off (the sequential portion) and why distributed computing helps with very large problems.
Connected topics
Videos
Check yourself
4 questions on 4.3 Parallel and Distributed Computing. Pick an answer to see if you got it, and why.
Which of the following best describes sequential computing?
A research project uses thousands of volunteers' home computers, connected over the internet, to analyze one enormous data set. Which computing model is this?
Which of the following is the best reason to use distributed computing instead of a single computer?
A task takes 120 seconds when run sequentially and 50 seconds when run as a parallel solution. What is the speedup?
0 of 4 answered