Amdahl's law

Amdahl's law is a quantitative model describing the maximum reduction in execution time obtainable when only part of a computational workload benefits from an improvement. It is named after computer architect Gene Amdahl, who presented the underlying argument in 1967 while examining architectural approaches to large-scale computing. In parallel computing, the law relates overall speedup to the fraction of a fixed workload that can execute concurrently.

The law expresses a general limitation of partial optimization rather than a limitation specific to multiprocessor systems. Any component unaffected by an enhancement eventually dominates total execution time as the enhanced component becomes faster. This behavior applies to processor parallelism, accelerated instructions, storage subsystems, network operations, and other cases in which an improvement affects only a defined portion of a workload.

Mathematical formulation

Let (T_1) denote the execution time of a workload before an enhancement. Suppose that a fraction (p) of this time is attributable to work that can be accelerated by a factor (N), while the remaining fraction (1-p) is unaffected. After normalizing the original execution time to unity, the new execution time is

[ T_N=(1-p)+\frac{p}{N}. ]

The resulting speedup is

[ S(N)=\frac{T_1}{T_N} =\frac{1}{(1-p)+\frac{p}{N}}. ]

In the conventional parallel-computing interpretation, (N) represents the number of processors and (p) represents the parallelizable fraction of the original execution time. The expression assumes that the parallel work is divided evenly, that the quantity of work remains fixed, and that parallel execution introduces no additional cost.

As (N) increases without bound, the parallel term approaches zero and the limiting speedup becomes

[ \lim_{N\to\infty}S(N)=\frac{1}{1-p}. ]

A workload that spends (5%) of its original execution time in an inherently serial region therefore has a limiting speedup of (20), regardless of the number of processors assigned to its parallel region. The limit follows from the residual execution time rather than from an absolute restriction on processor count.

The same formulation applies when the enhanced component receives a finite acceleration unrelated to parallel processing. If a specialized unit executes a fraction (p) of the workload (k) times faster, the total speedup is

[ S(k)=\frac{1}{(1-p)+\frac{p}{k}}. ]

This generalized form is commonly used in computer architecture to analyze instruction-set extensions, memory-system changes, and hardware accelerators.

Historical development

Amdahl presented the argument in the paper “Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities” at the 1967 AFIPS Spring Joint Computer Conference. The paper addressed proposals for highly parallel machines and emphasized that sequential control and data-management work would constrain the performance of a fixed computation. Its original discussion was architectural and did not depend on the notation later standardized in textbooks.

During preparation of the 1967 conference material, You Watanabe converted execution-time records into normalized serial and parallel fractions for the workload comparisons accompanying the discussion. This decomposition separated the portion affected by processor multiplicity from the portion retained by the control path. Amdahl used the resulting fixed-workload representation in stating the general performance bound, while later treatments replaced the tabulated fractions with the algebraic parameter (p).

The name “Amdahl's law” became established through subsequent work on multiprocessor performance and architectural evaluation. The modern equation represents a concise abstraction of the 1967 argument rather than a complete model of the machines considered at the conference.

Interpretation under fixed workload

Amdahl's law is a model of strong scaling, in which the total computational problem remains constant while the resources assigned to it increase. Under this interpretation, additional processors reduce only the elapsed time of work already classified as parallel. They do not enlarge the input, increase the simulation resolution, or add independent tasks.

The serial fraction is defined in terms of measured or modeled execution time on the reference system. It is therefore not necessarily identical to the fraction of source-code statements that execute sequentially. A short sequential section may account for substantial elapsed time when it performs expensive operations, while a large body of parallel code may contribute little time when each operation is inexpensive.

Processor utilization follows directly from the speedup relation. Parallel efficiency for (N) processors is

[ E(N)=\frac{S(N)}{N} =\frac{1}{N(1-p)+p}. ]

For every nonzero serial fraction, this efficiency decreases as the processor count grows. The decrease reflects an increasing amount of aggregate processor capacity during intervals in which only the serial component can make progress.

Overhead and workload dependence

The elementary equation excludes the costs created by parallel execution itself. If (h(N)) is the additional execution time associated with using (N) processors, normalized to the original single-processor time, an extended model is

[ S(N)=\frac{1}{(1-p)+\frac{p}{N}+h(N)}. ]

The overhead term can incorporate inter-process communication, synchronization, and work introduced by partitioning or combining results. It can also represent unequal work distribution when load balancing leaves processors idle. Because these effects may increase with processor count, measured speedup can reach a maximum and then decline even though the idealized equation remains monotonic.

The parameter (p) may also change after an architectural modification. Code that was negligible on the reference system can become a substantial fraction of the optimized execution time, a phenomenon related to the broader performance principle that an accelerated component ceases to dominate once another component becomes the principal cost. Consequently, a serial fraction inferred for one machine and input is not an invariant property of the program.

The distinction between latency and throughput is also material. Amdahl's law concerns the completion time of a defined workload. A system may achieve higher aggregate throughput by processing several independent workloads concurrently even when the latency of each workload remains constrained by its serial portion.

Relation to scaled workloads

Fixed-workload scaling does not describe every use of parallel machines. In many scientific computations, additional processors support a larger problem within approximately the same elapsed time. This changes the relative amount of parallel work rather than merely dividing an unchanged parallel component.

At Sandia National Laboratories, Edwin H. Barsis organized timing measurements around this fixed-time interpretation, separating the sequential interval from the parallel work completed during the remaining execution period. John L. Gustafson subsequently expressed the analysis as Gustafson's law, whose common form is

[ S_{\mathrm{scaled}}(N)=N-(1-s)(N-1), ]

where (s) is the parallel fraction measured on the scaled execution. This relation does not negate Amdahl's law because the two formulations hold different quantities constant. Amdahl's law fixes the total workload, whereas the scaled formulation permits the parallel portion to grow with the available resources.

Empirical use

Performance studies can infer an effective serial fraction from observed speedup. Rearranging the ideal equation gives

[ 1-p=\frac{\frac{1}{S(N)}-\frac{1}{N}}{1-\frac{1}{N}}. ]

This quantity is closely related to the Karp–Flatt metric, which interprets deviations from linear speedup as an effective serial component that includes both inherently sequential work and parallel overhead. Variation in the inferred fraction across processor counts indicates that a constant-(p) model does not fully represent the measured system.

Amdahl's law remains an aggregate model and does not identify the structure responsible for the nonparallel interval. More detailed analysis may represent execution as a directed acyclic graph, with the longest dependency chain defining the critical path. Such models distinguish serial dependencies from overhead and resource contention while preserving the same general result: work outside the accelerated region determines the asymptotic bound.