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