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

4.3 Speedup and its limitsWhy more processors stop helping

Mr. Thompkins
If two processors make a job faster, why not use a thousand? Let's find out, because the answer explains why your phone has a handful of cores, not a thousand.

Two things limit speedup. First, whole tasks can't always be split evenly, so some processors finish early and sit idle while the busiest one works. Second, the sequential portion never shrinks. Even if the parallel work could be divided perfectly among any number of processors, the sequential steps would still take their full time.

Take five independent tasks of 60, 50, 40, 30 and 20 seconds, 200 seconds in all. On two processors you can split them perfectly, 60 + 40 and 50 + 30 + 20, for 100 seconds. On three, the ideal would be 66.7 each, but no combination of whole tasks gets there; the best is 70. On four, the best is 60, and on five it's still 60, because the 60-second task can't be split.

Minimum seconds2001 CPU1002 CPUs703 CPUs604 CPUs605 CPUs
Best finish times for tasks of 60, 50, 40, 30 and 20 seconds, found by trying every assignment in Python. After four processors, the 60-second task sets the floor.
?Wait, what's a heuristic?
A heuristic, from Unit 3, is an approach that finds a good-enough answer when finding the best one would take too long. Splitting tasks perfectly among processors gets very hard as the number of tasks grows, so real systems use heuristics, like "give the next biggest task to whichever processor is least busy".

Now the second limit. Suppose a job has 10 seconds that must run alone and 90 seconds of work that can be split evenly among any number of processors. With n processors it takes 10 + 90 ÷ n seconds. Going from 1 processor to 2 saves 45 seconds. Going from 8 to 12 saves less than 4. And however many processors you add, the time can never drop below 10 seconds, so the speedup can never reach past 100 ÷ 10 = 10.

024681012024681012processorsspeedupceiling: 100 ÷ 10 = 10actual speedup1.8245.71
Speedup for 10 seconds of sequential work plus 90 seconds split evenly: 100 ÷ (10 + 90 ÷ n). Each new processor helps less, and the curve can never reach 10.

The CED's way of saying this: when you increase the use of parallel computing, the efficiency of the solution is still limited by its sequential portion, so at some point adding parallel portions will no longer meaningfully increase efficiency. Still, parallel solutions scale more effectively than sequential ones: a bigger problem can be given more processors. Beyond the course, as a bonus: this limit is known as Amdahl's law.

?Wait, how does REPEAT n TIMES work?
REPEAT n TIMES runs the block of code inside the braces exactly n times, from the Exam Reference Sheet in Unit 3. Variables changed inside the block keep their new values for the next time around.
Pause and think
In the job above (10 seconds sequential, 90 seconds shareable), what's the speedup with 9 processors? Is it worth going to 90 processors?
I thought about it. Show me
With 9: 10 + 90 ÷ 9 = 20 seconds, speedup 100 ÷ 20 = 5. With 90: 10 + 1 = 11 seconds, speedup about 9.1. Ten times the processors for less than double the speedup, probably not worth the cost.
Trace the pseudocode
The program below prints the time for the 10 + 90 job on 1, 2, 4 and 8 processors. Trace it. What does it display, and what speedup does 8 processors give?
1seq ← 102work ← 903n ← 14REPEAT 4 TIMES5{6  time ← seq + work / n17  DISPLAY(n)8  DISPLAY(time)9  n ← n * 2210}
  1. line 6 the sequential part never shrinks; only the 90 seconds is shared
  2. line 9 double the processors each time
output › 1 100 2 55 4 32.5 8 21.25
  1. Start: seq = 10, work = 90, n = 1.
  2. Pass 1: time = 10 + 90 / 1 = 100. Displays 1 and 100. Then n becomes 2.
  3. Pass 2: time = 10 + 90 / 2 = 55. Displays 2 and 55. n becomes 4.
  4. Pass 3: time = 10 + 90 / 4 = 32.5. Displays 4 and 32.5. n becomes 8.
  5. Pass 4: time = 10 + 90 / 8 = 21.25. Displays 8 and 21.25. n becomes 16, and the loop has run 4 times, so it stops.
    Why?
    Division happens before addition, like in algebra, so it's 10 + (90 / 8).
  6. Speedup with 8 processors: 100 ÷ 21.25 ≈ 4.71. Eight processors, less than five times as fast.

Answer: It displays 1 100 2 55 4 32.5 8 21.25. With 8 processors the speedup is about 4.71.

Stuck? Get a hint
  1. Keep a table with columns n and time, and fill in one row per pass.
  2. n doubles at the end of each pass: 1, 2, 4, 8.
  3. For the speedup, divide the 1-processor time by the 8-processor time.
Check yourself
Four independent tasks each take 30 seconds, and each must run entirely on one processor. On two processors the minimum time is 60 seconds. What is the minimum time on three processors?
  1. A40 seconds
  2. B30 seconds
  3. C60 seconds
  4. D20 seconds
Show the answer

C. With three processors, one of them must still run two of the 30-second tasks, so the finish is 60 seconds, no better than two. 40 seconds divides 120 by 3 as if tasks could be cut into pieces. You need four processors to reach 30.

Check yourself
A job has 20 seconds that must run alone and 80 seconds that can be split evenly among any number of processors. Which statement is true?
  1. AWith enough processors, the job can finish in under 20 seconds
  2. BWith 4 processors the job takes 25 seconds
  3. CThe speedup with 4 processors is 4
  4. DNo number of processors can make the speedup reach 5
Show the answer

D. Sequentially it takes 100 seconds. The 20 seconds never shrink, so the time stays above 20 and the speedup stays below 100 ÷ 20 = 5. With 4 processors it takes 20 + 80 ÷ 4 = 40 seconds (not 25), a speedup of 2.5 (not 4).

  • Speedup is limited by uneven tasks and by the sequential portion.
  • Adding processors helps less and less, and eventually stops helping in a meaningful way.
  • The time can never drop below the sequential portion, however many processors you add.
  • Parallel solutions still scale better than sequential ones as problems grow.