Amdahl’s Law is a formula that calculates the maximum speedup you can get by improving part of a system, while the rest stays the same. It’s most commonly applied to parallel computing, where it reveals a hard ceiling: no matter how many processors you throw at a problem, the parts that can’t run in parallel will always limit your total speed. The law was first described by computer architect Gene Amdahl in a 1967 paper presented at the AFIPS conference in Atlantic City, and it remains one of the most important concepts in computer science and system design.
The Core Idea
Every computing task is made up of two types of work. Some parts can be split across multiple processors and run simultaneously (the parallel portion). Other parts have to execute one step at a time, in order (the serial portion). Amdahl’s Law says the serial portion acts as a hard bottleneck. Even if you speed up the parallel portion to near-zero execution time, you’re still stuck waiting for the serial portion to finish.
Think of it like a factory assembly line. If one worker spends 30 minutes hand-painting each item and no one else can help with that step, it doesn’t matter if you hire 1,000 workers for every other step. Your throughput is capped by those 30 minutes.
The Formula
Amdahl’s Law is expressed as:
Speedup = 1 / ((1 – p) + p/N)
Where p is the fraction of the task that can be parallelized (a number between 0 and 1), N is the number of processors, and (1 – p) is the serial fraction that can’t be parallelized. The result tells you how many times faster the whole task completes compared to running it on a single processor.
If 90% of your program can run in parallel (p = 0.9) and you use 10 processors, the speedup is 1 / (0.1 + 0.9/10) = 1 / 0.19 ≈ 5.3x. That’s noticeably less than the 10x you might hope for. The remaining 10% of serial work eats a significant chunk of your potential gain.
The Speedup Ceiling
The most powerful insight from Amdahl’s Law comes when you imagine an unlimited number of processors. As N grows toward infinity, the p/N term shrinks to zero, and the formula simplifies to:
Maximum speedup = 1 / (1 – p)
This means the serial fraction alone determines your absolute ceiling. If 5% of your program must run sequentially, the best you can ever do is a 20x speedup, even with a million processors. If 25% is serial, you’re capped at 4x. If half the program is serial, you’ll never exceed 2x.
This is why Amdahl’s Law is often described as a law of diminishing returns. The first few processors you add deliver significant gains. Each additional processor contributes less and less, and eventually adding more hardware produces almost no measurable improvement. Research from Duke University’s physics department illustrates this starkly: unless the ratio of parallelizable work to serial work is around 100,000 to 1, you can’t meaningfully benefit from having 128 processors on a typical computing cluster.
What Counts as Serial Work
The serial portion isn’t just “slow code.” It includes any work that depends on the result of a previous step before it can proceed. Common examples include reading data from disk before processing can begin, writing final results to a single output, coordinating or synchronizing data between processors, and any sequential logic where step B needs the answer from step A.
Communication between processors is a particularly sneaky source of serial overhead. When processors need to share intermediate results, they spend time waiting for messages and coordinating. Research from IEEE has shown that without separating communication time from actual computing time, predictions about parallel performance are unreliable. In practice, the coordination overhead can grow as you add processors, making the real-world ceiling even lower than the formula predicts.
A Practical Example
Suppose you have a data analysis pipeline that takes 100 seconds on one processor. Loading the data takes 10 seconds and can’t be parallelized. The remaining 90 seconds of computation can be split across processors.
- 2 processors: 10 + 90/2 = 55 seconds (1.8x speedup)
- 4 processors: 10 + 90/4 = 32.5 seconds (3.1x speedup)
- 10 processors: 10 + 90/10 = 19 seconds (5.3x speedup)
- 100 processors: 10 + 90/100 = 10.9 seconds (9.2x speedup)
- 1,000 processors: 10 + 90/1000 = 10.09 seconds (9.9x speedup)
Going from 1 to 4 processors cuts execution time by two-thirds. Going from 100 to 1,000 processors saves less than one second. That 10-second serial portion dominates once the parallel work is subdivided enough.
Amdahl’s Law vs. Gustafson’s Law
A common criticism of Amdahl’s Law is that it assumes a fixed problem size. In 1988, John Gustafson proposed an alternative perspective: in practice, when people get more processors, they don’t just solve the same problem faster. They solve bigger problems in the same amount of time. A weather simulation on a supercomputer doesn’t run the same model faster; it runs a higher-resolution model.
Gustafson’s Law reframes the question. Instead of asking “how fast can I solve this fixed task?”, it asks “how much more work can I finish in the same time?” Under this formulation, speedup scales more optimistically because the parallel portion of the workload grows with the number of processors, while the serial portion stays roughly constant. The result is sometimes called “scaled speedup.”
The two laws don’t actually contradict each other. They answer different questions. If you translate Gustafson’s scaled percentages back into Amdahl’s fixed-size framework, the diminishing returns curve looks exactly the same. Gustafson’s version simply reflects how real users tend to behave: they scale their ambitions along with their hardware. Amdahl’s Law remains the right tool when you have a specific task of known size and want to know how much parallelism will help.
Why It Still Matters
Amdahl’s Law shapes decisions across modern computing. It explains why doubling the cores in your laptop doesn’t double its performance for most tasks. It guides software engineers toward optimizing the serial bottlenecks in their code before investing in more parallelism. And it informs cloud computing strategy, where paying for additional virtual machines only makes economic sense if the workload can actually use them effectively.
IEEE research on high-performance computing clouds confirms that either cloud infrastructure or traditional clusters can be exploited effectively, but only if the application can adapt to changing processing conditions dynamically. Simply scaling horizontally without understanding the serial fraction wastes money and hardware. Amdahl’s Law gives you the math to know exactly where that waste begins.