Amdahl's law describes the speedup limit when you parallelize a fixed-size workload. State the law, explain what the serial fraction is, and work out the best possible speedup for a job whose runtime is 5% serial.
answer
- S(N) = 1 / (s + (1-s)/N)
- ceiling = 1/s, fixed problem size
- 5% serial -> 20x max, 10.3x at N=20
- strong scaling, ignores overhead
- shrink s beats adding cores
basics
~20 sAmdahl's law: for a fixed job with serial fraction s, speedup on N workers is 1 / (s + (1 - s)/N), capped at 1/s as N grows. At 5% serial the ceiling is 20x, however many workers you add.
solid answer
~50 sAmdahl's law models a **fixed-size** workload split into a fraction `s` that must run sequentially and `1 - s` that parallelizes perfectly. Speedup on N workers is: `S(N) = 1 / (s + (1 - s)/N)` As N goes to infinity the parallel term vanishes and speedup approaches `1/s`. The serial fraction is not "the code you didn't parallelize yet" — it is work that is inherently sequential: startup, final aggregation, I/O that must be ordered, critical sections everything funnels through. With s = 0.05 the ceiling is 20x. Concretely, on 20 workers you already get 1 / (0.05 + 0.95/20) ≈ 10.3x — barely half the theoretical maximum, at 51% efficiency. Going to 100 workers only reaches ≈16.8x. The practical lesson: the payoff from more workers collapses long before the ceiling, so shrinking `s` usually beats adding hardware. Real systems do worse still, because Amdahl ignores communication, synchronization, and contention overhead.
code
text · 9 liness = 0.05 (serial fraction)
S(N) = 1 / (0.05 + 0.95/N)
N=1 -> 1.00x
N=2 -> 1.90x
N=8 -> 5.93x
N=20 -> 10.26x <- half the ceiling, 51% efficiency
N=100 -> 16.81x
N=inf -> 20.00x <- hard ceiling = 1/sgo deeper
Know the formula, know that the ceiling is 1/s, and be able to plug in numbers: 5% serial means at most 20x. Say plainly that more workers stop helping.
Derive the formula from the runtime split, compute intermediate points, and explain why efficiency collapses long before the ceiling. Name the fixed-problem-size assumption.
Estimate the serial fraction from a measured scaling run, translate speedup targets into serial-fraction budgets, and argue for reducing s over buying hardware. Note that Amdahl ignores coordination overhead, so it is an optimistic bound.
Use it as a capacity-planning tool: decide whether a target is reachable at all, where the economically sensible N sits, and when the answer is an architectural change rather than a scaling change. Be explicit that a monotonic model cannot describe retrograde real systems.
## The setup Amdahl's law answers one narrow question: *if I keep the problem exactly the same size and throw more processors at it, how much faster can it finish?* That framing — fixed work, growing hardware — is called **strong scaling**, and every conclusion below depends on it. Split the single-worker runtime into two parts. A fraction `s` (the **serial fraction**) is work that must happen one step at a time: process startup, reading a configuration file, the final merge of partial results, a critical section that every worker must pass through one at a time. The remaining fraction `p = 1 - s` is **perfectly parallelizable**: with N workers it takes `p/N` of the original time. ## The formula New runtime, relative to the original time normalized to 1: `T(N) = s + (1 - s)/N` Speedup is old time over new time: `S(N) = 1 / (s + (1 - s)/N)` As `N -> infinity`, `(1 - s)/N -> 0`, so: `S(max) = 1 / s` The serial part is a hard floor on runtime. You can drive the parallel part to nearly zero, but the serial seconds stay. ## Working the 5% example With `s = 0.05`: - Ceiling: `1 / 0.05 = 20x`. Unlimited hardware buys 20x, never more. - N = 2: `1 / (0.05 + 0.475) = 1.90x` (95% efficiency) - N = 8: `1 / (0.05 + 0.11875) = 5.93x` (74% efficiency) - N = 20: `1 / (0.05 + 0.0475) = 10.26x` (51% efficiency) - N = 100: `1 / (0.05 + 0.0095) = 16.8x` (17% efficiency) - N = 1000: `1 / (0.05 + 0.00095) = 19.6x` (2% efficiency) The shape matters more than any single number. Speedup is steeply sublinear: doubling from 20 to 40 workers moves you from 10.3x to 12.4x. You paid 100% more hardware for 20% more speed. The curve flattens asymptotically toward 20x and never touches it. ## Why the serial fraction dominates Invert the question. To reach a 50x speedup you need `s <= 0.02`. For 100x you need `s <= 0.01`. Speedup targets translate directly into serial-fraction budgets, and those budgets get brutal fast. This is why experienced engineers attack `s` — removing a global lock, replacing a single-writer aggregation step with a tree reduction, overlapping startup with work — before they order more cores. Halving `s` doubles the ceiling; doubling the cores does not. It also explains a common production surprise: a service scales beautifully to 8 workers, then stops improving. That is not a bug — it is Amdahl's curve entering its flat region. The measured knee lets you *estimate* `s`: from an observed speedup `S` on `N` workers, the Karp-Flatt metric gives an experimentally determined serial fraction `e = (1/S - 1/N) / (1 - 1/N)`. If `e` grows as N grows, your losses are not pure serialization — overhead is climbing too. ## What the law deliberately ignores Amdahl's model is optimistic. It assumes: - The parallel portion parallelizes **perfectly**, with zero communication or synchronization cost. - Work divides **evenly**; there is no load imbalance and no straggler. - Adding workers costs nothing — no scheduling overhead, no cache-coherence traffic, no memory-bandwidth saturation. - The problem size is **fixed**. Real systems violate all four. Coordination costs typically grow with N, so measured curves fall below Amdahl's prediction and can even peak and then decline — behavior Amdahl cannot express, since `S(N)` is monotonically increasing. Models with an explicit crosstalk penalty capture that. The fixed-size assumption is the most consequential one. It is a modelling choice, not a law of nature: if bigger machines are used to solve *bigger* problems rather than the same problem faster, the serial part often stays roughly constant while the parallel part grows, and the pessimistic ceiling dissolves. That is a genuinely different question with a genuinely different answer. ## How to use it Treat Amdahl's law as a budgeting tool, not a prophecy. Measure the serial fraction (profile, or fit it from a scaling run), compute the ceiling, and compare the ceiling to your target. If the target is above the ceiling, no amount of hardware will get you there and the only path is redesigning the sequential part. If the target is within reach, the curve tells you the cheapest N that hits it — usually far below the point of diminishing returns.
- You measure 6x speedup on 16 workers. What serial fraction does that imply, and what does it tell you about adding more workers?Solve Amdahl for s: from S = 1/(s + (1-s)/N) with S=6, N=16 you get s ≈ 0.11 (the Karp-Flatt estimate gives the same neighbourhood). That implies a ceiling near 9x, so even infinite workers buy you only 50% more than you already have. The right move is to find and shrink the serial section, not to double the pool.
- Does Amdahl's law say parallelism is not worth pursuing on large machines?No — it says that *for a fixed problem size* the returns flatten. Two escapes exist: reduce the serial fraction, or grow the problem with the machine so the parallel work grows while the serial part stays roughly constant. Amdahl's pessimism is a consequence of its fixed-workload assumption, not a universal verdict on parallel computing.
- Why do real measurements often fall below the Amdahl curve?Amdahl assumes the parallel portion is free of coordination cost and splits evenly. In practice you pay for synchronization, cache-coherence traffic, memory-bandwidth contention, scheduling, and load imbalance, and those costs typically grow with worker count. That is why measured throughput can plateau — or even decline — while Amdahl's formula only ever increases.
A recipe where the oven must preheat for 5 minutes before any cooking starts: hire a hundred cooks and the meal still can't beat the preheat time plus a sliver of chopping.
saying these in an interview costs you the question
- Claiming speedup is linear in the number of workers, or that N workers give N-times speedup
- Treating the serial fraction as 'the part I haven't parallelized yet' rather than inherently sequential work
- Saying Amdahl's law accounts for communication and synchronization overhead — it explicitly does not
- Thinking the ceiling 1/s is approached quickly; in fact you reach only half of it around N = 1/s workers
- Applying the fixed-workload conclusion to a system whose problem size grows with capacity