Amdahl's Law and the Serial Fraction That Caps Speedup

Sixteen cores should give a program sixteen times the throughput. They give four. The work was split carefully, the split was balanced, and no core is idle, and yet the aggregate rate barely moved past a certain point. The reason is almost always the same: some fraction of the work cannot be split, and that fraction sets a ceiling that additional hardware approaches but never reaches.

Gene Amdahl stated the bound in 1967 as an argument about the practical limits of parallel processing, and it remains the first calculation to perform before buying cores. The calculation is one line of arithmetic. Interpreting it correctly, and knowing when it does not apply, takes more care.

The bound written out

Take a workload that takes time $T$ on one processor. A fraction $s$ of that time is inherently serial and a fraction $1-s$ can be divided among $N$ processors. The parallel time is

$$T(N) = sT + \frac{(1-s)T}{N}$$

so the speedup relative to one processor is

$$S(N) = \frac{T}{T(N)} = \frac{1}{s + \frac{1-s}{N}}$$

As $N$ grows without bound, the term $(1-s)/N$ vanishes and the speedup approaches $1/s$. A serial fraction of 5% caps speedup at 20. A serial fraction of 1% caps it at 100. A serial fraction of 20% caps it at 5, which is why a program with an unexamined global lock rarely benefits from more than a handful of cores.

Serial fraction	Cap on speedup	8 cores	64 cores
0.50	2.0	1.8	2.0
0.10	10.0	4.7	8.8
0.01	100.0	7.5	39.0
0.001	1000.0	7.9	60.2

The table shows the shape that matters in practice: the first few processors deliver most of the improvement, and the value of each additional processor falls off sharply. Going from 1 to 8 cores with a 1% serial fraction yields 7.5x. Going from 8 to 64 yields another 5.2x, for an eightfold increase in hardware. Going from 64 to 256 would yield roughly 2x more.

What actually counts as serial

The serial fraction is not a property of the algorithm in the abstract; it is a property of the execution. Code that is single-threaded is serial. So is a critical section, a barrier, an atomic counter that every worker increments, a malloc call that takes an allocator lock, and a page fault on a shared mapping that requires the kernel to take a global lock. None of these look like “the serial part” in a design document, and all of them count.

The nontrivial contributors are usually small in line count and large in time:

• Initialization and teardown that run on one thread while others wait. Amdahl’s framing assumes the serial part is interspersed, but concentrated serial phases at the start and end behave the same way for the bound.
• Reduction and aggregation. Work that must combine per-thread results is serial unless the combination is itself a tree over $N$ partial results, which is still $O(\log N)$ serial steps rather than $O(1)$.
• Amortized maintenance. Reference counting with shared counts, membarrier-driven reclamation, and any statically sized freelist touched by all workers all serialize.
• Work distribution. A single queue from which every worker pops introduces a serial operation per item. Whether that operation costs nanoseconds or microseconds determines whether the fraction is negligible or dominant.

The measurement that matters is not the fraction of source lines, but the fraction of wall time during which only one thread can make progress. A profiler that records thread timelines answers this directly: the serial fraction is the length of the intervals in which exactly one thread is runnable, divided by the total.

Estimating the fraction without a profiler

For a fixed workload, two measurements determine $s$ exactly. Run on one processor to obtain $T_1$, and on $N$ processors to obtain $T_N$. Then solve the equation for $s$:

def serial_fraction(t1, tn, n):
    # Solve t1/tn = 1/(s + (1-s)/n)
    speedup = t1 / tn
    return (1.0 / speedup - 1.0 / n) / (1.0 - 1.0 / n)

print(serial_fraction(1.00, 0.25, 8))   # 0.142857 -> cap near 7x
print(serial_fraction(1.00, 0.14, 8))   # 0.017094 -> cap near 58x

Two runs suffice because the model has one free parameter. The estimate is only as good as the measurements: if the $N$-processor run was affected by memory bandwidth saturation rather than serialization, the fitted $s$ absorbs that effect and the resulting cap is optimistic for larger $N$.

A useful refinement is to fit across several processor counts and check whether a single $s$ explains all of them. Real code usually shows a serial fraction that grows with $N$, because the cost of coordination grows. When the fit to two points predicts a value that the four-point measurement contradicts, the model is being asked to describe something it does not cover, which is the situation discussed below.

Why the bound overstates in practice and understates in theory

Amdahl’s law assumes the serial fraction is a property of the problem and the parallel part scales perfectly. Both assumptions fail in different directions.

The first failure makes it optimistic. A fixed workload divided among more processors means each processor handles a smaller slice, so per-processor overheads that are constant per item, such as loop setup or function call overhead, become a larger share of each slice. More importantly, memory bandwidth and last-level cache are shared resources that do not scale with core count; a workload whose parallel part is memory-bound stops scaling once the cores together saturate the memory controllers. Amdahl’s law has no term for this, and the fitted serial fraction will look as though it grew.

The second failure makes it pessimistic. Gustafson pointed out that the reason to use more processors is usually to solve a larger problem in the same time, not to solve the same problem faster. If the problem size grows with $N$ while the serial part stays fixed in duration, the speedup is $s + N(1-s)$, which is unbounded in $N$. The distinction matters when choosing between the two framings: a fixed workload is the right model for a transaction processing service with fixed request sizes, and a scaled workload is the right model for a simulation whose grid resolution increases with available compute.

/* Amdahl bound for a fixed workload; time_units arbitrary */
double amdahl_speedup(double serial_frac, int procs) {
    double parallel = 1.0 - serial_frac;
    return 1.0 / (serial_frac + parallel / procs);
}

The practical reading is that fixed-workload speedup degrades before the formula says it will, and the formula describes a ceiling that no amount of tuning of the parallel part can raise. If a program is at 4x on 8 cores, the ceiling is not 8x with better code; it is somewhere below 8x determined by the serial part, and the only way past it is to shorten the serial part.

Shortening the serial part rather than adding processors

The interventions that raise the ceiling are the ones that remove serialization rather than parallelize further.

Replace per-item serial operations with per-thread accumulators. A shared counter incremented once per item is a serial operation per item, and its cost grows under contention. Thread-local counters summed at the end turn $N$ contended increments into one uncontended increment per thread plus a final reduction. The trade is memory per thread and a stale intermediate value, which is acceptable for statistics and not acceptable for a sequence number.

Shorten critical sections to the state that truly must be shared. The serial time is the total time each item spends inside a critical section, not the lock count. Moving a log write, an allocation, or a hash computation outside the lock reduces the serial fraction even if the lock is still taken once per item.

Replace a global rendezvous with a tree. A barrier over $N$ threads that has every thread wait on one counter costs $O(N)$ work serialized in the contended case; a combining tree costs $O(\log N)$. For $N = 64$ that is a factor of ten in the serial cost of synchronization.

Reconsider whether the phase must be serial at all. Some operations framed as reductions are associative and can be performed redundantly. Others, such as allocating a unique identifier, need a serialized source but not necessarily a serialized duration: blocks of identifiers can be reserved by one atomic operation and then distributed locally.

The cost sits at the boundary, not in the work

A useful way to read the fitted serial fraction is as the share of wall time spent at any point where the number of runnable threads is one. That includes time inside the kernel on behalf of an operation that takes a global resource, and it includes time waiting for another thread to finish a handoff, which is not running code at all but is still serialized time. On a system with 32 hardware threads, a mere 100 microseconds of serialized handoff per 10 milliseconds of parallel work puts the serial fraction at 1%, capping speedup near 100x before any other effect is considered.

The corollary is that reducing the count of synchronization operations is often more valuable than reducing their individual cost. Two locks acquired at once cost the sum of their serial times; a design that acquires one covers both operations. Merger of this kind changes the serial fraction multiplicatively, which matters far more at the ceiling than equivalent effort spent optimizing the parallel part.

The companion bound, which accounts for the cost of coordination rising with processor count and predicts that throughput eventually falls rather than flattening, is derived in The Universal Scalability Law: Why Throughput Peaks and Then Falls. The serial fraction described here usually turns out, on inspection, to be a lock-protected section of the kind analysed in Critical Sections, Futexes, and What a Mutex Really Costs.