Paralelní výpočty

Paralelní výpočty (anglicky parallel computing) je v informatice označení pro výpočty, které jsou řešeny souběžně („paralelně“).^[1] Paralelizace je využívána pro zvýšení výpočetního výkonu v situaci, kdy nelze použít rychlejší počítač (vyšší frekvenci)^[2] nebo pro zjednodušení použitého algoritmu nebo pro lepší využití elektrické energie.^[3] Paralelní výpočty se mohou realizovat pomocí víceprocesorových systémů^[4] nebo spuštěním úlohy na počítačovém clusteru, kde jsou jednotlivé počítače propojené pomocí výpočetní sítě. Paralelizace funguje na principu rozdělování složitějších úloh na jednodušší a je považována za obtížnější formu programování.^[5] Existuje několik rozdílných forem paralelních výpočtů: bitové, instrukční, datové a paralelní úlohy.

Paralelní výpočty mohou být klasifikovány podle úrovní, na kterých podporují paralelismus, s vícejádrovými a víceprocesorovými počítači, které mají více prvků zpracovávajících data v rámci jednoho stroje, zatímco clustery, MPP a gridy pomocí velkého množství počítačů pracují na stejné úloze. Specializované paralelní počítačové architektury (např. MIC - anglicky Many Integrated Core Architecture) jsou často využívány vedle tradičních procesorů, pro urychlení konkrétních výpočtů.

Paralelní počítačové programy jsou mnohem náročnější na vytvoření než je tomu u sekvenčních programů, protože souběžnost zavádí několik nových tříd potenciálních programátorských chyb, z kterých je nejčastější souběh. Komunikace a synchronizace mezi jednotlivými úlohami je nejčastěji největší překážkou pro dobrou výkonnost paralelních programů.

Paralelismus byl využíván po mnoho let zejména při vysoko výkonnostních výpočtech, ale zájem o něj roste v poslední době díky fyzickým omezením bránícím dalšímu zvyšování frekvence procesorů. Jako se stala spotřeba energie počítače (a s tím zvýšené generování tepla) problémem v posledních letech, tak se paralelní výpočty staly dominantním paradigmatem v počítačové architektuře, zejména ve formě vícejádrových procesorů.

Maximální možné zrychlení jednoho programu v důsledku paralelizace je možné odhadnout pomocí Amdahlova zákona.

Tradičně je počítačový software psán pro sekvenční výpočty. K vyřešení problému je vytvořen algoritmus, zapsán jako program, přeložen do strojových instrukcí, které jsou prováděny na CPU. Pouze jedna instrukce je prováděna v čase - poté co byla instrukce dokončena, poté se může vykonávat další instrukce.^[6]

Paralelní výpočty naproti tomu, používají najednou vícero prvků, zpracovávajících data, k vyřešení úlohy. Toho se dosahuje rozčleněním úlohy na dílčí úkoly, tak aby každý prvek mohl zpracovat část algoritmu současně s ostatními. Tyto prvky mohou být různé a zahrnují i zdroje jako jeden počítač s více procesory, několik počítačů v síti, specializovaný hardware, nebo kombinací zmíněných.^[7]

Navyšování taktovací frekvence CPU bylo dominantní ve vylepšování výkonu počítačů od poloviny roku 1980 do roku 2004. Doba běhu programu byla úměrná počtu instrukcí a době zpracování jedné instrukce. Zvýšením frekvence tedy došlo ke zrychlení programů prováděných počítačem.

Nicméně spotřeba energie digitálního obvodu je dána vzorcem:

P = C x V2 x F

kde P je výkon, C je kapacita měnící se v každém cyklu hodin (úměrně počtu tranzistorů jejichž vstupy mění), V je elektrické napětí, a F je frekvence procesoru (cykly za sekundu).^[8] Zvýšením frekvence se zvýší i výkon procesoru.

Zvyšující se spotřeba energie nakonec vedla v červnu 2004 Intel k ukončení vývoje procesorů Tejas a Jayhawk, které jsou obecně uváděny jako poslední procesory vyrobené s frekvenčním rozsahem jakožto dominantním paradigmatem počítačové architektury.^[9]

Mooreův zákon je empirické pozorování, které říká že hustota tranzistorů v mikroprocesorech, při zachování stejné ceny, se zdvojnásobí každých 24 měsíců^[10] (v originále uváděno 18 měsíců, dnešní vývoj odpovídá spíše 24 měsícům). Navzdory otázkám spotřeby energie a opakované předpovědi jeho konci, Moorův zákon je stále v platnosti. S koncem frekvenční škálovatelnosti, mohou být tyto tranzistory (nepoužívané více k frekvenčnímu škálování) použity k přidání dalšího hardwaru umožňujícímu paralelní výpočty.

Porozumění závislosti dat je základ v implementaci paralelních algoritmů. Žádný program nemůže běžet rychleji než nejdelší řetězec na sobě závislých kalkulací (někdy se označuje jako kritická cesta), protože výpočty závislé na předchozích výpočtech musejí být provedeny v určeném pořadí. Nicméně, mnoho algoritmů není jen jedním velkým řetězem závislých výpočtů, ale vyskytují se zde příležitosti k provádění paralelních výpočtů.

Ať P_i a P_j jsou dva segmenty programu. Bernsteinova podmínka^[11] popisuje kdy jsou tyto dva segmenty nezávislé a mohou být prováděny paralelně. Pro P_i, bude I_i značit všechny vstupní proměnné a O_i výstupní proměnné, a také pro P_j. P_j a P_i jsou nezávislé pokud splňují následující podmínky:

• ${\displaystyle I_{j}\cap O_{i}=\varnothing ,\,}$
• ${\displaystyle I_{i}\cap O_{j}=\varnothing ,\,}$
• ${\displaystyle O_{i}\cap O_{j}=\varnothing .\,}$

Porušení první podmínky způsobí závislost toku, odpovídající závislosti kdy první segment produkuje výsledek používaný druhým segmentem. Druhá podmínka reprezentuje anti-závislost, druhý segment (P_j) produkuje proměnnou, kterou potřebuje první segment (P_i). Třetí a poslední podmínka pak reprezentuje závislost výstupu: když dva segmenty zapíšou do stejného místa, pak výsledek pochází logicky od posledního segmentu.^[12]

Následující instrukce demonstrují několik závislostí:

• 1: funkce Dep(a, b)
• 2: c := a·b
• 3: d := 3·c
• 4: konec funkce

Třetí operace v tomto příkladě nemůže být provedena před (nebo paralelně) s operací druhou, protože třetí operace používá výsledek z druhé. Porušuje se tím první podmínka o závislosti toku.

• 1: funkce NoDep(a, b)
• 2: c := a·b
• 3: d := 3·b
• 4: e := a+b
• 5: end funkce

V tomto příkladě, nejsou žádné závislosti mezi proměnnými a proto mohou být spuštěny paralelně.

Bersteinova podmínka nedovoluje sdílení paměti mezi různými procesy. Kvůli tomuto, je potřeba používat systémy vynucování a předávání mezi procesy, jako například semafory, bariéry nebo některé další synchronizační metody.

Při využívání paralelních výpočtů může docházet k různým problémům, které u klasického programování nemusí nastat.

Dílčí výpočty mohou být v paralelních programech implementovány buď jako samostatné procesy nebo jako vlákna. Výhodou vláken je sdílená paměť. Když jsou aktualizována data, která jsou sdílená mezi vlákny či procesy, může dojít k souběhu. Prozkoumejme následující situaci:

Když instrukce 1B je provedena mezi instrukcemi 1A a 3A, nebo když instrukce 1A je provedena mezi 1B a 3B, program vyprodukuje špatná data. Toto je známo jako souběh. Programátor musí použít zámek a provést vzájemné vyloučení. Zámek je konstrukce programovacího jazyka, která umožňuje vláknu převzít kontrolu nad proměnnou a zamezit ostatním vláknům čtení a zápis, dokud není proměnná otevřena. Vlákno vlastnící zámek může zcela volně provádět svoji kritickou sekci (sekce programu, která vyžaduje exkluzivní přístup k proměnné), a otevírá zámek po provedení operací. Proto, aby byl zajištěn správný běh programu, program výše by měl vypadat následovně:

Jedno vlákno úspěšně uzamkne proměnnou V, pro ostatní vlákna je uzamknutá - tedy nemohou k ní přistupovat dokud není znova odemknuta. Toto zajistí správné provádění programu. Zámky, jsou nezbytné k správnému chodu programu, ale také ho mohou výrazně zpomalit.

Zamykání mnoha proměnných používáním neatomických zámků může zapříčinit programové uváznutí. Atomický zámek uzamkne vícero proměnných najednou. Pokud nemůže zamknout některé z nich nezamkne žádné. Když dvě vlákna potřebují zamknout dvě stejné proměnné s použitím ne-atomického zámku, je možné že jedno vlákno zamkne první z nich a druhé vlákno zamkne druhou. V tomto případě, žádné z vláken neskončí, a dojde k uváznutí.

Mnoho paralelních programů potřebuje, aby jejich dílčí úkoly byly vykonány synchronně. Toto vyžaduje používání bariér. Bariéry jsou typicky implementovány používáním softwarových zámků. Jedna třída algoritmů, známá jako lock-free a wait-free algoritmy, se zcela vyhýbá používání bariér a zámků. Nicméně, tento postup je obecně obtížné implementovat a vyžaduje správně vytvořené datové struktury.

Paralelizacovaný výpočet nemusí být nutně rychlejší než klasický sekvenční výpočet. Když je úloha rozložena na více procesů nebo vláken, může být totiž část doby běhu úlohy spotřebována na jejich vzájemnou komunikaci (nebo pro vyjednávání a čekání na přístup do společné paměti či úložiště). Tím vzniká režie a spotřebovaný strojový čas počítače se zvyšuje, i když náročnost vlastního výpočtu zůstává stejná. Objem vzájemné komunikace může při nevhodně zvoleném postupu výpočtu dokonce růst exponenciálně vůči počtu vláken (například zdvojnásobením počtu vláken se režie zvýší čtyřnásobně). Tím může paradoxně kvůli paralelizaci dojít ke zpomalení výpočtu, což se označuje jako „paralelní zpomalení“.^[13]

Vždy pro danou velikost úlohy a počet procesorů:^[14]

• Paralelní čas – je čas mezi spuštěním výpočtu a dokončením výpočtu na nejpomalejším procesoru
• Paralelní cena – je součinem paralelního času a počtu procesorů
• Paralelní práce – odpovídá počtu provedených operací na všech procesorech, je tedy přesnější metrikou než paralelní cena
• Paralelní zrychlení – definuje zrychlení vykonání problému na daném počtu procesorů oproti nejrychlejšímu známému sekvenčnímu algoritmu
• Paralelní efektivnost – je poměrem sekvenční a paralelní složitosti(ceny), udává tedy zrychlení na jeden procesor
• Paralelní režie – je rozdílem paralelní ceny a času nejrychlejšího známého sekvenčního algoritmu

Aplikace jsou často klasifikovány podle toho, jak často jejich dílčí úkoly potřebují synchronizovat nebo komunikovat vzájemně mezi sebou. Aplikace se řadí mezi jemnozrnný paralelismus, pokud dílčí úkoly spolu komunikují mnohokrát za sekundu; pokud se jedná o hrubozrnný paralelismus, nepotřebují spolu komunikovat mnohokrát za sekundu, a pokud se jedná o jednoduchý paralelismus pak spolu komunikují vzácně nebo vůbec. Jednoduché paralelní aplikace jsou považovány za nejjednodušší k paralelizaci.

Z hlediska stavby je možné rozdělit paralelní počítače na:

• multipočítače (volně vázané, s distribuovanou pamětí) – počítače zapojené do sítě, které si předávají zprávy po sériové síti; velkým zapojením tohoto typu se říká cluster
• multiprocesory (těsně vázané, se sdílenou pamětí) – obsahují několik procesorů připojených k jedné paměti

Flynnova klasifikace je zřejmě nejznámější klasifikací paralelních systémů, vznikla v roce 1966. Systémy jsou klasifikovány podle dvou hledisek - toku instrukcí a toku dat. Klasifikace obsahuje 4 hlavní typy paralelních systémů a další 2 rozšiřující typy.

SISD (s jedním tokem instrukcí, s jedním tokem dat): Počítač zpracovává data sériově podle jednoho programu. Takto pracuje například počítač von Neumannova typu.

SIMD (s jedním tokem instrukcí, s vícenásobným tokem dat): Počítač používající více stejných procesorů, které jsou řízeny společným programem. Zpracovávaná data jsou různá, takže každý procesor pracuje s jinou hodnotu, ale všechny procesory současně provádějí stejnou instrukci.

MISD (s vícenásobným tokem instrukcí, s jedním tokem dat): Tento typ se v praxi prakticky nepoužívá. Vznikl spíše pro doplnění jednotlivých kategorií.

MIMD (s vícenásobným tokem instrukcí, s vícenásobným tokem dat): Víceprocesorový systém, v němž je každý procesor řízen vlastním programem a pracuje na vlastních datech.

MSIMD (vícenásobné SIMD): V tomto systému pracuje několik podsystémů SIMD nezávisle na sobě. Jednotlivé podsystémy zpracovávají jiný program, proto musí být řízeny stejně jako systém MIMD.

SPMD (stejný program, s vícenásobným tokem dat): Všechny procesory vykonávají stejný program, ale jsou na sobě nezávislé (nejsou synchronizovány). Jednotlivé procesory musí mít svůj řadič, který řídí rychlost přísunu instrukcí a jejich provádění.

• Paralelní programování
• Meziprocesová komunikace – hraje v paralelním programování velkou roli
• Symetrický multiprocesing (SMP)
• Non-Uniform Memory Access (NUMA)
• Paralelismus

• Obrázky, zvuky či videa k tématu paralelní výpočty na Wikimedia Commons