Amdahl's law - Wikipedia
Jump to content
Search
Search
Donate
Create account
Log in
Personal tools
Donate
Create account
Log in
Amdahl's law
27 languages
العربية<br>Català<br>Čeština<br>Deutsch<br>Español<br>Eesti<br>فارسی<br>Français<br>עברית<br>Hrvatski<br>Bahasa Indonesia<br>Italiano<br>日本語<br>한국어<br>Македонски<br>Nederlands<br>Polski<br>Português<br>Română<br>Русский<br>Slovenčina<br>Slovenščina<br>Српски / srpski<br>Türkçe<br>Українська<br>Tiếng Việt<br>中文
Edit links
From Wikipedia, the free encyclopedia
Formula in computer architecture
Amdahl's law demonstrates the theoretical maximum speedup of an overall system and the concept of diminishing returns. Plotted here is logarithmic parallelization vs linear speedup. If exactly 50% of the work can be parallelized, the best possible speedup is 2 times. If 95% of the work can be parallelized, the best possible speedup is 20 times. According to the law, even with an infinite number of processors, the speedup is constrained by the unparallelizable portion.<br>In computer architecture, Amdahl's law (or Amdahl's argument [1]) is a formula limiting the speedup of a task as resources are added to the system executing that task.
The law can be stated as[disputed – discuss]:
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.[2]
It is named after computer scientist Gene Amdahl, and was presented at the American Federation of Information Processing Societies (AFIPS) Spring Joint Computer Conference in 1967.
Amdahl's law is often used in parallel computing to predict the theoretical speedup when using multiple processors.
Definition<br>[edit]
In the context of Amdahl's law, speedup can be defined as:[3]
Speedup
Performance for the entire task when enhancements are applied<br>Performance for the same task without those enhancements
{\displaystyle {\text{Speedup}}={\frac {\text{Performance for the entire task when enhancements are applied}}{\text{Performance for the same task without those enhancements}}}}
or
Speedup
Execution time for the entire task without enhancements<br>Execution time for the same task when enhancements are applied
{\displaystyle {\text{Speedup}}={\frac {\text{Execution time for the entire task without enhancements}}{\text{Execution time for the same task when enhancements are applied}}}}
Amdahl's law can be formulated in the following way:[4]
Speedup
overall
time
optimized
time
optimized
speedup
optimized
{\displaystyle {\text{Speedup}}_{\text{overall}}={\frac {1}{(1-{\text{time}}_{\text{optimized}})+{\frac {{\text{time}}_{\text{optimized}}}{{\text{speedup}}_{\text{optimized}}}}}}}
where
Speedup
overall
{\displaystyle {\text{Speedup}}_{\text{overall}}}
represents the total speedup of a program
Time
optimized
{\displaystyle {\text{Time}}_{\text{optimized}}}
represents the proportion of time spent on the portion of the code where improvements are made
Speedup
optimized
{\displaystyle {\text{Speedup}}_{\text{optimized}}}
represents the extent of the improvement
The
Speedup
overall
{\displaystyle {\text{Speedup}}_{\text{overall}}}
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.
Time
optimized
{\displaystyle {\text{Time}}_{\text{optimized}}}
of 0.10) and achieves a
Speedup
optimized
{\displaystyle {\text{Speedup}}_{\text{optimized}}}
of 10,000, then
Speedup
overall
{\displaystyle {\text{Speedup}}_{\text{overall}}}
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.
Time
optimized
{\displaystyle {\text{Time}}_{\text{optimized}}}
of 0.99) with a speedup factor of 100 (i.e.
Speedup
optimized
{\displaystyle {\text{Speedup}}_{\text{optimized}}}
of 100), the
Speedup
overall
{\displaystyle {\text{Speedup}}_{\text{overall}}}
only reaches 50. This indicates that half of the potential performance gain (
Speedup
overall
{\displaystyle {\text{Speedup}}_{\text{overall}}}
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.[4]
Derivation<br>[edit]
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...