Motivace pro paralelizaci algoritm˚ u Z´ akladn´ı typy paralelismu Metodika n´ avrhu paraleln´ıho algoritmu
´ 4. Uvod do paralelismu, metody paralelizace algoritm˚ u Ing. Michal Bliˇzn ˇ´ak, Ph.D. ´ Ustav informatiky a umˇ el´ e inteligence Fakulta aplikovan´ e informatiky UTB Zl´ın
Paraleln´ı procesy a programov´an´ı, Zl´ın, 26. u ´nora 2014
1 / 20
Motivace pro paralelizaci algoritm˚ u Z´ akladn´ı typy paralelismu Metodika n´ avrhu paraleln´ıho algoritmu
Motivace pro paralelizaci algoritm˚ u
2 / 20
Motivace pro paralelizaci algoritm˚ u Z´ akladn´ı typy paralelismu Metodika n´ avrhu paraleln´ıho algoritmu
Udrˇziteln´y n´arust v´ykonu v´ypoˇcetn´ı techniky Tvrzen´ı o trvale udrˇziteln´em n´arustu v´ykonu v´ypoˇcetn´ı techniky se pˇrenesenˇe op´ır´a o platnost Mooroveova z´akona. Moore˚ uv z´akon ”Poˇcet tranzistor˚ u, kter´e mohou b´yt um´ıstˇeny na integrovan´y obvod se pˇri zachov´an´ı stejn´e ceny zhruba kaˇzd´ych 18 mˇes´ıc˚ u zdvojn´asob´ı.” Je tento trend udrˇziteln´y i do budoucna? Lze pokraˇcovat v miniaturizaci ˇcip˚ u a jejich z´akladn´ıch komponent (tranzistor˚ u)? Lze pokraˇcovat v navyˇsov´an´ı pracovn´ı frekvence procesor˚ ua m´a to v˚ ubec smysl? 3 / 20
Motivace pro paralelizaci algoritm˚ u Z´ akladn´ı typy paralelismu Metodika n´ avrhu paraleln´ıho algoritmu
Proˇc nemus´ı Mooreo˚ uv z´akon platit i nad´ale Prostorov´a omezen´ı d´ıky vlastnostem souˇcasn´ych pouˇz´ıvan´ych materi´al˚ u Navyˇsov´an´ı pracovn´ı frekvence mikroˇcip˚ u je energeticky i technologick´y n´aroˇcn´e Navyˇsov´an´ı pracovn´ı frekvence mikroˇcip˚ u m˚ uˇze postr´adat smysl, viz. argument rychlosti svˇ etla: rychlost svˇetla je cca 30 cm/ns - sign´aly v mikrochipu se ˇs´ıˇr´ı zlomkem t´eto rychlosti, je-li velikost mikroˇcipu cca 3 cm, m˚ uˇzeme ˇr´ıci, ˇze informace nesen´a sign´alem na druhou stranu ˇcipu po pˇr´ım´e cestˇe nem˚ uˇze b´yt transportov´ana v´ıcekr´at neˇz 1010 za sekundu, redukc´ı vzd´alenosti o n´asobky 10, ˇci dokonce 100 se zv´yˇs´ı mnoˇzstv´ı proveden´ych operac´ı zase jenom o tyto n´asobky, coˇz je vzhledem k n´arok˚ um na danou minimalizaci zanedbateln´y n´ar˚ ust. 4 / 20
Motivace pro paralelizaci algoritm˚ u Z´ akladn´ı typy paralelismu Metodika n´ avrhu paraleln´ıho algoritmu
Jak udrˇzet Moore˚ uv z´akon v platnosti?
Vyuˇzit´ım u ´plnˇe nov´ych netradiˇcn´ıch koncept˚ u kvantov´e poˇc´ıtaˇce, ...
Paralelizac´ı st´ avaj´ıc´ıch typ˚ u v´ ypoˇ cetn´ıch syst´ em˚ u v´ıc hlav v´ıc v´ı ...
5 / 20
Motivace pro paralelizaci algoritm˚ u Z´ akladn´ı typy paralelismu Metodika n´ avrhu paraleln´ıho algoritmu
Pˇr´ıklad paralelizace v´ypoˇcetn´ı u´lohy Zad´ an´ı: Naleznˇete vˇsechna prvoˇc´ısla z mnoˇziny cel´ych ˇc´ısel N ∈ {0, 1, ..., n}. Sekvenˇ cn´ı (neparalelizovan´ e) ˇreˇsen´ı: 1
Mˇejme pole hodnot v rozsahu < 2, n > a promˇennou oznaˇcuj´ıc´ı aktu´aln´ı prvoˇc´ıslo v poli a tu nastavme na prvn´ı prvek pole.
2
Mˇejme promˇennou ukazuj´ıc´ı na pr´avˇe zpracov´avan´y prvek pole; hodnotu toho ukazatele nastavme na druhou mocninu hodnoty aktu´aln´ıho prvoˇc´ısla.
3
Z pole odstran´ıme prvek o hodnotˇe uloˇzen´e v ukazateli.
4
Z pole odstran´ıme vˇsechny prvky o hodnotˇe uloˇzen´e v ukazateli postupnˇe navyˇsovan´e o hodnotu aktu´aln´ıho prvoˇc´ısla aˇz do n.
5
Jako aktu´aln´ı prvoˇc´ıslo nastavme dalˇs´ı n´asleduj´ıc´ı hodnotu uloˇzenou v poli.
6
Pokraˇcujeme v bodˇe 3. 6 / 20
Motivace pro paralelizaci algoritm˚ u Z´ akladn´ı typy paralelismu Metodika n´ avrhu paraleln´ıho algoritmu
Postup sekvenˇcn´ıho v´ypoˇctu 1 2 3
2 2 2
3 3 3
4
5 5 5
6
7 7 7
8
9 9
10
11 11 11
12
13 13 13
14
15 15
16
17 17 17
18
Tabulka: Iterace algoritmu Eratosthenova s´ıta nad vstupn´ım polem
P
Aktuální prvočíslo
Ukazatel na prvek
1, 2, …, n
Obr´azek: Implementace algoritmu na sekvenˇcn´ım v´ypoˇcetn´ım stroji
7 / 20
Motivace pro paralelizaci algoritm˚ u Z´ akladn´ı typy paralelismu Metodika n´ avrhu paraleln´ıho algoritmu
Paralelizaci na syst´emu se sd´ılenou pamˇ et´ı (implementace)
P1 SM
P2
Ukazatel na prvek
Aktuální prvočíslo 1, 2, …, n
Ukazatel na prvek
Pp
Ukazatel na prvek
I/O zařízení
Obr´azek: Implementace algoritmu na paraleln´ım SMP syst´emu
8 / 20
Motivace pro paralelizaci algoritm˚ u Z´ akladn´ı typy paralelismu Metodika n´ avrhu paraleln´ıho algoritmu
Paralelizaci na syst´emu se sd´ılenou pamˇ et´ı (ˇcasov´e charakteristiky)
(a) V´ypoˇcetn´ı ˇcas
(b) Zrychlen´ı
Obr´azek: Paraleln´ı implementace Eratosthenova s´ıta na SMP stroji
9 / 20
Motivace pro paralelizaci algoritm˚ u Z´ akladn´ı typy paralelismu Metodika n´ avrhu paraleln´ıho algoritmu
Paralelizaci na syst´emu s distribuovanou pamˇ et´ı (implementace)
P1
Aktuální prvočíslo
Ukazatel na prvek
1, 2, …, n/p
Komunikace
P2
Aktuální prvočíslo
Pp
Aktuální prvočíslo
Ukazatel na prvek
n/p + 1, 2, …, 2n/p
Ukazatel na prvek
n- n/p + 1, 2, …, n
Obr´azek: Implementace algoritmu na paraleln´ım MIMD stroji
10 / 20
Motivace pro paralelizaci algoritm˚ u Z´ akladn´ı typy paralelismu Metodika n´ avrhu paraleln´ıho algoritmu
Paralelizaci na syst´emu s distribuovanou pamˇ et´ı (ˇcasov´e charakteristiky)
(a) V´ypoˇcetn´ı ˇcas
(b) Zrychlen´ı
Obr´azek: Paraleln´ı implementace Eratosthenova s´ıta na MIMD stroji
11 / 20
Motivace pro paralelizaci algoritm˚ u Z´ akladn´ı typy paralelismu Metodika n´ avrhu paraleln´ıho algoritmu
Z´akladn´ı typy paralelismu
12 / 20
Motivace pro paralelizaci algoritm˚ u Z´ akladn´ı typy paralelismu Metodika n´ avrhu paraleln´ıho algoritmu
Z´akladn´ı typy paralelismu Typy paralelismu: Datov´ y paralelismus Funkcion´ aln´ı paralelismus Instrukˇ cn´ı fronty (Pipelining) Pˇri hled´an´ı vhodn´eho zp˚ usobu paralelizace algoritmu je ˇz´adouc´ı vytvoˇrit tzv. graf datov´ e z´ avislosti: orientovan´y graf uzly pˇredstavuj´ı u ´lohy prov´adˇen´e nad datov´ymi instancemi hrany pˇredstavuj´ı z´avislosti mezi tˇemito u ´lohami
13 / 20
Motivace pro paralelizaci algoritm˚ u Z´ akladn´ı typy paralelismu Metodika n´ avrhu paraleln´ıho algoritmu
Datov´y paralelismus Graf datov´e z´avislosti obsahuje nez´ avisl´ eu ´lohy prov´ adˇ ej´ıc´ı totoˇ zn´ e operace nad r˚ uzn´ ymi instancemi dat. A x0 B
x1 B
x2 B
C
Obr´azek: Datov´y paralelismus 14 / 20
Motivace pro paralelizaci algoritm˚ u Z´ akladn´ı typy paralelismu Metodika n´ avrhu paraleln´ıho algoritmu
Funkcion´aln´ı paralelismus Graf datov´e z´avislosti obsahuje nez´ avisl´ eu ´lohy prov´ adˇ ej´ıc´ı r˚ uzn´ e operace nad r˚ uzn´ ymi instancemi dat. A x0 B
x1 C
x2 D
E
Obr´azek: Funkcion´aln´ı paralelismus 15 / 20
Motivace pro paralelizaci algoritm˚ u Z´ akladn´ı typy paralelismu Metodika n´ avrhu paraleln´ıho algoritmu
Instrukˇcn´ı fronty (pipelining) Graf datov´e z´avislosti obsahuje jednoduchou cestu nebo vˇ etev prov´ adˇ ej´ıc´ı r˚ uzn´ e z´ avisl´ e operace nad jednou instanc´ı dat. A
B
E
x0
x1
x2
x3
x0
x1
x2
x0
x1
Obr´azek: Instrukˇcn´ı fronta (pipeline) 16 / 20
Motivace pro paralelizaci algoritm˚ u Z´ akladn´ı typy paralelismu Metodika n´ avrhu paraleln´ıho algoritmu
Metodika n´avrhu paraleln´ıho algoritmu
17 / 20
Motivace pro paralelizaci algoritm˚ u Z´ akladn´ı typy paralelismu Metodika n´ avrhu paraleln´ıho algoritmu
Fosterova metodika n´avrhu paraleln´ıho algoritmu
N´avrh paraleln´ıho algoritmu dle Fostera spoˇc´ıv´a ve 4 kroc´ıch: 1
Rozloˇ zen´ı - nalezen´ı co nejvˇetˇs´ıho mnoˇzstv´ı v´ypoˇcetn´ıch u ´loh a datov´ych instanc´ı, kter´e mohou b´yt zpracov´any soubˇeˇznˇe.
2
Komunikace - nalezen´ı komunikaˇcn´ıch kan´al˚ u mezi rozloˇzen´ymi subjekty.
3
Aglomerace - slouˇcen´ı rozloˇzen´e v´ypoˇcetn´ı u ´lohy do vˇetˇs´ıch logick´ych v´ypoˇcetn´ıch celk˚ u (minimalizace komunikaˇcn´ı reˇzie).
4
Mapov´ an´ı - pˇriˇrazen´ı logick´ych v´ypoˇcetn´ıch celk˚ u k fyzick´ym v´ypoˇcetn´ım uzl˚ um paraleln´ıho syst´emu.
18 / 20
Motivace pro paralelizaci algoritm˚ u Z´ akladn´ı typy paralelismu Metodika n´ avrhu paraleln´ıho algoritmu
Fosterova metodika n´avrhu paraleln´ıho algoritmu
Problém
rozložení komunikace
mapování aglomerace
Obr´azek: Fosterova metodika n´avrhu paraleln´ıho algoritmu 19 / 20
Motivace pro paralelizaci algoritm˚ u Z´ akladn´ı typy paralelismu Metodika n´ avrhu paraleln´ıho algoritmu
Dˇekuji za pozornost A to je pro dneˇsek vˇse. Nast´av´a ˇcas pro vaˇse dotazy...
20 / 20
