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.

Charakteristika

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.

Původ

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 V² 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.

Závislost dat

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:

$I_{j}\cap O_{i}=\varnothing ,\,$
$I_{i}\cap O_{j}=\varnothing ,\,$
$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.

Problematika paralelních výpočtů

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.

Souběh

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:

Vlákno A	Vlákno B
1A: Čti proměnnou V	1B: Čti proměnnou V
2A: Přičti 1 k proměnné V	2B: Přičti 1 k proměnné V
3A: Zapiš zpět do proměnné V	3B: Zapiš zpět do proměnné V

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ě:

Vlákno A	Vlákno B
1A: Zamkni proměnnou V	1B: Zamkni proměnnou V
2A: Čti proměnnou V	2B: Čti proměnnou V
3A: Přičti 1 k proměnné V	3B: Přičti 1 k proměnné V
4A: Zapiš zpět do proměnné V	4B: Zapiš zpět do proměnné V
5A: Otevři proměnnou V	5B: Otevři proměnnou V

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í.

Synchronizace

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.

Paralelní zpomalení

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]

Parametry hodnocení paralelních algoritmů

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

Jemnozrnný, hrubozrnný a jednoduchý paralelismus

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.

Druhy paralelních počítačů

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 paralelních systémů

**Flynnova taxonomie**
	Single Instruction	Multiple Instruction
Single Data	SISD	MISD
Multiple Data	SIMD	MIMD

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í.

Reference

↑ GOTTLIEB, Allan, Almasi, George S. Highly parallel computing. Redwood City, Calif.: Benjamin/Cummings, 1989. Dostupné online. ISBN 0-8053-0177-1.
↑ S.V. Adve et al. (November 2008). "Parallel Computing Research at Illinois: The UPCRC Agenda" Archivováno 9. 12. 2008 na Wayback Machine. (PDF). Parallel@Illinois, University of Illinois at Urbana-Champaign. "The main techniques for these performance benefits – increased clock frequency and smarter but increasingly complex architectures – are now hitting the so-called power wall. The computer industry has accepted that future performance increases must largely come from increasing the number of processors (or cores) on a die, rather than making a single core go faster."
↑ Asanovic et al. Old [conventional wisdom]: Power is free, but transistors are expensive. New [conventional wisdom] is [that] power is expensive, but transistors are "free".
↑ Asanovic, Krste et al. (December 18, 2006). "The Landscape of Parallel Computing Research: A View from Berkeley" (PDF). University of California, Berkeley. Technical Report No. UCB/EECS-2006-183. "Old [conventional wisdom]: Increasing clock frequency is the primary method of improving processor performance. New [conventional wisdom]: Increasing parallelism is the primary method of improving processor performance ... Even representatives from Intel, a company generally associated with the 'higher clock-speed is better' position, warned that traditional approaches to maximizing performance through maximizing clock speed have been pushed to their limit."
↑ HENNESSY, John L., Patterson, David A., Larus, James R. Computer organization and design : the hardware/software interface. 2. ed., 3rd print.. vyd. San Francisco: Kaufmann, 1999. Dostupné online. ISBN 1-55860-428-6.
↑ Barney, Blaise. Introduction to Parallel Computing [online]. Lawrence Livermore National Laboratory [cit. 2007-11-09]. Dostupné v archivu pořízeném dne 2013-06-29.
↑ HENNESSY, John L., Patterson, David A. Computer architecture / a quantitative approach.. 3rd. vyd. San Francisco, Calif.: International Thomson, 2002. ISBN 1-55860-724-2. S. 43.
↑ RABAEY, Jan M. Digital integrated circuits : a design perspective. Upper Saddle River, N.J.: Prentice-Hall, 1996. ISBN 0-13-178609-1. S. 235.
↑ FLYNN, Laurie J. Intel Halts Development Of 2 New Microprocessors. New York Times. 8 May 2004. Dostupné online [cit. 5 June 2012].
↑ MOORE, Gordon E. Electronics Magazine [PDF]. [cit. 2006-11-11]. S. 4. Dostupné v archivu pořízeném dne 2008-02-18.
↑ BERNSTEIN, A. J. Analysis of Programs for Parallel Processing. IEEE Transactions on Electronic Computers. 1 October 1966, s. 757–763. DOI 10.1109/PGEC.1966.264565.
↑ ROOSTA, Seyed H. Parallel processing and parallel algorithms : theory and computation. New York, NY [u.a.]: Springer, 2000. ISBN 0-387-98716-9. S. 114.
↑ KUKANOV, Alexey. Why a simple test can get parallel slowdown. Intel blog [online]. 2008-03-04 [cit. 2017-02-15]. Dostupné online.
↑ TVRDÍK, Pavel. Paralelní systémy a algoritmy. Praha: ČVUT v Praze Fakulta elektrotechnická, 2006. ISBN 8001035654. S. 4–7.

Související články

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

Externí odkazy

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

[1] GOTTLIEB, Allan, Almasi, George S. Highly parallel computing. Redwood City, Calif.: Benjamin/Cummings, 1989. Dostupné online. ISBN 0-8053-0177-1.

[2] S.V. Adve et al. (November 2008). "Parallel Computing Research at Illinois: The UPCRC Agenda" Archivováno 9. 12. 2008 na Wayback Machine. (PDF). Parallel@Illinois, University of Illinois at Urbana-Champaign. "The main techniques for these performance benefits – increased clock frequency and smarter but increasingly complex architectures – are now hitting the so-called power wall. The computer industry has accepted that future performance increases must largely come from increasing the number of processors (or cores) on a die, rather than making a single core go faster."

[3] Asanovic et al. Old [conventional wisdom]: Power is free, but transistors are expensive. New [conventional wisdom] is [that] power is expensive, but transistors are "free".

[View-Power-4] Asanovic, Krste et al. (December 18, 2006). "The Landscape of Parallel Computing Research: A View from Berkeley" (PDF). University of California, Berkeley. Technical Report No. UCB/EECS-2006-183. "Old [conventional wisdom]: Increasing clock frequency is the primary method of improving processor performance. New [conventional wisdom]: Increasing parallelism is the primary method of improving processor performance ... Even representatives from Intel, a company generally associated with the 'higher clock-speed is better' position, warned that traditional approaches to maximizing performance through maximizing clock speed have been pushed to their limit."

[5] HENNESSY, John L., Patterson, David A., Larus, James R. Computer organization and design : the hardware/software interface. 2. ed., 3rd print.. vyd. San Francisco: Kaufmann, 1999. Dostupné online. ISBN 1-55860-428-6.

[llnltut-6] Barney, Blaise. Introduction to Parallel Computing [online]. Lawrence Livermore National Laboratory [cit. 2007-11-09]. Dostupné v archivu pořízeném dne 2013-06-29.

[7] HENNESSY, John L., Patterson, David A. Computer architecture / a quantitative approach.. 3rd. vyd. San Francisco, Calif.: International Thomson, 2002. ISBN 1-55860-724-2. S. 43.

[8] RABAEY, Jan M. Digital integrated circuits : a design perspective. Upper Saddle River, N.J.: Prentice-Hall, 1996. ISBN 0-13-178609-1. S. 235.

[9] FLYNN, Laurie J. Intel Halts Development Of 2 New Microprocessors. New York Times. 8 May 2004. Dostupné online [cit. 5 June 2012].

[Moore1965paper-10] MOORE, Gordon E. Electronics Magazine [PDF]. [cit. 2006-11-11]. S. 4. Dostupné v archivu pořízeném dne 2008-02-18.

[11] BERNSTEIN, A. J. Analysis of Programs for Parallel Processing. IEEE Transactions on Electronic Computers. 1 October 1966, s. 757–763. DOI 10.1109/PGEC.1966.264565.

[12] ROOSTA, Seyed H. Parallel processing and parallel algorithms : theory and computation. New York, NY [u.a.]: Springer, 2000. ISBN 0-387-98716-9. S. 114.

[13] KUKANOV, Alexey. Why a simple test can get parallel slowdown. Intel blog [online]. 2008-03-04 [cit. 2017-02-15]. Dostupné online.

[14] TVRDÍK, Pavel. Paralelní systémy a algoritmy. Praha: ČVUT v Praze Fakulta elektrotechnická, 2006. ISBN 8001035654. S. 4–7.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]