Parallel Performance Laws (Amdahl's Law and Gustafson's Law)
1. Overview
A. Definition
Amdahl's Law states that when the total size of a task is held fixed and the number of processors is increased, the achievable speedup is bounded by the fraction of work that must run serially. Gustafson's Law (Gustafson–Barsis) shows that if the size of the problem is scaled up together with the processor count, speedup can grow almost in proportion to the number of processors. The two laws describe the same parallel system from two viewpoints: "how fast can we finish a fixed amount of work (strong scaling)" versus "how much work can we do in the same time (weak scaling)".
The core question of parallel processing is simple: "If I increase processors (cores) N-fold, does performance also increase N-fold?" Intuitively it should, but reality differs. Every program contains a serial section that must be processed one step at a time in order — initialization, I/O, critical sections, result merging — and this section does not get faster no matter how many processors are added. Amdahl's Law shows quantitatively that this serial section imposes a "ceiling" on overall speedup, while Gustafson's Law shows that scaling up the problem size can effectively push that ceiling upward.
These two laws do not contradict each other; they are complementary models with different assumptions. Amdahl "fixes the amount of work," while Gustafson "fixes the time (scales the amount of work)." The question is not which is correct, but which scenario your workload corresponds to — and that judgment is the starting point of parallel design. From a professional engineer's perspective, these laws serve as a basic tool for capacity planning and architectural decision-making, predicting the return on investment (ROI) and scaling limits of multicore CPUs, GPU acceleration, large-scale distributed training, and big-data processing.
B. Background and Necessity
Amdahl's Law was proposed in 1967 by Gene Amdahl in the context of comparing the economics of a single high-speed processor versus many slower processors. At the time, optimism about the utility of parallel computers was widespread, but Amdahl presented the sober bound that "if a substantial part of a program is inherently serial, the gains from parallelization are limited," establishing a realistic standard for parallelization investment. Later, as Moore's Law hit its limits and the era of raising performance through increased core counts (multicore) rather than clock speed arrived, Amdahl's Law was revisited as a key tool for explaining "why adding cores does not speed things up as expected."
In contrast, in 1988 John Gustafson, while parallelizing real scientific computations on a 1024-processor hypercube at Sandia National Laboratories, observed a phenomenon different from Amdahl's pessimistic prediction. When processors increase, people tend not to solve the same problem faster but rather to solve a larger problem (finer grids, longer simulations) within the same time. In other words, the serial fraction becomes relatively smaller as the problem size grows, so real HPC exhibited scaling nearly proportional to processor count. This insight underpinned the feasibility of large-scale parallel supercomputing. Today, training huge language models (LLMs) on thousands of GPUs or running weather and fluid simulations on tens of thousands of cores is possible because Gustafson-style scaling holds; conversely, Amdahl's limit applies directly to the single-request processing of online services where response time matters.
2. Amdahl's Law — Fixed Work (Strong Scaling)
Amdahl's Law "fixes the total amount of work." If program execution time is divided into a parallelizable fraction p (0≤p≤1) and a serial fraction 1-p, then the speedup from deploying N processors is as follows.
Speedup(N) = 1 / ( (1 − p) + p/N ), and as N → ∞, the maximum speedup = 1 / (1 − p)
The structure diagram below shows the Amdahl model, in which the total work is decomposed into a serial section and a parallel section, and only the parallel section is distributed across N processors. The serial section is not distributed and remains as is, creating a lower bound on total time.
flowchart TB
JOB["Fixed total work<br/>(runtime 1)"]
JOB --> SER["Serial section (1−p)<br/>unchanged by more processors"]
JOB --> PAR["Parallel section p<br/>splittable into N"]
PAR --> P0["Processor 0<br/>(p/N)"]
PAR --> P1["Processor 1<br/>(p/N)"]
PAR --> Pn["Processor N−1<br/>(p/N)"]
SER --> OUT["Total runtime<br/>(1−p) + p/N"]
P0 --> OUT
P1 --> OUT
Pn --> OUT
style SER fill:#fce8e6,stroke:#d93025,stroke-width:2px
style PAR fill:#e6f4ea,stroke:#188038,stroke-width:2px
style OUT fill:#e8f0fe,stroke:#2f6fed,stroke-width:2px
A. The Ceiling Created by the Serial Section
The most powerful message of Amdahl's Law is that "even a small non-parallelizable portion sharply limits overall scalability." For example, even if 95% of the whole is perfectly parallelized (p=0.95), the remaining serial 5% caps the maximum speedup at 1/(1−0.95)=20x no matter how many processors are added. Beyond 20 processors, additional deployment has almost no effect; even 1,000 processors yield only about 19.6x. This means that a small value like "serial 5%" determines the fate of overall scaling.
B. Diminishing Returns in Numbers
Concretely, consider a task with p=0.90. At N=2 the speedup is 1/(0.1+0.45)=about 1.82x, at N=4 it is 1/(0.1+0.225)=about 3.08x, at N=8 about 4.71x, at N=16 about 6.40x, and at N=∞ the ceiling is 10x. Even doubling the processors yields ever-smaller gains — clear diminishing returns. The table below summarizes the theoretical ceilings by serial fraction.
| Parallel fraction p | Serial fraction 1−p | Max speedup (N→∞) | At N=16 |
|---|---|---|---|
| 0.50 | 0.50 | 2x | about 1.88x |
| 0.90 | 0.10 | 10x | about 6.40x |
| 0.95 | 0.05 | 20x | about 9.14x |
| 0.99 | 0.01 | 100x | about 13.9x |
C. Practical Implications
Amdahl's Law tells us the optimization priority that "reducing the serial section may matter more than adding parallelism." Commit serialization of database transactions, lock contention, global counters, and sequential writes to a single log file are typical serial bottlenecks; unless they are reduced through sharding, lock-free data structures, and batching, adding cores is a waste of money. In fact, there is a case where an OLTP system increased CPUs from 8 to 32 cores (a 4x increase) but throughput rose only 1.6x; because the serial section of the connection pool and commit path was around p≈0.8, it fell short even of the theoretical ceiling at N=32 (about 4.7x) — a textbook Amdahl phenomenon.
The same perspective applies directly to software profiling. Amdahl's Law is also the mathematical basis for the principle "optimize the part that takes up a large share of the whole first." Making a function that accounts for 5% of total execution time 10x faster reduces the whole by only about 4.5%, but improving a function that accounts for 60% by just 2x reduces the whole by 30%. Whether through parallelization or algorithmic improvement, the payoff is always limited by "the share the optimization target occupies in the whole" — the universal lesson of Amdahl.
3. Gustafson's Law — Fixed Time (Weak Scaling)
Gustafson's Law reverses the perspective. It "fixes the time," and assumes that if processors increase N-fold, the problem size handled also grows. If, based on parallel execution time, the serial fraction is s and the parallel fraction is 1−s, then the scaled speedup is as follows.
Speedup(N) = s + (1 − s)·N = N − s·(N − 1)
Here s is the serial fraction "based on parallel execution," which differs from Amdahl. The diagram below compares, from a process viewpoint, how Amdahl (fixed work → shorter time) and Gustafson (fixed time → expanded work) use resources when processors are added.
flowchart LR
START["Scale processors by N"] --> Q{"What is held fixed?"}
Q -->|"Fixed work"| A1["Amdahl: same work<br/>done faster"]
A1 --> A2["Serial share grows<br/>→ speedup saturates"]
A2 --> A3["Ceiling 1/(1−p)"]
Q -->|"Fixed time"| G1["Gustafson: bigger work<br/>in the same time"]
G1 --> G2["Larger problem raises<br/>parallel share"]
G2 --> G3["Speedup ≈ N<br/>near-linear scaling"]
style A3 fill:#fce8e6,stroke:#d93025,stroke-width:2px
style G3 fill:#e6f4ea,stroke:#188038,stroke-width:2px
A. Why the Serial Fraction Becomes Relatively Smaller
In scientific computing, the absolute time of serial work (initialization, I/O) stays roughly constant even as the problem grows, whereas the amount of parallel work (grid computation, matrix operations) explodes in proportion to the problem size. Therefore, as the problem grows, the fraction of serial work in the whole shrinks, and Amdahl's assumed "fixed serial fraction" no longer holds. For example, doubling the grid resolution multiplies the computation several-fold but leaves the file-open time unchanged, so the serial fraction drops from 10% to 2%. This is why near-linear scaling was observed even at 1,024 processors.
B. Linear Scaling in Numbers
When s=0.05 (serial 5% on a parallel basis), the Gustafson speedup is 0.05+0.95×16=about 15.25x at N=16 and about 972.9x at N=1,024. This stands in stark contrast to Amdahl, which caps at 20x for the same serial 5%. The key is "what you measure." Amdahl measures the response-time reduction of the same problem, while Gustafson measures the processing scale (throughput, problem size) within the same time.
C. Areas of Application
Representative cases where Gustafson-style scaling holds are HPC simulations (weather, fluids, structural analysis), large-scale deep-learning training (batch and data parallelism), and Monte Carlo simulations — problems where "we want to solve more precisely or at larger scale as resources grow." Conversely, Amdahl's limit applies directly to problems where the amount of work is fixed, such as the response time of a single user request or the deadline of a fixed-size batch. Thus a designer must first define "does our workload want faster (strong) or more (weak)."
4. Comparison of the Two Laws
The difference between the two laws arises not from "right versus wrong" but from a difference in problem setup. Amdahl presumes fixed work (strong scaling) and Gustafson presumes scaled work (weak scaling); the real-world problems they target and the practical conclusions that follow differ.
| Category | Amdahl's Law | Gustafson's Law |
|---|---|---|
| Fixed target | Work (problem size) | Execution time |
| Scaling type | Strong scaling | Weak scaling |
| Speedup formula | 1/((1−p)+p/N) | s+(1−s)·N |
| Behavior as N→∞ | Saturates at ceiling 1/(1−p) | Grows linearly with N |
| Metric | Response-time reduction | Processing scale, throughput |
| Fitting cases | Online transactions, fixed batches | HPC simulations, large-scale training |
The fundamental reason for the difference in the table lies in whether the serial fraction is regarded as a constant or as a function of problem size. Amdahl treats the serial fraction as a constant, so as N grows p/N converges to 0 and only the serial term remains, hence saturation. Gustafson holds that scaling up the problem increases the absolute amount of parallel work, so the serial fraction decreases and no saturation occurs. The practical implication is clear. For investment to reduce response latency (accelerating a single query), you must first compute Amdahl's ceiling to avoid over-provisioning; for investment to grow processing capacity (larger models, more users), you should design horizontal scaling on the premise of Gustafson-style scaling, while also checking whether communication and synchronization costs become the new bottleneck.
As a concrete case, consider the nightly batch training of a recommendation system. If the data is yesterday's fixed logs (strong), increasing GPUs from 2 to 8 still hits Amdahl's ceiling because of the serial sections of preprocessing and checkpoint saving, yielding a 2.5x rather than 4x reduction. However, if the operations team changes the goal to "train more features and larger embeddings within the same 4 hours" (weak), the same 8 GPUs can scale the model size almost linearly. Even with the same hardware, which of the two curves you ride depends on how the goal is set.
5. Deep Dive: The Universal Scalability Law (USL) and Recent Trends
Amdahl and Gustafson have the limitation of being idealized models that ignore communication and synchronization costs. In reality, as processors increase, contention for shared resources and coherency communication to maintain data consistency both grow, so beyond a certain point performance may actually decrease (retrograde). Neil Gunther's Universal Scalability Law (USL) models this with two penalty terms.
C(N) = N / ( 1 + α·(N − 1) + β·N·(N − 1) ) — α: contention (serialization), β: coherency (mutual communication) coefficient
Here, if β=0 the USL reduces to Amdahl's Law, and if β is non-zero it explains the realistic behavior where the performance curve declines after a certain peak concurrency. The USL regresses α and β from a small set of load measurements (throughput at several thread counts) to give a quantitative answer to the capacity-planning question "up to how many nodes/cores is it worth scaling." That is, if Amdahl tells the ceiling and Gustafson tells the scaling potential, the USL points to the realistic optimal concurrency including contention and communication costs.
As a concrete figure, consider a distributed aggregation job on a Spark cluster scaled from 10 to 40 nodes (a 4x increase): throughput rises near-linearly to 3.9x (the Gustafson region), but at 80 nodes it peaks at about 7.2x due to shuffle-network contention and then bends down to 7.0x at 100 nodes. This reversal region cannot be explained by Amdahl and Gustafson alone and is captured only by the USL's β term. Therefore the assumption "more nodes always means faster" is dangerous; one must find the peak concurrency by measurement and change the algorithm or communication structure beyond that point.
In recent trends, these laws have become the design language of AI and data-center-scale expansion. When training LLMs on thousands of GPUs, data, tensor, and pipeline parallelism aim for Gustafson-style scaling, but all-reduce collective communication acts like the USL's β term, so beyond a certain scale communication becomes the bottleneck. Hence high-speed interconnects such as NVLink, InfiniBand, and RoCE, overlapping communication with computation, and gradient compression become key challenges. Apache Spark shuffles and distributed-database consensus share the same structure, creating a point where contention and communication costs bend linear scaling. Ultimately, modern distributed-system design converges on simultaneous optimization of two axes: "increase the parallel section (Gustafson) and reduce the serial, contention, and communication (Amdahl and USL)."
6. Considerations and Implications
From a professional engineer's perspective, these laws should be used not as mere formulas but as a decision framework for judging the feasibility and limits of parallel and distributed investment, with the following strategic implications.
Application strategy — pre-classify the workload type: Before investing in expansion, first classify whether the target workload is response-time-reduction type (strong, Amdahl) or processing-scale-expansion type (weak, Gustafson). The former measures the serial fraction
p, computes the theoretical ceiling, and sets the right number of cores within it; the latter presumes problem expansion and horizontal scaling and designs the communication architecture first.Trade-off — reducing serial versus expanding parallel: Amdahl's Law implies that "eliminating the serial bottleneck can yield more than adding parallelism." One must compare, on a cost-benefit basis, refactoring that removes lock contention, global resources, and sequential I/O via sharding, lock-free structures, and batching against adding cores or nodes. Over-provisioning merely inflates TCO in the diminishing-returns region.
Reflecting real costs (USL): Trusting only the idealized Amdahl and Gustafson underestimates communication and synchronization costs and falls into the trap of "the more you add, the slower it gets." Estimate α and β from small-scale load tests to compute the optimal concurrency (peak), and reflect in decision-making that scaling beyond that point has no effect without interconnect improvement or algorithmic change.
Outlook and related technologies — heterogeneous, large-scale acceleration: As accelerators such as GPUs, NPUs, and TPUs, CXL-based memory expansion, and ultra-fast interconnects become common, the bottleneck of parallel performance is shifting from "computation" to "data movement and synchronization." Overlapping communication with computation, collective-communication optimization, and data locality (NUMA and topology-aware placement) are the practical extensions of the three laws, and are set to become core capabilities that determine the cost and power efficiency of huge-model training and real-time inference.
Governance and operations perspective: Scalability is not a one-off benchmark but a continuous observation target. One must constantly measure the throughput-concurrency curve to catch performance regressions early, and embed into operations a capacity-management process that re-estimates α and β upon hardware-generation changes and topology changes — thereby sustaining the return on investment.
References
- G. M. Amdahl, "Validity of the single processor approach to achieving large scale computing capabilities" (1967) — https://doi.org/10.1145/1465482.1465560
- J. L. Gustafson, "Reevaluating Amdahl's Law", CACM (1988) — https://doi.org/10.1145/42411.42415
- Neil J. Gunther, "Universal Scalability Law" — https://en.wikipedia.org/wiki/Neil_J._Gunther
- USL R package (vignette/manual) — https://cran.r-project.org/web/packages/usl/vignettes/usl.pdf
In one line: Amdahl's Law describes strong scaling, where with fixed work the serial fraction sets the ceiling on speedup (1/(1−p)), while Gustafson's Law describes weak scaling, where scaling the problem size lets performance grow almost linearly with processor count; the USL complements them by reflecting contention and communication costs to point out the realistic optimal concurrency.