Amdahls lov - Amdahl's law

Fra Wikipedia, den gratis encyklopædi
Den teoretiske fremskyndelse af latenstiden til udførelsen af ​​et program som en funktion af antallet af processorer, der udfører det, ifølge Amdahls lov. Speedup 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 latenstid af udførelsen af ​​en opgave ved fast arbejdsbyrde, der kan forventes af et system, hvis ressourcer forbedres. 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 til at gennemføre ved hjælp af en enkelt tråd, men en times times del af programmet ikke kan paralleliseres, kan derfor kun de resterende 19 timer ( p = 0,95 ) af udførelsestiden 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 hastighed begrænset til højst 20 gange ydelsen af ​​en enkelt tråd .

Definition

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

hvor

  • S latenstid er den teoretiske hastighed ved udførelsen af ​​hele opgaven;
  • s er hastigheden af ​​den del af opgaven, der drager fordel af forbedrede systemressourcer;
  • p er den del af udførelsestid, som den del, der nyder godt af forbedrede ressourcer, oprindeligt blev brugt.

Desuden,

viser, at den teoretiske hastighed af 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 finder kun anvendelse i de tilfælde, hvor problemstørrelsen er løst. I praksis, når flere databehandlingsressourcer bliver tilgængelige, har de en tendens til at vænne sig til større problemer (større datasæt), og tiden brugt i den paralleliserbare del vokser ofte meget hurtigere end det iboende seriearbejde. I dette tilfælde giver Gustafsons lov en mindre pessimistisk og mere realistisk vurdering af den parallelle præstation.

Afledning

En opgave, der udføres af et system, hvis ressourcer forbedres sammenlignet med et indledende lignende system, kan opdeles i to dele:

  • en del, der ikke drager fordel af forbedring af systemets ressourcer
  • en del, der drager fordel af forbedring af systemets ressourcer.

Et eksempel er et computerprogram, der behandler filer fra disken. En del af dette program kan scanne biblioteket på disken 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 den del, der behandler filerne, kan.

Udførelsestiden for hele opgaven før forbedring af systemets ressourcer betegnes som . Det inkluderer udførelsestid for den del, der ikke ville drage fordel af forbedring af ressourcerne, og udførelsestid for den, der ville drage fordel af den. Den brøkdel af udførelsestiden for opgaven, der vil drage fordel af forbedring af ressourcerne, er angivet med . Det, der vedrører den del, der ikke ville have gavn af det, er derfor . Derefter:

Det er udførelsen af ​​den del, der drager fordel af forbedring af ressourcerne, der accelereres af faktoren efter forbedring 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 være genstand for en hastighed, 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 for at anvende forbedringen vil være:

Antag for eksempel, at vi får en seriel opgave, der er opdelt i fire på hinanden følgende dele, hvis procentdele af udførelsestid er henholdsvis p 1 = 0,11 , p 2 = 0,18 , p 3 = 0,23 og p 4 = 0,48 . Så får vi at vide, at den første del ikke øges, så s 1 = 1 , mens den anden del øges 5 gange, så s 2 = 5 , den tredje del øges 20 gange, så s 3 = 20 , og 4. del øges 1,6 gange, så s 4 = 1,6 . Ved at bruge Amdahls lov er den samlede hastighed

Bemærk, hvordan 5 gange og 20 gange hastighed på henholdsvis 2. og 3. del ikke har særlig stor indflydelse på den samlede hastighed, når den 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 gøre denne del 5 gange hurtigere, men dette reducerer tiden for hele beregningen kun lidt. Derimod 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 serielt program i to dele A og B, hvor T A = 3 s og T B = 1 s ,

  • hvis del B får kørt 5 gange hurtigere, det vil s = 5 og p = T B / ( T A + T B ) = 0,25 , så
  • hvis del A får kørt 2 gange hurtigere, det vil s = 2 og p = T A / ( T A + T B ) = 0,75 , så

Derfor er det bedre at lave del A til at løbe 2 gange hurtigere end at gøre del B til at løbe 5 gange hurtigere. Den procentvise forbedring i hastighed kan beregnes som

  • Forbedring af del A med en faktor 2 øger den samlede programhastighed med en faktor på 1,60, hvilket gør den 37,5% hurtigere end den oprindelige beregning.
  • Forbedring af del B med en faktor 5, som formodentlig kræver mere indsats, opnår dog kun 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

Hvornår har vi , hvilket betyder, at hastigheden måles i forhold til udførelsestiden, efter at den ikke-paralleliserbare del er optimeret.

Når ,

Hvis , og derefter:

Transformere sekventielle dele af parallelle programmer til paralleliserbare

Dernæst betragter vi det tilfælde, hvor den ikke-paralleliserbare del reduceres med en faktor på , og den paralleliserbare del tilsvarende øges. Derefter

Det følger af Amdahls lov, at hastigheden på grund af parallelisme er givet af

Ovenstående afledning er i overensstemmelse med Jakob Jenkovs analyse af udførelsestid versus hurtigere kompromis.

Forholdet til loven om faldende afkast

Amdahls lov er ofte sammensat med loven om faldende afkast , hvorimod kun et specielt tilfælde af anvendelse af Amdahls lov viser lov om faldende afkast. Hvis man vælger optimalt (med hensyn til den opnåede hastighed), hvad der skal forbedres, så vil man se monotont faldende forbedringer, når man forbedrer. Hvis man imidlertid vælger ikke-optimalt, efter at have forbedret en suboptimal komponent og gå videre for at forbedre en mere optimal komponent, kan man 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 bruger alle tilgængelige processorer til deres kapacitet. Hver nye processor, der føjes til systemet, tilføjer mindre anvendelig strøm end den foregående. Hver gang man fordobler antallet af processorer, reduceres hastighedsforholdet, da det samlede gennemløbshoved mod grænsen på 1 / (1 -  p ).

Denne analyse forsømmer 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 dele, kræves heterogene computingsteknikker . For eksempel kan en CPU-GPU heterogen processor muligvis give højere ydelse og energieffektivitet end en processor, der kun er CPU eller GPU.

Se også

Referencer

Yderligere læsning

eksterne links