Amdahlův zákon - Amdahls law - Wikipedia

Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Dubna 2017) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Teoretické zrychlení latence provádění programu jako funkce počtu procesorů, které jej provádějí, podle Amdahlova zákona. Zrychlení je omezeno sériovou částí programu. Například pokud lze 95% programu paralelizovat, teoretické maximální zrychlení pomocí paralelního výpočtu by bylo 20krát.

v počítačová architektura, Amdahlův zákon (nebo Amdahlova argumentace^[1]) je vzorec, který dává teoretický zrychlit v latence provádění úkolu na pevné pracovní zátěž to lze očekávat od systému, jehož zdroje jsou vylepšeny. Je pojmenována po počítačovém vědci Gene Amdahl, a byl představen na AFIPS Společná jarní počítačová konference v roce 1967.

Amdahlův zákon je často používán v paralelní výpočty předpovědět teoretické zrychlení při použití více procesorů. Například pokud program potřebuje 20 hodin k dokončení pomocí jednoho vlákna, ale hodinovou část programu nelze paralelizovat, proto zbývá pouze zbývajících 19 hodin (p = 0.95) času spuštění lze paralelizovat, pak bez ohledu na to, kolik vláken je věnováno paralelnímu spuštění tohoto programu, nesmí být minimální doba spuštění kratší než jedna hodina. Proto je teoretické zrychlení omezeno na maximálně 20násobek výkonu jednoho vlákna, ${ displaystyle left ({ dfrac {1} {1-p}} = 20 right)}$.

Definice

Amdahlův zákon lze formulovat následujícím způsobem:

${ displaystyle S _ { text {latence}} (s) = { frac {1} {(1-p) + { frac {p} {s}}}}}$

kde

• S_latence je teoretické zrychlení provedení celého úkolu;
• s je počet vláken, přes která je rozdělena paralelní část;
• p je podíl doby realizace, kterou část využívající vylepšené zdroje původně obsadila.

Dále

${ displaystyle { begin {cases} S _ { text {latency}} (s) leq { dfrac {1} {1-p}} [8pt] lim limits _ {s to infty } S _ { text {latency}} (s) = { dfrac {1} {1-p}}. End {cases}}}$

ukazuje, že teoretické zrychlení provádění celého úkolu se zvyšuje se zlepšením zdrojů systému a že bez ohledu na rozsah zlepšení je teoretické zrychlení vždy omezeno částí úkolu, která ze zlepšení nemůže těžit .

Amdahlův zákon se vztahuje pouze na případy, kdy je velikost problému opravena. V praxi, jakmile bude k dispozici více výpočetních zdrojů, mají tendenci si zvykat na větší problémy (větší datové sady) a čas strávený v paralelizovatelné části často roste mnohem rychleji než neodmyslitelně sériová práce. V tomto případě, Gustafsonův zákon poskytuje méně pesimistické a realističtější hodnocení paralelního výkonu.^[2]

Derivace

Úkol provedený systémem, jehož zdroje jsou vylepšeny ve srovnání s původním podobným systémem, lze rozdělit na dvě části:

• část, která neprospívá zlepšení zdrojů systému;
• část, která těží ze zlepšení zdrojů systému.

Příkladem je počítačový program, který zpracovává soubory z disku. Část tohoto programu může prohledat adresář disku a vytvořit seznam souborů interně v paměti. Poté další část programu předá každý soubor zvlášť vlákno pro zpracování. Část, která prohledá adresář a vytvoří seznam souborů, nelze na paralelním počítači zrychlit, ale část, která soubory zpracovává, může.

Čas provedení celého úkolu před zlepšením zdrojů systému je označen jako ${ displaystyle T}$. Zahrnuje čas provedení části, která by neměla prospěch ze zlepšení zdrojů, a dobu provedení té, která by z toho měla prospěch. Zlomek doby provedení úkolu, kterému by prospělo zlepšení zdrojů, je označen ${ displaystyle p}$. Část týkající se části, která by z toho neměla prospěch, tedy je ${ displaystyle 1-p}$. Pak:

${ displaystyle T = (1-p) T + pT.}$

Jedná se o provedení součásti, která těží ze zlepšení zdrojů, které je faktorem urychleno ${ displaystyle s}$ po vylepšení zdrojů. V důsledku toho zůstává doba provedení části, která z ní nemá prospěch, stejná, zatímco část, která z ní těží, se stává:

${ displaystyle { frac {p} {s}} T.}$

Teoretická doba provedení ${ Displaystyle T (s)}$ celého úkolu po vylepšení zdrojů je pak:

${ displaystyle T (s) = (1-p) T + { frac {p} {s}} T.}$

Amdahlův zákon dává teorii zrychlit v latence provedení celého úkolu při pevné pracovní zátěži ${ displaystyle W}$, který přináší

${ displaystyle S _ { text {latence}} (s) = { frac {TW} {T (s) W}} = { frac {T} {T (s)}} = { frac {1} {1-p + { frac {p} {s}}}}.}$

Paralelní programy

Pokud může být 30% doby provedení předmětem zrychlení, p bude 0,3; pokud vylepšení způsobí, že je postižená část dvakrát rychlejší, s bude 2. Amdahlův zákon stanoví, že celkové urychlení uplatnění zlepšení bude:

${ displaystyle S _ { text {latence}} = { frac {1} {1-p + { frac {p} {s}}}} = { frac {1} {1-0,3 + { frac { 0,3} {2}}}} = 1,18.}$

Předpokládejme například, že dostáváme sériovou úlohu, která je rozdělena na čtyři po sobě jdoucí části, jejichž procenta doby provedení jsou p1 = 0.11, p2 = 0.18, p3 = 0.23, a p4 = 0.48 resp. Pak nám bylo řečeno, že první část není zrychlena, takže s1 = 1, zatímco druhá část je zrychlena 5krát, takže s2 = 5, třetí část je zrychlena 20krát, takže s3 = 20a 4. část je zrychlena 1,6krát, takže s4 = 1.6. Použitím Amdahlova zákona je celkové zrychlení

${ displaystyle S _ { text {latence}} = { frac {1} {{ frac {p1} {s1}} + { frac {p2} {s2}} + { frac {p3} {s3} } + { frac {p4} {s4}}}} = { frac {1} {{ frac {0,11} {1}} + { frac {0,18} {5}} + { frac {0,23} {20}} + { frac {0,48} {1,6}}}} = 2,19.}$

Všimněte si, že pětinásobné a dvacetinásobné zrychlení ve 2. a 3. části nemají velký vliv na celkové zrychlení, když je čtvrtý díl (48% doby provedení) zrychlen pouze o 1,6krát.

Sériové programy

Předpokládejme, že úkol má dvě nezávislé části, A a B. Část B zabere zhruba 25% času celého výpočtu. Při velmi tvrdé práci může být člověk schopen udělat tuto část 5krát rychlejší, ale to snižuje čas celého výpočtu jen mírně. Naproti tomu je možné, že budete muset vykonat méně práce, abyste se stali součástí A hrajte dvakrát rychleji. Díky tomu bude výpočet mnohem rychlejší než optimalizací součásti B, i když část B 'zrychlení je větší z hlediska poměru (5krát oproti 2krát).

Například se sériovým programem ve dvou částech A a B pro který T_A = 3 s a T_B = 1 s,

• pokud je součástí B je spuštěn 5krát rychleji, to znamená s = 5 a p = T_B/(T_A + T_B) = 0.25, pak

${ displaystyle S _ { text {latence}} = { frac {1} {1-0,25 + { frac {0,25} {5}}}} = 1,25;}$

• pokud je součástí A je spuštěn dvakrát rychleji, to znamená s = 2 a p = T_A/(T_A + T_B) = 0.75, pak

${ displaystyle S _ { text {latence}} = { frac {1} {1-0,75 + { frac {0,75} {2}}}} = 1,60.}$

Proto je součástí A běžet dvakrát rychleji je lepší než být součástí B běžet 5krát rychleji. Procentní zlepšení rychlosti lze vypočítat jako

${ displaystyle { text {procento vylepšení}} = 100 vlevo (1 - { frac {1} {S _ { text {latence}}}} vpravo).}$

• Vylepšování části A o faktor 2 zvýší celkovou rychlost programu o faktor 1,60, což je o 37,5% rychleji než původní výpočet.
• Vylepšující část B faktorem 5, který pravděpodobně vyžaduje více úsilí, dosáhne celkového faktoru zrychlení pouze 1,25, což zrychlí o 20%.

Optimalizace sekvenční části paralelních programů

Pokud je neparalelizovatelná část optimalizována faktorem ${ displaystyle O}$, pak

${ displaystyle T (O, s) = (1-p) { frac {T} {O}} + { frac {p} {s}} T.}$

Z Amdahlova zákona vyplývá, že zrychlení způsobené paralelismem je dáno vztahem

${ displaystyle S _ { text {latence}} (O, s) = { frac {T (O)} {T (O, s)}} = { frac {(1-p) { frac {1 } {O}} + {p}} {{ frac {1-p} {O}} + { frac {p} {s}}}}.}$

Když ${ displaystyle s = 1}$, my máme ${ displaystyle S _ { text {latence}} (O, s) = 1}$, což znamená, že zrychlení je měřeno s ohledem na čas provedení po optimalizaci neparalelizovatelné části.

Když ${ displaystyle s = infty}$,

${ displaystyle S _ { text {latence}} (O, infty) = { frac {T (O)} {T (O, s)}} = { frac {(1-p) { frac { 1} {O}} + {p}} {{ frac {1-p} {O}} + { frac {p} {s}}}} = 1 + { frac {p} {1-p }}Ó.}$

Li ${ displaystyle 1-p = 0,4}$, ${ displaystyle O = 2}$ a ${ displaystyle s = 5}$, pak:

${ displaystyle S _ { text {latence}} (O, s) = { frac {T (O)} {T (O, s)}} = { frac {{0.4} { frac {1} { 2}} + 0,6} {{ frac {0,4} {2}} + { frac {0,6} {5}}}} = 2,5.}$

Transformace sekvenčních částí paralelních programů na paralelizovatelné

Dále uvažujeme případ, kdy je neparalelizovatelná část snížena o faktor ${ displaystyle O '}$a paralelizovatelná část je odpovídajícím způsobem zvětšena. Pak

${ displaystyle T '(O', s) = { frac {1-p} {O '}} T + left (1 - { frac {1-p} {O'}} right) { frac {T} {s}}.}$

Z Amdahlova zákona vyplývá, že zrychlení způsobené paralelismem je dáno vztahem

${ displaystyle S '_ { text {latence}} (O', s) = { frac {T '(O')} {T '(O', s)}} = { frac {1} { { frac {1-p} {O '}} + left (1 - { frac {1-p} {O'}} right) { frac {1} {s}}}}.}$

Výše uvedená derivace je v souladu s analýzou Jakoba Jenkova ohledně doby provedení vs. kompromisu zrychlení.^[3]

Vztah k zákonu snižování výnosů

Amdahlův zákon je často sjednocen s Zákon o snižování výnosů, zatímco pouze zvláštní případ použití Amdahlova zákona prokazuje zákon o snižování výnosů. Pokud si člověk vybere optimálně (z hlediska dosaženého zrychlení), co má vylepšit, uvidí při zlepšování monotónně klesající vylepšení. Pokud však jeden vybere neoptimálně, po vylepšení suboptimální komponenty a přechodu na vylepšení optimálnější komponenty lze vidět zvýšení návratnosti. Všimněte si, že je často racionální vylepšit systém v pořadí, které je v tomto smyslu „neoptimální“, vzhledem k tomu, že některá vylepšení jsou obtížnější nebo vyžadují delší čas na vývoj než ostatní.

Amdahlův zákon představuje zákon snižování návratnosti, pokud vezmeme v úvahu, jaký druh návratnosti se získá přidáním více procesorů do stroje, pokud je spuštěn výpočet pevné velikosti, který využije všechny dostupné procesory. Každý nový procesor přidaný do systému přidá méně využitelného výkonu než předchozí. Pokaždé, když jeden zdvojnásobí počet procesorů, poměr zrychlení se sníží, protože celková propustnost směřuje k hranici 1 / (1 -p).

Tato analýza zanedbává další potenciální úzká místa, jako je šířka pásma paměti a I / O šířku pásma. Pokud se tyto prostředky nezmění s počtem procesorů, pak pouze přidání procesorů poskytuje ještě nižší výnosy.

Důsledkem Amdahlova zákona je, že k urychlení skutečných aplikací, které mají sériovou i paralelní část, heterogenní výpočty jsou vyžadovány techniky.^[4] Například heterogenní procesor CPU-GPU může poskytovat vyšší výkon a energetickou účinnost než procesor pouze s CPU nebo pouze s GPU.^[5]

Viz také

• Gustafsonův zákon
• Metoda kritické cesty
• Moorův zákon

Reference

Další čtení

• Amdahl, Gene M. (1967). „Platnost přístupu jednoho procesoru k dosažení velkých výpočetních schopností“ (PDF). Sborník konferencí AFIPS (30): 483–485. doi:10.1145/1465482.1465560.CS1 maint: ref = harv (odkaz)

externí odkazy

• „Paralelní programování: Když je Amdahlův zákon nepoužitelný?“. 25. 06. 2011. Archivovány od originál dne 14.4.2013. Citováno 2011-06-26.
• Gene M. Amdahl (1989), Rozhovor o ústní historii s Genem M. Amdahlem, Charles Babbage Institute University of Minnesota, hdl:11299/104341. Amdahl pojednává o své postgraduální práci na University of Wisconsin a jeho designu WISC. Diskutuje o jeho roli při navrhování několika počítačů pro IBM, včetně PROTÁHNOUT SE, IBM 701, a IBM 704. Diskutuje o své práci Nathaniel Rochester a řízení procesu návrhu společností IBM. Zmínky pracují s Ramo-Wooldridge, Aeronutronic, a Computer Sciences Corporation
• Amdahlův zákon: Ne všechna vylepšení výkonu jsou vytvořena stejně (2007)
• „Amdahlův zákon“ Joel F. Klein, Demonstrační projekt Wolfram (2007)
• Amdahlův zákon ve vícejádrové éře (Červenec 2008)
• Co $ # @! je paralelismus? (Charles Leiserson, květen 2008)
• Vyhodnocení funkce Intel Core i7 Turbo Boost (James Charles, Preet Jassi, Ananth Narayan S, Abbas Sadat a Alexandra Fedorova (2009)
• Výpočet zrychlení paralelních programů jako funkce počtu vláken, George Popov, Valeri Mladenov a Nikos Mastorakis (leden 2010)
• Danny Hillis - Prokazování Amdahlova zákona špatné, video nahráno v říjnu 2016