Amdahlův a Gustafsonův zákon, Karp-Flattova metrika.

Hodně dobrý materiál přímo od intelu, který popisuje nejen Amdahlův a Gustavsonův zákon, ale i jejich důsledky a důvody, proč dnes už Amdahl nestačí:

Amdahlův zákon

Předpokládá, že velikost problému zůstane při paralelizaci stejná 

Předpokládá tedy problém o konstantní velikosti

Tzn. že s rostoucím počtem CPU se nemění rozsah úlohy

Nevyužívá tak plně výpočetní sílu, která je k dispozici při navýšení počtu procesorů 

Nelze dosáhnout perfektního urychlení, protože vždy bude nějaká část výpočtu provedena sekvenčně. G, H – čas strávený sekvenčně prováděným výpočtem. G je čas strávený vykonáváním neparalelizovatelného kódu. H je čas strávený výpočtem paralelizovatelného kódu, ale sekvenčně. Pro velké p platí S(p)=1 + H/G. To by znamenalo, že perfektní urychlení je možné, pokud se lze vyhnout kódu, který nelze paralelizovat. Ale čím větší počet procesorů, tím větší bude režie jejich komunikace, takže to přece jen nepůjde (režie OS je další faktor).

Nebere v potaz load balancing, režii komunikace

Pro problém pevné velikosti s narůstajícím počtem CPU narůstá režie, což od jistého počtu CPU vede k pomalejšímu běhu než při menším počtu CPU

Distribuce rozsáhlých dat u distribuované aplikace může omezit nutnost stránkovat RAM. S dostatečně rychlými komunikačními kanály pak dojde k rychlejšímu vykonávání programového kódu, protože odpadá čekání na zpomalující IO operace provázející stránkování, včetně obsluhy příslušných přerušení. Např. paralelizované vyhledávací algoritmy mohou mít větší než lineární urychlení – lze rychleji upřesnit výběrová kritéria.

Je možné, aby S vyšlo lépe než perfektní urychlení. Nejedná se o chybu ve výpočtu, zejména, pokud porovnáváme proti nejlepšímu sekvenčnímu algoritmu. Vliv na to má cache procesoru, především případ, kdy nastane mnohem častější cache hit než je obvyklé. Výpočet je pak prováděn mnohem rychleji, než když se programový kód dostává k procesoru z pomalejší paměti. Záleží na konkrétním programovém kódu, zda se ho bude dostatečné množství nalézat právě v lokální cache jednotlivých procesorů. Analogicky to platí i pro datovou cache.

Gustavsonův zákon

Říká, že výpočty nad velkou množinou dat mohou být efektivně paralelizovány.

Změna oproti Amdahlovi - místo konstatního rozsahu se uvažuje konstantní doba běhu.

Pokud jde něco paralelizovat, vyřeší se za stejnou dobu větší problémy ("vypočte se toho víc")

Pokud bude sériová část zanedbatelná a budeme mít k dispozici spoustu procesoru s distribuovanou paměti, Amdahl nám nepomůže. A(n)=čas výpočtu sériově, b(n) = čas výpočtu paralelně na p procesorech.

 určuje podíl, kolik kódu se provedlo sériově - y (má to být psí) určuje urychlení na p procesorech.

Např. z tabulky s počtem využitých procesorů (první řádka) a dosaženého urychlení (druhá řádka) lze vypočítat pro jednotlivé počty CPU sériově prováděný podíl - e

Pokud e zůstavá stejné s přibývajícím počtem CPU - hlavním důvodem je omezená možnost paralelismu (a urychlení psí narůstá čím dál méně)

Pokud e s přibývajícím počtem CPU roste, důvodem k slabému urychlení je režie paralelismu (buď se týká nastartování procesů, komunikace, synchronizace nebo omezení architektury)

Pokud e postupně klesá = ideál, čím dál větší část výpočtu se provádí paralelně
