Technology & Computing · Computers & hardware
Why adding cores stops helping
A fixed job has a part that won't split, and that part sets a ceiling no number of processors can lift.

What you will learn
- Identify the part of a job that extra processors can't help with
- Work out an overall speedup from the fraction of time an improvement covers
- Calculate the maximum speedup a fixed job can reach with unlimited processors
- Name bottlenecks that make added processors return even less than the formula promises
Lesson 1 of 4 · 6 min
Why a 10,000 times speedup can gain you just 11%
Take a program and make one part of it 10,000 times faster. If that part used to take 10% of the running time, the whole program ends up about 11% faster. The other 90% runs exactly as before.
This is Amdahl's law, which the computer scientist Gene Amdahl presented in 1967. The gain from improving one part of a system is limited by the fraction of time that part is in use.
The law is most often applied when the improvement is more processors. Picture a program that processes files. First it scans the disk's directory and builds a list of the files. Then it hands each file to a separate thread, a stream of work that can run on its own processor.
The second part spreads across as many processors as you have. The first part can't. There's one directory, and the list has to exist before any work can be handed out. That's the serial part, the work that has to happen one step at a time.
The result surprises people because they watch the part they improved. Its speedup is the number their effort produced. But the fraction decides the outcome. So the first thing to measure is how much of the clock the untouched part is holding.
The arithmetic is short. Take the fraction of time the improvement doesn't cover. Add the fraction it does cover, divided by how much faster that part became. The overall speedup is 1 divided by that sum.
Try it on the opening example. The untouched fraction is 0.9. The improved fraction is 0.1 divided by 10,000, which is close to nothing. And 1 divided by 0.9 is about 1.11.
A large share doesn't escape either. Speed up a section that takes 99% of the time by a factor of 100, and the overall speedup is 50, not 100. The 1% you didn't improve costs half the benefit.
In practice this becomes a choice between jobs. Suppose part A takes three seconds and part B takes one. Working hard to make B five times faster gives an overall speedup of about 1.25. Making A just twice as fast gives about 1.60.
A modest gain on the larger share beats a big gain on the smaller one.
Try to recallPart A of a job takes three seconds and part B takes one. You can make B five times faster or A twice as fast. Which is the better investment, and what general rule does that illustrate?
Making A twice as fast is the better investment. A holds three quarters of the total time and B holds one quarter. Speeding B up five times leaves A's three seconds untouched and gives an overall speedup of about 1.25. Doubling A's speed gives about 1.60. The rule is that the fraction of total time an improvement covers matters more than how big the improvement is.
Before you speed anything up, find out how much of the clock it holds. A part that takes 10% of the time can never make the whole job more than about 11% faster, however fast you make that part.
Lessons in this topic
Why a 10,000 times speedup can gain you just 11%
Every job has a share that an improvement can't touch. See why that share decides how much faster the whole job gets, more than the size of the improvement does.
The speed limit no number of processors can break
With unlimited processors, a fixed job's speedup still stops at a number you can work out in advance. Real machines deliver less than that.
Why bigger jobs escape the processor speed limit
Hold the time fixed and let the job grow, and the ceiling goes away. See why that worked on a 1,024-processor machine in 1988, and where it doesn't.
What threads share, and why it trips them up
Threads in one program share almost everything except their own stack. See why that makes some ordinary functions give wrong answers when two threads use them at once.
Three quick stories from this topic
Over 1,000 times on 1,024 processors
In 1988, a computer with 1,024 processors ran three programs over 1,000 times faster
The usual formula allowed programs like these a speedup of about 200 at best. The team at Sandia National Laboratories hadn't broken it. Instead of running a fixed job faster, they let the job grow with the machine and kept the running time the same.
The ceiling they seemed to break
If 0.4% of a fixed job has to run one step at a time, 1,024 processors can speed it up about 200 times, and no number of processors can pass 250.
Gustafson's answer
People given a bigger machine solve a bigger problem. The added work is nearly all parallel, so the speedup keeps rising with the number of processors.
The 20 times ceiling
A job that's 95% parallel can't run more than 20 times faster on any number of processors
The 5% that has to run one step at a time takes as long as ever. With 8 processors the job runs about 6 times faster, and with 1,024 about 19.6 times. By then the serial 5% is nearly all that's left on the clock.
The formula
The best possible speedup is 1 divided by the fraction of the work that can't be split. For 5% that's 20. For half the work it's 2.
Real machines do worse
The formula ignores other bottlenecks, such as how fast data moves in and out of memory. When those don't grow with the processor count, the gain is smaller still.
The fraction that matters
Speeding up 10% of a program 10,000 times makes the whole program 11% faster
The other 90% of the running time is untouched, so the program can never finish in less than nine-tenths of its old time. Merely doubling the speed of a part that takes half the time would do three times as much good.
Three seconds against one
Making the one-second part five times faster gives about 1.25. Making the three-second part merely twice as fast gives about 1.60.
The ceiling
If half the work is parallel, you're capped at 2 times. At 95%, the cap is 20. An infinite number of processors doesn't lift it.
Sources
- Amdahl law, Wikipedia
- Reevaluating Amdahl's law, Communications of the ACM, 1988 (copy hosted by the University of Utah)
- Gustafson law, Wikipedia





