1. Úvod do paralelizace

1. PRAM Model a Ošetření Konfliktů Při Přístupu do Sdílené Paměti¶

PRAM (Parallel Random Access Machine) je výpočetní model, který se používá k analýze paralelních algoritmů. V tomto modelu každý proces má soukromou paměť a zná svůj index. Navíc existuje externí sdílená paměť, ke které mají přístup všechny procesy.

Procesy mají přístup ke sdílené paměti v $O(1)$ čase
Procesy jsou synchronizované externími hodinami.
Všechny procesy vykonávají synchronně v každém taktu hodin jednu z nasledujicich instrukci.
1. Čtení buňky sdílené paměti (READ, zkráceně R).
2. Lokální operace (LOCAL, zkráceně L).
3. Zápis do buňky sdílené paměti (WRITE, zkráceně W).
Každá operace trvá $O(1)$ čas
Algoritmy lze zapsat regulárními výrazy, např. $<RLW>^k$
Důležité je řešení konfliktů při přístupu do sdílené paměti.

Přístupu do Sdílené Paměti¶

EREW: Exclusive Read Exclusive Write - Procesory nemohou současně číst ani zapisovat do stejné paměťové buňky.
CREW: Concurrent Read Exclusive Write - Procesory mohou současně číst ze stejné paměťové buňky, ale nemohou současně zapisovat.
CRCW: Concurrent Read Concurrent Write - Procesory mohou současně číst i zapisovat do stejné paměťové buňky

Řešení konfliktů¶

Konflikty nastávají, když více procesorů současně přistupuje k jedné paměťové buňce a chtějí současně zapisovat.
Řešení pro CRCW model:
- Priority CRCW: Každému procesoru je přidělena priorita, procesor s vyšší prioritou má přednost.
- Arbitrary CRCW: Libovolný procesor může zapsat hodnotu.
- Common CRCW: Všichni procesory musí zapisovat stejnou hodnotu.

2. APRAM Model a Implementace Synchronizační Bariéry¶

APRAM (Asynchronous PRAM) je varianta PRAM modelu, kde operace procesorů nemusí trvat stejně dlouho a procesory pracují asynchronně.

Neexistují centrální hodiny.
Synchronizace je řešena pomocí bariér, které oddělují globální fáze od sebe.
Dva procesory nemohou přistupovat do téže buňky sdílené paměti v téže globální fázi, pokud jeden z nich do ní zapisuje.

Operace	Čas
Lokální operace	$1$
Globální READ nebo WRITE	$d$
$K$ po sobě jdoucích globálních READ nebo WRITE	$d + k - 1$
Bariérová synchronizace	$B(p)$

Synchronizační bariéra¶

Je to mechanismus, který umožňuje více procesorům čekat, dokud všechny nedosáhnou určitého bodu, než budou pokračovat dále.
Využívá se např. pro synchronizaci po dokončení určité fáze výpočtu.

Implementace bariéry¶

Centrální čítač¶

$B(p)=\Theta(dp)$
Existuje sdílený čítač a každý procesor, který dosáhne bariéry, inkrementuje tento čítač.
Je-li čítač $< p$ , proces se deaktivuje
Je-li čítač $= p$ nastaví bariéru do odchozí fáze a aktivuji ostatní procesy.
Poslední aktivovaný proces nastaví bariéru do příchozí fáze.

Binární redukční strom¶

$B(p)=\Theta(d \cdot log(p)))$
Procesory jsou uspořádány do binárního stromu.
Process dorazí k bariéře a zkontroluje, zda je v příchozí fázi.
Čeká, až skončí redukce v jeho podstromu.
Po jejím skončení pošle signál rodiči.
Kořen stromu počká na redukci z obou podstromů a přepne do odchozí fáze.
Procesy se aktivují ve zpětném pořadí.

3. Paralelní Čas, Zrychlení, Cena, Efektivnost a Paralelní Optimalita Výkonnosti¶

Optimalni algoritmus¶

Měřítka složitosti sekvenčních algoritmů:

$T_A^K(n)$ : časová složitost/doba výpočtu sekvenčního algoritmu $A$ , který řeší problém $K$ na vstupních datech velikosti $n$ .
$SL^K(n)$ : spodní mez sekvenční časové složitosti řešení problému $K$ (= nejhorší časová složitost nejlepšího možného sekvenčního algoritmu pro řešení $K$ ).
Triviální spodní mez je dána velikostí množiny vstupních (výstupních) dat $n$ .
$SU^K(n)$ : horní mez časové složitosti pro řešení problému $K$ (= nejhorší časová složitost nejrychlejšího existujícího sekvenčního algoritmu pro $K$ ).

Rust funkce¶

$O$ -notace popisuje horní hranici růstu funkce.
$\Omega$ -notace popisuje dolní hranici růstu funkce.
$\Theta$ -notace popisuje přesný řád růstu funkce.

Algoritmus $A$ je (asymptoticky) optimální sekvenční algoritmus pro řešení problému $K$ právě tehdy, když platí:

$T_A(n) = \Theta(SU^K(n)) = \Theta(SL^K(n))$

Paralelní Čas $T(n, p)$ ¶

Paralelní čas, označovaný $T(n, p)$ , je čas od začátku paralelního výpočtu do chvíle, kdy poslední procesor skončí výpočet.
Závisí na architektuře paralelního počítače ⇒ hodnocení výkonnosti paralelního algoritmu musí vždy brát v úvahu architekturu počítače.
Měření časového trvání závisí na:
- Výpočetní kroky: aritmetické, logické a paměťové operace.
- Komunikační kroky: přenos a výměna dat mezi procesory.
Závisí na velikosti problému $n$ a počtu vláken výpočtu $p$ .

Paralelní Zrychlení $S(n, p)$ ¶

Paralelní zrychlení, označované jako $S(n, p)$ , je definované jako poměr sekvenčního času k paralelnímu času.

$S(n, p) = \frac{T_s(n)}{T(n, p)}$

Lineární Zrychlení: Pokud $S(n, p) = \Theta(p)$ , to znamená, že při běhu na p vláknech je čas p krát menší. To je v reálu často obtížně dosažitelné.
Superlineární Zrychlení: Pokud $S(n, p) > p$ , může nastat v situaci, kdy například sekvenční algoritmus má velkou paměťovou složitost.

Paralelní Cena $C(n, p)$ ¶

Paralelní cena, označovaná jako $C(n, p)$ , je definována jako součin paralelního času a počtu procesorů.

$C(n, p) = p \cdot T(n, p) = \Omega (SU(n))$

Paralelní Efektivnost $E(n, p)$ ¶

Paralelní efektivnost, označovaná jako $E(n, p)$ , je definovaná jako poměr sekvenčního času k paralelní ceně.

$E(n, p) = \frac{SU(n)}{C(n, p)} \le 1$

Optimální efektivnost je 1, ale kvůli komunikační a synchronizační režii bývá často menší než 100%.

Paralelní Optimalita¶

Paralelní algoritmus je optimální, pokud splňuje jednu z následujících podmínek:

Je cenově optimální: $C(n,p)=\Theta(SU(n))$
Má lineární zrychlení: $S(n,p)=\Theta(p)$
Má konstantní efektivnost: $E(n,p) = \Omega(1)$

4. Amdahlův zákon, Gustafsonův zákon a izoefektivní funkce¶

Amdahlův Zákon¶

Amdahlův zákon stanovuje teoretické maximum možného zrychlení, které lze dosáhnout paralelizací daného algoritmu. Podle Amdahlůva zákona každý sekvenční algoritmus A se skládá z:

Inherentně sekvenčního podílu $f_s$ , který může provést jen $1$ vlákno $(0 < f_s < 1)$ .
Paralelizovatelného podílu $1 – f_s$ .

Pokud provedeme paralelizaci algoritmu $A$ pro pevné $n$ pomocí $p > 1$ vláken, pak ideálně platí:

$S(p) = \frac{T_A(n)}{f_s \cdot T_A(n) + \frac{1-f_s}{p} \cdot T_A(n)} = \frac{1}{f_s + \frac{1 - f_s}{p}} \le \frac{1}{f_s}$

Toto zrychlení má limitu, kterou lze vyjádřit jako $1/f_s$ . To znamená, že nezávisle na počtu spuštěných vláken nemůže zrychlení přesáhnout $1/f_s$ .

Gustafsonův Zákon¶

Na rozdíl od Amdahlůva zákona, Gustafsonův zákon předpokládá, že s rostoucím počtem procesorů $p$ máme úměrně navyšovat i velikost problému $n$ .

Inherentně sekvenční část trvá vždy konstantní čas $t_{seq}$ nezávisle na $p$ (vstup, výstup).
Inherentně paralelní část $t_{par}$ lineárně škáluje s $p$ v čase.

Gustafsonův zákon je formulován jako:

$S(p) = \frac{t_{seq}+t_{par}(n,1)}{t_{seq}+t_{par}(n,p)}$

Předpokládáme, že paralelní část je perfektně paralelizovatelná. Pak:

$t_{\text{par}}(n, 1) = SU(n) - t_{\text{seq}} \ \ \ \text{a}\ \ \ t_{\text{par}}(n, p) = \frac{SU(n) - t_{\text{seq}}}{p}$

Potom

$S(n, p) = \frac{t_{\text{seq}} + SU(n) - t_{\text{seq}}}{t_{\text{seq}} + \frac{SU(n) - t_{\text{seq}}}{p}} = \frac{ \frac{t_{\text{seq}}}{SU(n) - t_{\text{seq}}} + 1 } { \frac{t_{\text{seq}}}{SU(n) - t_{\text{seq}}} + \frac{1}{p} }$

Tedy

$\lim_{n \to \infty} S(n, p) = p$

pro jakoukoli monotonně rostoucí funkci $SU(n)$ (např. lineární, polynomiální).

Silná a slabá škálovatelnost¶

Silná škálovatelnost: Systém je považován za silně škálovatelný, pokud dokáže udržet konstantní čas výpočtu při zvyšování počtu procesorů pro pevnou velikost problému. (Amdahlův zákon zde dává přísná omezení.)
Slabá škálovatelnost: Systém je považován za slabě škálovatelný, pokud dokáže udržet konstantní čas výpočtu při zvyšování počtu procesorů a proporcionální zvětšování velikosti problému.

Izoefektivní Funkce¶

Izoefektivní funkce se týká udržení konstantní efektivnosti při škálování paralelního systému.

Pro každé $n$ existuje funkce $\psi_1(p)$ taková, že $E(n, p) \geq E_0$ pro $n \geq \psi_1(p)$ .
- Toto je dolní mez velikosti problému v závislosti na počtu procesorů za účelem udržení konstantní efektivnosti.
Pro každé $p$ existuje funkce $\psi_2(n)$ taková, že $E(n, p) \geq E_0$ pro $p \leq \psi_2(n)$ .
- Toto je horní mez počtu procesorů v závislosti na velikosti problému za účelem udržení konstantní efektivnosti.

Souhrn¶

Amdahlův zákon poukazuje na omezení, která paralelizace přináší kvůli sekvenčním částem algoritmu.
Gustafsonův zákon nabízí optimističtější pohled na paralelizaci tím, že předpokládá, že velikost problému roste s počtem procesorů.
Izoefektivní funkce jsou užitečné pro analýzu, jak se efektivnost mění v závislosti na velikosti problému a počtu procesorů.