Amdahls lov - Amdahl's law
I computerarkitektur er Amdahls lov (eller Amdahls argument ) en formel, der giver den teoretiske hastighed i forsinkelse af udførelsen af en opgave ved fast arbejdsbyrde, der kan forventes af et system, hvis ressourcer er forbedret. Det er opkaldt efter computerforsker Gene Amdahl og blev præsenteret på AFIPS Spring Joint Computer Conference i 1967.
Amdahls lov bruges ofte i parallel computing til at forudsige den teoretiske hastighed ved brug af flere processorer. For eksempel, hvis et program har brug for 20 timer for at fuldføre ved hjælp af en enkelt tråd, men en times del af programmet ikke kan paralleliseres, kan derfor kun de resterende 19 timer ( p = 0,95 ) udførelsestid paralleliseres, så uanset hvor mange tråde der er afsat til en paralleliseret udførelse af dette program, kan den minimale udførelsestid ikke være mindre end en time. Derfor er den teoretiske hastighedsforøgelse begrænset til højst 20 gange den indre tråd præstation .
Definition
Amdahls lov kan formuleres på følgende måde:
hvor
- S latency er den teoretiske fremskyndelse af udførelsen af hele opgaven;
- s er hastigheden på den del af opgaven, der drager fordel af forbedrede systemressourcer;
- p er andelen af udførelsestiden, som den del, der havde fordel af forbedrede ressourcer, oprindeligt besatte.
Desuden,
viser, at den teoretiske hastighed ved udførelsen af hele opgaven øges med forbedringen af systemets ressourcer, og at uanset størrelsen af forbedringen, er den teoretiske hastighed altid begrænset af den del af opgaven, der ikke kan drage fordel af forbedringen .
Amdahls lov gælder kun i de tilfælde, hvor problemstørrelsen er rettet. I praksis, efterhånden som flere computerressourcer bliver tilgængelige, har de en tendens til at blive brugt til større problemer (større datasæt), og tiden brugt i den paralleliserbare del vokser ofte meget hurtigere end det iboende serielle arbejde. I dette tilfælde giver Gustafsons lov en mindre pessimistisk og mere realistisk vurdering af den parallelle præstation.
Afledning
En opgave udført af et system, hvis ressourcer er forbedret i forhold til et første lignende system, kan opdeles i to dele:
- en del, der ikke drager fordel af forbedringen af systemets ressourcer;
- en del, der drager fordel af forbedringen af systemets ressourcer.
Et eksempel er et computerprogram, der behandler filer fra disk. En del af programmet kan scanne diskens bibliotek og oprette en liste over filer internt i hukommelsen. Derefter sender en anden del af programmet hver fil til en separat tråd til behandling. Den del, der scanner biblioteket og opretter fillisten, kan ikke fremskyndes på en parallel computer, men det kan den del, der behandler filerne.
Hele opgavens udførelsestid før forbedringen af systemets ressourcer betegnes som . Det inkluderer udførelsestiden for den del, der ikke ville drage fordel af forbedringen af ressourcerne og udførelsestiden for den, der ville have gavn af den. Den brøkdel af udførelsestiden for opgaven, der ville drage fordel af forbedringen af ressourcerne, er angivet med . Den, der vedrører den del, der ikke ville have gavn af den, er derfor . Derefter:
Det er udførelsen af den del, der drager fordel af forbedringen af ressourcerne, der accelereres af faktoren efter forbedringen af ressourcerne. Følgelig forbliver udførelsestiden for den del, der ikke drager fordel af den, den samme, mens den del, der drager fordel af den, bliver:
Den teoretiske udførelsestid for hele opgaven efter forbedring af ressourcerne er derefter:
Amdahls lov giver den teoretiske hastighed i latens for udførelsen af hele opgaven ved fast arbejdsbyrde , hvilket giver
Parallelle programmer
Hvis 30% af udførelsestiden kan blive genstand for en speedup, vil p være 0,3; hvis forbedringen gør den berørte del dobbelt så hurtig, vil s være 2. Amdahls lov siger, at den samlede hastighed ved anvendelse af forbedringen vil være:
Antag f.eks., At vi får en seriel opgave, der er opdelt i fire på hinanden følgende dele, hvis procentdel af udførelsestiden er henholdsvis p 1 = 0,11 , p 2 = 0,18 , p 3 = 0,23 og p 4 = 0,48 . Derefter får vi at vide, at 1. del ikke er fremskyndet, så s 1 = 1 , mens 2. del er fremskyndet 5 gange, så s 2 = 5 , den tredje del er fremskyndet 20 gange, så s 3 = 20 , og den fjerde del er fremskyndet 1,6 gange, så s 4 = 1,6 . Ved at bruge Amdahls lov er den samlede hastighed
Læg mærke til, hvordan 5 gange og 20 gange hurtigere på henholdsvis 2. og 3. del ikke har den store effekt på den samlede hastighed, når 4. del (48% af udførelsestiden) kun accelereres med 1,6 gange.
Serielle programmer
For eksempel med et serieprogram i to dele A og B, for hvilke T A = 3 s og T B = 1 s ,
- hvis del B er lavet til at køre 5 gange hurtigere, det er s = 5 og p = T B /( T A + T B ) = 0,25 , så
- hvis del A er lavet til at køre 2 gange hurtigere, det er s = 2 og p = T A /( T A + T B ) = 0,75 , så
Derfor er det bedre at få del A til at køre 2 gange hurtigere end at få del B til at køre 5 gange hurtigere. Den procentvise forbedring af hastigheden kan beregnes som
- Forbedring af del A med en faktor 2 øger den samlede programhastighed med en faktor 1,60, hvilket gør den 37,5% hurtigere end den oprindelige beregning.
- Imidlertid vil forbedring af del B med en faktor 5, som formentlig kræver mere indsats, kun opnå en samlet hastighedsfaktor på 1,25, hvilket gør den 20% hurtigere.
Optimering af den sekventielle del af parallelle programmer
Hvis den ikke-paralleliserbare del er optimeret med en faktor på , så
Det følger af Amdahls lov, at hastigheden på grund af parallelisme er givet af
Når vi har , hvilket betyder, at hastigheden måles i forhold til udførelsestiden, efter at den ikke-paralleliserbare del er optimeret.
Hvornår ,
Hvis , og , så:
Transformere sekventielle dele af parallelle programmer til paralleliserbare
Dernæst overvejer vi det tilfælde, hvor den ikke-paralleliserbare del reduceres med en faktor på , og den paralleliserbare del øges tilsvarende. Derefter
Det følger af Amdahls lov, at hastigheden på grund af parallelisme er givet af
Afledningen ovenfor er i overensstemmelse med Jakob Jenkovs analyse af udførelsestid kontra speedup -afvejning.
Forholdet til loven om faldende afkast
Amdahls lov er ofte i konflikt med loven om faldende tilbagevenden , hvorimod kun et særligt tilfælde af anvendelse af Amdahls lov demonstrerer lov om faldende afkast. Hvis man vælger optimalt (hvad angår den opnåede speedup) det, der skal forbedres, så vil man se monotonisk faldende forbedringer, efterhånden som man forbedrer. Hvis man imidlertid vælger ikke-optimalt, kan man efter en forbedring af en suboptimal komponent og gå videre med at forbedre en mere optimal komponent se en stigning i afkastet. Bemærk, at det ofte er rationelt at forbedre et system i en rækkefølge, der er "ikke-optimal" i denne forstand, da nogle forbedringer er vanskeligere eller kræver større udviklingstid end andre.
Amdahls lov repræsenterer loven om faldende afkast, hvis man overvejer, hvilken slags retur man får ved at tilføje flere processorer til en maskine, hvis man kører en beregning i fast størrelse, der vil bruge alle tilgængelige processorer til deres kapacitet. Hver ny processor, der tilføjes til systemet, tilføjer mindre brugbar strøm end den forrige. Hver gang man fordobler antallet af processorer, vil hastighedsforholdet falde, da den samlede gennemstrømningshoveder mod grænsen 1/(1 - p ).
Denne analyse negligerer andre potentielle flaskehalse, såsom hukommelsesbåndbredde og I/O -båndbredde. Hvis disse ressourcer ikke skaleres med antallet af processorer, giver blot tilføjelse af processorer endnu lavere afkast.
En implikation af Amdahls lov er, at for at fremskynde virkelige applikationer, der har både serielle og parallelle portioner, kræves heterogene computingteknikker .
Se også
Referencer
Yderligere læsning
- Amdahl, Gene M. (1967). "Gyldigheden af den enkelte processormetode til opnåelse af store computerkapaciteter i stor skala" (PDF) . AFIPS Conference Proceedings (30): 483–485. doi : 10.1145/1465482.1465560 .
eksterne links
- "Parallel programmering: Når Amdahls lov ikke finder anvendelse?" . 2011-06-25. Arkiveret fra originalen 2013-04-14 . Hentet 2011-06-26 .
- Gene M. Amdahl (1989), Oral historie interview med Gene M. Amdahl , Charles Babbage Institute , University of Minnesota, HDL : 11299/104341. Amdahl diskuterer sit kandidatarbejde ved University of Wisconsin og hans design af WISC . Diskuterer sin rolle i designet af flere computere til IBM, herunder STRETCH , IBM 701 og IBM 704 . Han diskuterer sit arbejde med Nathaniel Rochester og IBMs ledelse af designprocessen. Mentions arbejder med Ramo-Wooldridge , Aeronutronic og Computer Sciences Corporation
- Amdahls lov: Ikke alle præstationsforbedringer er skabt lige (2007)
- "Amdahls lov" af Joel F. Klein, Wolfram Demonstrations Project (2007)
- Amdahls lov i multicore -æraen (juli 2008)
- Hvad $#@! er Parallelisme, under alle omstændigheder? (Charles Leiserson, maj 2008)
- Evaluering af Intel Core i7 Turbo Boost -funktionen , af James Charles, Preet Jassi, Ananth Narayan S, Abbas Sadat og Alexandra Fedorova (2009)
- Beregning af accelerationen af parallelle programmer som en funktion af antallet af tråde , af George Popov, Valeri Mladenov og Nikos Mastorakis (januar 2010)
- Danny Hillis - Beviser Amdahls lov forkert, video optaget oktober 2016