A job splits into a part that can be shared out and a part that cannot. Machines shrink the first and leave the second exactly as it was, so the speedup climbs toward 1/(1 − p) and stops there. Five per cent of serial work caps the whole job at twenty times, and no machine count anywhere on the curve changes that number.
Core ideas
One equation, and then the two things it is usually misread about: where its limit is, and what you paid for the part of the curve you are on.
Split the runtime on one machine into p that can be spread across machines and 1 − p that cannot. Adding machines divides the first by n and does nothing whatever to the second, so the total time falls to (1 − p) + p/n of what it was and the speedup is the reciprocal. The serial piece is not a percentage that shrinks as the rest does — it is a fixed stretch of wall-clock time, and at large n it is essentially the whole runtime.
p/n falls toward zero and never reaches it, so S(n) rises toward 1/(1 − p) and never reaches that either. At p = 19/20 the ceiling is 20×: two machines give 1.905×, thirty-two give 12.549×, and five hundred and twelve give 19.284×. Reading a table of the first few rows tells you the curve is bending; only the asymptote tells you what it is bending toward.
S(n)/n is the share of each machine you are actually using. At n = 32 it is 20/51, or 39.22% — three fifths of the fleet is waiting on the serial part. At the 171 machines that reach ninety per cent of the ceiling it is 10.5%. A speedup quoted without its efficiency hides what the speedup cost.
The material
Where the formula comes from, why its limit is the interesting part, and the closed form for the machine count that reaches a fraction of it.
Let p be the fraction of a job’s single-machine runtime that can be executed in parallel, so 1 − p is the serial fraction. On n machines the runtime becomes (1 − p) + p/n of the original, and the speedup is
S(n) = 1/((1 − p) + p/n).
The model assumes the parallel part divides perfectly, the machines are identical, and coordinating them is free. All three are optimistic, which is why this curve is an upper bound.
Normalise the one-machine runtime to 1. The serial part takes 1 − p no matter how many machines are present; the parallel part takes p on one machine and p/n on n. Add them, and the speedup is the ratio of the old runtime to the new one.
As n grows without bound, p/n → 0, so
S(n) → 1/(1 − p),
and because p/n > 0 for every finite n, S(n) is strictly below 1/(1 − p) at every machine count. The bound depends on the serial fraction alone: the hardware does not appear in it.
This is the whole point of the law and the reason it is worth a lesson. A curve that climbs more and more slowly could be climbing toward anything; this one is climbing toward a number you can write down before you buy a single machine. The reciprocal of the serial fraction is the answer, and “Graphs and Asymptotes” on the Algebra path is where reading a limit off a curve was set up.
p = 19/20 gives a ceiling of 20×. Two machines reach 40/21 = 1.905×; four reach 80/23 = 3.478×; eight reach 160/27 = 5.926×; thirty-two reach 640/51 = 12.549×. Each doubling adds less than the one before, and the sequence is converging on 20 rather than on anything larger. A team that has measured the first three rows and extrapolated a line through them will budget for a speedup that does not exist.
Since the ceiling is never reached, the useful question is how many machines it takes to get a given share of the way there. Write the target as a fraction f of the ceiling and solve the inequality: the algebra is one cross-multiplication and it leaves no root and no logarithm behind.
The two factors are worth reading separately. f/(1 − f) is the odds of the target — nine for ninety per cent, ninety-nine for ninety-nine — and p/(1 − p) is the ratio of parallel work to serial work. The machine count is their product, so tightening the target from ninety to ninety-nine per cent costs eleven times as many machines against the same code.
The lab finds 171 twice: once by scanning integer n until the speedup clears the target, and once by evaluating the product above and rounding up. Two routes to one integer is the check, and the scan is the one that carries the claim — a closed form that happens to agree is a check on the algebra, not a substitute for it.
S(n)/n is the fraction of a machine each machine contributes. It starts at 1 and falls monotonically: 95.2% at two machines, 74.1% at eight, 39.22% at thirty-two, 10.5% at the one hundred and seventy-one that reach ninety per cent of the ceiling. Every one of those machines is paid for in full.
At p = 19/20, thirty-two machines give 640/51 = 12.549× and sixty-four give 1280/83 = 15.422×. The second block of thirty-two adds a factor of 1.23, and everything still unbought above it is the 20/12.549 = 1.59× between here and the ceiling — which no purchase can close. That is the arithmetic a “double the fleet, halve the runtime” plan is up against.
One caution about p itself. It is a share of time measured on one machine, not a share of code or of functions: a lock held for a tenth of the runtime is a tenth of the serial fraction even if it is two lines. This course takes p as given. Measuring it is “Measuring Systems”, and it is harder than this lesson.
Interactive
What the next machine buys, and where it stops buying anything
Method
The ceiling first, because it decides whether the rest of the arithmetic is worth doing.
1/(1 − p) is the most the job can ever go faster. If that number is below what the plan needs, no machine count rescues it and the next move is to shrink 1 − p, not to buy.
Substitute into 1/((1 − p) + p/n) and keep it as a fraction. Compare it to n — the speedup people assume — and to the ceiling, and report the gaps to both.
S(n)/n is the share of each machine you are using. It is the figure that turns a speedup into a bill, and quoting a speedup without it is how a 12.5× result on thirty-two machines gets called a success.
n ≥ (f/(1 − f))·(p/(1 − p)), rounded up. Do it for two targets, not one: the jump from ninety to ninety-nine per cent of the ceiling multiplies the fleet by eleven, and seeing that pair is what makes the target a decision.
Perfect division of the parallel part, identical machines, free coordination. Every one of those is generous, so S(n) is an upper bound — and “The Universal Scalability Law” is the lesson that charges for the third one.
Everything below is an exact fraction of p = 19/20. The decimals are printed only where a reader wants to compare two of them by eye.
The S(171) = 18 line is the one doing the work. 171 came out of an inequality, and substituting it back gives exactly 18, which is exactly nine tenths of 20 — so the algebra and the definition of the target agree on the nose rather than to three decimal places.
Notice what 171 machines bought: 18× where the honest linear expectation was 171×, at 10.5% efficiency. Ninety per cent of the ceiling is a long way past the point where the fleet is mostly idle.
For a faded attempt, take p = 4/5. Write down the ceiling, then S(8) and S(64) as fractions, then the efficiency at each, then the n that reaches ninety per cent. Predict which of the two speedups is closer to half the ceiling before you compute either, and check your four answers against the lab with the parallel fraction set to 80%.
You should be able to write 1/(1 − p) down before evaluating anything, compute S(n) and S(n)/n as exact fractions at a stated n, and produce the machine count for a target fraction of the ceiling both by the inequality and by a scan, getting the same integer twice.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.