Law

Amdahl's Law

Fixed work: how fast can I finish this job?

Speedup (N) = \frac{1}{s + \frac{1 - s}{N}} \leq \frac{1}{s}

$s$: Serial fraction; fraction of a job that is serial (cannot be parallelized)
$N$: Processors; number of processors

How it behaves

One input on the horizontal axis, the others held fixed.

s = 1%s = 5%s = 20%

Data table

Speedup by processors, for three serial fractions
Processors N	series	Speedup
1	s = 1%	1×
1.09	s = 1%	1.09×
1.19	s = 1%	1.19×
1.3	s = 1%	1.29×
1.41	s = 1%	1.41×
1.54	s = 1%	1.53×
1.68	s = 1%	1.67×
1.83	s = 1%	1.82×
2	s = 1%	1.98×
2.18	s = 1%	2.15×
2.37	s = 1%	2.34×
2.59	s = 1%	2.54×
2.82	s = 1%	2.77×
3.07	s = 1%	3.01×
3.35	s = 1%	3.27×
3.65	s = 1%	3.56×
3.98	s = 1%	3.87×
4.34	s = 1%	4.2×
4.73	s = 1%	4.56×
5.16	s = 1%	4.95×
5.62	s = 1%	5.37×
6.13	s = 1%	5.83×
6.68	s = 1%	6.32×
7.29	s = 1%	6.86×
7.94	s = 1%	7.43×
8.66	s = 1%	8.04×
9.44	s = 1%	8.71×
10.3	s = 1%	9.42×
11.2	s = 1%	10.2×
12.2	s = 1%	11×
13.3	s = 1%	11.9×
14.5	s = 1%	12.8×
15.8	s = 1%	13.8×
17.3	s = 1%	14.9×
18.8	s = 1%	16×
20.5	s = 1%	17.2×
22.4	s = 1%	18.4×
24.4	s = 1%	19.8×
26.6	s = 1%	21.2×
29	s = 1%	22.7×
31.6	s = 1%	24.2×
34.5	s = 1%	25.8×
37.6	s = 1%	27.5×
41	s = 1%	29.3×
44.7	s = 1%	31.1×
48.7	s = 1%	33×
53.1	s = 1%	34.9×
57.9	s = 1%	36.9×
63.1	s = 1%	38.9×
68.8	s = 1%	41×
75	s = 1%	43.1×
81.8	s = 1%	45.2×
89.1	s = 1%	47.4×
97.2	s = 1%	49.5×
106	s = 1%	51.7×
115	s = 1%	53.8×
126	s = 1%	56×
137	s = 1%	58.1×
150	s = 1%	60.2×
163	s = 1%	62.2×
178	s = 1%	64.2×
194	s = 1%	66.2×
211	s = 1%	68.1×
230	s = 1%	69.9×
251	s = 1%	71.7×
274	s = 1%	73.4×
299	s = 1%	75.1×
325	s = 1%	76.7×
355	s = 1%	78.2×
387	s = 1%	79.6×
422	s = 1%	81×
460	s = 1%	82.3×
501	s = 1%	83.5×
546	s = 1%	84.7×
596	s = 1%	85.7×
649	s = 1%	86.8×
708	s = 1%	87.7×
772	s = 1%	88.6×
841	s = 1%	89.5×
917	s = 1%	90.3×
1K	s = 1%	91×
1	s = 5%	1×
1.09	s = 5%	1.09×
1.19	s = 5%	1.18×
1.3	s = 5%	1.28×
1.41	s = 5%	1.38×
1.54	s = 5%	1.5×
1.68	s = 5%	1.62×
1.83	s = 5%	1.76×
2	s = 5%	1.9×
2.18	s = 5%	2.05×
2.37	s = 5%	2.22×
2.59	s = 5%	2.4×
2.82	s = 5%	2.58×
3.07	s = 5%	2.78×
3.35	s = 5%	3×
3.65	s = 5%	3.22×
3.98	s = 5%	3.46×
4.34	s = 5%	3.72×
4.73	s = 5%	3.99×
5.16	s = 5%	4.27×
5.62	s = 5%	4.57×
6.13	s = 5%	4.88×
6.68	s = 5%	5.2×
7.29	s = 5%	5.54×
7.94	s = 5%	5.9×
8.66	s = 5%	6.26×
9.44	s = 5%	6.64×
10.3	s = 5%	7.03×
11.2	s = 5%	7.43×
12.2	s = 5%	7.83×
13.3	s = 5%	8.25×
14.5	s = 5%	8.67×
15.8	s = 5%	9.1×
17.3	s = 5%	9.53×
18.8	s = 5%	9.96×
20.5	s = 5%	10.4×
22.4	s = 5%	10.8×
24.4	s = 5%	11.2×
26.6	s = 5%	11.7×
29	s = 5%	12.1×
31.6	s = 5%	12.5×
34.5	s = 5%	12.9×
37.6	s = 5%	13.3×
41	s = 5%	13.7×
44.7	s = 5%	14×
48.7	s = 5%	14.4×
53.1	s = 5%	14.7×
57.9	s = 5%	15.1×
63.1	s = 5%	15.4×
68.8	s = 5%	15.7×
75	s = 5%	16×
81.8	s = 5%	16.2×
89.1	s = 5%	16.5×
97.2	s = 5%	16.7×
106	s = 5%	17×
115	s = 5%	17.2×
126	s = 5%	17.4×
137	s = 5%	17.6×
150	s = 5%	17.7×
163	s = 5%	17.9×
178	s = 5%	18.1×
194	s = 5%	18.2×
211	s = 5%	18.4×
230	s = 5%	18.5×
251	s = 5%	18.6×
274	s = 5%	18.7×
299	s = 5%	18.8×
325	s = 5%	18.9×
355	s = 5%	19×
387	s = 5%	19.1×
422	s = 5%	19.1×
460	s = 5%	19.2×
501	s = 5%	19.3×
546	s = 5%	19.3×
596	s = 5%	19.4×
649	s = 5%	19.4×
708	s = 5%	19.5×
772	s = 5%	19.5×
841	s = 5%	19.6×
917	s = 5%	19.6×
1K	s = 5%	19.6×
1	s = 20%	1×
1.09	s = 20%	1.07×
1.19	s = 20%	1.15×
1.3	s = 20%	1.22×
1.41	s = 20%	1.3×
1.54	s = 20%	1.39×
1.68	s = 20%	1.48×
1.83	s = 20%	1.57×
2	s = 20%	1.66×
2.18	s = 20%	1.76×
2.37	s = 20%	1.86×
2.59	s = 20%	1.96×
2.82	s = 20%	2.07×
3.07	s = 20%	2.17×
3.35	s = 20%	2.28×
3.65	s = 20%	2.39×
3.98	s = 20%	2.49×
4.34	s = 20%	2.6×
4.73	s = 20%	2.71×
5.16	s = 20%	2.82×
5.62	s = 20%	2.92×
6.13	s = 20%	3.03×
6.68	s = 20%	3.13×
7.29	s = 20%	3.23×
7.94	s = 20%	3.33×
8.66	s = 20%	3.42×
9.44	s = 20%	3.51×
10.3	s = 20%	3.6×
11.2	s = 20%	3.69×
12.2	s = 20%	3.77×
13.3	s = 20%	3.85×
14.5	s = 20%	3.92×
15.8	s = 20%	3.99×
17.3	s = 20%	4.06×
18.8	s = 20%	4.12×
20.5	s = 20%	4.18×
22.4	s = 20%	4.24×
24.4	s = 20%	4.3×
26.6	s = 20%	4.35×
29	s = 20%	4.39×
31.6	s = 20%	4.44×
34.5	s = 20%	4.48×
37.6	s = 20%	4.52×
41	s = 20%	4.56×
44.7	s = 20%	4.59×
48.7	s = 20%	4.62×
53.1	s = 20%	4.65×
57.9	s = 20%	4.68×
63.1	s = 20%	4.7×
68.8	s = 20%	4.73×
75	s = 20%	4.75×
81.8	s = 20%	4.77×
89.1	s = 20%	4.79×
97.2	s = 20%	4.8×
106	s = 20%	4.82×
115	s = 20%	4.83×
126	s = 20%	4.85×
137	s = 20%	4.86×
150	s = 20%	4.87×
163	s = 20%	4.88×
178	s = 20%	4.89×
194	s = 20%	4.9×
211	s = 20%	4.91×
230	s = 20%	4.91×
251	s = 20%	4.92×
274	s = 20%	4.93×
299	s = 20%	4.93×
325	s = 20%	4.94×
355	s = 20%	4.94×
387	s = 20%	4.95×
422	s = 20%	4.95×
460	s = 20%	4.96×
501	s = 20%	4.96×
546	s = 20%	4.96×
596	s = 20%	4.97×
649	s = 20%	4.97×
708	s = 20%	4.97×
772	s = 20%	4.97×
841	s = 20%	4.98×
917	s = 20%	4.98×
1K	s = 20%	4.98×

Worked examples, recomputed

Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.

Where it appears

Each mechanism states it in its own names. The general symbol each name stands for is shown with it.

Physical Substrate & Performance Laws
Why do trade-offs exist at all?
$Speedup = \frac{1}{s + ( 1 - s ) / N}$
Read it in place →
Execution Engine Runtime
Once a query plan is chosen, why does the machine still sit idle, and what does each mechanism of a query runtime pay to buy that idle time back?
$speedup \leq \frac{1}{f}$
f (share of the largest partition) = $s$
Read it in place →
Streaming
What does it cost to remember, when the input never ends?
$T \leq C \div 0.3 \approx 3.3 C$
0.3 (the hot key's share) = $s$
Read it in place →