Amdahl’s Law (but simpler)

tl;dr The Amdahl’s Law Wikipedia article translated into clean, razor-sharp Technical English. No pseudo-academic clutter, no masturbatory notation. Just pure engineering truth.

Amdahl’s law calculates the maximum improvement you can get across an entire system when you only improve one part of it.

In plain terms: Your total performance improvement is strictly limited by the parts of the job you cannot speed up.

It is named after computer scientist Gene Amdahl, who presented it in 1967. It is most commonly used in computing to predict how much faster a software program will run when you run it across multiple processor cores.

The Core Concept: How Speedup Works

“Speedup” is simply how many times faster a system completes a task after an upgrade:

$\displaystyle \text{Speedup} = \frac{\text{Time taken BEFORE improvement}}{\text{Time taken AFTER improvement}}$

Amdahl’s formula calculates total speedup based on two numbers:

$p$ (Parallelizable fraction): The percentage of the execution time that can actually benefit from extra resources (like additional CPU cores).
$s$ (Local speedup): How many times faster that specific improved section runs.

The formula is:

$\displaystyle \text{Overall Speedup} = \frac{1}{(1 - p) + \frac{p}{s}}$

Where:

$(1 - p)$ is the unchangeable, sequential part of the work (the stubborn anchor).
$\frac{p}{s}$ is the accelerated part of the work divided by the firepower you threw at it.

Why the Results Are Worse Than You Expect

People routinely expect that doubling their hardware will double their program’s speed. Amdahl’s law proves why this fails.

Example 1: Optimizing the Wrong Part

Suppose you optimize a routine that only accounts for 10% of total runtime ( $p = 0.10$ ).
You rewrite it to run 10,000 times faster ( $s = 10,000$ ).
The improved slice now finishes in zero seconds.
However, the remaining 90% of the program was untouched.
Overall Speedup: $\frac{1}{0.90 + 0} \approx 1.11$ (an 11% overall improvement).
Result: An infinite improvement to a small section yields an almost unnoticeable real-world gain.

Example 2: The Limits of Brute Force

Suppose 95% of your code can run in parallel across many CPU cores ( $p = 0.95$ ).
Only 5% must run sequentially on a single core ( $1 - p = 0.05$ ).
Even if you buy a supercomputer with infinite processors ( $s = \infty$ ), the parallel part shrinks to zero time.
Maximum Possible Speedup: $\frac{1}{0.05} = 20\times$ .
Result: That tiny 5% single-threaded setup loop prevents you from ever exceeding a $20\times$ speedup, even with millions of processors running.

Step-by-Step Task Breakdown

Any job can be divided into two chunks:

The Sequential Part: Work that must happen in strict step-by-step order (like reading a file from disk or creating a thread). Adding more workers does nothing for this step.
The Parallel Part: Independent work that can be divided among multiple workers (like calculating pixel colors in an image or processing rows in a spreadsheet).

If a task takes 100 seconds:

20 seconds are sequential.
80 seconds are parallel.

If you throw 4 processors at the parallel part, those 80 seconds drop to 20 seconds.
Your total time becomes:

$\displaystyle \text{Total Time} = 20\text{s (sequential)} + \frac{80\text{s}}{4} = 40\text{ seconds (a } 2.5\times \text{ total speedup)}$

Optimizing the Sequential Part of Parallel Programs

Because the sequential portion sets the ultimate speed ceiling, the best way to speed up a parallel program is often to optimize the sequential part itself, rather than just adding more processors.

If you can cut the sequential portion in half (for example, by rewriting an unparallelizable routine to be twice as efficient), your maximum theoretical speed limit immediately doubles.

Transforming Sequential Parts into Parallel Parts

An even more effective strategy is restructuring the algorithm so that work previously considered “strictly sequential” can now be computed in parallel:

Converting global loops into tree reductions.
Breaking large locked data structures into lock-free or partitioned data structures.
Streaming input data in parallel chunks instead of reading it in one single-threaded batch.

Shrinking the sequential fraction ( $(1 - p)$ ) is the only way to allow massive hardware scaling.

Relation to the Law of Diminishing Returns

Amdahl’s law is a concrete demonstration of diminishing returns in computer systems:

Each additional processor core you add produces less total speedup than the one before it.

Going from 1 core to 2 cores cuts parallel time by 50%.
Going from 2 cores to 4 cores cuts it by only an additional 25%.
Going from 64 cores to 128 cores cuts it by less than 1%.

Eventually, the parallel work is compressed so small that your system spends virtually all its time waiting on the sequential part. Adding more hardware beyond this point is simply wasting electricity.

Now I go back to sleep to dream of stainless-steel buttercups.