Amdahls lag - Amdahl's law

Den teoretiska påskyndandet av latensen för genomförandet av ett program som en funktion av antalet processorer som kör det, enligt Amdahls lag. Hastigheten begränsas av den seriella delen av programmet. Till exempel, om 95% av programmet kan parallelliseras, skulle den teoretiska maximala hastigheten med parallell beräkning vara 20 gånger.

Inom datorarkitektur är Amdahls lag (eller Amdahls argument ) en formel som ger den teoretiska hastigheten i latens för utförandet av en uppgift vid fast arbetsbelastning som kan förväntas av ett system vars resurser förbättras. Det är uppkallat efter datavetenskapsmannen Gene Amdahl och presenterades vid AFIPS Spring Joint Computer Conference 1967.

Amdahls lag används ofta i parallell beräkning för att förutsäga den teoretiska hastigheten vid användning av flera processorer. Till exempel, om ett program behöver 20 timmar att slutföra med en enda tråd, men en timmes del av programmet inte kan parallelliseras, kan därför endast de återstående 19 timmarna ( p = 0,95 ) av körningstiden parallelliseras, oavsett hur många trådar som ägnas åt ett parallellt utförande av detta program, kan minsta körningstid inte vara mindre än en timme. Därför är den teoretiska uppsnabbning begränsad till högst 20 gånger den enda tråd prestanda, . ${\ displaystyle \ left ({\ dfrac {1} {1-p}} = 20 \ right)}$

Definition

Amdahls lag kan formuleras på följande sätt:

${\ displaystyle S _ {\ text {latens}} (s) = {\ frac {1} {(1-p)+{\ frac {p} {s}}}}}$

var

• S _latens är den teoretiska hastigheten för utförandet av hela uppgiften;
• s är hastigheten på den del av uppgiften som gynnas av förbättrade systemresurser;
• p är andelen exekveringstid som den del som gynnades av förbättrade resurser ursprungligen upptog.

Vidare,

${\ displaystyle {\ begin {cases} S _ {\ text {latens}} (s) \ leq {\ dfrac {1} {1-p}} \\ [8pt] \ lim \ limit _ {s \ to \ infty } S _ {\ text {latens}} (s) = {\ dfrac {1} {1-p}}. \ End {case}}}$

visar att den teoretiska hastigheten för utförandet av hela uppgiften ökar med förbättringen av systemets resurser och att oavsett storleken på förbättringen är den teoretiska hastigheten alltid begränsad av den del av uppgiften som inte kan dra nytta av förbättringen .

Amdahls lag gäller endast de fall där problemstorleken är fast. I praktiken, när fler datorresurser blir tillgängliga, tenderar de att vänja sig vid större problem (större datamängder), och tiden som spenderas i den parallelliserbara delen växer ofta mycket snabbare än det i sig seriella arbetet. I detta fall ger Gustafsons lag en mindre pessimistisk och mer realistisk bedömning av parallellframträdandet.

Härledning

En uppgift som utförs av ett system vars resurser förbättras jämfört med ett initialt liknande system kan delas upp i två delar:

• en del som inte gynnas av förbättringen av systemets resurser;
• en del som gynnas av förbättringen av systemets resurser.

Ett exempel är ett datorprogram som bearbetar filer från hårddisken. En del av det programmet kan skanna skivkatalogen och skapa en lista med filer internt i minnet. Därefter skickar en annan del av programmet varje fil till en separat tråd för bearbetning. Den del som skannar katalogen och skapar fillistan kan inte påskyndas på en parallell dator, men den del som bearbetar filerna kan.

Utförandetiden för hela uppgiften innan förbättringen av systemets resurser betecknas som . Det inkluderar utförandetiden för den del som inte skulle dra nytta av förbättringen av resurserna och utförandetiden för den som skulle ha nytta av den. Den bråkdel av utförandetiden för uppgiften som skulle gynnas av förbättringen av resurserna betecknas med . Den som rör delen som inte skulle ha nytta av den är därför . Sedan: ${\ displaystyle T}$${\ displaystyle p}$${\ displaystyle 1-p}$

${\ displaystyle T = (1-p) T+pT.}$

Det är utförandet av den del som drar nytta av förbättringen av resurserna som accelereras av faktorn efter förbättringen av resurserna. Följaktligen förblir utförandetiden för den del som inte drar nytta av den samma, medan den del som drar nytta av den blir: ${\ displaystyle s}$

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

Den teoretiska genomförandetiden för hela uppgiften efter förbättring av resurserna är då: ${\ displaystyle T (s)}$

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

Amdahls lag ger den teoretiska hastigheten i latens för utförandet av hela uppgiften vid fast arbetsbelastning${\ displaystyle W}$ , vilket ger

${\ displaystyle S _ {\ text {latens}} (s) = {\ frac {TW} {T (s) W}} = {\ frac {T} {T (s)}} = {\ frac {1} {1-p+{\ frac {p} {s}}}}.}$

Parallella program

Om 30% av exekveringstiden kan bli föremål för en hastighetsuppgradering är p 0,3; om förbättringen gör att den drabbade delen dubbelt så snabbt blir s 2. Amdahls lag säger att den totala hastigheten för att tillämpa förbättringen kommer att vara:

${\ displaystyle S _ {\ text {latens}} = {\ frac {1} {1-p+{\ frac {p} {s}}}} = {\ frac {1} {1-0.3+{\ frac { 0,3} {2}}}} = 1,18.}$

Anta till exempel att vi får en serieuppgift som är uppdelad i fyra på varandra följande delar, vars procentsatser av körtiden är p 1 = 0,11 , p 2 = 0,18 , p 3 = 0,23 respektive p 4 = 0,48 . Då får vi veta att den första delen inte är snabbare, så s 1 = 1 , medan den andra delen hastas upp 5 gånger, så s 2 = 5 , den tredje delen hastas upp 20 gånger, så s 3 = 20 , och den fjärde delen hastas upp 1,6 gånger, så s 4 = 1,6 . Genom att använda Amdahls lag är den totala hastigheten

${\ displaystyle S _ {\ text {latens}} = {\ 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.}$

Lägg märke till hur 5 och 20 gånger snabbare hastighet på 2: a respektive 3: e delen inte har stor effekt på den totala hastigheten när den 4: e delen (48% av körtiden) accelereras med endast 1,6 gånger.

Seriella program

Antag att en uppgift har två oberoende delar, A och B . Del B tar ungefär 25% av tiden för hela beräkningen. Genom att arbeta mycket hårt kan man kanske göra den här delen 5 gånger snabbare, men detta minskar tiden för hela beräkningen bara något. Däremot kan man behöva utföra mindre arbete för att få del A att dubbelt så snabbt. Detta kommer att göra beräkningen mycket snabbare än genom att optimera del B , även om hastigheten på del B är större när det gäller förhållandet, (5 gånger kontra 2 gånger).

Till exempel med ett serieprogram i två delar A och B för vilka T _A = 3 s och T _B = 1 s ,

• om del B körs 5 gånger snabbare, det vill säga s = 5 och p = T _B /( T _A + T _B ) = 0,25 , då

${\ displaystyle S _ {\ text {latens}} = {\ frac {1} {1-0,25+{\ frac {0,25} {5}}}} = 1,25;}$

• om del A är gjord för att köra 2 gånger snabbare, det vill säga s = 2 och p = T _A /( T _A + T _B ) = 0,75 , då

${\ displaystyle S _ {\ text {latens}} = {\ frac {1} {1-0,75+{\ frac {0,75} {2}}}} = 1,60.}$

Därför är det bättre att få del A att springa 2 gånger snabbare än att få B att springa 5 gånger snabbare. Den procentuella förbättringen av hastigheten kan beräknas som

${\ displaystyle {\ text {procentuell förbättring}} = 100 \ vänster (1-{\ frac {1} {S _ {\ text {latens}}}} \ höger).}$

• Att förbättra del A med en faktor 2 ökar den totala programhastigheten med en faktor 1,60, vilket gör den 37,5% snabbare än den ursprungliga beräkningen.
• Att förbättra del B med en faktor 5, som förmodligen kräver mer ansträngning, kommer dock att uppnå en total hastighetsfaktor på endast 1,25, vilket gör den 20% snabbare.

Optimera den sekventiella delen av parallella program

Om den icke-parallelliserbara delen är optimerad med en faktor på , då ${\ displaystyle O}$

${\ displaystyle T (O, s) = (1-p) {\ frac {T} {O}}+{\ frac {p} {s}} T.}$

Det följer av Amdahls lag att hastigheten på grund av parallellitet ges av

${\ displaystyle S _ {\ text {latens}} (O, s) = {\ frac {T (O)} {T (O, s)}} = {\ frac {(1-p) {\ frac {1 } {O}}+{p}} {{\ frac {1-p} {O}}+{\ frac {p} {s}}}}.}$

När vi har , vilket betyder att hastigheten mäts med avseende på exekveringstiden efter att den icke-parallelliserbara delen är optimerad. ${\ displaystyle s = 1}$${\ displaystyle S _ {\ text {latens}} (O, s) = 1}$

När , ${\ displaystyle s = \ infty}$

${\ displaystyle S _ {\ text {latens}} (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.}$

Om , och , då: ${\ displaystyle 1-p = 0.4}$${\ displaystyle O = 2}$${\ displaystyle s = 5}$

${\ displaystyle S _ {\ text {latens}} (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.}$

Omvandla sekventiella delar av parallella program till parallelliserbara

Därefter överväger vi fallet där den icke-parallelliserbara delen reduceras med en faktor på och den parallelliserbara delen ökar på motsvarande sätt. Sedan ${\ displaystyle O '}$

${\ displaystyle T '(O', s) = {\ frac {1-p} {O '}} T+\ vänster (1-{\ frac {1-p} {O'}} \ höger) {\ frac {T} {s}}.}$

Det följer av Amdahls lag att hastigheten på grund av parallellitet ges av

${\ displaystyle S '_ {\ text {latens}} (O', s) = {\ frac {T '(O')} {T '(O', s)}} = {\ frac {1} { {\ frac {1-p} {O '}}+\ vänster (1-{\ frac {1-p} {O'}} \ höger) {\ frac {1} {s}}}}.}$

Avledningen ovan stämmer överens med Jakob Jenkovs analys av utförandetid kontra snabbare avvägningar.

Förhållande till lagen om minskande avkastning

Amdahls lag står ofta i konflikt med lagen om minskande avkastning , medan endast ett särskilt fall av tillämpning av Amdahls lag visar på lagen om minskande avkastning. Om man väljer optimalt (vad gäller den uppnådda hastigheten) vad som ska förbättras, kommer man att se monotont minskande förbättringar när man förbättrar. Om man däremot väljer icke-optimalt, efter att ha förbättrat en suboptimal komponent och gått vidare för att förbättra en mer optimal komponent, kan man se en ökning av avkastningen. Observera att det ofta är rationellt att förbättra ett system i en ordning som är "icke-optimal" i denna mening, med tanke på att vissa förbättringar är svårare eller kräver större utvecklingstid än andra.

Amdahls lag representerar lagen om minskande avkastning om man överväger vilken typ av avkastning man får genom att lägga till fler processorer till en maskin, om man kör en beräkning med fast storlek som kommer att använda alla tillgängliga processorer till sin kapacitet. Varje ny processor som läggs till i systemet kommer att lägga till mindre användbar effekt än den föregående. Varje gång man fördubblar antalet processorer kommer hastighetsförhållandet att minska, eftersom den totala genomströmningshuvudet når gränsen 1/(1 -  p ).

Denna analys försummar andra potentiella flaskhalsar som minnesbandbredd och I/O -bandbredd. Om dessa resurser inte skala med antalet processorer, ger bara att lägga till processorer ännu lägre avkastning.

En implikation av Amdahls lag är att för att påskynda verkliga applikationer som har både seriella och parallella delar krävs heterogena datortekniker .

Se även

• Gustafsons lag
• Kritisk vägmetod
• Moores lag

Referenser

Vidare läsning

• Amdahl, Gene M. (1967). "Giltigheten för den enda processormetoden för att uppnå storskaliga beräkningskapacitet" (PDF) . AFIPS Conference Proceedings (30): 483–485. doi : 10.1145/1465482.1465560 .

externa länkar

• "Parallell programmering: När Amdahls lag inte är tillämplig?" . 2011-06-25. Arkiverad från originalet 2013-04-14 . Hämtad 2011-06-26 .
• Gene M. Amdahl (1989), muntlig historiaintervju med Gene M. Amdahl , Charles Babbage Institute , University of Minnesota, hdl : 11299/104341. Amdahl diskuterar sitt forskararbete vid University of Wisconsin och hans design av WISC . Diskuterar hans roll i utformningen av flera datorer för IBM inklusive STRETCH , IBM 701 och IBM 704 . Han diskuterar sitt arbete med Nathaniel Rochester och IBMs ledning av designprocessen. Mentions arbetar med Ramo-Wooldridge , Aeronutronic och Computer Sciences Corporation
• Amdahls lag: Alla prestationsförbättringar skapas inte lika (2007)
• "Amdahl's Law" av Joel F. Klein, Wolfram Demonstrations Project (2007)
• Amdahls lag i flerkärniga eran (juli 2008)
• Vad $#@! är Parallelism, hur som helst? (Charles Leiserson, maj 2008)
• Utvärdering av Intel Core i7 Turbo Boost -funktionen , av James Charles, Preet Jassi, Ananth Narayan S, Abbas Sadat och Alexandra Fedorova (2009)
• Beräkning av accelerationen av parallella program som en funktion av antalet trådar , av George Popov, Valeri Mladenov och Nikos Mastorakis (januari 2010)
• Danny Hillis - bevisar att Amdahls lag är fel, video inspelad oktober 2016