Gustafson's Law

In one sentence: Gustafson’s law estimates how much more work a computer with many workers can finish in the same time, when the job grows as you add workers.

$S = N - s\,(N - 1)$

Read it out loud: “S equals N minus s times the quantity N minus 1. S is the scaled speedup, how many times more work the parallel run finishes in the same time. N is the number of processors, the workers that run at the same time. s is the serial fraction, the share of the run that one worker must do alone and cannot be split. The brackets mean do the subtraction first, then multiply by s, and then take the result away from N.”

Before you start

The ideas and signs this page uses, explained from zero. For powers of ten, Greek letters and other notation in general, see Math basics.

Processor, parallel and serial work: A processor is a worker inside a computer that carries out instructions. A program is parallel when several processors work on different parts of it at the same time. Work that must be done one piece after another, on one processor, is called serial. If eight processors share a job evenly, each does one eighth of it, and the whole job takes about one eighth of the time, if none of it is serial.
Speedup: Speedup is how many times faster a job finishes. If a job takes 10 minutes on one setup and 2 minutes on another, the speedup is $10 \div 2 = 5$ , because the second setup finishes five times faster. A speedup of 1 means no change at all. A speedup of 7.3 means 7.3 times as much work gets done in the same time.
Fractions, decimals and percent: A fraction such as $0.1$ is a share of a whole. Since $0.1 = \frac{1}{10}$ , it means one tenth. To write it as a percent, multiply by 100, which moves the decimal point two places to the right, so 0.1 is 10%. The serial share in this formula is always a number between 0 and 1, because it is a share of the run.
Order of operations and brackets: Work inside brackets first, then multiply, then add or subtract. In $N - s(N - 1)$ , the part $N - 1$ is done inside the brackets, then multiplied by $s$ , and only then is the product taken away from $N$ . So $8 - 0.1 \times 7$ means $8 - 0.7 = 7.3$ . It does not mean $(8 - 0.1) \times 7$ , which would give 55.3.
Amdahl’s law, the fixed-size comparison: This page compares Gustafson’s law with Amdahl’s law, the older model that assumes the job keeps the same size however many processors you add. In Amdahl’s model the serial share is measured on a single processor running the fixed job. Both models split a run into a serial share and a parallel share, so their results can be compared on the same numbers.

What each symbol means

Symbol	Meaning
$S$	The scaled speedup: how many times more work the parallel run finishes in the same time, compared with one processor doing the same enlarged job. It is a plain number with no unit. A value of 7.3 means the parallel run finishes about 7.3 times as much work in the same time.
$N$	The number of processors working at the same time, a whole number such as 1, 2, 8 or 64. It is a count with no unit. The example uses $N = 8$ , which means eight processors running in parallel.
$s$	The serial fraction: the share of the parallel run’s time that is spent on work that cannot be split across processors. It is a fraction from 0 to 1 with no unit. The example uses $s = 0.1$ , which means 10% of the run is serial.

The formula piece by piece

$N$: Start with the number of processors. Each processor is one worker, and with $N$ of them the parallel part of the job can be shared among $N$ workers. It is a count with no unit. A larger $N$ means more workers doing the parallel work at the same time.
$1 - s$: The parallel share of the parallel run. The serial share is $s$ , and everything else is parallel, so the parallel share is $1 - s$ . If $s = 0.1$ , then $1 - s = 0.9$ , which means 90% of the run is parallel work that every processor shares equally.
$N(1 - s)$: The time one processor would need for all of the parallel work, if it did every share alone. Each of the $N$ processors did $1 - s$ of the work during the parallel run, so one processor doing all $N$ shares needs $N \times (1 - s)$ . In the example that is $8 \times 0.9 = 7.2$ units of time.
$s + N(1 - s)$: The total time one processor needs for the enlarged job. It does the serial part once, which takes $s$ , and then all of the parallel shares, which take $N(1 - s)$ . The parallel run took 1 unit of time, so this total is also the speedup. In the example it is $0.1 + 7.2 = 7.3$ .
$S = N - s\,(N - 1)$: The whole formula as one sentence: the scaled speedup equals the number of processors, minus the serial fraction times one less than the number of processors. Written this way, each extra processor adds $1 - s$ to the speedup.

What the formula is doing, and why

Amdahl’s law assumes the job stays the same size while you add processors. Gustafson’s law looks at the same machine from the other side. In many real programs the problem grows with the machine: a bigger simulation, more data or more users. The useful question becomes how much more work fits into the same time, and that is what the scaled speedup $S$ measures.

Start with the parallel run. Measure the job on the parallel machine, and call its run time 1 unit. A fraction $s$ of that time is serial work, which ran on one processor while the others waited. The rest, $1 - s$ , is parallel work, and each of the $N$ processors did an equal share of it. So every processor was busy for $1 - s$ of the time.

Why the formula has this shape. Now ask how long one processor would need for the same enlarged job. It does the serial part once, which takes $s$ . It must also do all the parallel work. Each processor’s share took $1 - s$ , and there are $N$ shares, so one processor needs $N(1 - s)$ more. The total is $s + N(1 - s)$ . Since the parallel run took 1 unit, this total is the speedup. Expanding it gives $N - s(N - 1)$ , which is the formula above.

Why this view is more hopeful. Each extra processor adds $1 - s$ to the speedup. So the speedup keeps rising as $N$ grows, instead of stopping at a fixed ceiling. The catch is that the serial part still costs something. The larger the serial share $s$ , the smaller the gain from each new processor. The law fits jobs that really grow with the machine, and it does not fit jobs that must stay the same size.

An everyday picture

Think of a bakery that adds ovens to fill a bigger order. In the same afternoon, the extra ovens bake many more loaves, so the total output grows with the number of ovens. One step, such as mixing the dough in a single bowl, still takes its usual time and cannot be shared between the ovens. That single-bowl step is the serial part, and the bigger the share of time it takes, the less each new oven adds.

Worked example: Resizing photos on 8 processors with 10% serial work

A photo-resizing program runs on $N = 8$ processors. In one hour of the parallel run, 10% of the time goes to serial work that only one processor can do, such as reading the list of photos and writing the summary at the end. So $s = 0.1$ . Call the parallel run’s time 1 unit, which is one hour. The numbers are made up for this example.

Write down the inputs. The formula needs $N = 8$ and $s = 0.1$ . The serial share $0.1$ is one tenth, so 10% of the parallel run is serial. The rest of the run is parallel, and the next step works out how much that is.
Find the parallel share. Everything outside the serial part is parallel, so the parallel share is $1 - s = 1 - 0.1 = 0.9$ . That is 90% of the parallel run, and the 8 processors split it between them.
Find the parallel work for one processor. If one processor did all eight parallel shares by itself, it would need $N(1 - s) = 8 \times 0.9 = 7.2$ units of time. Each share is 0.9 units, and eight of them add up to 7.2, which is the work the eight processors finished together.
Add the serial part. The serial work runs once, and it takes $s = 0.1$ unit on that processor. The total for one processor is $0.1 + 7.2 = 7.3$ units. The parallel run took 1 unit, so the speedup is 7.3, and one processor needs 7.3 hours for the same, larger, batch.
Check the answer with the formula. Gustafson’s formula gives $S = N - s(N - 1) = 8 - 0.1 \times 7$ . Do the multiplication first: $0.1 \times 7 = 0.7$ . Then $S = 8 - 0.7 = 7.3$ . This matches the total from the previous step.
Compare with Amdahl’s fixed-size job. Amdahl’s law keeps the job the same size, and gives $S = \frac{1}{s + (1 - s)/N} = \frac{1}{0.1 + 0.9/8}$ . Dividing 0.9 by 8 gives 0.1125, so the denominator is $0.1 + 0.1125 = 0.2125$ . Then $S = 1 \div 0.2125 \approx 4.71$ .
Explain the difference in plain words. Gustafson’s answer of 7.3 assumes the photo batch grows to fill all eight processors in the same hour. Amdahl’s answer of 4.71 assumes the batch stays the same size. Then the same serial 0.1 hour becomes a bigger share of a shorter run, which is $0.1 \div 0.2125 \approx 0.47$ , or about 47%.

Answer: With 8 processors and 10% serial work, the parallel run does about 7.3 times as much work in the same hour as one processor would. If the batch must stay the same size, Amdahl’s law gives only about 4.71 times the speed for the same 10% serial share.

The numbers in this example are recomputed by script every time the site is built.

Common mistakes

Mixing up the two serial fractions. In Amdahl’s law the serial share is measured on one processor running a fixed job. In Gustafson’s law it is measured on the parallel run, where the processors are already working together.
Expecting the speedup to equal $N$ . Whenever $s > 0$ and $N > 1$ , the result is smaller than $N$ , because the serial part still takes its share of the time.
Using Gustafson’s law for a job that does not grow. If the job stays the same size, Amdahl’s law is the right model to use.
Entering $s$ as a percentage, such as 10, instead of a fraction, such as 0.1. With $s = 10$ the formula gives a negative speedup, so check that $s$ lies between 0 and 1.

Where you will meet it

Estimating how large a simulation or data job can become on a bigger machine while the run time stays fixed.
Weak scaling tests in high-performance computing, where the work per processor is kept fixed as processors are added.
Planning cluster sizes for batch jobs, such as processing more data inside the same nightly window.
Comparing the fixed-size and growing-size views of speedup, to decide whether a program should be made bigger or made faster.

Questions people ask

When should I use Gustafson's law instead of Amdahl's law?

Use Amdahl’s law when the job has a fixed size and you want to know how much faster it finishes. Use Gustafson’s law when the job grows with the machine, such as a bigger grid, more data or more users, and you want to know how much more work fits into the same time.

Does Gustafson's law say serial work is harmless?

No. Each extra processor adds only $1 - s$ to the speedup, so a larger serial share means smaller gains from every new processor. The serial part is still there, and it still sets a limit on how much each processor can add.

Who is the law named after?

It is named after John L. Gustafson, who described this view of scaled speedup in a 1988 paper that revisited Amdahl’s law.

Amdahl's Law: Amdahl’s law tells you how much faster a whole program gets when you speed up only part of its work, and why the part you leave alone caps the gain.
Little's Law: Little’s law says the number of things inside a system equals how fast they arrive, multiplied by how long each one stays.