Editing Amdahl's law (section)

== 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 (computing)|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 <math> T </math>. 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 <math> p </math>. The one concerning the part that would not benefit from it is therefore {{nowrap |<math> 1 - p </math>}}. Then:

: <math>T = (1 - p)T + pT.</math>

It is the execution of the part that benefits from the improvement of the resources that is accelerated by the factor <math> s </math> 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:

: <math>\frac{p}{s}T.</math>

The theoretical execution time <math> T (s) </math> of the whole task after the improvement of the resources is then:

: <math>T(s) = (1 - p)T + \frac p s T.</math>

Amdahl's law gives the theoretical [[speedup]] in [[Latency (engineering)|latency]] of the execution of the whole task ''at fixed workload <math> W </math>'', which yields
: <math>S_\text{latency}(s) = \frac{TW}{T(s)W} = \frac{T}{T(s)} = \frac 1 {1 - p + \frac p s}.</math>

=== 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&nbsp;2. Amdahl's law states that the overall speedup of applying the improvement will be:

: <math>S_\text{latency} = \frac{1}{1 - p + \frac{p}{s}} = \frac 1 {1 - 0.3 + \frac {0.3} 2} = 1.18.</math>

For example, assume that we are given a serial task which is split into four consecutive parts, whose percentages of execution time are {{nowrap|1=''p''1 = 0.11}}, {{nowrap|1=''p''2 = 0.18}}, {{nowrap|1=''p''3 = 0.23}}, and {{nowrap|1=''p''4 = 0.48}} respectively. Then we are told that the 1st part is not sped up, so {{nowrap|1=''s''1 = 1}}, while the 2nd part is sped up 5 times, so {{nowrap|1=''s''2 = 5}}, the 3rd part is sped up 20 times, so {{nowrap|1=''s''3 = 20}}, and the 4th part is sped up 1.6 times, so {{nowrap|1=''s''4 = 1.6}}. By using Amdahl's law, the overall speedup is
: <math>S_\text{latency} = \frac{1}{\frac{p1}{s1} + \frac{p2}{s2} + \frac{p3}{s3} + \frac{p4}{s4}} = \frac{1}{\frac{0.11}{1} + \frac{0.18}{5} + \frac{0.23}{20} + \frac{0.48}{1.6}} = 2.19.</math>
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 ===
[[File:Optimizing-different-parts.svg|thumb|400px|Assume that a task has two independent parts, ''A'' and ''B''. Part ''B'' takes roughly 25% of the time of the whole computation. By working very hard, one may be able to make this part 5 times faster, but this reduces the time of the whole computation only slightly. In contrast, one may need to perform less work to make part ''A'' perform twice as fast. This will make the computation much faster than by optimizing part ''B'', even though part ''B'''s speedup is greater in terms of the ratio, (5 times versus 2 times).]]

For example, with a serial program in two parts ''A'' and ''B'' for which {{nowrap|1=''T''<sub>''A''</sub> = 3 s}} and {{nowrap|1=''T''<sub>''B''</sub> = 1 s}},

* if part ''B'' is made to run 5 times faster, that is {{nowrap|1=''s'' = 5}} and {{nowrap|1=''p'' = ''T''<sub>''B''</sub>/(''T''<sub>''A''</sub> + ''T''<sub>''B''</sub>) = 0.25}}, then <math display="block">S_\text{latency} = \frac 1 {1 - 0.25 + \frac{0.25}{5}} = 1.25;</math>
*if part ''A'' is made to run 2 times faster, that is {{nowrap|1=''s'' = 2}} and {{nowrap|1=''p'' = ''T''<sub>''A''</sub>/(''T''<sub>''A''</sub> + ''T''<sub>''B''</sub>) = 0.75}}, then <math display="block">S_\text{latency} = \frac 1 {1 - 0.75 + \frac{0.75}{2}} = 1.60.</math>

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
: <math>\text{percentage improvement} = 100 \left(1 - \frac 1 {S_\text{latency}}\right).</math>

* 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 {{nowrap |<math> O </math>}}, then

: <math>T(O,s) =  (1 - p)\frac{T}{O} + \frac{p}{s} T.</math>

It follows from Amdahl's law that the speedup due to parallelism is given by
: <math>S_\text{latency}(O,s) = \frac{T(O)}{T(O,s)} = \frac {(1 - p)\frac{1}{O} + {p} } {\frac{1 - p}{O} + \frac p s}.</math>

When <math>s=1</math>, we have <math>S_\text{latency}(O,s)=1</math>, meaning that the speedup is
measured with respect to the execution time after the non-parallelizable part is optimized.

When  <math>s=\infty</math>, 
: <math>S_\text{latency}(O,\infty) = \frac{T(O)}{T(O,s)} = \frac {(1 - p)\frac{1}{O} + {p} } {\frac{1 - p}{O} + \frac p s}= 1 + \frac{p}{1-p}O.</math>

If  <math>1-p=0.4</math>, <math>O=2</math> and <math>s=5</math>, then:

: <math>S_\text{latency}(O,s) = \frac{T(O)}{T(O,s)} = \frac{ {0.4} \frac{1}{2} + 0.6} {\frac{0.4}{2} + \frac{0.6}{5} }   = 2.5.</math>

=== Transforming sequential parts of parallel programs into parallelizable ===

Next, we consider the case wherein the non-parallelizable part is reduced by a factor of {{nowrap |<math> O' </math>}}, and the parallelizable part is correspondingly increased. Then

: <math>T'(O',s) =  \frac{1 - p}{O'} T + \left(1-\frac{1-p}{O'}\right) \frac{T}{s}.</math>

It follows from Amdahl's law that the speedup due to parallelism is given by
: <math>S'_\text{latency}(O',s) = \frac{T'(O')}{T'(O',s)} = \frac { 1  } {  \frac{1 - p}{O'} + \left(1-\frac{1-p}{O'}\right) \frac{1}{s}}.</math>