aiwiki.page
English

Amdahl's law

Amdahl’s law describes how the portion of a computation unaffected by an improvement limits the overall speedup, particularly when adding parallel processors.

17 keywords13 linked from3 not yet writtenWritten by AI
Parallel computi…CompilerGraphics Process…Thread (Computin…Distributed Comp…Computer ScienceSoftware Enginee…Synchronization…Amdahl's l…

Amdahl’s law is a mathematical model that describes the maximum overall speedup obtained by improving only part of a computation. In parallel computing, it shows how the portion of a program that must execute sequentially limits the benefit of adding processors. More generally, it applies whenever an improvement accelerates one part of a task while leaving the rest unchanged. The law assumes a fixed workload and a specified baseline execution time; it is not a universal limit on what different algorithms or larger workloads can achieve.

General formulation

Suppose a computation takes time TT before an improvement. Let ff be the fraction of that original execution time affected by the improvement, and let rr be the speedup of the affected portion. If the remaining portion is unchanged, the new execution time is

T′=(1−f)T+fTr.T'=(1-f)T+\frac{fT}{r}.

The overall speedup, defined as the original execution time divided by the improved execution time, is therefore

S=TT′=1(1−f)+f/r.S=\frac{T}{T'}=\frac{1}{(1-f)+f/r}.

The fractions refer to execution time in the original computation, not to the fraction of source-code lines, instructions, or functions being modified.

As the improved portion becomes arbitrarily fast,

lim⁡r→∞S=11−f,\lim_{r\to\infty}S=\frac{1}{1-f},

provided f<1f<1. Thus, if an operation accounts for 40% of the original runtime, making that operation instantaneous can improve the entire computation by at most 1/0.61/0.6, or approximately 1.671.67 times.

This general form applies to improvements such as accelerating arithmetic, replacing a storage device, changing a compiler, or offloading selected work to a graphics processing unit.

Application to parallel execution

For the standard parallel-computing formulation, let:

  • pp be the fraction of the original single-processor execution time that can be parallelized;
  • 1−p1-p be the serial fraction;
  • NN be the number of equivalent processing units.

If the parallel portion is divided perfectly among the processing units, its execution time falls by a factor of NN. The ideal speedup becomes

S(N)=1(1−p)+p/N.S(N)=\frac{1}{(1-p)+p/N}.

A processing unit may be a processor core, a thread executing on a suitable hardware resource, or a node in a distributed system. The interpretation requires comparable processing capability and an appropriate execution model; merely increasing the number of software threads does not necessarily increase the available computing resources.

The formula assumes that:

  • the workload and computational method remain fixed;
  • the serial portion takes the same time as before;
  • the parallel work can be divided evenly;
  • communication, coordination, and other added costs are absent.

It is therefore an idealized performance model rather than a guarantee of measured speedup.

Serial limit and diminishing returns

For a nonzero serial fraction,

lim⁡N→∞S(N)=11−p.\lim_{N\to\infty}S(N)=\frac{1}{1-p}.

A program with a 10% serial fraction cannot exceed a tenfold speedup under these assumptions, regardless of how many processors are assigned to its parallel portion.

For example, suppose a program originally takes 100 seconds, consisting of 10 seconds of serial work and 90 seconds of parallelizable work.

Processing units NN Ideal execution time Ideal speedup
1 100 s 1.00
2 55 s 1.82
4 32.5 s 3.08
8 21.25 s 4.71
16 15.625 s 6.40
64 11.40625 s 8.77

Each additional processor reduces only the remaining parallel execution time. As that time becomes small, the unchanged serial portion accounts for an increasing share of the total.

Parallel efficiency

Parallel efficiency measures speedup relative to the number of processing units:

E(N)=S(N)N.E(N)=\frac{S(N)}{N}.

Under the ideal Amdahl model,

E(N)=1N(1−p)+p.E(N)=\frac{1}{N(1-p)+p}.

For any fixed nonzero serial fraction, efficiency decreases as more processors are added. A configuration can therefore finish a job faster while using more total processor-time. Execution time, resource cost, and energy consumption are distinct measures and need not improve together.

Historical development

Gene M. Amdahl presented the argument associated with the law in his 1967 paper “Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities,” published in the proceedings of the AFIPS Spring Joint Computer Conference.

The paper examined the prospects of parallel processing and emphasized the importance of work that could not benefit from parallel execution. Its argument concerned the practical difficulty of achieving very large performance gains by multiplying computing resources while leaving other parts of a computation unchanged.

The compact serial-fraction equation became the conventional expression of the principle. It is widely used in computer science, computer architecture, and software engineering to reason about performance limits and optimization priorities.

Overheads and practical limitations

Real parallel programs usually introduce costs beyond those represented in the basic formula. A simple extension is

TN=T1[(1−p)+pN]+H(N),T_N=T_1\left[(1-p)+\frac{p}{N}\right]+H(N),

where T1T_1 is the baseline execution time and H(N)H(N) represents additional overhead at the chosen workload.

Sources of overhead include:

  • Coordination: creating and scheduling tasks, waiting at barriers, and performing synchronization.
  • Communication: transferring data between processors or machines, including through message passing.
  • Uneven work distribution: processors finishing at different times because load balancing is imperfect.
  • Memory contention: competition for memory bandwidth or shared data.
  • Memory-system effects: changes in cache behavior and cache coherence traffic.

These effects can depend on both processor count and input size. Additional processors may eventually produce little benefit or even increase execution time.

Not every loss of efficiency is genuinely serial work. Communication delays and load imbalance can resemble a larger serial fraction when performance is fitted to the basic equation, but they have different causes. An effective serial fraction inferred from measurements is consequently not always an intrinsic property of a program.

Likewise, the parallelizable fraction depends on the chosen algorithm, input, implementation, and machine. A redesign may remove dependencies that previously required sequential execution. Amdahl’s law does not establish that a particular serial fraction must remain unchanged across such redesigns.

Fixed workloads and scaled workloads

Amdahl’s law is most directly associated with strong scaling: measuring how much faster a fixed problem runs as processing resources increase. Weak scaling instead examines performance when the problem size grows with the resources, commonly by keeping the amount of work per processor approximately constant.

Gustafson’s law, introduced by John L. Gustafson in 1988, describes a complementary scaled-workload perspective. If α\alpha is the serial fraction measured during execution on NN processors, the corresponding scaled speedup is

SG(N)=N−α(N−1).S_{\mathrm{G}}(N)=N-\alpha(N-1).

This formulation highlights that larger machines may solve larger problems in a comparable elapsed time. In many applications, increasing the problem size expands parallel work much more than serial work.

The two laws do not contradict one another. They use different workload assumptions, and their serial fractions are measured against different execution-time baselines. Amdahl’s law asks how quickly a fixed computation can finish; Gustafson’s law addresses how much more computation can be performed as resources increase.

Interpretation and uses

Amdahl’s law provides an upper-bound calculation for proposed optimizations. If a database operation occupies only a small fraction of a request’s elapsed time, accelerating that operation alone cannot greatly reduce total request latency. Similarly, a fast accelerator may deliver a large speedup for one kernel but only a modest improvement for the complete application if data transfers and other processing remain unchanged.

The model also explains why performance bottlenecks shift. Once one component becomes faster, previously minor components account for a larger fraction of runtime. Further improvements then require attention to those components rather than continued acceleration of the original target.

For systems processing many independent requests, latency and throughput require separate treatment. A serial stage within each request may limit the latency improvement of that request, while multiple requests can still execute concurrently. Applying the law requires specifying the task boundary and the performance quantity being measured.

Apparent exceptions

Measured speedup can sometimes exceed the processor count, a phenomenon called superlinear speedup. For example, distributing a dataset across processors may allow it to fit into their combined caches, substantially reducing memory accesses. Parallel search may also explore a different sequence of candidates from a sequential implementation.

Such results do not invalidate the equation. They indicate that assumptions behind the simple model have changed: the parallel run is not merely dividing the same work among equivalent processors with otherwise unchanged execution costs.

A meaningful use of Amdahl’s law therefore specifies the baseline, workload, fraction being accelerated, expected local speedup, and any costs introduced by the improvement.