3. Úvod do paralelních algoritmů

9. Paralelní algoritmy pro prohledávání stavového prostoru, anomálie prohledávání, statické rozdělení prostoru a dynamické vyvažování zátěže.

Paralelní algoritmy pro prohledávání stavového prostoru

Paralelní Prohledávání kombinatorického stavového prostoru (PKSP) je technika, která využívá více procesorů nebo vláken k efektivnímu prohledávání stavového prostoru.

Charakterizace problemu PKSP

Problém PKSP (Prohledávání kombinatorického stavového prostoru) může být charakterizován následujícím způsobem:

• Množina vstupních proměnných: Reprezentuje počáteční stav systému.

• Množina stavových (konfiguračních) proměnných: Reprezentuje mezistavy, kterými systém prochází.

• Množina výstupních proměnných: Reprezentuje koncový stav systému po dokončení procesů.

• Podmínky/Omezení: Definují pravidla a omezení, která musí splňovat přípustné stavy.

• Optimalizační kritérium: Určuje metriku, podle které je hodnoceno, jaké řešení je nejlepší (obvykle cenová funkce).

Podmínka úspěšného paralelního PKSP

• Jádra by měla být stále vytížena
• Prohledáváním by melo byt přes disjunktní části stavového prostoru

Klasifikace PKSP

Existují 3 typy PKSP:

• Rozhodovací: Odpovídá na otázku, zda existuje přípustný koncový stav.
• Konstruktivní: Cílem je nalézt alespoň jeden přípustný koncový stav, popřípadě ten nejlepší.
• Enumerační: Zahrnuje hledání všech přípustných koncových stavů, popřípadě všech nejlepších.

Kriteria pro paralelní prohledávaní

1. Kritéria pro návrat a ukončení DFS/BFS.
2. Úplnost prohledávání stavového prostoru.
3. Omezenost hloubky prohledávaného prostoru.
4. Struktura zásobníku.

Příklady paralelních algoritmů pro prohledávání stavového prostoru:

1. Paralelní DFS: Master-Slave DFS

1. Master ($M$) vygeneruje dostatečně velkou množinu podprostorů pro Slave vlákna ($S$) pomocí standardního sekvenčního prohledávání do šířky (BFS). Množina má velikost $zp$, kde $z \ge 3$ je empirická konstanta závislá na typu a velikosti problému PKSP. Každý podprostor (což je podproblém PKSP) je definován lokálním přednastaveným zásobníkem.

2. Master ($M$) pošle každému Slave vláknu ($S$) jeden podprostor z množiny.

3. Slave ($S$), po přijmutí svého podprostoru, provede sekvenční prohledávání do hloubky (DFS) tak, že se nikdy nevrací za počáteční stav svého zásobníku.

4. Jakmile Slave ($S$) neúspěšně ukončí své lokální PKSP, požádá Master ($M$) o další podprostor (lokální zásobník).

5. Pokud Master ($M$) má stále nepřidělené podprostory, přidělí jeden Slave vláknu ($S$), které pak začne další lokální PKSP. V opačném případě Master ($M$) odpoví negativně a požádá Slave ($S$) o ukončení aktivity.

6. V případě FSB-DFS:

   • Pokud Slave ($S$) nalezne řešení, informuje Master ($M$). Následně Master ($M$) oznámí všem Slave vláknům ($S$) ukončení výpočtu.
   • Toto globální ukončení výpočtu musí proběhnout korektně i v situaci, kdy je řešení nalezeno několika Slave vlákny ($S$) současně.

2. Paralelní Breadth-First Search (BFS)

V paralelním BFS je každá úroveň stromu stavů prohledávána paralelně více vlákny. Vlákna mohou sdílet frontu uzlů, které mají být prozkoumány. Je důležité řídit synchronizaci přístupu k sdílené frontě.

3. DFS s postupným prohlubováním (Iterative Deepening DFS)

Tento algoritmus opakuje prohledávání do hloubky s postupně se zvyšující maximální hloubkou. Je to kombinace DFS a BFS. V paralelní verzi mohou být různé instance DFS spuštěny na různých vláknech s různými limitními hloubkami.

4. Branch & Bound DFS

Branch & Bound DFS je varianta DFS, která používá ořezávání větví k redukci prohledávaného prostoru. Algoritmus odhaduje dolní meze na nejlepší možné řešení a ořezává větve stromu, které nemohou vést k lepšímu řešení. V paralelní verzi může být náročné udržovat globální informace o odhadech a provádět ořezávání efektivně.

Anomálie prohledávání

Anomálie prohledávání se mohou vyskytovat, když paralelní prohledávání nevede k očekávaným výsledkům nebo výkonnosti. Například:

• Duplicitní práce: Když více procesorů prohledává stejné oblasti stavového prostoru.
• Komunikační režie: Nadměrná komunikace mezi procesory může snižovat výkonnost.
• Anomálie statického prohledávání: Mohou nastat, když statické rozdělení stavového prostoru vede k nevyvážené distribuci práce. Tedy 1 vlákno dostane malý podstrom, zatímco jiné vlákno velký podstrom.

Statické rozdělení stavového prostoru

• Hlavní (master) vlákno $τ_0$ provádí sekvenční BFS pro vygenerování $p$ odlišných stavových podprostorů s přibližně stejným počtem nastavených stavových proměnných.
• Prohledávání těchto stavových podprostorů je přiděleno jednotlivým vláknům $τ_i , i = 0, . . . , p − 1$.
• Každé vlákno (je tedy zapojeno i hlavní vlákno $τ_0$) provede sekvenční DFS přiděleného podprostoru pomocí lokálního zásobníku.

• Výsledky svých lokálních PKSP předají vlákna zpět hlavnímu vláknu $τ_0$, které zkonstruuje globální řešení.

• Výhody: Menší režie komunikace mezi procesory.

• Nevýhody: Neefektivní využití procesorů, pokud některé části vyžadují více času na prohledání než jiné.

Dynamické rozdělení stavového prostoru a vyvažování zátěže

• Na počátku vlákno $τ_0$ provede vygenerování p podprostorů a přiřadí je vláknům.
• Každé vlákno $τ_i$ provádí DFS svého podprostoru pomocí lokálního zásobníku (= je aktivní).
• Když aktivní $τ_i$ vyprázdní svůj zásobník a řešení stále není nalezeno, stane se sice nečinným, ale iniciativně žádá jiná vlákna o přidělení neprozkoumaných částí jejich stavových podprostorů.

• Označme vlákno $τ_j$ jako dárce a vlákno $τ_i$ jako příjemce.

• Výhody: Lepší využití procesorů, adaptace na nejednotnou náročnost úloh.

• Nevýhody: Vyšší režie komunikace.

10. Klasifikace paralelizovatelných OpenMP programů a zdroje jejich neefektivity, falešné sdílení a jeho eliminace

Klasifikace paralelizovatelných programů:

Výpočetně intenzivní algoritmy:

V těchto algoritmech je čas trávený výpočtem nad daty větší než čas potřebný pro přesun dat.

• Typické příklady: NP-těžké úlohy, faktorizace matic, násobení matic.
• Tato kategorie algoritmů má tendenci dobře škálovat a paralelizovat, protože výpočetní náročnost je vysoká ve srovnání s datovou komunikací.

Paměťově intenzivní algoritmy:

V těchto algoritmech je čas strávený výpočtem menší než čas potřebný na přesun dat.

• Typické příklady: skalární součin, dynamické programování, Fourierovy transformace.
• Výkonnost těchto algoritmů není omezena výpočetní kapacitou, ale rychlostí paměti.

Optimalizace sekvenčních kódů:

• Cílem je maximalizovat počet výpočetních operací na jeden načtený byte a efektivně využívat cache.
• Důležité je načítání celých bloků cache a vyhýbání se nepřímé adresaci.

Zdroje neefektivity OpenMP programů:

• Nevyvážená výpočetní zátěž: Kvůli bariéře se čeká na nejpomalejší vlákno.
• Příliš těsná synchronizace: Použití mnoha bariér a kritických sekcí vede k vysokému času strávenému synchronizací.
• Omezený paralelismus: Méně iterací nebo úloh než je počet vláken.
• Vysoká režie správy vláken: Vysoký počet malých úloh vede k větší režii správy vláken.
• Velká sekvenční část: Omezení dle Amdahlova zákona.
• Neefektivní práce s cache: Časté zápisy do sdílených proměnných a falešné sdílení mohou způsobit neefektivitu.

Nepřímá indexace

Nepřímá indexace je technika přístupu k prvkům pole, kde index použitý k přístupu k prvkům není pevně stanoven, ale je odvozen z hodnot dalších dat. To znamená, že místo sekvenčního procházení pole (tj. přístup k prvkům s indexy 0, 1, 2, ...) může být pořadí, v jakém jsou prvky navštíveny, dynamické a závislé na vstupních datech.

Nepřímá indexace může být problematická při paralelizaci výpočtů z následujících důvodů:

1. Race Conditions (Souběžný přístup): Pokud více vláken současně upravuje hodnotu na stejném indexu pole, může dojít k souběžnému přístupu, což může vést k nesprávným výsledkům. Je nutné zajistit, aby byly operace prováděny atomicky nebo použít zámky, což může mít negativní vliv na výkon.

2. False Sharing: Když různá vlákna pracují s daty, která jsou blízko sebe v paměti, mohou negativně ovlivnit výkonnost cache. To je proto, že když jedno vlákno upravuje data v paměťovém bloku, může to způsobit, že cache tohoto bloku bude neplatná pro ostatní vlákna, což vede k zbytečným přečtením dat z hlavní paměti.

3. Nepředvídatelnost přístupu k paměti: Protože nepřímá indexace vede k dynamickému a nepředvídatelnému přístupu k paměti, optimalizace cache mohou být méně efektivní. Sekvenční přístup k paměti je obvykle rychlejší, protože moderní počítače mají optimalizace pro přednačítání sekvenčních dat do cache.

Falešné sdílení:

• Falešné sdílení nastává, když procesory sdílejí jen cache a mohou si ji navzájem zneplatňovat.
• Toto je běžné u datového paralelismu a vede k výpadku cache a zpomalení výpočtu.
• Typický případ: více vláken zapisuje do jednoho pole, které je v jednom bloku cache.

Eliminace falešného sdílení:

• Podmínka zarovnání: Rozdělení problému tak, aby každý procesor pracoval s celými bloky cache paměti.
• Dummy data: Alternativně, umělé nafouknutí řešených dat podle velikosti bloku cache (zvětšuje paměťovou náročnost, a proto je lepší tuto možnost nepoužívat).