Amdahls lov - Amdahl's law

Den teoretiske fremskyndelse af latenstiden ved udførelsen af ​​et program som en funktion af antallet af processorer, der udfører det, ifølge Amdahls lov. Hastigheden er begrænset af den serielle del af programmet. For eksempel, hvis 95% af programmet kan paralleliseres, ville den teoretiske maksimale hastighed ved hjælp af parallel computing være 20 gange.

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

Antag, at en opgave har to uafhængige dele, A og B . Del B tager cirka 25% af tiden for hele beregningen. Ved at arbejde meget hårdt kan man muligvis lave denne del 5 gange hurtigere, men dette reducerer hele beregningstiden kun lidt. I modsætning hertil kan det være nødvendigt at udføre mindre arbejde for at få del A til at udføre dobbelt så hurtigt. Dette vil gøre beregningen meget hurtigere end ved at optimere del B , selvom del B 's hastighed er større med hensyn til forholdet, (5 gange versus 2 gange).

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

eksterne links