Amdahlův zákon

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 21. prosince 2020; kontroly vyžadují 2 úpravy .

Amdahlův zákon ( anglicky  Amdahlův zákon , někdy též Amdahlův zákon - Ware ) - ilustruje omezení růstu výkonu výpočetního systému s nárůstem počtu kalkulaček . Gene Amdahl formuloval zákon v roce 1967, když objevil omezení růstu produktivity při paralelních výpočtech , které je v podstatě jednoduché, ale obsahově nepřekonatelné : „V případě, že je úkol rozdělen na několik částí, celková doba jeho provádění na paralelním systému nemůže být kratší než doba provádění pomalého fragmentu“ [1] . Podle tohoto zákona je zrychlení provádění programu v důsledku paralelizace jeho instrukcí na sadě kalkulaček omezeno časem potřebným k provedení jeho sekvenčních instrukcí.

Matematický výraz

Nechť je třeba vyřešit nějaký výpočetní problém. Předpokládejme, že jeho algoritmus je takový, že podíl z celkového množství výpočtů lze získat pouze sekvenčními výpočty, a proto lze podíl ideálně paralelizovat (to znamená, že doba výpočtu bude nepřímo úměrná počtu zapojených uzlů). ). Pak zrychlení, které lze získat na výpočetním systému procesorů, ve srovnání s jednoprocesorovým řešením nepřekročí hodnotu

Ilustrace

Tabulka ukazuje, kolikrát rychleji bude program proveden s podílem sekvenčních výpočtů při použití procesorů.

\ deset 100 1000
0 deset 100 1000
deset % 5,263 9,174 9,910
25 % 3,077 3,883 3,988
40 % 2,174 2,463 2,496

Tabulka ukazuje, že pouze algoritmus, který vůbec neobsahuje sekvenční výpočty ( ), umožňuje získat lineární nárůst výkonu s nárůstem počtu počítačů v systému. Pokud je podíl sekvenčních výpočtů v algoritmu 25 %, pak zvýšení počtu procesorů na 10 způsobí zrychlení 3,077krát a zvýšení počtu procesorů na 1000 způsobí zrychlení 3,988krát.

Odtud je také zřejmé, že při podílu sekvenčních výpočtů nemůže celkový nárůst výkonu překročit . Pokud je tedy polovina kódu sekvenční, pak celkový zisk nikdy nepřekročí dvě.

Ideologická hodnota

Amdahlův zákon ukazuje, že zvýšení výpočetní účinnosti závisí na algoritmu problému a je shora omezeno pro jakýkoli problém s . Ne pro každý úkol má smysl zvyšovat počet procesorů v počítačovém systému.

Pokud navíc vezmeme v úvahu čas potřebný pro přenos dat mezi uzly výpočetního systému, pak bude mít závislost doby výpočtu na počtu uzlů minimální . To omezuje škálovatelnost výpočetního systému, to znamená, že od určitého okamžiku přidání nových uzlů do systému prodlouží čas na výpočet problému.

Viz také

Poznámky

  1. ↑ Za předpokladu stejné rychlosti všech kalkulaček.

Literatura