Speedup - Speedup

I computerarkitektur er speedup et tal, der måler den relative ydeevne for to systemer, der behandler det samme problem. Mere teknisk er det forbedringen i hastighed på udførelsen af ​​en opgave, der udføres på to lignende arkitekturer med forskellige ressourcer. Begrebet speedup blev oprettet ved Amdahls lov , som især var fokuseret på parallel behandling . Speedup kan dog bruges mere generelt til at vise effekten på ydeevnen efter enhver ressourceforbedring.

Definitioner

Speedup kan defineres for to forskellige typer størrelser: latenstid og kapacitet .

Forsinkelse af en arkitektur er den gensidige udførelseshastighed for en opgave:

${\ displaystyle L = {\ frac {1} {v}} = {\ frac {T} {W}},}$

hvor

• v er udførelseshastigheden for opgaven
• T er udførelsestiden for opgaven;
• W er opgavens arbejdsbyrde.

Gennemstrømning af en arkitektur er udførelsesgraden for en opgave:

${\ displaystyle Q = \ rho vA = {\ frac {\ rho AW} {T}} = {\ frac {\ rho A} {L}},}$

hvor

• ρ er udførelsestætheden (f.eks. antallet af trin i en instruktionsrørledning til en pipelined arkitektur);
• A er udførelseskapaciteten (f.eks. Antallet af processorer til en parallel arkitektur).

Ventetid måles ofte i sekunder pr. Enhed af arbejdsbelastning. Gennemstrømning måles ofte i enheder med arbejdsbelastning pr. Sekund. En anden gennemstrømningsenhed er instruktioner pr. Cyklus (IPC), og dens gensidige cyklusser pr. Instruktion (CPI) er en anden latensenhed.

Speedup er dimensionsløs og defineret forskelligt for hver type mængde, så det er en ensartet metrik.

Speedup i ventetid

Speedup i latency er defineret ved følgende formel:

${\ displaystyle S _ {\ text {latency}} = {\ frac {L_ {1}} {L_ {2}}} = {\ frac {T_ {1} W_ {2}} {T_ {2} W_ {1 }}},}$

hvor

• S _latens er hastigheden i arkitekturens 2 latens med hensyn til arkitekturen 1;
• L ₁ er latenstiden for arkitekturen 1;
• L ₂ er latenstiden for arkitekturen 2.

Hastighed i latenstid kan forudsiges ud fra Amdahls lov eller Gustafsons lov .

Hastighed i kapacitet

Speedup i kapacitet er defineret ved følgende formel:

${\ displaystyle S _ {\ text {throughput}} = {\ frac {Q_ {2}} {Q_ {1}}} = {\ frac {\ rho _ {2} A_ {2} T_ {1} W_ {2 }} {\ rho _ {1} A_ {1} T_ {2} W_ {1}}} = {\ frac {\ rho _ {2} A_ {2}} {\ rho _ {1} A_ {1} }} S _ {\ text {latency}},}$

hvor

• S- _{gennemstrømning} er hastigheden i gennemstrømningen af ​​arkitekturen 2 med hensyn til arkitekturen 1;
• Q ₁ er gennemstrømningen af ​​arkitekturen 1;
• Q ₂ er gennemstrømningen af ​​arkitekturen 2.

Eksempler

Brug af udførelsestider

Vi tester effektiviteten af ​​en grenprediktor ved udførelsen af ​​et program. Først udfører vi programmet med standardgrenens forudsigelse på processoren, hvilket giver en udførelsestid på 2,25 sekunder. Dernæst udfører vi programmet med vores modificerede (og forhåbentlig forbedrede) grenprediktor på den samme processor, der producerer en udførelsestid på 1,50 sekunder. I begge tilfælde er udførelsesarbejdsbelastningen den samme. Ved hjælp af vores speedup-formel ved vi det

${\ displaystyle S _ {\ text {latency}} = {\ frac {L _ {\ text {old}}} {L _ {\ text {new}}}} = {\ frac {2.25 ~ \ mathrm {s}} { 1,50 ~ \ mathrm {s}}} = 1.5.}$

Vores nye grenprediktor har leveret en 1,5x hastighed i forhold til originalen.

Brug af cykler pr. Instruktion og instruktioner pr. Cyklus

Vi kan også måle hastighed i cykler pr. Instruktion (CPI), hvilket er en latens. For det første udfører vi programmet med standard grenprediktor, som giver en CPI på 3. Derefter udfører vi programmet med vores modificerede grenprediktor, som giver en CPI på 2. I begge tilfælde er udførelsesarbejdsbelastningen den samme, og begge arkitekturer er ikke rørledte eller parallelle. Brug af hastighedsformlen giver

${\ displaystyle S _ {\ text {latency}} = {\ frac {L _ {\ text {old}}} {L _ {\ text {new}}}} = {\ frac {3 ~ {\ text {CPI}} } {2 ~ {\ text {CPI}}}} = 1.5.}$

Vi kan også måle hastighed i instruktioner pr. Cyklus ( IPC ), som er en gennemstrømning og det omvendte af CPI. Brug af hastighedsformlen giver

${\ displaystyle S _ {\ text {throughput}} = {\ frac {Q _ {\ text {new}}} {Q _ {\ text {old}}}} = {\ frac {0,5 ~ {\ text {IPC}} } {0,33 ~ {\ text {IPC}}}} = 1,5.}$

Vi opnår den samme 1,5x hastighed, selvom vi målte forskellige størrelser.

Yderligere detaljer

Lad S være hastigheden af ​​udførelsen af ​​en opgave og s hastigheden for udførelsen af ​​den del af opgaven, der drager fordel af forbedring af ressourcerne i en arkitektur. Lineær hastighed eller ideel hastighed opnås, når S = s . Når du kører en opgave med lineær hastighed, fordobler den lokale hastighed den samlede hastighed. Da dette er ideelt, betragtes det som meget god skalerbarhed .

Effektivitet er en måling af udnyttelsen af ​​ressourcerne i det forbedrede system defineret som

${\ displaystyle \ eta = {\ frac {S} {s}}.}$

Dens værdi er typisk mellem 0 og 1. Programmer med lineær hastighed og programmer, der kører på en enkelt processor, har en effektivitet på 1, mens mange vanskeligt parallelle programmer har effektivitet såsom 1 / ln ( s ), der nærmer sig 0 som antallet af processorer A = s stiger.

I tekniske sammenhænge anvendes effektivitetskurver oftere til grafer end hastighedskurver, siden

• hele området i grafen er nyttigt (hvorimod i hastighedskurver er halvdelen af ​​pladsen spildt);
• det er let at se, hvor godt forbedringen af ​​systemet fungerer;
• der er ikke behov for at tegne en "perfekt hastighed" -kurve.

I marketing sammenhænge anvendes hurtigere kurver oftere, hovedsageligt fordi de går op og til højre og dermed ser bedre ud for de mindre informerede.

Super-lineær hastighed

Nogle gange observeres en hastighedsoverskridelse på mere end A ved brug af A- processorer i parallel computing , hvilket kaldes superlinjær hastighed . Super-lineær hastighed sker sjældent og forvirrer ofte begyndere, der mener, at den teoretiske maksimale hastighed skal være A, når A- processorer bruges.

En mulig årsag til superlinjær hastighed i beregninger på lavt niveau er cacheeffekten, der skyldes de forskellige hukommelseshierarkier på en moderne computer: i parallel computing ændres ikke kun antallet af processorer, men også størrelsen på akkumulerede cacher fra forskellige processorer. Med den større akkumulerede cache-størrelse kan mere eller endda hele arbejdssættet passe ind i cacher, og hukommelsestiden reduceres dramatisk, hvilket medfører ekstra hastighed ud over den faktiske beregning.

En analog situation opstår, når der søges i store datasæt, såsom genomiske data, der søges af BLAST- implementeringer. Der gør det akkumulerede RAM fra hver af noderne i en klynge det muligt for datasættet at flytte fra disk til RAM og derved drastisk reducere den tid, der kræves af f.eks. MpiBLAST til at søge i den.

Super-lineære speedups kan også forekomme, når du udfører backtracking parallelt: en undtagelse i en tråd kan få flere andre tråde til at backtracke tidligt, før de selv når undtagelsen.

Superlinjære speedups kan også forekomme i parallelle implementeringer af branch-and-bound for optimering: behandlingen af ​​en node af en processor kan påvirke det arbejde, som andre processorer skal udføre for de andre noder.

Referencer

Se også

• Amdahls lov
• Gustafsons lov
• Brooks lov
• Karp – Flatt metrisk
• Parallel afmatning
• Skalerbarhed