Wet van Amdahl

De wet van Amdahl wordt gebruikt in computerarchitectuur om de theoretische prestatieverbetering te bepalen bij het uitvoeren van een vaste taak door een systeem waarvan bepaalde onderdelen verbeterd zijn. De wet stelt dat "de algehele prestatieverbetering die wordt verkregen door het optimaliseren van een enkel onderdeel van een systeem beperkt wordt door de fractie van de tijd dat het verbeterde onderdeel daadwerkelijk wordt gebruikt". De wet is vernoemd naar computerwetenschapper Gene Amdahl en werd gepresenteerd op de Spring Joint Computer Conference van de American Federation of Information Processing Societies (AFIPS) in 1967.

De theoretische verbetering van de latentie (via een reductie van de vertragingstijd tussen het verzoek en het retourneren van gegevens in een computersysteem) bij het uitvoeren van een programma in functie van het aantal processors die bij de uitvoering gebruikt worden, volgens de wet van Amdahl.

De wet van Amdahl wordt vaak gebruikt bij parallel computergebruik om de theoretische versnelling te voorspellen bij gebruik van meerdere processors. Stel dat een programma 20 uur nodig heeft om te voltooien met behulp van een enkele thread. Als een één uur durend gedeelte van het programma niet kan geparallelliseerd worden, dan kan alleen de resterende uitvoeringstijd van 19 uur geparallelliseerd worden en zal de minimale uitvoeringstijd altijd meer dan 1 uur bedragen, ongeacht hoeveel threads er gebruikt worden voor de parallelle uitvoering van dit programma. Daarom is de theoretische versnelling minder dan 20 keer de prestatie met één thread.

Definitie

De wet van Amdahl kan als volgt geformuleerd worden:

$S_{\text{latentie}}(s)={\frac {1}{(1-p)+{\frac {p}{s}}}}$

waarbij

• S_latentie de theoretische versnelling is van de uitvoering van de volledige taak
• s de versnelling is van het gedeelte van de taak dat profiteert van de verbeterde onderdelen van het systeem
• p het deel van de uitvoeringstijd is dat het gedeelte van de taak dat profiteert van de verbeterde onderdelen van het systeem oorspronkelijk in beslag nam

Bovendien toont

${\begin{cases}S_{\text{latentie}}(s)\leq {\dfrac {1}{1-p}}\\[8pt]\lim \limits _{s\to \infty }S_{\text{latentie}}(s)={\dfrac {1}{1-p}}\end{cases}}$

aan dat de theoretische versnelling van de volledige taak toeneemt met de verbetering van de onderdelen van het systeem en dat de theoretische versnelling altijd begrensd wordt door het gedeelte van de taak dat niet kan profiteren van de verbeteringen aan het systeem, ongeacht de omvang van de verbeteringen.

De wet van Amdahl is alleen van toepassing in gevallen waar de omvang van het probleem vastligt, een zogenaamde vaste workload. In de praktijk wordt bijkomende rekenkracht vaak gebruikt om complexere problemen op te lossen, waardoor de tijd die gespendeerd wordt in het geparallelliseerde gedeelte van het programma vaak sneller toeneemt dan de tijd die besteed wordt aan het inherent seriële gedeelte. In dit geval geeft de wet van Gustafson een minder pessimistische en meer realistische beoordeling van de parallelle prestatie.

Deductie

Een taak die wordt uitgevoerd door een systeem waarvan de onderdelen zijn verbeterd (in vergelijking met een vergelijkbaar niet-gewijzigd systeem) kan in twee delen worden opgesplitst: een deel dat profiteert van de verbeteringen en een deel dat er niet van profiteert.

De uitvoeringstijd van de hele taak vóór de verbetering van onderdelen van het systeem wordt aangegeven als $T$. Dit omvat de uitvoeringstijd van zowel het deel dat niet zou profiteren van de verbeteringen als de uitvoeringstijd van het deel dat er wel baat bij zou hebben. Het gedeelte van de uitvoeringstijd van het deel dat baat zou hebben bij de verbeteringen wordt aangegeven met $p$. De uitvoeringstijd die betrekking heeft op het deel dat er geen baat bij zou hebben is daarom $1-p$. Dit geeft dus:

$T=(1-p)T+pT$

Enkel het gedeelte dat door de verbeterde onderdelen met een factor $s$ kan versneld worden heeft een impact op de totale uitvoeringstijd:

${\frac {p}{s}}T$

Voor het andere gedeelte verandert er niets. De theoretische uitvoeringstijd $T(s)$ van de hele taak na de verbetering van onderdelen van het systeem is dus:

$T(s)=(1-p)T+{\frac {p}{s}}T$

De wet van Amdahl geeft de theoretische verbetering in latentie bij het uitvoeren van de taak bij een vaste workload $W$:

$S_{\text{latentie}}(s)={\frac {TW}{T(s)W}}={\frac {T}{T(s)}}={\frac {1}{(1-p)+{\frac {p}{s}}}}$

Voorbeelden

Als 30% van de uitvoeringstijd in aanmerking komt voor een versnelling, dan is p gelijk aan 0,3. Als deze verbetering het gedeelte in kwestie twee keer zo snel maakt, dan is s gelijk aan 2. De wet van Amdahl bepaalt dan dat de algehele prestatieverbetering gelijk is aan:

$S_{\text{latentie}}={\frac {1}{(1-p)+{\frac {p}{s}}}}={\frac {1}{(1-0,3)+{\frac {0,3}{2}}}}=1,18$

Veronderstel bijvoorbeeld dat een seriële taak kan opgesplitst worden in vier opeenvolgende delen waarvan het aandeel in de totale uitvoeringstijd respectievelijk p1 = 0,11, p2 = 0,18, p3 = 0,23 en p4 = 0,48 bedraagt. Als vervolgens blijkt dat het eerste deel niet versneld kan worden (dus s1 = 1), het tweede deel versneld kan worden met een factor 5 (s2 = 5), het derde deel met een factor 20 (s3 = 20) en het vierde deel met een factor 1,6 (s4 = 1,6), dan zegt de wet van Amdahl dat de algehele prestatieverbetering gelijk is aan

$S_{\text{latentie}}={\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$

Merk op dat de versnelling van het tweede en derde deel met respectievelijk een factor 5 en een factor 20 niet veel bijdragen aan de algehele prestatieverbetering omdat het vierde deel (dat 48% van de totale uitvoeringstijd in beslag neemt) met slechts een factor 1,6 versneld kon worden.

Optimalistie van verschillende onderdelen van een programma. Het kan een aanzienlijke inspanning vragen om taak B met een factor 5 te versnellen, terwijl dit de totale uitvoeringstijd slechts beperkt verbetert. De optimalisatie van taak A met een factor 2 vergt wellicht minder werk maar heeft een grotere impact op de verbetering van de totale uitvoeringstijd.

De wet van Amdahl kan helpen bij het bepalen of de optimalisatie van onderdelen van het systeem de moeite loont, en zo ja welke onderdelen het meeste bijdragen tot een prestatieverbetering. Neem bijvoorbeeld een seriële taak die kan opgesplitst worden in twee opeenvolgende delen A en B, waarbij T_A = 3 s en T_B = 1 s.

• Als taak B met een factor 5 kan versneld worden (dus s = 5 en p = T_B/(T_A + T_B) = 0,25), dan is de prestatieverbetering:

$S_{\text{latentie}}={\frac {1}{(1-0,25)+{\frac {0,25}{5}}}}=1,25$

• Als taak A met een factor 2 kan versneld worden (dus s = 2 en p = T_A/(T_A + T_B) = 0,75), dan is de prestatieverbetering:

$S_{\text{latentie}}={\frac {1}{(1-0,75)+{\frac {0,75}{2}}}}=1,60$

Er valt dus meer winst te boeken door taak A te versnellen. Het winstpercentage kan als volgt berekend worden:

${\text{winstpercentage}}=100\left(1-{\frac {1}{S_{\text{latentie}}}}\right)$

Taak A versnellen met een factor 2 levert een algehele prestatieverbetering op met een factor 1,60, dus een snelheidswinst van 37,5%. Taak B versnellen met een factor 5, wat waarschijnlijk complexer en duurder is, levert een snelheidswinst van slechts 20% op.