Laundry day: washing takes 30 minutes, drying 40. You have 3 loads and one washer-dryer pair. Sequential thinking: wash+dry load 1 (70 min), then load 2, then load 3 — 210 minutes.
But while load 1 dries, the washer is idle. Pipeline it: wash 1 (30), then dry 1 while washing 2, and so on. Total: about 150 minutes. Same machines, same laundry — 60 minutes saved by overlapping work.
Yet notice: you can't finish faster than 40 × 3 = 120 minutes of drying, because drying is your bottleneck — no cleverness shrinks it. Parallel computing is exactly this: overlap what can overlap, and accept that the part that can't be parallelized sets the floor. The exam turns this into arithmetic; the arithmetic is laundry.
Parallel vs. distributed, the exam's line: parallel = multiple processors, often within one machine, sharing the work; distributed = multiple machines cooperating via messages over a network. Distributed systems must communicate (coordination overhead), and they scale essentially without ceiling — add more machines.
The model: some operations must run sequentially; others can run at the same time on different processors.
Parallel execution time = (time of the sequential portion) + (time of the LONGEST parallel branch)
The longest branch rule is everything: parallel work finishes when the slowest simultaneous piece finishes. Waiting on the slowest = the whole point.
Standard setup: a program has three independent tasks taking 40, 60, and 30 seconds.
With a required sequential prefix, add it to both sides. Example: 20 seconds of setup that cannot be parallelized, then the three tasks: sequential total = 150; two-processor parallel = 20 + 70 = 90.
More processors shrink only the parallel portion — at best to the longest single task, and with unlimited processors, toward zero for perfectly divisible work. The sequential portion never shrinks. So:
Minimum possible time = the sequential portion (+ the longest indivisible parallel task). Speedup is limited by the fraction of work that must be sequential.
If a 100-second program has 20 sequential seconds, then even with infinite processors it takes ≥ 20 seconds — speedup can never exceed 5×. The exam asks this as "adding more processors will..." → correct answer: help less and less; the sequential part sets a floor (diminishing returns). (You may have heard "Amdahl's Law" — the CED doesn't name it, so answer in plain language.)
Distributed computing's virtues: scale (data or work beyond any one machine — indexing the web, climate models, DNA analysis) and collaboration across locations (many machines, even volunteers' idle computers). Its costs: machines must communicate over a network (slow compared to in-machine work) and coordinate (split the work, gather results, handle stragglers and failures — Lesson 18's fault-tolerance thinking reappears at the compute layer).
Exam framing: "when is a distributed solution appropriate?" → when the problem's size/time exceeds a single machine's capacity, and the work divides into largely independent chunks whose benefit outweighs communication overhead.
Problem: Independent tasks of 25, 50, and 45 seconds. (i) Time on one processor? (ii) Time on three processors, one task each? (iii) Speedup?
Solution: (i) 25 + 50 + 45 = 120 s. (ii) max(25, 50, 45) = 50 s — everyone waits for the 50. (iii) 120/50 = 2.4×.
Interpretation: Sum for sequential; max for parallel. Two operations, one exam point.
Problem: Four independent tasks: 30, 20, 25, 15 seconds. Two processors. What's the best possible finishing time?
Strategy: Balance the loads — minimize the larger pile.
Solution: Total = 90 → ideal split 45/45. Try: 30+15 = 45 and 20+25 = 45. Perfectly balanced → finish at 45 seconds. (A careless split like 30+25 vs 20+15 gives max(55, 35) = 55.)
Interpretation: With two processors, aim each pile at total/2. The exam usually offers a clean split; find it rather than settling for the first grouping you see.
Problem: A program: 10 seconds of setup (must be sequential), then 60 seconds of perfectly parallelizable work. Compute the time with (i) 1 processor, (ii) 2, (iii) 4, (iv) unlimited processors. What's the pattern?
Solution: (i) 10 + 60 = 70 s. (ii) 10 + 30 = 40 s. (iii) 10 + 15 = 25 s. (iv) 10 + (≈0) = approaching 10 s, never below.
Pattern: each doubling of processors halves only the parallel part; gains shrink (70→40 saves 30; 40→25 saves 15) and the total can never beat the 10-second sequential floor.
Interpretation: "Diminishing returns + a floor at the sequential portion" — the sentence to bring to any "should we buy more processors?" question.
Problem: A research project must analyze 100 million telescope images — more data than any single computer can store, and independent per image. Which approach and why?
(A) Sequential computing, to keep the analysis simple (B) Parallel computing on one machine, since images are independent (C) Distributed computing: many networked machines each storing and analyzing a share of the images (D) Binary search across the images
Solution: (C). The deciding phrase: more than any single computer can store — that's distribution's home turf (parallel-on-one-machine dies at the storage wall). Independence makes the division clean; coordination overhead is dwarfed by the scale win.
Interpretation: "Too big for one machine" → distributed. "Speed up divisible work on one machine" → parallel. The scenario always plants the deciding phrase.
1. (A). Definition. (B) is parallel; (C) is distributed; (D) is event-driven programming (Lesson 1) — different axis entirely.
2. (B). max(20, 35, 25) = 35. The 35-second task is the straggler everyone awaits.
3. (A). Sequential = 80; parallel = 35; speedup = 80/35 ≈ 2.3×. (C) is the "processors = speedup" fallacy — the unbalanced tasks prevent a full 3×; (B) divides upside down (speedups are > 1 when parallel helps).
4. (C). 15 + max(30, 50) = 15 + 50 = 65. (A) sums everything (sequential); (B) uses the shorter branch; (D) adds 15 + 30 + ... wrong pile.
5. (D). The floor = sequential 15 + longest indivisible branch 50 = 65 as given — with only two branches stated, no extra processors help at all; the answer choice articulating "sequential + longest branch" is the principled one. (Note the trap: (C) forgets the sequential prefix.)
6. (B). Devices-over-network vs. simultaneous-processing. (D) is exactly backwards — communication is distribution's defining cost.
7. (C). Total = 100 → ideal 50/50. Split: 40+10 = 50 and 30+20 = 50 → 50 seconds. (B) is the longest-single-task answer (needs 4 processors); (D) is an unbalanced split (40+20 / 30+10 → 60).
8. (C). The storage wall — single machines need not apply. (A), (B), (D) are single-machine trivialities.
9. (A). The sequential 10% is the floor: time → 10% of original, speedup → 10×. (B)/(C) ignore the floor. This is the diminishing-returns question, in its standard costume.
10. (A) and (C). Scale beyond one machine; grow by adding machines. (B) reverses the overhead reality; (D) invents a guarantee (stragglers are precisely the problem).
11. (B). Processor 1: 12 + 18 = 30; Processor 2: 25. Both must finish: max(30, 25) = 30. Within a processor, tasks are sequential (sum); across processors, parallel (max). This two-level structure is the full exam pattern in miniature.
12. (B). Speedup = how many times faster = old time ÷ new time = sequential ÷ parallel. Bigger = better; if your "speedup" is less than 1, you divided upside down.
Answer letter distribution check: A, B, A, C, D, B, C, C, A, A+C, B, B — singles: A×3, B×4, C×4, D×1 + multi (A,C). Phase 4 complete; cumulative through L19 ≈ A 23%, B 31%, C 26%, D 20%.
Your PT runs on one processor, sequentially — and that's a feature for the written responses: sequential execution is why your trace tables (Lessons 7–16) predict behavior exactly. There's still one transferable idea: independence. Parallel decomposition works when tasks don't depend on each other; your PT's procedure works cleanly when it doesn't depend on hidden outside state — it reads its parameters, returns its result (Lesson 14). If you can say "my procedure's result depends only on its inputs," you've stated the same property that makes work parallelizable — and given WR 2(c) a sharp sentence about why your abstraction is trustworthy.
Heads-up for the mocks: the parallel-time calculation is the closest thing Section I has to a "plug the numbers" question. In both CSPIQ mocks (and almost certainly on your real form), expect: sum for sequential, sequential-plus-longest-branch for parallel, division for speedup. Free point. Collect it.
1. (A). Definition. (B) is parallel; (C) is distributed; (D) is event-driven programming (Lesson 1) — different axis entirely.
2. (B). max(20, 35, 25) = 35. The 35-second task is the straggler everyone awaits.
3. (A). Sequential = 80; parallel = 35; speedup = 80/35 ≈ 2.3×. (C) is the "processors = speedup" fallacy — the unbalanced tasks prevent a full 3×; (B) divides upside down (speedups are > 1 when parallel helps).
4. (C). 15 + max(30, 50) = 15 + 50 = 65. (A) sums everything (sequential); (B) uses the shorter branch; (D) adds 15 + 30 + ... wrong pile.
5. (D). The floor = sequential 15 + longest indivisible branch 50 = 65 as given — with only two branches stated, no extra processors help at all; the answer choice articulating "sequential + longest branch" is the principled one. (Note the trap: (C) forgets the sequential prefix.)
6. (B). Devices-over-network vs. simultaneous-processing. (D) is exactly backwards — communication is distribution's defining cost.
7. (C). Total = 100 → ideal 50/50. Split: 40+10 = 50 and 30+20 = 50 → 50 seconds. (B) is the longest-single-task answer (needs 4 processors); (D) is an unbalanced split (40+20 / 30+10 → 60).
8. (C). The storage wall — single machines need not apply. (A), (B), (D) are single-machine trivialities.
9. (A). The sequential 10% is the floor: time → 10% of original, speedup → 10×. (B)/(C) ignore the floor. This is the diminishing-returns question, in its standard costume.
10. (A) and (C). Scale beyond one machine; grow by adding machines. (B) reverses the overhead reality; (D) invents a guarantee (stragglers are precisely the problem).
11. (B). Processor 1: 12 + 18 = 30; Processor 2: 25. Both must finish: max(30, 25) = 30. Within a processor, tasks are sequential (sum); across processors, parallel (max). This two-level structure is the full exam pattern in miniature.
12. (B). Speedup = how many times faster = old time ÷ new time = sequential ÷ parallel. Bigger = better; if your "speedup" is less than 1, you divided upside down.
Answer letter distribution check: A, B, A, C, D, B, C, C, A, A+C, B, B — singles: A×3, B×4, C×4, D×1 + multi (A,C). Phase 4 complete; cumulative through L19 ≈ A 23%, B 31%, C 26%, D 20%.
Exam tip: For any parallel-time question, draw two (or n) columns — one per processor — stack each task's seconds in a column, add each column, and circle the tallest: sequential prefix + tallest column = answer. The drawing takes 30 seconds and converts the exam's one arithmetic question into transcription.