4.3 Speedup and its limitsWhy more processors stop helping

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.
?Wait, what's a heuristic?
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.
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?
I thought about it. Show me
1seq ← 102work ← 903n ← 14REPEAT 4 TIMES5{6 time ← seq + work / n17 DISPLAY(n)8 DISPLAY(time)9 n ← n * 2210}
- line 6 the sequential part never shrinks; only the 90 seconds is shared
- line 9 double the processors each time
- Start: seq = 10, work = 90, n = 1.
- Pass 1: time = 10 + 90 / 1 = 100. Displays 1 and 100. Then n becomes 2.
- Pass 2: time = 10 + 90 / 2 = 55. Displays 2 and 55. n becomes 4.
- Pass 3: time = 10 + 90 / 4 = 32.5. Displays 4 and 32.5. n becomes 8.
- 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). - 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
- Keep a table with columns n and time, and fill in one row per pass.
- n doubles at the end of each pass: 1, 2, 4, 8.
- For the speedup, divide the 1-processor time by the 8-processor time.
- A40 seconds
- B30 seconds
- C60 seconds
- 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.
- AWith enough processors, the job can finish in under 20 seconds
- BWith 4 processors the job takes 25 seconds
- CThe speedup with 4 processors is 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.