Wet van Gustafson

De wet van Gustafson (of ook de wet van Gustafson-Barsis^[1]) wordt gebruikt in computerarchitectuur om de versnelling in de uitvoeringstijd te bepalen van een taak die theoretisch wint bij parallelle verwerking, waarbij een hypothetische uitvoering van de taak op een single-core machine als ijkpunt gebruikt wordt. Anders gezegd, het is de theoretische "vertraging" van een reeds geparallelliseerde taak als deze op een seriële machine wordt uitgevoerd. De wet is vernoemd naar computerwetenschapper John Gustafson en zijn collega Edwin Barsis en werd gepresenteerd in het artikel Reevaluating Amdahl's Law in 1988.^[2]

Evolutie van de theoretische verbetering van de latentie bij het uitvoeren van een programma in functie van het aantal processors die bij de uitvoering gebruikt worden, volgens de wet van Gustafson

Definitie

Gustafson schatte de versnelling $S$ van een programma verkregen door gebruik te maken van parallelle verwerking als volgt in:

{\begin{aligned}S&=s+p\times N\\&=s+(1-s)\times N\\&=N+(1-N)\times s\end{aligned}}

waarbij:

$S$ de theoretische versnelling is van het programma met parallelisme
$N$ het aantal processoren is
$s$ en $p$ de fracties van de tijd zijn die respectievelijk worden besteed aan het uitvoeren van de seriële delen en de parallelle delen van het programma op het parallelle systeem, waarbij $s+p=1$ .

$S$ kan ook uitgedrukt worden in functie van $p$ :

{\begin{aligned}S&=(1-p)+p\times N\\&=1+(N-1)\times p\end{aligned}}

De wet van Gustafson pakt de tekortkomingen van de wet van Amdahl aan, die ervan uitgaat dat de probleemgrootte vastligt, een zogenaamde vaste workload. Dat wil zeggen dat de probleemgrootte niet verandert wanneer er meer rekenkracht ter beschikking komt. De wet van Gustafson vertrekt van de aanname dat programmeurs de omvang van problemen neigen te vergroten om de extra computerkracht die beschikbaar komt volledig te benutten.^[2]

Gustafson en zijn collega's observeerden verder dat de tijd voor het seriële deel doorgaans niet groeit naarmate het probleem groter wordt,^[2] dat wil zeggen dat $s$ constant blijft. Dit levert een lineair model op tussen het aantal processors $N$ en de versnelling $S$ met helling $1-s$ , zoals weergegeven in de bovenstaande afbeelding (waar verschillende notaties worden gebruikt: $P$ voor $N$ en $a$ voor $s$ ). Bovendien verhoudt $S$ zich lineair tot $s$ en niet exponentieel zoals bij de wet van Amdahl.^[2]

De impact van de wet van Gustafson bestond erin dat problemen geselecteerd of geherformuleerd werden zodat het mogelijk werd om een groter probleem in dezelfde hoeveelheid tijd op te lossen. Op een bepaalde manier herdefinieert de wet efficiëntie, vanwege de mogelijkheid dat beperkingen die worden opgelegd door het sequentiële deel van een programma kunnen worden tegengegaan door de totale hoeveelheid berekeningen te vergroten.

Deductie

De uitvoeringstijd van een programma dat op een parallel systeem draait, kan in twee delen worden gesplitst: een deel dat niet profiteert van het toenemende aantal processoren (seriële deel) en een deel dat profiteert van het toenemende aantal processoren (parallelle deel).

De totale uitvoeringstijd op het parallelle systeem wordt aangegeven als $T$ . Dit omvat zowel de seriële tijd $s$ als de parallelle tijd $p$ , waarbij $s+p=1$ . Het aantal processors wordt aangegeven als $N$ .

Wanneer het programma uitgevoerd zou worden op een serieel systeem (slechts één processor), dan is het seriële gedeelte nog steeds $s$ , terwijl het parallelle deel nu $N\times p$ nodig heeft. De uitvoeringstijd op het seriële systeem is dus:

T'=s+N\times p

Met $T'$ als ijkpunt is de versnelling op het parallelle systeem:

S={\frac {T'}{T}}={\frac {s+N\times p}{s+p}}={\frac {s+N\times p}{1}}=s+N\times p

Door $p=1-s$ te substitueren geeft dit:

{\begin{aligned}S&=s+N\times (1-s)\\&=s+N-N\times s\\&=N+(1-N)\times s\end{aligned}}

Toepassing

In onderzoek

De wet van Amdahl veronderstelt dat de probleemgrootte hetzelfde blijft, gegeven de toegenomen verwerkingskracht. Met andere woorden, een analyse van dezelfde gegevens zal minder tijd kosten met meer computerkracht.

Gustafson betoogt daarentegen dat meer computerkracht ervoor zorgt dat de gegevens zorgvuldiger en vollediger worden geanalyseerd. Waar het bijvoorbeeld niet mogelijk of praktisch zou geweest zijn om de impact van een nucleaire detonatie op elk gebouw, elke auto en hun inhoud (inclusief meubilair, sterkte van de structuur, enz.) te simuleren omdat een dergelijke berekening meer tijd zou hebben gekost dan beschikbaar was om een antwoord te formuleren, zal de toename van de computerkracht onderzoekers ertoe aanzetten om meer gegevens toe te voegen om meer variabelen volledig te simuleren, wat een nauwkeuriger resultaat oplevert.

In alledaags computergebruik

De wet van Amdahl legt een beperking bloot in bijvoorbeeld het vermogen van meerdere processors om de tijd te verkorten die een computer nodig heeft om op te starten en zijn besturingssysteem te laden. Ervan uitgaande dat het opstartproces grotendeels parallel is, zou het verviervoudigen van de rekenkracht op een systeem dat één minuut nodig heeft om op te starten, de opstarttijd kunnen verkorten tot iets meer dan vijftien seconden. Maar steeds meer processors toevoegen zou er uiteindelijk niet in slagen om het opstarten sneller te laten verlopen als een deel van het opstartproces inherent sequentieel zou zijn.

De wet van Gustafson stelt dat een viervoudige toename van de rekenkracht in plaats daarvan zou leiden tot een vergelijkbare toename van de verwachtingen van wat het systeem zal kunnen. Als de laadtijd van één minuut acceptabel is voor de meeste gebruikers, dan is dat een startpunt om de functies en mogelijkheden van het systeem te vergroten. De tijd die nodig is om op te starten naar het besturingssysteem zal hetzelfde zijn, d.w.z. één minuut, maar het nieuwe systeem zou meer grafische of gebruiksvriendelijke functies bevatten.

Beperkingen

In sommige gevallen kan de probleemgrootte fundamenteel niet uitgebreid worden, zoals bijvoorbeeld bij het verwerken van persoonsgegevens aangezien de wereldbevolking jaarlijks slechts met enkele procenten toeneemt. Het belangrijkste punt van de wet van Gustafson is dat dergelijke problemen waarschijnlijk niet de meest aangewezen toepassingen van parallelisme zijn.

Niet-lineaire algoritmen kunnen vaak niet volledig profiteren van de door Gustafson beschreven parallellisatie. Snyder^[3] stelt dat bij een algoritme met een complexiteit van $O(n^{3})$ een verdubbeling van de parallellisatie slechts een toename van ongeveer 26% in probleemgrootte oplevert.

Hill en Marty^[4] stellen vast dat methoden om sequentiële uitvoering te versnellen nog steeds nodig zijn, zelfs voor multicore-machines. Ze wijzen erop dat lokaal inefficiënte methoden globaal efficiënt kunnen zijn wanneer ze de sequentiële fase verkorten. Bovendien bestudeerden Woo en Lee^[5] de implicatie van energie en vermogen op toekomstige multikernprocessors op basis van de wet van Amdahl, waarbij ze aantoonden dat een asymmetrische multikernprocessor de best mogelijke energie-efficiëntie kan bereiken door een optimaal aantal cores te activeren, gegeven de hoeveelheid parallelisme die bekend is voorafgaand aan de uitvoering.

Bronnen, noten en/of referenties

Dit artikel of een eerdere versie ervan is een (gedeeltelijke) vertaling van het artikel Gustafson's law op de Engelstalige Wikipedia, dat onder de licentie Creative Commons Naamsvermelding/Gelijk delen valt. Zie de bewerkingsgeschiedenis aldaar.

↑ (en) McCool, Michael D., Robison, Arch D., Reinders, James (2012). Structured Parallel Programming: Patterns for Efficient Computation. Elsevier, "2.5 Performance Theory", 61–62. ISBN 978-0-12-415993-8.
↑ ^a ^b ^c ^d (en) Gustafson, John L. (mei 1988). Reevaluating Amdahl's Law. Communications of the ACM 31 (5): 532–533. DOI:10.1145/42411.42415.
↑ (en) Snyder, Lawrence (juni 1986). Type Architectures, Shared Memory, and The Corollary of Modest Potential. Annu. Rev. Comput. Sci. 1: 289–317. DOI:10.1146/annurev.cs.01.060186.001445.
↑ (en) Hill, Mark D., Marty, Michael R. (juli 2008). Amdahl's Law in the Multicore Era. IEEE Computer 41 (7): 33–38. DOI:10.1109/MC.2008.209.
↑ (en) Woo, Dong Hyuk, Lee, Hsien-Hsin S. (december 2008). Extending Amdahl's Law for Energy-Efficient Computing in the Many-Core Era. IEEE Computer 41 (12): 24–31. DOI:10.1109/mc.2008.494.

[spp-1] (en) McCool, Michael D., Robison, Arch D., Reinders, James (2012). Structured Parallel Programming: Patterns for Efficient Computation. Elsevier, "2.5 Performance Theory", 61–62. ISBN 978-0-12-415993-8.

[Gustafson1988-2] (en) Gustafson, John L. (mei 1988). Reevaluating Amdahl's Law. Communications of the ACM 31 (5): 532–533. DOI:10.1145/42411.42415.

[Snyder1986-3] (en) Snyder, Lawrence (juni 1986). Type Architectures, Shared Memory, and The Corollary of Modest Potential. Annu. Rev. Comput. Sci. 1: 289–317. DOI:10.1146/annurev.cs.01.060186.001445.

[Hill&Marty2008-4] (en) Hill, Mark D., Marty, Michael R. (juli 2008). Amdahl's Law in the Multicore Era. IEEE Computer 41 (7): 33–38. DOI:10.1109/MC.2008.209.

[Woo&Lee2008-5] (en) Woo, Dong Hyuk, Lee, Hsien-Hsin S. (december 2008). Extending Amdahl's Law for Energy-Efficient Computing in the Many-Core Era. IEEE Computer 41 (12): 24–31. DOI:10.1109/mc.2008.494.

[1]

[2]

[3]

[4]

[5]