BIG IDEA 4: COMPUTER SYSTEMS AND NETWORKS · TOPIC 4.3
4.3 Parallel and Distributed Computing
Splitting a task across processors or machines. The exam's signature question here is computing the speedup — and understanding why it's never as much as you'd hope.
What you need to know
- Sequential computing executes one operation at a time, in order. Total time = sum of all operations.
- Parallel computing breaks a task into parts that run simultaneously on multiple processors (cores) in one computer.
- Distributed computing uses multiple separate computers, connected by a network, working together on one problem — often for tasks too large for a single machine.
- Parallel solutions are generally faster than sequential ones, but only if the task can be divided. Parts that depend on each other's results must still run in order.
- Speedup = sequential time ÷ parallel time. The exam gives you operation times and asks for the minimum time on a given number of processors.
- Speedup is limited by the sequential portion: if 20% of a task can't be parallelized, no number of processors gets you more than a 5× speedup.
- There's also overhead — the cost of coordinating between processors — so real speedup is always less than the ideal.
- Distributed computing's advantages: scales beyond one machine's limits, and can be more fault tolerant (one machine failing doesn't stop the whole job).
Worked example
A program has three independent tasks taking 40, 30, and 20 seconds, plus a final step of 10 seconds that needs all three results.
- Sequential: 40 + 30 + 20 + 10 = 100 seconds.
- Two processors: put the 40 on one processor, the 30 and 20 (= 50) on the other. The parallel phase takes 50 seconds (the longer of the two). Then the 10-second step. Total: 60 seconds.
- Three processors: 40, 30, 20 each on its own → 40 seconds (the max), plus 10 → 50 seconds.
Speedup with three processors = 100 ÷ 50 = 2×, not 3×, because of the 10-second sequential step and the uneven task sizes.
Exam tip: For the timing calculation: (1) list tasks that must be sequential — they add up; (2) for parallel tasks, distribute them to balance the processors and take the longest processor's total; (3) add the two. The answer is never the average of parallel tasks — it's the maximum.
Going deeper
The nuance, edge cases, and connections that turn a 3 into a 5.
- Sequential: one processor, one operation at a time. Time = sum of all operations. Parallel: multiple processors in one machine, operations that don't depend on each other run at the same time. Distributed: multiple machines over a network, each handling part of the problem.
- The speedup calculation the exam uses: find the operations that must run sequentially (they add up), find the operations that can run in parallel, distribute those to processors as evenly as possible, and the parallel phase takes as long as the busiest processor. Total time = sequential + max(parallel). Speedup = sequential time ÷ parallel time.
- Why speedup is limited: if 10% of a task must be sequential, then even with infinite processors, that 10% takes its full time. Maximum speedup is 10×. This is Amdahl's law in spirit; the CED just says the sequential portion limits speedup.
- Overhead: splitting work, coordinating, and combining results all take time. Two processors don't quite halve the time even for a perfectly divisible task.
- A task is parallelizable when its parts are independent — summing a list (each half can be summed separately then combined) is; a chain where each step needs the previous step's result (computing a running total step by step) is not.
- Distributed computing adds scalability (add more machines) and fault tolerance (one machine dying doesn't stop the job), at the cost of network communication overhead. It's how large-scale data processing (2.3) is actually done.
- Parallel programs must also handle synchronization — making sure results are combined correctly. The CED doesn't go deep here, but it's part of why parallel programming is harder than sequential.
Mistakes that cost points
- Averaging parallel tasks instead of taking the max. If two processors run tasks of 40s and 20s, the parallel phase takes 40s, not 30s. The slower processor sets the pace.
- Forgetting the sequential part. Any step that needs all the parallel results must wait for them and then adds its own time.
- Claiming n processors give n× speedup. Only for a perfectly parallel task with no overhead — which doesn't exist. Real speedup is always less.
- Mixing up parallel and distributed. Multiple cores = parallel. Multiple computers = distributed.
Practice questions
Written in the style of the real exam. Try each one before revealing the answer.
Q1 A program has four independent tasks that take 8, 6, 4, and 2 seconds. Using two processors that can each run one task at a time, what is the minimum time to complete all tasks?
Show answer
Answer: B. Sequential would be 20. Balance: processor 1 runs 8 + 2 = 10, processor 2 runs 6 + 4 = 10. Minimum time is 10 seconds.
Q2 Which of the following best describes distributed computing?
Show answer
Answer: C. Multiple separate machines over a network = distributed. Multiple cores in one machine = parallel.
Q3 A task consists of a 30-second step that must run first, followed by parts that can run in parallel. Even with an unlimited number of processors, the task cannot complete in less than 30 seconds. Which of the following best explains why?
Show answer
Answer: B. The non-parallelizable part sets a floor on total time. This is the core limit of parallel speedup.
Key vocabulary
- Sequential computing
- operations executed one after another on a single processor
- Parallel computing
- splitting a task across multiple processors running at the same time
- Distributed computing
- multiple networked computers cooperating on one problem
- Speedup
- sequential time divided by parallel time