Paralelní výpočty

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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] Pro zrychlení výpočtu se používá buď zdánlivý paralelní běh úloh pomocí multitaskingu nebo víceprocesorové systémy[4] nebo počítačové clustery. 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[editovat | editovat zdroj]

Paralelní výpočty mohou být klasifikovány podle úrovní, na kterých podporují paralelismus, s vícejaderný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 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 potencioná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ícejaderných procesorů.

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

Původ[editovat | editovat zdroj]

Tradičně je počítačový software psán pro sériové kalkulace. K vyřešení problému je vytvořen algoritmus a ten je poté implementován jako sériový proud instrukcí. Tyto instrukce 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ímy. 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]

Frekveční rozsah byl dominantní ve vylepšování výkonu počítačů od poloviny roku 1980 do roku 2004. Doba běhu programu je rovna počtu instrukcí znásobených dobou zpracování jedné instrukce. Při zachování stejných hodnot, zvýšením frekvence hodin snížíme čas provádění instrukcí. Zvýšením frekvence tedy zajistíme zrychlení všech programů prováděných počítačem. Nicméně spotřeba energie čipu 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 vteřinu).[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ýroby 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[editovat | editovat zdroj]

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í (označuje se jako kritická sekce), 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ť Pi a Pj 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 Pi, bude Ii značit všechny vstupní proměnné a Oi výstupní proměnné, a také pro Pj. Pj a Pi 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 (Pj) produkuje proměnnou, kterou potřebuje první segment (Pi). 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ředt(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.

Souběh, vzájemné vyloučení, synchronizace a paralelní zpomalení[editovat | editovat zdroj]

Dílčí úlohy jsou v paralelních programech často nazývány vlákna. Některé paralelní počítačové architektury používají menší, odlehčené verze vláken známe jako fibers, zatímco jiní používají termín proces. Nicméně "vlákno" je obecně přijímaný termín pro dílčí úkoly. Vlákno často potřebují aktualizovat proměnné, které jsou sdílené mezi vlákny. Instrukce mezi dvěma programy mohou být prokládány v libovolném pořadí. Zvažte 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 ne-atomický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.

Paralelizace nemusí být rychlejší než sekvenční sled instrukcí. Obecně, jakmile je úloha rozložena na víc a víc vláken, tyto vlákna využijí část svého času na komunikaci s ostatnímy vlákny. Nakonec, čas potřebný pro komunikaci dominuje nad časy potřebným k vyřešení úlohy, další paralelizace (to jest rozložení zátěže mezi další vlákna) zvýší spíše než sníží čas potřebný pro vyřešení úlohy. Toto je známé jako paralelní zpomalení.

Jemnozrný, hrubozrný a jednoduchý paralelismus[editovat | editovat zdroj]

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 jemnozrný paralelismus pokud dílčí úkoly spolu komunikují mnohokrát za sekundu; pokud se jedná o hrubozrný 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čů[editovat | editovat zdroj]

Z hlediska stavby je možné rozdělit paralelního 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ů[editovat | editovat zdroj]

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[editovat | editovat zdroj]

  1. Gottlieb, Allan; Almasi, George S.(1989). Highly parallel computing. Redwood City, Calif.:Benjamin/Cummings. ISBN 0-8053-0177-1. 
  2. S.V. Adve et al. (November 2008). "Parallel Computing Research at Illinois: The UPCRC Agenda" (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".
  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.(1999). Computer organization and design : the hardware/software interface, 2. ed., 3rd print., San Francisco:Kaufmann. ISBN 1-55860-428-6. 
  6. Barney, Blaise. Introduction to Parallel Computing [online]. Lawrence Livermore National Laboratory, [cit. 2007-11-09]. Dostupné online. (anglicky) 
  7. Hennessy, John L.; Patterson, David A.(2002). Computer architecture / a quantitative approach., 3rd, San Francisco, Calif.:International Thomson, 43. ISBN 1-55860-724-2. 
  8. Rabaey, Jan M.(1996). Digital integrated circuits : a design perspective. Upper Saddle River, N.J.:Prentice-Hall, 235. ISBN 0-13-178609-1. 
  9. Flynn, Laurie J.."Intel Halts Development Of 2 New Microprocessors", 8 May 2004. Ověřeno k 5 June 2012. 
  10. MOORE, Gordon E.. Cramming more components onto integrated circuits [PDF]. 1965, [cit. 2006-11-11]. S. 4. Dostupné online. (anglicky) 
  11. Bernstein, A. J.(1 October 1966).  "Analysis of Programs for Parallel Processing". IEEE Transactions on Electronic Computers EC-15 (5): 757–763. doi:10.1109/PGEC.1966.264565. 
  12. Roosta, Seyed H.(2000). Parallel processing and parallel algorithms : theory and computation. New York, NY [u.a.]:Springer, 114. ISBN 0-387-98716-9. 

Související články[editovat | editovat zdroj]