4.3 Sequential and parallel computingMany processors, one job

The CED names three computational models. Sequential computing performs operations in order, one at a time. Parallel computing breaks a program into multiple smaller sequential operations, some of which are performed at the same time, usually on several processors (the cores in your phone are processors). Distributed computing uses multiple separate devices to run a program; that's section 10. You compare the efficiency of solutions by comparing the time each takes to do the same task.
| Model | How it runs | Time it takes |
|---|---|---|
| Sequential | One operation at a time, in order, on one processor | The sum of all the steps |
| Parallel | Split into smaller sequential parts, some running at the same time on several processors | Sequential part + longest parallel part |
| Distributed | Several separate devices on a network each run part of the program | Lets problems too big or too slow for one device be solved |
?Wait, what's a processor?
Now the timing rules. A sequential solution takes as long as the sum of all of its steps. A parallel solution has a sequential portion, steps that must happen alone and in order (like loading the data first or combining results at the end), and a parallel portion that is shared across processors. It takes as long as its sequential portion plus its longest parallel portion, because the parallel part isn't done until the slowest processor finishes.
The speedup of a parallel solution is the time it took to complete the task sequentially divided by the time it took in parallel. A speedup of 2 means twice as fast. Speedup is a ratio with no units, and it's always sequential time on top.
The timing rules
?Wait, what does "independent" mean for tasks?
I thought about it. Show me
- Sequential: add every step. 8 + 24 + 18 + 12 + 6 + 4 = 72 seconds.
- The tiles total 24 + 18 + 12 + 6 = 60 seconds. Two processors can do no better than 60 ÷ 2 = 30 each.
Why?
That ideal is a floor. Whether you can reach it depends on whether the whole tasks can be split into two equal piles. - Try to reach 30: 24 + 6 = 30 on one processor and 18 + 12 = 30 on the other. Perfect balance.
- Add the sequential part: 8 + 30 + 4 = 42 seconds.
Why?
The load and stitch steps run while the other processor waits. They count in full. - Speedup = 72 ÷ 42 ≈ 1.71.
Why?
I checked every possible way to split the four tiles in Python: 30 is the best possible parallel part, so 42 seconds is the minimum.
Answer: 72 seconds sequentially, 42 seconds on two processors, speedup about 1.71. Less than 2, because 12 seconds can never be shared.
Stuck? Get a hint
- First add everything for the sequential time.
- Split the four tiles into two piles that are as equal as possible.
- Parallel time is load + the bigger pile + stitch.
- A90
- B0.4
- C2.5
- D210
Show the answer
C. Speedup = sequential ÷ parallel = 150 ÷ 60 = 2.5. 90 is the time saved, not the speedup, and 0.4 divides upside down. A speedup below 1 would mean the parallel version was slower.
- A80 seconds
- B40 seconds
- C55 seconds
- D27 seconds
Show the answer
B. Put 40 on one processor and 25 + 15 = 40 on the other: both finish at 40 seconds. No split can beat 40, since the 40-second task alone takes that long. 55 pairs 40 with 15, and 27 divides 80 by 3 as if tasks could be chopped up.

Before any timing math, write the longest single task in the margin. No parallel time can be smaller than that task plus the sequential steps, so you can cross out every answer below it right away.
- Sequential time = the sum of all steps.
- Parallel time = sequential part + longest parallel part (the busiest processor).
- Speedup = sequential time ÷ parallel time. Sequential on top, no units.
- Steps that must run alone are added in full, however many processors you have.