Computer Architecture · Parallel Computing

Amdahl's Law

Reference entry · last updated August 26, 2026

Amdahl's Law is a mathematical formula that calculates the theoretical maximum speedup achievable by a system when improving or parallelizing a specific fraction of its total workload.[1] Formulated by computer architect Gene Amdahl in 1967, the law demonstrates that overall performance speedup is strictly bounded by the serial, non-parallelizable portion of the task, regardless of how many parallel processing units are added.[2]

Mathematical formulation

Let a task have execution time \(T_1\) on a single processor. The task is partitioned into two fractions:[1]

\(s\): The fraction of execution time that is strictly serial (\(0 \le s \le 1\)).
\(p = 1 - s\): The fraction of execution time that can be perfectly parallelized.

When executed across \(N\) parallel execution units, total runtime \(T_N\) becomes:

\[T_N = T_1 \left( s + \frac{1 - s}{N} \right)\]

The resulting speedup factor \(S(N) = \frac{T_1}{T_N}\) is defined as:[1]

\[S(N) = \frac{1}{s + \frac{1 - s}{N}}\]

The serial fraction ceiling

As the number of parallel processors approaches infinity (\(N \to \infty\)), the parallel term \(\frac{1-s}{N}\) approaches zero, establishing a hard asymptotic ceiling:[2]

\[\lim_{N \to \infty} S(N) = \frac{1}{s}\]

If even 10% of a program cannot be parallelized (\(s = 0.10\)), the maximum possible speedup is 10x, even with millions of processing cores.[2]

Amdahl's law in parallel AI agent swarms

Amdahl's Law directly governs the scaling of multi-agent coding swarms and autonomous fleets:[3]

Parallel fraction (\(p\)): Independent code authoring, background file audits, unit test generation, and documentation drafting.
Serial fraction (\(s\)): Architectural alignment, task graph decomposition, git branch merge conflict resolution, and final integration verification.

Deploying 16 parallel subagents on a task with 10% serial coordination delivers roughly 9x real throughput, not 16x. Sizing agent swarms requires calculating the serial dependency tail before provisioning large worker pools.[3]

Comparison with Gustafson's Law

Amdahl's Law assumes a fixed problem size (strong scaling). In contrast, Gustafson's Law (1988) addresses weak scaling, where larger parallel systems are used to solve larger problem sizes within the same total time window rather than solving a fixed problem faster.[4]

References

↑ Amdahl, Gene M. "Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities." AFIPS Conference Proceedings, vol. 30, 1967, pp. 483–485. https://doi.org/10.1145/1465482.1465560
↑ Patterson, David A., and John L. Hennessy. Computer Organization and Design: The Hardware/Software Interface. 6th ed., Morgan Kaufmann, 2020.
↑ Anthropic. "Building Effective Agents: Multi-Agent Workflows and Coordination Overheads," 2024.
↑ Gustafson, John L. "Reevaluating Amdahl's Law." Communications of the ACM, vol. 31, no. 5, 1988, pp. 532–533.