1 IB109 Návrh a implementace paralelních systémů Principy návrhu paralelních algoritmů Jiří Barnat Více-práce programátora paralelních aplikací • Identifikovat souběžně proveditelné činnosti a jejich závislosti. • Mapovat souběžně proveditelné části práce do procesů. 9 Zajistit distribuci vstupních, vnitřních a výstupních dat. 9 Spravovat souběžný přístup k datům a sdíleným prostředkům. <* Synchronizovat jednotlivé procesy v různých stádiích výpočtu tak, jak vyžaduje paralelní algoritmus. • Mít znalost přídavných programátorských prostředků související s vývojem paralelních algoritmů. IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 2/39 Základy návrhu paralelních algoritmu IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 3/39 Návrh a realizace paralelního systému Problém Dekompozice Úlohy Mapování Procesy Vlákna Implementace Aplikace IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 4/39 De zice a Dekompozice • Proces rozdělení celé výpočetní úlohy na podúlohy. • Některé podúlohy mohou být prováděny paralelně. (Pod)úlohy • Jednotky výpočtu získané dekompozicí. o Po vyčlenění se považují za dále nedělitelné. • Mají uniformní/neuniformní velikost. • Jsou definované v době kompilace / za běhu programu Příklad • Násobení matice A (r? x n) vektorem B • C[í\ = Tj=1A[i,j\.B[j\ IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 5/39 Graf závislostí 9 Zachycuje závislosti prováděných úloh. • Definuje relativní pořadí provádění úloh (částečné uspořádání). Vlastnosti a využití grafu • Orientovaný acyklický graf. • Graf může být nespojitý, či dokonce prázdný. • Úloha je připravena ke spuštění, pokud úlohy, na kterých závisí, dokončily svůj výpočet (topologické uspořádání). Příklady závislostí 9 Pořadí oblékání svršků. • Paralelní vyhodnocování výrazů v AND x AND (y OR z) IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 6/39 Granularita a Stupeň souběžnosti Granularita 9 Počet úloh, na které se problém dekomponuje. • Mnoho malých úloh - jemnozrnná granularita (fine-grained). • Málo větších úloh - hrubozrnná granularita (coarse-grained). • Každý problém má vnitřní hranici granularity. Stupeň souběžnosti 9 Maximální počet úloh, které mohou být prováděny souběžně. • Limitem je vnitřní hranice granularity. IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 7/39 Průměrný stupeň souběžnosti Průměrný stupeň souběžnosti • Závislý na grafu závislostí a granularitě. • Mějme množství práce asociované k uzlům grafu. • Kritická cesta - cesta, na které je součet prací maximální. • Průměrný stupeň souběžnosti je podíl celkového množství práce vůči množství práce na kritické cestě. 9 Udává maximální zrychlení, pokud je cílová platforma schopna vykonávat souběžně maximální stupeň souběžnosti úloh. Pozorování • Zjemňování dekompozice může zvýšit stupeň souběžnosti. • Čím méně práce je na kritické cestě, tím větší je potenciál pro paralelizaci. IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 8/39 Interakce úloh - Další omezení paralelizace Interakce úloh • Nezávislé úlohy mohou vzájemně komunikovat. • Obousměrná komunikace může snižovat stupeň souběžnosti (úlohy musí co-existovat ve stejný okamžik). • Komunikace úloh - neorientovaný graf interakcí. • Graf interakcí pokrývá graf závislostí (ověření splnění předpokladů pro spuštění úlohy je forma interakce). Příklad jednosměrné komunikace • Násobení matice vektorem (y = Ab) • Dekompozice na nezávislé úlohy dle řádků matice A. o Prvky vektoru b jsou čteny ze všech úloh, je nutné je vhodně distribuovat k jednotlivým úlohám. IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 9/39 Techniky dekompozice IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 10/39 Techniky dekompozice Dekompozice o Fundamentální technika v návrhu paralelních algoritmů. Obecné dekompozice • Rekurzivní o Datová Specializované dekompozice • Průzkumová • Spekulativní • Hybridní IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 11/39 Rekurzivní dekompozice Vhodné pro problémy typu rozděl a panuj. Princip o Problém se dekomponuje na podúlohy tak, aby jednotlivé úlohy mohly být dekomponovány stejným způsobem jako rodičovská úloha. <* Někdy je třeba restrukturalizovat úlohu. Příklad • Quicksort • Provede se volba pivota. • Rozdělení pole na prvky menší než a větší rovno než. • Rekurzivně se opakuje dokud je množina prvků neprázdná. o Hledání minima v lineárním poli. o Princip půlení prohledávaného pole. • Typický příklad restrukturalizace výpočtu. IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 12/39 Datová dekompozice Základní princip • Data se rozdělí na části (data partitioning). o Úlohy se provádí souběžně nad jednotlivými částmi dat. Datová dekompozice podle místa o Vstupní data • Výstupní data • Vnitřní data o Kombinace Mapování dat na úlohy Funkce identifikující vlákno odpovědné za zpracování dat. Úlohy typu "Embarrassingly parallel" • Triviální datová dekompozice na dostatečný počet zcela nezávislých, vzájemně nekomunikujících úloh. IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 13/39 Průzkumová dekompozice Princip Specializovaná technika paralelizace. • Vhodná pro prohledávací úlohy. • Prohledávaný prostor se rozdělí podle směru hledání. Vlastnosti • Při znalosti prohledávaného stavového prostoru lze dosáhnout optimálního vyvážení a zatížení procesorů. • Na rozdíl od datové dekompozice, úloha končí jakmile je nalezeno požadované. a Množství provedené práce se liší od sekvenční verze. • V případě, že graf není strom, je třeba řešit problém opakujících se konfigurací (riziko nekonečného výpočtu). Příklad • Řešení hlavolamu "patnáct" IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 14/39 Spekulativní dekompozice Princip Specializovaná technika paralelizace. • Vhodná pro úlohy se sekvencí datově závislých podúloh. o Úloha, která čeká na výstup předchozí úlohy, se spustí nad všemi možnými vstupy (výstupy předchozí úlohy). Vlastnosti o Provádí se zbytečná práce. • Nemusí být ve výsledku rychlejší jak serializovaná verze. o Vhodné pro úlohy, kde jistá hodnota mezivýsledku má velkou pravděpodobnost. • Vzniká potenciální problém při přístupu ke zdrojům (některé zdroje nemusí být sdílené v případě sekvenčního vykonávání úloh). Příklady • Spekulativní provádění kódu (větvení). IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 15/39 Hybridní dekompozice Kombinace různých způsobů dekompozice Příklad 9 Hledání minima v poli. • Sekvenční verze najde minimum v O(n). • Při použití datové a rekurzivní dekompozice lze trvání této úlohy zkrátit na 0(n/p + log(p)). 9 Vstupní pole se datově dekomponuje na p stejných částí. • Najdou se minima v jednotlivých částech v čase 0(r?/p). o Výsledky z jednotlivých třídění se zkombinují v čase 0(log(p)). • Teoreticky lze při dostatečném počtu procesorů nalézt minimum v čase 0(log(n)). • Tento styl paralelismu je obecně označován jako MAP-REDUCE. IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 16/39 Techniky mapovaní a vyrovnávaní zátěže IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 17/39 Mapovaní úloh na vlákna/procesy. Mapování • Přiřazování úloh jednotlivým vláknům/procesům. o Optimální mapování bere v potaz grafy závislostí a interakce. 9 Ovlivňuje výkon aplikace. 9 Naivní mapování (úloha=proces/vlákno) Cíle mapování • Minimalizovat celkový čas řešení celé úlohy. • Redukovat prodlevy způsobené čekáním (idling) • Redukovat zátěž způsobenou interakcí o Redukovat režii spouštění, ukončovania přepínání • Vyrovnat zátěž na jednotlivé procesory • Maximalizovat souběžnost. • Minimalizovat zatížení systému (zatížení datových cest). • Využít dostupnost zdrojů použitých předchozí úlohou. IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 18/39 Charakteristiky úloh, které ovlivňují mapovaní Způsob zadání úlohy • Statické zadání úloh - dekompozice problému na úlohy je dána v době kompilace, případně je přímo odvozena od vstupních dat. • Dynamické zadání úloh - nové úlohy jsou vytvářeny za běhu aplikace dle průběhu výpočtu, případně jako důsledek provádění původně zadaných úloh. Velikost úlohy • Relativní množství času potřebné k dokončení úlohy, o Uniformní vs. neuniformní. o Dopředná znalost/neznalost. Velikost dat asociovaných k úloze • Snaha o zachování lokality dat. • Různá data mají různou roli a velikost (vstupní/výstupní data u hlavolamu patnáct). IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 19/39 Charakteristiky interakcí, které ovlivňují mapování Statické vs Dynamické o Statické: Probíhají v předdefinovaném časovém intervalu, mezi předem známou množinou úloh. • Dynamické: Pokud předem neznáme počet interakcí, časový rámec interakcí, nebo participující úlohy. Další charakteristiky • Jednosměrná versus obousměrná interakce. • Mód přístupu k datům: Read-Only versus Read-Write. • Pravidelné versus nahodilé interakce. Režie související s mapováním do různých vláken/procesů • Uzpůsobení aplikace pro neočekávanou interakci. 9 Připravenost dat k odeslání / adresáta k přijetí. 9 Řízení přístupu ke sdíleným zdrojům. Optimalizace aplikace pro redukci prodlev. IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 20/39 Schémata pro Statické Mapování Mapování založené na rozdělení dat • Bloková distribuce • Cyklická a blokově-cyklická distribuce • Náhodná distribuce bloků • Dělení grafu Mapování založené na rozdělení úloh o Dělení dle grafu závislostí úloh o Hierarchické dělení IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 21/39 Mapovaní založené na rozdělení dat Bloková distribuce datových polí Procesy svázány s daty rozdělenými na souvislé bloky. • Bloky mohou být vícerozměrné (redukce interakcí). • Příklad • Násobení matic A x B = C • Dělení matice C na 1- a 2-rozměrné bloky. Cyklická a blokově-cyklická distribuce datových polí o Nerovnoměrné množství práce spojené s jednotlivými prvky o =4> blokové dělení způsobuje nerovnoměrné zatížení. • Blokově-cyklická distribuce: dělení na menší díly a cyklické přiřazení procesům (round robin). 9 Zmenšování bloků vede k cyklické distribuci (blok je atomický prvek datového pole). IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 22/39 Mapovaní založené na rozdělení dat - pokračovaní Náhodná distribuce bloků • Zátěž související s prvky pole vytváří pravidelné vzory. • =4> špatná distribuce v cyklickém rozdělení. • Náhodné přiřazení bloků procesům. Grafové dělení • Pro případy, kdy je nevhodné organizovat data do polí (například drátové modely 3D objektů). • Data organizována jako graf. o Optimální dělení. Stejný počet vrcholů v jednotlivých částech. • Co možná nejmenší počet hran mezi jednotlivými částmi. • NP-úplný problém. IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 23/39 Princip • Graf závislostí úloh. • Grafové dělení (NP-úplné). Speciální případy pro konkrétní tvar grafů Binární strom (rekurzivní dekompozice). Hierarchické mapování • Úlohové dělení nebere v potaz neuniformitu úloh. 9 Shlukování úloh do nad-úloh. 9 Definuje hierarchie (vrstvy). • Jiné mapovací a dekompoziční techniky na jednotlivých vrstvách. IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů Schémata pro Dynamické Mapování Motivace • Statické mapování nedostatečné, neboť charakteristiky úloh nejsou známy v době překladu. Centralizovaná schémata dynamického mapování o Úlohy jsou shromažd ovány v jednom místě. • Dedikovaná úloha pro přiřazování úloh procesům. • Samo-plánování • Jakmile proces dokončí úlohu, vezme si další. • Blokové plánování Přístup ke shromaždišti úloh může být úzkým místem, • přidělování úloh po blocích. Příklad • Třídění prvků v n x n matici A • for (i=l; i P2, P2 -> P3, Ps -> Pa • Pi -> P2, ^2 -> IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 36/39 Redukce ceny komunikace 1/3 Komunikace v nesdíleném adresovém prostoru • Synchronizace posíláním zpráv. • Předávání dat posíláním zpráv. Komunikace ve sdíleném adresovém prostoru Synchronizace korektním přístupem ke sdíleným datům. • Předávání dat pomocí sdílených datových struktur. (FIFO) Obecné charakteristiky • Latence - doba potřebná pro doručení prvního bitu. • Přenosová rychlost - objem dat přenesených za jednotku času. IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 37/39 Redukce ceny komunikace 2/3 Latence • Celková cena pro zahájení komunikace — rs • čas pro přípravu zprávy/dat • identifikace adresáta / routování • doba trvání vylití informace z cache do paměti případně na síťové rozhraní o Cena " hopů" (přeposílání uvnitř komunikační sítě) — th čas strávený na jednotlivých routerech v síti • doba, po kterou putuje hlavička zprávy z přijímacího na odesílací port Přenosová rychlost • Ovlivněno šířkou pásma r • Cena za přenos jednoho slova (word = 2 bajty) — tw = 1/r IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 38/39 Redukce ceny komunikace 3/3 Cena komunikace • m - délka zprávy ve slovech o I - počet linek, přes které zpráva putuje • ts + I * (th + mtw) Obecné metody redukce ceny • Spojování malých zpráv (amortizuje se hodnota rs) • Komprese (snižování hodnoty m) • Minimalizace vzdálenosti (snižování hodnoty /) Paketování (eliminace režie způsobené jednotlivými hopy) ts + I * (ŕ/7 + mtw) —> ts + lth + mtw IB109 Návrh a implementace paralelních systémů: Principy návrhu paralelních algoritmů str. 39/39