← Reference · Nestor G Pestelos Jr · Print this page

Computer Architecture · Parallel Computing

Gustafson's Law for Parallel AI Agents

Reference entry · last updated September 4, 2026

Gustafson's Law is a scaled-speedup formula for parallel computers. When problem size grows with processor count and wall-clock time stays about constant, speedup stays near-linear in \(N\), reduced only by the serial fraction of time measured on the parallel run.[1] John L. Gustafson published the argument in 1988. The same relation is also called Gustafson–Barsis's law, after E. Barsis at Sandia, who suggested the scaled-speedup form.[2]

Processors (\(N\)) Scaled speedup \(S\) 0 16 32 0 16 32 1% serial (\(s = 0.01\)) 5% serial (\(s = 0.05\)) 10% serial (\(s = 0.10\))

Mathematical formula

Let \(s\) be the serial fraction of time on the parallel system, with total parallel-run time normalized to 1. This \(s\) is not the serial fraction of a fixed sequential baseline. Let \(p = 1 - s\) be the parallel fraction of that same parallel-run time, and let \(N\) be the number of processors. Scaled speedup is:[1]

\[S = N - (N-1)s\]

Equivalent forms are \(S = s + pN\) and \(S = 1 + (N-1)p\).[1] A serial processor would need time \(s + pN\) for the same scaled work. The scaled-speedup form is also called Gustafson–Barsis's law.[2]

Weak scaling

Amdahl's Law holds problem size fixed. That is strong scaling: the same job, more processors, shorter wall-clock. Gustafson's Law lets problem size grow so wall-clock time stays about constant. That is weak scaling, or scaled speedup.[1] The two formulas answer different questions about workload. Gustafson later wrote that people scale their problems to match the power available, and that Amdahl's assumptions do not match that use of parallel processors.[3]

Sandia 1988

On a 1024-processor hypercube at Sandia National Laboratories, Gustafson reported scaled speedups of 1021 for beam stress analysis (conjugate gradients), 1020 for baffled surface wave simulation (explicit finite differences), and 1016 for unstable fluid flow (flux-corrected transport). Serial fractions on those parallel runs were about 0.4 to 0.8 percent.[1]

Parallel AI agent fleets

The same formula applies to a swarm of AI agents if \(N\) is the number of concurrent agents and \(s\) is the share of wall-clock spent on coordination, merge, and integration after the parallel work.[1] The matching use is to cover a larger task graph in the same wall-clock window: more files, more test cases, more independent reviews. Serial remainder remains coordination, merge, and integration.

The mapping from processors to agents is an application of Gustafson's formula. It is not a lab measurement of a named agent product.

Comparison with Amdahl's Law

Amdahl's Law for Parallel AI Agents bounds speedup of a fixed job as processors increase. Gustafson's Law bounds how much scaled work a fleet can finish in a fixed time. Both remain true under their assumptions.[1]

Limits

Workloads that cannot grow with \(N\) stay in Amdahl's fixed-size frame. Communication and coherence costs sit outside the simple \(s + pN\) model. Serial work that grows with problem size reduces scaled speedup below the line.

These limits follow from the model's assumptions. They are not additional Sandia measurements.

See also

References

  1. ↑ Gustafson, John L. "Reevaluating Amdahl's Law." Communications of the ACM, vol. 31, no. 5, 1988, pp. 532–533. https://doi.org/10.1145/42411.42415
  2. ↑ McCool, Michael, Arch D. Robison, and James Reinders. Structured Parallel Programming: Patterns for Efficient Computation. Morgan Kaufmann, 2012, pp. 61–62.
  3. ↑ Gustafson, John L. "Gustafson's Law." http://www.johngustafson.net/glaw.html