Amdahls lov - Amdahl's law

Den teoretiske hastigheten på forsinkelsen i utførelsen av et program som en funksjon av antall prosessorer som utfører det, ifølge Amdahls lov. Hastigheten er begrenset av den serielle delen av programmet. For eksempel, hvis 95% av programmet kan parallelliseres, vil den teoretiske maksimale hastigheten ved bruk av parallell databehandling være 20 ganger.

I datamaskinarkitektur , Amdahl lov (eller Amdahl argument ) er en formel som gir den teoretiske hastighetsøkning i latens av utførelsen av en oppgave ved fast arbeidsmengden som kan forventes fra et system hvis ressurser er forbedret. Det er oppkalt etter informatiker Gene Amdahl , og ble presentert på AFIPS Spring Joint Computer Conference i 1967.

Amdahls lov brukes ofte i parallell databehandling for å forutsi den teoretiske hastigheten ved bruk av flere prosessorer. For eksempel, hvis et program trenger 20 timer for å fullføre ved hjelp av en enkelt tråd, men en times del av programmet ikke kan parallelliseres, kan derfor bare de resterende 19 timene ( p = 0,95 ) utføringstiden parallelliseres, uavhengig av hvor mange tråder som er viet til en parallellisert utførelse av dette programmet, kan minimum kjøringstid ikke være mindre enn en time. Derfor er den teoretiske hastighetsøkning begrenset til høyst 20 ganger den eneste tråd ytelse . ${\ displaystyle \ left ({\ dfrac {1} {1-p}} = 20 \ right)}$

Definisjon

Amdahls lov kan formuleres på følgende måte:

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

hvor

• S _latens er den teoretiske hastigheten på utførelsen av hele oppgaven;
• s er hastigheten på den delen av oppgaven som drar fordel av forbedrede systemressurser;
• p er andelen eksekveringstid som delen som hadde fordel av forbedrede ressurser opprinnelig okkuperte.

Dessuten,

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

viser at den teoretiske hastigheten på utførelsen av hele oppgaven øker med forbedringen av systemets ressurser, og at uansett størrelsen på forbedringen, er den teoretiske hastigheten alltid begrenset av den delen av oppgaven som ikke kan ha nytte av forbedringen .

Amdahls lov gjelder bare i tilfeller der problemstørrelsen er løst. I praksis, etter hvert som flere databehandlingsressurser blir tilgjengelige, pleier de å bli vant til større problemer (større datasett), og tiden som brukes i den parallelliserbare delen vokser ofte mye raskere enn det iboende serieverket. I dette tilfellet gir Gustafsons lov en mindre pessimistisk og mer realistisk vurdering av den parallelle forestillingen.

Avledning

En oppgave som utføres av et system hvis ressurser er forbedret sammenlignet med et første lignende system, kan deles opp i to deler:

• en del som ikke drar fordel av forbedringen av systemets ressurser;
• en del som drar fordel av forbedringen av systemets ressurser.

Et eksempel er et dataprogram som behandler filer fra disk. En del av det programmet kan skanne katalogen på disken og lage en liste over filer internt i minnet. Etter det sender en annen del av programmet hver fil til en egen tråd for behandling. Delen som skanner katalogen og lager fillisten, kan ikke fremskyndes på en parallell datamaskin, men den delen som behandler filene kan.

Utførelsestiden for hele oppgaven før forbedring av ressursene i systemet er betegnet som . Den inkluderer utførelsestiden for delen som ikke ville ha fordeler av forbedringen av ressursene og utførelsestiden for den som ville ha nytte av den. Brøkdelen av utførelsestiden for oppgaven som vil ha nytte av forbedring av ressursene er angitt med . Den som angår delen som ikke ville ha nytte av den, er derfor . Deretter: ${\ displaystyle T}$${\ displaystyle p}$${\ displaystyle 1-p}$

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

Det er utførelsen av delen som drar fordel av forbedringen av ressursene som akselereres av faktoren etter forbedringen av ressursene. Følgelig forblir utførelsestiden for delen som ikke har nytte av den den samme, mens delen som drar fordel av den blir: ${\ displaystyle s}$

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

Den teoretiske gjennomføringstiden for hele oppgaven etter forbedring av ressursene er da: ${\ displaystyle T (s)}$

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

Amdahls lov gir den teoretiske hastigheten i ventetid for utførelsen av hele oppgaven ved fast arbeidsbelastning${\ displaystyle W}$ , noe som gir

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

Parallelle programmer

Hvis 30% av gjennomføringstiden kan bli gjenstand for en speedup, vil p være 0,3; hvis forbedringen gjør den berørte delen dobbelt så rask, vil s være 2. Amdahls lov sier at den generelle hastigheten på å bruke forbedringen vil være:

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

Anta for eksempel at vi får en serieoppgave som er delt inn i fire påfølgende deler, hvis prosentandel av utførelsestiden er henholdsvis p 1 = 0,11 , p 2 = 0,18 , p 3 = 0,23 og p 4 = 0,48 . Så får vi beskjed om at den første delen ikke er oppskyndet, så s 1 = 1 , mens den andre delen blir spilt opp 5 ganger, så s 2 = 5 , den tredje delen er hastet opp 20 ganger, så s 3 = 20 , og den fjerde delen hastes opp 1,6 ganger, så s 4 = 1,6 . Ved å bruke Amdahls lov er den totale hastigheten

${\ displaystyle 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.}$

Legg merke til hvordan 5 ganger og 20 ganger hastigheten på henholdsvis 2. og 3. del ikke har stor effekt på den totale hastigheten når 4. del (48% av gjennomføringstiden) akselereres med bare 1,6 ganger.

Serielle programmer

Anta at en oppgave har to uavhengige deler, A og B . Del B tar omtrent 25% av tiden for hele beregningen. Ved å jobbe veldig hardt kan man kanskje gjøre denne delen 5 ganger raskere, men dette reduserer tiden til hele beregningen bare litt. Derimot må man kanskje utføre mindre arbeid for å få del A til å utføre dobbelt så raskt. Dette vil gjøre beregningen mye raskere enn ved å optimalisere del B , selv om hastigheten på del B er større når det gjelder forholdet, (5 ganger versus 2 ganger).

For eksempel med et serieprogram i to deler A og B som T _A = 3 s og T _B = 1 s ,

• hvis del B blir kjørt 5 ganger raskere, det vil si s = 5 og p = T _B /( T _A + T _B ) = 0,25 , da

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

• hvis del A blir kjørt 2 ganger raskere, det vil si s = 2 og p = T _A /( T _A + T _B ) = 0,75 , da

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

Derfor er det bedre å få del A til å løpe 2 ganger raskere enn å få del B til å løpe 5 ganger raskere. Den prosentvise forbedringen i hastighet kan beregnes som

${\ displaystyle {\ text {prosent forbedring}} = 100 \ venstre (1-{\ frac {1} {S _ {\ text {latens}}}} \ høyre).}$

• Å forbedre del A med en faktor 2 vil øke den totale programhastigheten med en faktor på 1,60, noe som gjør den 37,5% raskere enn den opprinnelige beregningen.
• Imidlertid vil en forbedring av del B med en faktor 5, som antagelig krever mer innsats, bare oppnå en total hastighetsfaktor på 1,25, noe som gjør den 20% raskere.

Optimalisering av den sekvensielle delen av parallelle programmer

Hvis den ikke-parallelliserbare delen er optimalisert med en faktor på , da ${\ displaystyle O}$

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

Det følger av Amdahls lov at hastigheten på grunn av parallellitet er gitt 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 , noe som betyr at hastigheten måles i forhold til utførelsestiden etter at den ikke-parallelliserbare delen er optimalisert. ${\ displaystyle s = 1}$${\ displaystyle S _ {\ text {latency}} (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.}$

Hvis , og , så: ${\ 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.}$

Transformere sekvensielle deler av parallelle programmer til parallelliserbare

Deretter vurderer vi saken der den ikke-parallelliserbare delen reduseres med en faktor på , og den parallelliserbare delen økes tilsvarende. Deretter ${\ displaystyle O '}$

${\ displaystyle T '(O', s) = {\ frac {1-p} {O '}} T+\ venstre (1-{\ frac {1-p} {O'}} \ høyre) {\ frac {T} {s}}.}$

Det følger av Amdahls lov at hastigheten på grunn av parallellitet er gitt av

${\ displaystyle S '_ {\ text {latency}} (O', s) = {\ frac {T '(O')} {T '(O', s)}} = {\ frac {1} { {\ frac {1-p} {O '}}+\ venstre (1-{\ frac {1-p} {O'}} \ høyre) {\ frac {1} {s}}}}.}$

Avledningen ovenfor er i samsvar med Jakob Jenkovs analyse av henrettelsestid kontra speedup -avveining.

Forholdet til loven om redusert avkastning

Amdahls lov er ofte i konflikt med loven om redusert retur , mens bare et spesielt tilfelle av å anvende Amdahls lov demonstrerer lov om redusert avkastning. Hvis man velger optimalt (når det gjelder oppnådd speedup) det som skal forbedres, vil man se monotont avtagende forbedringer etter hvert som man forbedrer seg. Hvis man imidlertid velger ikke-optimalt, etter å ha forbedret en suboptimal komponent og gått videre for å forbedre en mer optimal komponent, kan man se en økning i avkastningen. Vær oppmerksom på at det ofte er rasjonelt å forbedre et system i en rekkefølge som er "ikke-optimal" i denne forstand, gitt at noen forbedringer er vanskeligere eller krever større utviklingstid enn andre.

Amdahls lov representerer loven om redusert avkastning hvis man vurderer hva slags avkastning man får ved å legge til flere prosessorer i en maskin, hvis man kjører en beregning med fast størrelse som vil bruke alle tilgjengelige prosessorer til sin kapasitet. Hver ny prosessor som legges til systemet, vil legge til mindre brukbar strøm enn den forrige. Hver gang en dobler antall prosessorer vil hastighetsforholdet reduseres, ettersom den totale gjennomstrømningshodet går mot grensen på 1/(1 -  p ).

Denne analysen neglisjerer andre potensielle flaskehalser som minnebåndbredde og I/O -båndbredde. Hvis disse ressursene ikke skaleres med antall prosessorer, gir bare å legge til prosessorer enda lavere avkastning.

En implikasjon av Amdahls lov er at for å få fart på virkelige applikasjoner som har både serielle og parallelle deler, kreves heterogene datateknikker .

Se også

• Gustafsons lov
• Kritisk banemetode
• Moores lov

Referanser

Videre lesning

• Amdahl, Gene M. (1967). "Gyldigheten til enkeltprosessormetoden for å oppnå store databehandlingskapasiteter" (PDF) . AFIPS Conference Proceedings (30): 483–485. doi : 10.1145/1465482.1465560 .

Eksterne linker

• "Parallell programmering: Når Amdahls lov ikke kan brukes?" . 2011-06-25. Arkivert fra originalen 2013-04-14 . Hentet 2011-06-26 .
• Gene M. Amdahl (1989), muntlig historieintervju med Gene M. Amdahl , Charles Babbage Institute , University of Minnesota, hdl : 11299/104341. Amdahl diskuterer sitt utdanningsarbeid ved University of Wisconsin og hans design av WISC . Drøfter sin rolle i utformingen av flere datamaskiner for IBM inkludert STRETCH , IBM 701 og IBM 704 . Han diskuterer arbeidet hans med Nathaniel Rochester og IBMs ledelse av designprosessen. Nevner arbeide med Ramo-Wooldridge , Aeronutronic og Computer Sciences Corporation
• Amdahls lov: Ikke alle ytelsesforbedringer er skapt like (2007)
• "Amdahl's Law" av Joel F. Klein, Wolfram Demonstrations Project (2007)
• Amdahl's Law in the Multicore Era (juli 2008)
• Hva $#@! er parallellisme, uansett? (Charles Leiserson, mai 2008)
• Evaluering av Intel Core i7 Turbo Boost -funksjonen , av James Charles, Preet Jassi, Ananth Narayan S, Abbas Sadat og Alexandra Fedorova (2009)
• Beregning av akselerasjonen av parallelle programmer som en funksjon av antall tråder , av George Popov, Valeri Mladenov og Nikos Mastorakis (januar 2010)
• Danny Hillis - Beviser Amdahls lov feil, video spilt inn oktober 2016