Gustavson-Barsis lag

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 13 januari 2017; kontroller kräver 3 redigeringar .

Gustafsons lag (ibland Gustafson ) - Barsis ( eng. Gustafson - Barsis lag ) - en uppskattning av den maximalt uppnåbara accelerationen av exekveringen av ett parallellt program, beroende på antalet samtidigt exekverade beräkningstrådar ("processorer") och andelen av sekventiella beräkningar. Analogue of the Amdal Law : John L. Gustafson och Edwin H. Barsis presenterade artikeln "A Reassessment of the Amdal Law" 1988.

Gustafson-Barsis lag uttrycks med formeln: , där $S_{n}=s+(1-s)n=n+(1-n)s$

s är andelen på varandra följande beräkningar i programmet, n är antalet processorer.

Denna snabbhetsuppskattning kallas skalad hastighet , eftersom denna egenskap visar hur effektivt parallell beräkning kan organiseras med en ökning av komplexiteten i de uppgifter som löses.

Skillnad från Amdahls lag

När man utvärderar snabbheten av parallellt utförande antar Amdahls lag att uppgiftens storlek förblir konstant . Värdet av acceleration enligt Amdahls lag visar hur många gånger kortare tid det tar för ett parallellt program att köras. Accelerationsvärdet kan dock också betraktas som en ökning av volymen av den genomförda uppgiften under en konstant tidsperiod . Gustafsons lag utgick ur detta antagande.

Härledning av formeln

Skalningshastighet definieras som förhållandet mellan mängden beräkning som utförs med hjälp av multithreading och mängden beräkning som utförs sekventiellt under samma tid.

$S_{n}={\frac {p\cdot n+s}{p+s}}={\frac {n(p+s)}{p+s}}+{\frac {ss\ cdot n}{p+s}}=n+(1-n){\frac {s}{p+s}}=n+(1-n)s$ , var

s är andelen på varandra följande beräkningar i programmet, p är andelen parallella beräkningar i programmet, n är antalet processorer.

Se även

Amdahls lag

Litteratur

Quinn MJ Parallell programmering i C med MPI och OpenMP. — New York: NY: McGraw-Hill, 2004.

Länkar

Uppskattning av den maximalt uppnåbara parallelliteten . Föreläsning från kursen "Theory and Practice of Parallel Computing" på webbplatsen för Institute of Distance Learning INTUIT .
Omvärderar Amdahls lag. John. L. Gustafson.

Parallell beräkning
Allmänna bestämmelser	Högpresterande datoranvändning Cluster Computing Distribuerad databehandling Grid beräkning dimberäkning
Samtidighetsnivåer	bitar Instruktioner Data Uppgifter
Tråd om utförande	supertrådning Hyper Threading
Teori	Amdahls lag Gustavson-Barsis lag Kostnadseffektivitet Karp-Flatt Metrisk sakta ner Accelerationsfaktor
Element	Bearbeta Flöde Fiber PMPD instruktionsfönster
Samspel	multibearbetning multitasking ( förebyggande multitasking ) kooperativ multitasking ) Multithreading Minneskoherens Cachekoherens Cache-ogiltigförklaring Barriär Synkronisering Check Point
Programmering	Modeller ( Dold parallellism Uttryckt samtidighet Parallellism ) Flynns taxonomi SISD SIMD MISD MIMD SPMD Flöde Icke-blockerande synkronisering
Datateknik	Multiprocessor ( Symmetrisk asymmetrisk ) Minne ( NUMA KOMA Distribuerad delad distribueras delade transaktionell ) Samtidig multithreading MPP Superskalär Vektor processor Matrix processor Superdator Beowulf
API	Ateji PX POSIX-trådar openmp Öppna HMPP PVM MPI UPC Intel Threading Building Blocks Lyft Globala arrayer Charm++ Cilk Co-array Fortran OpenCL CUDA eldström Dryad DryadLINQ
Problem	Svår parallellisering Extrem parallellism Problem med den stora utmaningen Programvarublockering Skalbarhet Race skick Dödläge Aktiv återvändsgränd Deterministisk algoritm Parallell retardation