The question this answers
I parallelised the expensive loop and the job is only twice as fast on sixteen cores — where did the rest of the speedup go?
A 100-second batch job: 10 seconds of sequential setup (read config, open a connection, load a lookup table, and at the end write one output file) and 90 seconds of a parallelisable transformation over records.
Nothing during the parallel phase — records are independent. The serial phase is serial for structural reasons (ordering, a single output file, a single connection handshake), not because of a lock. That distinction matters: a lock can be removed, a structural dependency usually cannot.
The serial section executes exactly once, on exactly one worker, in every schedule. Therefore total time is never less than the serial time, whatever the core count.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
The intuition, before any formula
Take the 100-second job. Ten seconds of it are sequential. Now imagine the parallel part becomes *free* — infinitely many cores, zero time. The job still takes 10 seconds. That is the whole of Amdahl's Law, and it is worth sitting with before seeing an equation, because the equation tends to be memorised while the intuition is what you actually use in a design review.
Two consequences follow immediately. First, the ceiling: maximum speedup is total time ÷ serial time — here 100/10 = 10×, and no hardware purchase changes it. Second, and more useful day to day, the *approach* to the ceiling is brutally sublinear. With 8 cores the parallel part takes 90/8 = 11.25 s, so total is 21.25 s and speedup is 4.7×, not 8×. Going from 8 to 16 cores takes it to 15.6 s — a 1.36× improvement for double the hardware. Going from 16 to 32 gets 12.8 s: 1.22× for double again. You are paying linearly for a return that is converging.
The third consequence is the one that changes behaviour: as you add cores, the serial section becomes the whole job. At 1 core it is 10% of the time. At 8 cores it is 47%. At 32 cores it is 78%. So a profiler run on a big machine points at the setup code, which looked negligible on a laptop and now dominates. Optimising the parallel part further is nearly worthless at that point; shaving 2 seconds off the serial part is worth more than doubling the core count.
- Maximum speedup = 1 ÷ serial fraction. 10% serial caps you at 10×, 5% at 20×, 1% at 100×.
- The formula, second: S(P) = 1 / (s + (1 − s)/P), where s is the serial fraction and P the worker count.
- The serial section's *share of wall time* grows with core count — it becomes the profile's hot spot on big machines.
- Above a modest core count, reducing the serial fraction beats adding hardware, usually by a lot.
job = 10s serial + 90s parallelisable (serial fraction s = 0.10)
cores parallel part total speedup serial share of total cost of the last doubling
1 90.00s 100.00s 1.00x 10% —
2 45.00s 55.00s 1.82x 18% 1.82x
4 22.50s 32.50s 3.08x 31% 1.69x
8 11.25s 21.25s 4.71x 47% 1.53x
16 5.63s 15.63s 6.40x 64% 1.36x
32 2.81s 12.81s 7.81x 78% 1.22x
64 1.41s 11.41s 8.77x 88% 1.12x
128 0.70s 10.70s 9.35x 93% 1.07x
inf 0.00s 10.00s 10.00x 100% 1.00x
CEILING total / serial = 100 / 10 = 10x <- unreachable, and
approached slowly
WHERE THE LEVERAGE IS, at 32 cores (total 12.81s):
halve the parallel work (90s -> 45s) -> total 11.41s ( 1.12x better )
halve the serial work (10s -> 5s) -> total 7.81s ( 1.64x better )
double the cores (32 -> 64) -> total 11.41s ( 1.12x better )
The serial section is 10% of the code and the entire optimisation target.The curves, and what they say about buying hardware
Plotting speedup against core count for several serial fractions gives the picture worth carrying around. At 50% parallel the curve is essentially flat by 8 cores and asymptotes at 2×. At 80% it reaches 5×, but the last 20% of that takes 100 cores. At 95% it approaches 20× and still delivers real gains at 32. At 99% it behaves nearly ideally through 32 cores and then bends. Small differences in the serial fraction produce enormous differences in scaling, which is why "we parallelised most of it" is not a specification.
This is also the honest answer to a common budget question. If your workload is 80% parallel, a 64-core machine gives 4.7× and a 128-core machine gives 4.85× — you are paying twice for 3% more. The measurement that should precede any such purchase is not "how many cores can we get" but "what is our serial fraction", and it is measurable: run at two core counts, and solve for s from the observed speedup (the Karp–Flatt metric does exactly this and also exposes overhead that grows with P).
One caution the plotted curve does not show: real curves are usually *worse* than Amdahl predicts, because Amdahl assumes the parallel part scales perfectly and there is no coordination cost. Add Parallel Overhead, memory-bandwidth limits and contention and the curve can peak and then decline, which the idealised model never does. Amdahl gives you the ceiling; reality gives you less.
Where the serial fraction actually hides
The law is easy; finding your serial fraction is the work. It is almost never one clearly labelled setup function. It is distributed through the program in places that look parallel, and the matrix below is a checklist of where it usually lives.
The most under-recognised entry is the *implicitly* serial section: a critical section that every worker must pass through. A lock held for 1 ms by each of a million tasks is 1000 seconds of serialised time no matter how many cores run the rest, and Amdahl treats it exactly like the setup code — because it is exactly like the setup code. This is why What Contention Actually Costs and Amdahl are the same lesson from two directions, and why shrinking a critical section is often the highest-leverage parallel optimisation available (Finding the Critical Section).
The second under-recognised entry is anything that has to happen once, at the end: the combine step, writing one output file, committing one transaction, sorting the merged result. Those grow with the *number of chunks*, so over-decomposing to help load balance can quietly increase the serial fraction. And the third is process-level: JIT warmup, class loading, connection establishment and configuration parsing are serial, invisible on a long run, and dominant on a short one (JIT and Warm-Up: The First Thousand Requests Are a Different Program in perf is the depth here).
| Where | Why it is serial | How to spot it | What sometimes removes it |
|---|---|---|---|
| Setup and teardown | Runs once by definition: config, connections, warm caches, final flush | Fixed wall time regardless of input size or core count | Overlap with the parallel phase; make it lazy; amortise across runs |
| A shared lock every task takes | Only one worker at a time, so it is serial time in disguise | Lock wait time scales with worker count while throughput does not | Shrink the critical section, shard the lock, use private state and combine |
| The combine / merge step | One worker folds P partials, or one writer produces one output | Grows with chunk count, not with input size | Tree-combine instead of a linear fold; fewer chunks; parallel merge |
| Ordered output | The result must be emitted in input order | A buffer that reorders results before writing | Write per-chunk outputs and concatenate; or accept unordered output |
| A single connection, file handle or device | The resource itself serialises access | Workers blocked on the same handle in a thread dump | More handles, batching, or moving the I/O out of the parallel phase |
| Runtime warmup | JIT compilation, class loading, page faults on first touch | First iteration far slower; short runs scale worse than long ones | Warm up before measuring; not fixable for genuinely short jobs |
| Load imbalance at the tail | One straggler while everyone waits — behaves exactly like serial time | Workers idle before the join; long tail in task durations | Over-decompose; work stealing; split by cost rather than count |
Key points
- The serial section runs once, on one worker, in every schedule — so total time can never fall below it.
- Maximum speedup is 1 ÷ serial fraction: 10% serial caps you at 10×, and that ceiling is never actually reached.
- The approach to the ceiling is sharply sublinear; each core doubling buys progressively less.
- As cores increase, the serial section becomes the dominant share of wall time and the correct optimisation target.
- A critical section every task passes through is serial time in disguise and is counted by Amdahl exactly like setup code.
- Measure your serial fraction from two runs at different core counts rather than guessing it.
- Real curves fall below Amdahl's because it assumes perfect scaling and zero coordination cost.
The loop, answered
Every field is required, which is why no lesson here can recommend concurrency without naming the interleaving that breaks it, the complexity it adds, and the simpler thing to consider first.
- • Divide total sequential time into a serial portion s and a parallelisable portion (1 − s).
- • With P workers, the parallel portion takes (1 − s)/P and the serial portion still takes s.
- • Speedup S(P) = 1 / (s + (1 − s)/P), which increases with P and converges to 1/s.
- • The serial portion's share of wall time is s / (s + (1 − s)/P), which rises toward 1 as P grows.
- • Marginal benefit of doubling P shrinks with every doubling, so cost per unit of speedup rises continuously.
- • To improve the ceiling you must reduce s itself — parallelise more of the work, remove a lock, or overlap the serial phase with the parallel one.
- • Every schedule, at every core count, contains the serial section executed once by one worker while all others are idle — the invariant that makes the ceiling unavoidable.
- • At 32 cores the parallel phase completes in 2.8 s while the 10 s serial phase is unchanged, so 31 workers are idle for 78% of the job.
- • A "parallel" phase where every task takes a shared lock for 1 ms: the workers interleave, but only one is inside at a time, so the lock-held time sums exactly like a serial section.
- • A straggler at the end of the parallel phase: one worker computes while the rest wait at the join — indistinguishable from serial time in the wall-clock accounting (Fork/Join).
- • Overlapping setup with the parallel phase (start workers on records already loaded while the lookup table is still loading) removes serial time from the critical path without removing the work.
- • Guaranteed: no schedule finishes faster than the serial section, at any worker count.
- • Guaranteed: speedup is bounded above by 1/s, and the bound is approached asymptotically, never met.
- • NOT guaranteed: that you will get close to the bound. Overhead, contention and bandwidth put the real curve below it.
- • NOT guaranteed: that the serial fraction is constant. It usually grows with worker count as contention and combine cost grow.
- • NOT guaranteed: that the model applies to a fixed problem *size* growing with the machine — that is a different question, and it is Gustafson's Law.
- • NOT guaranteed: that s is small because the code looks parallel. Locks, ordered output and combine steps are serial and rarely labelled as such.
- • Every contended resource contributes to the effective serial fraction: a lock, a shared queue, a single output file, one database connection.
- • Contention typically grows with worker count, so the effective s rises as you scale — the measured curve bends earlier than the model predicts.
- • Memory bandwidth is a shared resource that behaves like a serial fraction for bandwidth-bound work, capping speedup regardless of cores (Memory Bandwidth: More Cores, Same Bus).
- • The join at the end of a parallel phase is a synchronization point whose cost grows with the number of participants.
- • Buying hardware against a serial-fraction-limited workload: linear cost, converging returns.
- • Optimising the parallel phase when the serial phase already dominates wall time on the target machine.
- • Mistaking a lock-serialised region for parallel code, so the measured s is far larger than the estimated one.
- • An effective serial fraction that grows with P from contention, producing a curve that peaks and then declines.
- • Over-decomposition increasing combine cost, raising s while trying to improve balance.
- • Benchmarking on a small machine where the serial section is invisible, then deploying to a large one where it is the whole profile.
- • As a design-time sanity check: knowing the ceiling before writing the parallel version prevents most disappointment.
- • As a diagnostic: measured speedup plus core count gives you s, which tells you whether to optimise, restructure or stop.
- • As a purchasing argument, in both directions — it justifies more cores for a 99%-parallel workload and refuses them for an 80% one.
- • As a redirect: it identifies the serial section as the target, which is usually a small amount of code with large leverage.
- • When used to argue that parallelism is not worth pursuing — a 95%-parallel workload still gets 12× on 32 cores, which is enormous.
- • When applied to a problem whose size grows with the machine, where the fixed-size assumption is simply wrong (Gustafson's Law).
- • When s is estimated by eye rather than measured; the estimate is almost always too low because implicit serialisation is invisible.
- • When treated as an upper bound that will be approached, rather than a ceiling that reality falls short of.
- • Speedup at two or more core counts, then solve for the serial fraction — the Karp–Flatt metric, which also reveals whether the effective s grows with P.
- • Wall time of the serial phase in isolation, and its share of total time at the target core count rather than on a laptop.
- • Profile taken at the *target* core count. A profile from a 4-core dev machine attributes time completely differently from one at 64 cores.
- • Lock wait time summed across workers, which converts directly into effective serial time.
- • Time from the last parallel task finishing to the job ending — the combine and teardown tail.
- • Idle-worker time during the run, which is serial time viewed from the other side.
- • Reducing the serial fraction usually means restructuring rather than tuning: overlapping phases, removing shared resources, or changing output ordering guarantees.
- • Overlapping setup with the parallel phase introduces genuine concurrency into code that was safely sequential, with all the correctness obligations that implies.
- • Removing a shared lock typically means duplicating state per worker and combining afterwards, which adds memory and a combine step.
- • The analysis itself needs measurement infrastructure at multiple core counts, which most benchmark harnesses are not set up for.
- • Reduce the total work instead: a better algorithm cuts both phases and composes with whatever parallelism you have.
- • Overlap rather than parallelise — pipeline the serial and parallel phases so the serial part is off the critical path (Pipeline Parallelism: Different Items, Different Stages).
- • Scale out across independent inputs: run many whole jobs concurrently, where each job's serial section overlaps another job's parallel section. This sidesteps the law entirely for throughput.
- • Grow the problem instead of the machine, when that is what you actually want — the reframing in Gustafson's Law.
- • Accept the ceiling and stop. For an 80%-parallel job, 8 cores captures most of what exists and the rest of the budget is better spent elsewhere.
Amdahl's law: the serial ceiling
s = 0.10 n = 32
Amdahl S(n) = 1 / (s + (1 − s)/n) = 7.805× ← fixed problem, more machine
S(1 000 000) = 10.000× ← a million cores, and still under 10×
Gustafson S(n) = s + n(1 − s) = 28.900× ← fixed time, bigger problemWhy is 8 cores only 4.5×?
| workers | ideal | Amdahl only | realistic | limited by |
|---|---|---|---|---|
| 1 | 1.0× | 1.00× | 1.00× | none |
| 2 | 2.0× | 1.90× | 1.85× | serial |
| 4 | 4.0× | 3.48× | 3.19× | serial |
| 6 | 6.0× | 4.80× | 4.17× | serial |
| 8 | 8.0× | 5.93× | 4.17× | bandwidth |
| 10 | 10.0× | 6.90× | 4.17× | bandwidth |
| 12 | 12.0× | 7.74× | 4.17× | bandwidth |
| 14 | 14.0× | 8.48× | 4.17× | bandwidth |
| 16 | 16.0× | 9.14× | 4.17× | bandwidth |
CPU parallelism simulator
Amdahl’s term, a synchronisation term, an oversubscription term and a bandwidth ceiling, each one a knob you can switch off. Real curves have more causes than four and are rarely this smooth. There is no ideal core count to read off this chart.
What people believe, and what is true
Amdahl's Law says parallelism is not worth it.
It says the ceiling is set by the serial fraction. At 95% parallel that ceiling is 20×, which is a transformative speedup. It bounds expectations; it does not discourage.
Our code is 90% parallel, so 16 cores should give roughly 14×.
It gives 6.4×. The serial 10% is a fixed 10 units of time while the parallel part falls to 5.6 — and the ceiling, even at infinite cores, is 10×.
The serial fraction is the setup code.
It is everything that happens one-at-a-time, including every critical section, the combine step, ordered output and the straggler tail. Those are usually larger than the setup.
Amdahl and Gustafson contradict each other.
They answer different questions. Amdahl fixes the problem size and asks how much faster; Gustafson fixes the time and asks how much bigger a problem fits.
Go deeper
Overview
If part of the job has to happen one step at a time, that part sets a floor on how fast the whole job can be — no matter how many cores you add.
Practical
Measure the serial fraction from two runs at different core counts. Above a modest core count, cutting it beats adding hardware, usually by a wide margin.
Advanced
Look for implicit serialisation: locks every task takes, the combine step, ordered output, the straggler tail. The effective serial fraction usually grows with worker count.
Internals
Karp–Flatt computes the experimentally determined serial fraction from measured speedup; if it rises with P, the extra is coordination overhead rather than genuine serial work, and the two have different remedies.