Motivace: sekvenční procesory dnes naráží na fyzikální hranice.

V 90. letech vícejádrové procesory, rozhraní a jazyky se "zabudovaným" paralelismem: CUDA, OpenCL.

Model RAM

Výpočetní model RAM by měl znamenat Random Access Machine. Popíšeme trochu neformálně:

• Páska programu s buňkami 0, 1, 2 ...

• Páska paměti s buňkami 0, 1, 2 ...

• buňky paměti mohou obsahovat libovolně dlouhá celá čísla

• Programový čítač (PC) - obsahuje číslo aktuální instrukce

• Instrukce: přiřazení konstanty, binární operace, nepřímá adresace (pointery), halt, goto X if buňka != 0

Lze definovat formálně, i s méně instrukcemi. Pak ukázat ekvivalenci s Turingovými stroji.

Model PRAM

• Posloupnost RAM strojů. Každý má své unikátní PID číslo, které "ví" (lze modelovat pomoci instrukce r = moje_PID).

• Navíc globální paměť. Na ní je vstup a na konci i výstup celého systému.

• Stroje mají navíc totožné instrukce i pro globální paměť.

Omezení systému

Omezení nezavádíme dobrovolně, často odpovídají hardwarovým možnostem.

Omezení při čtení z globální paměti:

• ER - Exclusive Read - jen jeden stroj může číst v jednom kroku danou buňku

• CR - Concurrent Read - více strojů může číst v jednom kroku danou buňku

Omezení při zápisu do globální paměti:

• EW - Exclusive Write - jen jeden stroj může psát v jednom kroku do dané buňky

• CW - Concurrent Write - více strojů může psát v jednom kroku do dané buňky

Co se stane při zápisu více strojů do stejné buňky?

• Priority - zapíše se údaj stroje s nejmenším PID

• Arbitrary - "nějaký" stroj zapíše údaj

• Common - zápis se podaří, jen když všichni zapisují stejné číslo

Většinou v zadání víme, že budeme na stroji s danými omezeními. Naším úkolem je přizpůsobit tomu náš program.

Exclusive přístup se považuje za lepší, než Concurrent, avšak bývá těžké vymyslet Exclusive algoritmus.

Příklad: Posloupnost n čísel v glob. paměti, chceme rozhodnout, zda je mezi nimi číslo 7.

Řešení: Vezmeme n strojů. V globální paměti je buňka b s hodnotou 0. Každý stroj se podívá na buňku dle svého PID, pokud je tam 7, zapíše 1 do buňky b. V posloupnosti je sedmička, právě když v buňce b je jednička. Pro čtení nám stačí ER. Pro zápis potřebujeme CW (libovolný ze tří).

Přiřazení instrukcí procesorům

• SIMD - Single Instruction Multiple Data - stejné programy, stejný čítač (nelze "skočit" čítačem jen v 1 stroji), různé vstupy. Součást běžných procesorů (Intel SSE atd.).

• Uniformní - stejný program, různé čítače. Budeme zkoumat ve zbytku přednášky.

• MIMD - Multiple Instructions Multiple Data - různé programy i čítače. Všechny počítače světa jsou 1 MIMD stroj.

Složitost paralelních výpočtů

Uvažujeme konstantní čas jedné operace, ačkoli čísla v buňkách jsou libovolně dlouhá. Předpokládáme, že se v praxi vejdeme do pevného počtu bitů.

• T(n) - čas výpočtu programu na vstupu délky n

• S(n) - prostor výpočtu programu na vstupu délky n

• P(n) - počet potřebných procesorů (strojů) pro vstup délky n

• W(n) - omezení na délku čísla (v bitech)

Simulace Common na EREW

V Common může více procesorů psát do jedné buňky stejné číslo. Chceme to provést v modelu, kde jen jeden stroj může psát do dané buňky.

• toto nechápu. Co když chce více procesorů psát do několika buněk, ne všichni do r?

Spojový seznam - odkaz na konec lze získat "zdvojováním".

Věta: Když nějaký TS řeší náš problém v čase $O(T(n))$, pak tento problém může být vyřešen i na jiném sekvenčním výpočetním modelu v čase $O(T(n))^k$. Tedy třída P je stejná pro všechny sekv. výpočetní modely.

Sekvenční teze: Všechny "rozumné" sekvenční modely jsou polynomiálně závislé.

Paralelní teze: Všechny "rozumné" paralelní modely jsou polynomiálně závislé. Jejich časová složitost je polynom. vázaná na prostorovou složitost sekvenčního modelu.

• $PARTIME(T(n)) \leq SPACE(T(n)^k)$

• $SPACE(T(n)) \leq PARTIME(T(n)^l)$

Tyto teze, podobně jako Church-Turingova teze, jsou spíše "názory". Nejsou to tvrzení v nějaké teorii, nelze je dokázat nebo vyvrátit, nebo s nimi jinak formálně pracovat.

Optimální a efektivní par. algoritmy

NC - Nick Pippenger's class - třída úloh, řešitelných v polylogaritmickém čase $\bigcup \limits_{k=0}^{\infty} PARTIME(\log^k n)$ s polynomiálním počtem procesorů. Všimněte si, že polynom logaritmu je stále sublineární (od nějakého n je $\log^k n <n$).

Nechť S je problém, řešitelný sekvenčním algoritmem v čase T(n). Paralelní algoritmus A řešící S v čase t(n) s p(n) procesory nazveme:

• optimální, když:

  • t(n) = polylog(n)

  • $p(n)*t(n) \in O(T(n))$ - algoritmus "nedělá více práce", než sekvenční verze

• efektivní, když:

  • t(n) = polylog(n)

  • $p(n)*t(n) \in O(T(n)) \cdot polylog(n)$