
In
computer architecture, Amdahl's law (or Amdahl's argument) is a formula that shows how much faster a task can be completed when more resources are added to the system.
The law can be stated as:
"the overall performance improvement gained by optimizing a single part of a system is limited by the fraction of time that the improved part is actually used".
It is named after computer scientist
Gene Amdahl
Gene Myron Amdahl (November 16, 1922 – November 10, 2015) was an American computer architect and high-tech entrepreneur, chiefly known for his work on mainframe computers at IBM and later his own companies, especially Amdahl Corporation. ...
, and was presented at the
American Federation of Information Processing Societies
The American Federation of Information Processing Societies (AFIPS) was an umbrella organization of professional societies established on May 10, 1961, and dissolved in 1990. Its mission was to advance knowledge in the field of information scien ...
(AFIPS) Spring Joint Computer Conference in 1967.
Amdahl's law is often used in
parallel computing
Parallel computing is a type of computing, computation in which many calculations or Process (computing), processes are carried out simultaneously. Large problems can often be divided into smaller ones, which can then be solved at the same time. ...
to predict the theoretical
speedup
In computer architecture, speedup is a number that measures the relative performance of two systems processing the same problem. More technically, it is the improvement in speed of execution of a task executed on two similar architectures with ...
when using multiple processors.
Definition
In the context of Amdahl's law, speedup can be defined as:
or
Amdahl's law can be formulated in the following way:
:
where
*
represents the total speedup of a program
*
represents the proportion of time spent on the portion of the code where improvements are made
*
represents the extent of the improvement
The
is frequently much lower than one might expect. For instance, if a programmer enhances a part of the code that represents 10% of the total execution time (i.e.
of 0.10) and achieves a
of 10,000, then
becomes 1.11 which means only 11% improvement in total speedup of the program. So, despite a massive improvement in one section, the overall benefit is quite small. In another example, if the programmer optimizes a section that accounts for 99% of the execution time (i.e.
of 0.99) with a speedup factor of 100 (i.e.
of 100), the
only reaches 50. This indicates that half of the potential performance gain (
will reach 100 if 100% of the execution time is covered) is lost due to the remaining 1% of execution time that was not improved.
Derivation
A task executed by a system whose resources are improved compared to an initial similar system can be split up into two parts:
* a part that does not benefit from the improvement of the resources of the system;
* a part that benefits from the improvement of the resources of the system.
An example is a computer program that processes files. A part of that program may scan the directory of the disk and create a list of files internally in memory. After that, another part of the program passes each file to a separate
thread for processing. The part that scans the directory and creates the file list cannot be sped up on a parallel computer, but the part that processes the files can.
The execution time of the whole task before the improvement of the resources of the system is denoted as
. It includes the execution time of the part that would not benefit from the improvement of the resources and the execution time of the one that would benefit from it. The fraction of the execution time of the task that would benefit from the improvement of the resources is denoted by
. The one concerning the part that would not benefit from it is therefore . Then:
:
It is the execution of the part that benefits from the improvement of the resources that is accelerated by the factor
after the improvement of the resources. Consequently, the execution time of the part that does not benefit from it remains the same, while the part that benefits from it becomes:
:
The theoretical execution time
of the whole task after the improvement of the resources is then:
:
Amdahl's law gives the theoretical
speedup
In computer architecture, speedup is a number that measures the relative performance of two systems processing the same problem. More technically, it is the improvement in speed of execution of a task executed on two similar architectures with ...
in
latency of the execution of the whole task ''at fixed workload
'', which yields
:
Parallel programs
If 30% of the execution time may be the subject of a speedup, ''p'' will be 0.3; if the improvement makes the affected part twice as fast, ''s'' will be 2. Amdahl's law states that the overall speedup of applying the improvement will be:
:
For example, assume that we are given a serial task which is split into four consecutive parts, whose percentages of execution time are , , , and respectively. Then we are told that the 1st part is not sped up, so , while the 2nd part is sped up 5 times, so , the 3rd part is sped up 20 times, so , and the 4th part is sped up 1.6 times, so . By using Amdahl's law, the overall speedup is
:
Notice how the 5 times and 20 times speedup on the 2nd and 3rd parts respectively don't have much effect on the overall speedup when the 4th part (48% of the execution time) is accelerated by only 1.6 times.
Serial programs

For example, with a serial program in two parts ''A'' and ''B'' for which and ,
* if part ''B'' is made to run 5 times faster, that is and , then
*if part ''A'' is made to run 2 times faster, that is and , then
Therefore, making part ''A'' to run 2 times faster is better than making part ''B'' to run 5 times faster. The percentage improvement in speed can be calculated as
:
* Improving part ''A'' by a factor of 2 will increase overall program speed by a factor of 1.60, which makes it 37.5% faster than the original computation.
* However, improving part ''B'' by a factor of 5, which presumably requires more effort, will achieve an overall speedup factor of 1.25 only, which makes it 20% faster.
Optimizing the sequential part of parallel programs
If the non-parallelizable part is optimized by a factor of , then
:
It follows from Amdahl's law that the speedup due to parallelism is given by
:
When
, we have
, meaning that the speedup is
measured with respect to the execution time after the non-parallelizable part is optimized.
When
,
:
If
,
and
, then:
:
Transforming sequential parts of parallel programs into parallelizable
Next, we consider the case wherein the non-parallelizable part is reduced by a factor of , and the parallelizable part is correspondingly increased. Then
:
It follows from Amdahl's law that the speedup due to parallelism is given by
:
Relation to the law of diminishing returns
Amdahl's law is often conflated with the
law of diminishing returns, whereas only a special case of applying Amdahl's law demonstrates law of diminishing returns. If one picks optimally (in terms of the achieved speedup) what is to be improved, then one will see monotonically decreasing improvements as one improves. If, however, one picks non-optimally, after improving a sub-optimal component and moving on to improve a more optimal component, one can see an increase in the return. Note that it is often rational to improve a system in an order that is "non-optimal" in this sense, given that some improvements are more difficult or require larger development time than others.
Amdahl's law does represent the law of diminishing returns if one is considering what sort of return one gets by adding more processors to a machine, if one is running a fixed-size computation that will use all available processors to their capacity. Each new processor added to the system will add less usable power than the previous one. Each time one doubles the number of processors the speedup ratio will diminish, as the total throughput heads toward the limit of 1/(1 − ''p'').
This analysis neglects other potential bottlenecks such as
memory bandwidth
Memory bandwidth is the rate at which data can be read from or stored into a semiconductor memory by a processor. Memory bandwidth is usually expressed in units of bytes/second, though this can vary for systems with natural data sizes that are ...
and I/O bandwidth. If these resources do not scale with the number of processors, then merely adding processors provides even lower returns.
An implication of Amdahl's law is that to speed up real applications which have both serial and parallel portions,
heterogeneous computing
Heterogeneous computing refers to systems that use more than one kind of processor or core. These systems gain performance or energy efficiency not just by adding the same type of processors, but by adding dissimilar coprocessors, usually incor ...
techniques are required. There are novel speedup and energy consumption models based on a more general representation of heterogeneity, referred to as the normal form heterogeneity, that support a wide range of heterogeneous many-core architectures. These modelling methods aim to predict system power efficiency and performance ranges, and facilitates research and development at the hardware and system software levels.
See also
*
Gustafson's law
In computer architecture, Gustafson's law (or Gustafson–Barsis's law) gives the speedup in the execution time of a task that theoretically gains from parallel computing, using a hypothetical run of ''the task'' on a single-core machine as the ba ...
*
Universal Law of Computational Scalability
*
Analysis of parallel algorithms
In computer science, analysis of parallel algorithms is the process of finding the computational complexity of algorithms executed in parallel – the amount of time, storage, or other resources needed to execute them. In many respects, analysis ...
*
Critical path method
The critical path method (CPM), or critical path analysis (CPA), is an algorithm for schedule (project management), scheduling a set of project activities. A critical path is determined by identifying the longest stretch of dependent activiti ...
*
Moore's law
Moore's law is the observation that the Transistor count, number of transistors in an integrated circuit (IC) doubles about every two years. Moore's law is an observation and Forecasting, projection of a historical trend. Rather than a law of ...
*
List of eponymous laws
References
Further reading
*
External links
* . Amdahl discusses his graduate work at the University of Wisconsin and his design of
WISC. Discusses his role in the design of several computers for IBM including the
STRETCH,
IBM 701
The IBM 701 Electronic Data Processing Machine, known as the Defense Calculator while in development, was IBM’s first commercial scientific computer and its first series production mainframe computer, which was announced to the public on May 2 ...
, and
IBM 704
The IBM 704 is the model name of a large digital computer, digital mainframe computer introduced by IBM in 1954. Designed by John Backus and Gene Amdahl, it was the first mass-produced computer with hardware for floating-point arithmetic. The I ...
. He discusses his work with
Nathaniel Rochester and IBM's management of the design process. Mentions work with
Ramo-Wooldridge,
Aeronutronic, and
Computer Sciences Corporation
Computer Sciences Corporation (CSC) was an American multinational corporation that provided information technology (IT) services and professional services. On April 3, 2017, it merged with the Enterprise Services line of business of HP Ente ...
"Amdahl's Law"by Joel F. Klein,
Wolfram Demonstrations Project
The Wolfram Demonstrations Project is an Open source, open-source collection of Interactive computing, interactive programmes called Demonstrations. It is hosted by Wolfram Research. At its launch, it contained 1300 demonstrations but has grown t ...
(2007)
Amdahl's Law in the Multicore Era(July 2008)
{{Parallel Computing
Analysis of parallel algorithms
Computer architecture statements