AP Computer Science Principles · Unit 4 lecture · Part 8 of 11 · 9 min

4.3 Sequential and parallel computingMany processors, one job

Mr. Thompkins
Here's a kitchen question. One cook makes a salad, a soup and a pie, one after another. Three cooks could each take one dish. But somebody still has to shop first, and somebody has to set the table at the end. That's this whole section, in a kitchen.

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.

ModelHow it runsTime it takes
SequentialOne operation at a time, in order, on one processorThe sum of all the steps
ParallelSplit into smaller sequential parts, some running at the same time on several processorsSequential part + longest parallel part
DistributedSeveral separate devices on a network each run part of the programLets problems too big or too slow for one device be solved
The three models. Parallel splits work across processors; distributed splits it across whole devices on a network.
?Wait, what's a processor?
A processor, or CPU, is the part of a computer that carries out a program's instructions. Most phones and laptops have several processor cores, so they can work on several things at the same moment.

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

$\text{sequential time} = \text{sum of all steps}$
One processor, one step at a time
$\text{parallel time} = \text{sequential part} + \text{longest parallel part}$
The slowest processor sets the finish
$\text{speedup} = \dfrac{\text{sequential time}}{\text{parallel time}}$
How many times faster
?Wait, what does "independent" mean for tasks?
Two tasks are independent if neither needs the other's result. Independent tasks can run at the same time on different processors. A task that needs another task's answer has to wait for it, so it belongs in the sequential part.
Pause and think
A program has two independent tasks of 30 seconds each and nothing else. Predict the speedup on two processors. Now add a 20-second setup that must run first. Predict whether the speedup is still 2.
I thought about it. Show me
Without setup: 60 seconds sequential, 30 in parallel, speedup 60 ÷ 30 = 2. With setup: sequential is 80 seconds, parallel is 20 + 30 = 50, speedup 80 ÷ 50 = 1.6. The setup can't be shared, so it drags the speedup below 2.
Compute the speedup
A photo app loads an image (8 seconds), then applies a filter to four tiles that take 24, 18, 12 and 6 seconds, then stitches the tiles together (4 seconds). Loading and stitching must run alone. Each tile is processed entirely on one processor. Find the sequential time, the minimum time on two processors, and the speedup.
1 processor: 72 secondsone CPU8241812642 processors: 42 secondsCPU 1CPU 2824641812done at 42 sorange: must run alone, in orderblue: independent tasks
  1. Sequential: add every step. 8 + 24 + 18 + 12 + 6 + 4 = 72 seconds.
  2. 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.
  3. Try to reach 30: 24 + 6 = 30 on one processor and 18 + 12 = 30 on the other. Perfect balance.
  4. 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.
  5. 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
  1. First add everything for the sequential time.
  2. Split the four tiles into two piles that are as equal as possible.
  3. Parallel time is load + the bigger pile + stitch.
Check yourself
A task takes 150 seconds when run sequentially. A parallel solution of the same task takes 60 seconds. What is the speedup?
  1. A90
  2. B0.4
  3. C2.5
  4. 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.

Check yourself
Three independent tasks take 40, 25 and 15 seconds. Each must run entirely on one processor. What is the minimum time on two processors?
  1. A80 seconds
  2. B40 seconds
  3. C55 seconds
  4. 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.

Exam tip from Mr. T

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.