https://hpc-wiki.info/hpc/index.php?title=Amdahl%27s_Law&feed=atom&action=history
Amdahl's Law - Revision history
2024-03-28T12:20:17Z
Revision history for this page on the wiki
MediaWiki 1.35.9
https://hpc-wiki.info/hpc/index.php?title=Amdahl%27s_Law&diff=1181&oldid=prev
Nina-loseke-fd7a@rwth-aachen.de: /* Formula */
2019-01-10T13:20:53Z
<p><span dir="auto"><span class="autocomment">Formula</span></span></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 13:20, 10 January 2019</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l4" >Line 4:</td>
<td colspan="2" class="diff-lineno">Line 4:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Formula ==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Formula ==</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">According to Amdahl's law, the speedup can never become infintely large. If that were possible, a program with 100 processes or threads would be 100x faster than the serial execution. However, the speedup is limited by the serial part of the program, whose time remains constant. Another important aspect is that the more threads or processor the program is run with, the more overhead will be introduced by managing threads etc.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">In the formulas below, T(N) describes the runtime of a program with N threads / processes.</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>s: serial part of the application</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>s: serial part of the application</div></td></tr>
</table>
Nina-loseke-fd7a@rwth-aachen.de
https://hpc-wiki.info/hpc/index.php?title=Amdahl%27s_Law&diff=1179&oldid=prev
Nina-loseke-fd7a@rwth-aachen.de: Created page with "Amdahl's law characterizes the speedup of a parallel program. It assumes perfect load balance, meaning that all threads / processes do the exact same amount..."
2019-01-10T12:24:50Z
<p>Created page with "Amdahl's law characterizes the speedup of a parallel program. It assumes perfect <a href="/hpc/Load_Balancing" title="Load Balancing">load balance</a>, meaning that all threads / processes do the exact same amount..."</p>
<p><b>New page</b></p><div>Amdahl's law characterizes the speedup of a parallel program. It assumes perfect [[Load_Balancing|load balance]], meaning that all threads / processes do the exact same amount of work and therefore all finish simultaneously.<br />
<br />
__TOC__<br />
<br />
== Formula ==<br />
<br />
s: serial part of the application<br />
<br />
p: parallel part of the application<br />
<br />
N: number of processors<br />
<br />
: <math>T(N) = (s + \frac p N) * T(1)</math><br />
<br />
: <math>\text{Speedup S(N)} = \frac {T(1)} {T(N)} = \frac 1 {s + \frac {1-s} N}</math><br />
<br />
: <math>\text{Efficiency E(N)} = \frac {S(N)} N = \frac {\frac 1 {s + \frac {1-s} N}} N = \frac 1 {s(N-1)+1}</math><br />
<br />
<br />
Amdahl's law is based on perfect load balance. Generally, load balance is defined as follows with tcomp being the time a processor spent with actual work.<br />
<br />
: <math>\text{Load Balance LB} = \frac {avg(tcomp)} {max(tcomp)}</math></div>
Nina-loseke-fd7a@rwth-aachen.de