Gustafsons lov - Gustafson's law

Udvikling i henhold til Gustafsons lov om den teoretiske hastighed i latens i udførelsen af et program som en funktion af antallet af processorer, der udfører det, for forskellige værdier af a .

Inden for computerarkitektur giver Gustafsons lov (eller Gustafson – Barsis lov ) den teoretiske hastighed i latens for udførelsen af en opgave på fast udførelsestid, der kan forventes af et system, hvis ressourcer er forbedret. Det er opkaldt efter computervidenskabsmand John L. Gustafson og hans kollega Edwin H. Barsis og blev præsenteret i artiklen Reevaluating Amdahl's Law i 1988.

Definition

Gustafson vurderede hastigheden ved at bruge processorer (i stedet for kun en) til en opgave med en seriel brøkdel (som ikke drager fordel af parallelisme) som følger: ${\ displaystyle S}$ ${\ displaystyle P}$ ${\ displaystyle a}$

{\ displaystyle S = (1-a) P+a = Pa (P-1)}

Ved hjælp af forskellige variabler ( ; ) kan Gustafsons lov formuleres på følgende måde: ${\ displaystyle P \ to s}$ ${\ displaystyle a \ til 1-p}$

{\ displaystyle S _ {\ text {latens}} (r) = 1-p+sp,}

hvor

${\ displaystyle S _ {\ text {latens}}}$ er den teoretiske hastighedshastighed i ventetid for udførelsen af hele opgaven;
${\ displaystyle s}$ er hastigheden i latens i udførelsen af den del af opgaven, der drager fordel af forbedringen af systemets ressourcer;
${\ displaystyle p}$ er den procentdel af udførelsen arbejdsbyrden for hele opgaven vedrørende den del, der nyder godt af forbedringen af ressourcerne i systemet , før forbedringen .

Gustafsons lov omhandler manglerne ved Amdahls lov , som er baseret på antagelsen om en fast problemstørrelse , det vil sige en udførelsesarbejdsbyrde, der ikke ændrer sig med hensyn til forbedring af ressourcerne. Gustafsons lov foreslår i stedet, at programmører har en tendens til at indstille størrelsen på problemer for fuldt ud at udnytte den computerkraft, der bliver tilgængelig, efterhånden som ressourcerne forbedres. Hvis hurtigere udstyr er tilgængeligt, kan større problemer derfor løses inden for samme tid.

Virkningen af Gustafsons lov var at flytte forskningsmål til at vælge eller omformulere problemer, så det ville være muligt at løse et større problem på samme tid. På en måde omdefinerer loven effektiviteten på grund af muligheden for, at begrænsninger pålagt af den sekventielle del af et program kan modvirkes ved at øge den samlede beregningsmængde.

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.

Eksempel. - 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ørelsesarbejde før forbedringen af systemets ressourcer er angivet . Det inkluderer udførelsesarbejdsbyrden for den del, der ikke drager fordel af forbedringen af ressourcerne og udførelsesarbejdsbyrden for den, der drager fordel af den. Den brøkdel af udførelsesarbejdsbyrden, der ville have gavn af forbedringen af ressourcerne, betegnes med . Fraktionen vedrørende den del, der ikke ville have gavn af den, er derfor . Derefter ${\ displaystyle W}$ ${\ displaystyle p}$ ${\ displaystyle 1-p}$

{\ displaystyle W = (1-p) W+pW.}

Det er udførelsen af den del, der drager fordel af forbedringen af ressourcerne, der fremskyndes af en faktor efter forbedringen af ressourcerne. Følgelig forbliver udførelsesarbejdsbyrden for den del, der ikke drager fordel af den, den samme. Den teoretiske udførelsesarbejdsbyrde for hele opgaven efter forbedring af ressourcerne er derefter ${\ displaystyle s}$ ${\ displaystyle W (s)}$

{\ displaystyle W (s) = (1-p) W+spW.}

Gustafsons lov giver den teoretiske hastighed i latens for udførelsen af hele opgaven på et bestemt tidspunkt ${\ displaystyle T}$ , hvilket giver

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

Ansøgninger

Ansøgning i forskning

Amdahls lov forudsætter, at computerkravene forbliver de samme, givet øget behandlingsevne. Med andre ord vil en analyse af de samme data tage mindre tid givet mere computerkraft.

Gustafson på den anden side hævder, at mere computerkraft vil få dataene til at blive mere omhyggeligt og fuldstændigt analyseret: pixel for pixel eller enhed for enhed, snarere end i større skala. Hvor det ikke ville have været muligt eller praktisk at simulere virkningen af nuklear detonation på hver bygning, bil og deres indhold (herunder møbler, strukturstyrke osv.), Fordi en sådan beregning ville have taget mere tid, end der var til rådighed svar, vil stigningen i computerkraft få forskere til at tilføje flere data for mere fuldstændigt at simulere flere variabler, hvilket giver et mere præcist resultat.

Anvendelse i hverdagens edb -systemer

Amdahls lov afslører en begrænsning i f.eks. Flere kerners evne til at reducere den tid, det tager for en computer at starte til sit operativsystem og være klar til brug. Forudsat at opstartsprocessen for det meste var parallel, kan firedobling af computerkraft på et system, der tog et minut at indlæse, reducere opstartstiden til lidt over femten sekunder. Men større og større parallelisering ville i sidste ende ikke få opstart til at gå hurtigere, hvis nogen del af opstartsprocessen i sagens natur var sekventiel.

Gustafsons lov hævder, at en firdobling af computerkraften i stedet ville føre til en lignende stigning i forventningerne til, hvad systemet vil være i stand til. Hvis et minuts indlæsningstid er acceptabel for de fleste brugere, er det et udgangspunkt, hvorfra man kan øge systemets funktioner og funktioner. Tiden det tager at starte til operativsystemet vil være det samme, dvs. et minut, men det nye system vil indeholde mere grafiske eller brugervenlige funktioner.

Begrænsninger

Nogle problemer har ikke fundamentalt større datasæt. Som et eksempel bliver behandlingen af et datapunkt pr. Verdensborger større med kun få procent om året. Det vigtigste punkt i Gustafsons lov er, at sådanne problemer sandsynligvis ikke er de mest frugtbare anvendelser af parallelisme.

Algoritmer med ikke -lineære driftstider kan have svært ved at drage fordel af parallelisme, der er "afsløret" af Gustafsons lov. Snyder påpeger, at en algoritme betyder, at dobbelt samtidighed kun giver en stigning på 26% i problemstørrelse. Selvom det kan være muligt at besætte enorm samtidighed, kan det imidlertid medføre ringe fordel i forhold til den originale, mindre samtidige løsning - men i praksis har der stadig været betydelige forbedringer. ${\ displaystyle O (N^{3})}$

Hill og Marty understreger også, at der stadig er behov for metoder til at fremskynde sekventiel henrettelse, selv for maskiner med flere kerner. De påpeger, at lokalt ineffektive metoder kan være globalt effektive, når de reducerer den sekventielle fase. Desuden studerede Woo og Lee konsekvenserne af energi og kraft på fremtidige mange-core-processorer baseret på Amdahls lov, hvilket viser, at en asymmetrisk multi-core processor kan opnå den bedst mulige energieffektivitet ved at aktivere et optimalt antal kerner givet mængden af parallelisme er kendt før udførelsen.

Languages

In other projects