1
Paraleln´ı a distribuovan´ e architektury
Flynnova klasifikace procesor˚ u: • SISD – konvenˇcn´ı procesory • SIMD – vektorov´e procesory • MISD – ˇretˇezov´e procesory • MIMD – multiprocesory (komukuj´ı sd´ılenou pamˇet´ı) – multicomputery a distribuovan´e syst´emy (zas´ıl´an´ı zpr´av) Flynnova klasifikace popisuje pouze Von-Neumannovsk´e architektury. Data-flow a reukˇcn´ı architektury jsou tak´e paraleln´ı architektury. Architektura data-flow nem´ a program a PC (Program Counter), prov´ad´ı interpretaci grafu toku dat. Do uzlu vstupuj´ı operandy a vystupuje v´ ysledek. V pamˇeti udrˇzuje struktury pro uzly, kter´e definuj´ı operace, vstupy a v´ ystupy, propojeno do orientovan´eho grafu. Paralelismus spoˇc´ıv´a v nˇekolika operaˇcn´ıch jednotk´ ach, kter´e vyb´ıraj´ı ud´ alosti a pouˇst´ı je grafem. Redukˇ cn´ı poˇ c´ıtaˇ c bere v´ yraz a nahrazuje jeho ˇc´asti v´ ysledkem dan´e operace (2*3 na 6). Program se pˇrevede na strom a po zad´ an´ı hodnot se strom redukuje aˇz na jeden uzel. VLIW (Very Long Instruction Word) je SISD, jedna velmi dlouh´a instrukce (pˇredstavuje nˇekolik menˇs´ıch pro r˚ uzn´e procesory). Tyto procesory mohou pracovat paralelnˇe, pokud je to moˇzn´e (nejsou kolize, neˇcek´ a se na meziv´ ysledek). Jednoduch´ a implementace a ˇsk´alovatelnost, ale nˇekter´e instrukce ˇspatn´e (skok vyuˇzije jedinou podinstrukci, meziv´ ysledky apod). Pohybuj´ı se nˇekde mezi statick´ ymi a dynamick´ ymi superskal´ary. Statick´ e superskal´ arn´ı procesory zpracov´avaj´ı sekvenˇcn´ı program na v´ıce procesorech in-order, takˇze paralelnost je jen za soubˇehu spr´ avn´ ych instrukc´ı. Dynamick´ e superskal´ arn´ı procesory zpracov´avaj´ı sekvenˇcn´ı program na v´ıce procesorech out-of-order, napˇr. spekulativn´ı v´ ypoˇcty za skokem. MISD jsou line´ arnˇe propojen´e procesory, ˇreˇs´ı proudov´e u ´lohy, sekvenˇcn´ı pr˚ uchod. Zˇ retˇ ezen´ e procesory vyuˇz´ıv´ aj´ı nˇekolik paraleln´ıch postup˚ u prov´adˇen´ı (pipelines), protoˇze jednotliv´e ˇc´asti v´ ypoˇcetn´ıho ˇretˇezce by jednou pipeline byly nevyuˇzity. Nˇekter´e jednotky se pak mohou vyskytovat v´ıcekr´at (ALU). SIMD jsou vektorov´e procesory, paralelnˇe se prov´ad´ı stejn´a instrukce na n procesorech a n ˇc´astech vstupn´ıch dat (MMX, SSE). Rozliˇsuj´ı se podle toho, zda kaˇzd´ y procesor m´a vlastn´ı pamˇet’, nebo je pˇr´ıstupn´ a vˇsem a alokuje se. Jednoduch´ a implementace, latence a synchronizace oproti MIMD. Ne vˇsechny probl´emy jsou vhodn´e, nevyplat´ı se v mal´em poˇctu. Granularita paralelismu – na u ´rovni instrukc´ı, mezi instrukcemi, mezi pˇr´ıkazy, mezi bloky procesu, mezi procesy ˇ s´ı soupeˇren´ı a kooperaci, pouˇziv´ Synchronizace zajiˇst’uje dodrˇzen´ı poˇzadovan´ ych ˇcasov´ ych vztah˚ u. Reˇ a zas´ıl´ an´ı zpr´ av, rendezvous, semafor, monitor a bari´eru. Komunikace je pˇrenos dat mezi paraleln´ımi procesy, hlavn´ımi prostˇredky je zas´ıl´an´ı zpr´av a sd´ılen´a pamˇet’.
1
2
Topologie
Multitasking – 1 CPU pˇrep´ın´ a kontext (virtu´aln´ı procesor), pamˇet’ je sd´ılen´a, pˇred´av´an´ı zpr´av simulov´ ano SW Syst´ em se sd´ılenou pamˇ et´ı – CPU maj´ı svou cache, zbytek na sbˇernici (boj), pˇred´av´an´ı zpr´av m˚ uˇze b´ yt v HW nebo simulace SW Virtu´ aln´ı sd´ılen´ a pamˇ et’ – CPU m´ a svou pamˇet’, ale je virtu´alnˇe spojena v simulovanou sd´ılenou, opˇet HW/SW simulovan´e zas´ıl´ an´ı zpr´ av Syst´ em s pˇ red´ av´ an´ım zpr´ av – CPU v´ az´ any volnˇe (napˇr. poˇc´ıtaˇcov´a s´ıt’), sd´ılen´a pamˇet’ simulovan´a SW Sd´ılen´ a pamˇ et’: • Vˇsechny procesory maj´ı pˇr´ıstup do cel´eho pamˇet’ov´eho prostoru. ˇ sen´ı souˇcasn´eho pˇr´ıstupu k jedn´e buˇ • Reˇ nce: – EREW – Exclusive Read, Exclusive Write (velmi omezuj´ıc´ı) – CREW – Concurrent Read, Exclusive Write (ˇcast´e, jednoduch´e) – ERCW – Exclusive Read, Concurrent Write (ned´av´a smysl) – CRCW – Concurrent Read, Concurrent Write (sloˇzit´e) Pˇ red´ av´ an´ı zpr´ av: • Kaˇzd´ y procesor m´ a vlastn´ı adresov´ y prostor. • Tak´e kaˇzd´ y procesor m´ a vlastn´ı fyzickou pamˇet’, pˇr´ıstup jinam komunikac´ı. Statick´ e propojovac´ı s´ıtˇ e: • Vˇsechny uzly jsou procesory. • Vˇsechny hrany jsou komunikaˇcn´ı kan´aly. • Neobsahuj´ı sd´ılenou pamˇet’. • Pr˚ umˇer je nejdelˇs´ı d´elka nejkratˇs´ıch cest mezi vˇsemi dvojicemi uzl˚ u. • Konektivita je minim´ aln´ı poˇcet hran, kter´e je nutn´e odstranit pro rozdˇelen´ı na dvˇe ˇc´asti. ˇıˇrka bisekce je minim´ • S´ aln´ı poˇcet hran, kter´e spojuj´ı dvˇe pˇribliˇznˇe stejnˇe velk´e ˇc´asti s´ıtˇe. Typick´ a statick´ a propojen´ı: ´ e propojen´ı • Upln´ • Hvˇezda • Line´ arn´ı pole • D-rozmˇern´ a mˇr´ıˇzka • K-´ arn´ı d-rozmˇern´ a kostka • D-´ arn´ı strom Dynamick´ e propojovac´ı s´ıtˇ e: • Uzly jsou procesory, pamˇet’ov´e moduly nebo pˇrep´ınaˇce. 2
ˇ • Casto implementuj´ı sd´ılenou pamˇet’. • Implementace: kˇr´ıˇzov´ y pˇrep´ınaˇc, sbˇernice, . . . V´ıce´ urovˇ nov´ e s´ıtˇ e spojuj´ı p procesor˚ u s p pamˇet’ov´ ymi moduly pomoc´ı p.log(p) pˇrep´ınaˇc˚ u.
3
Distribuovan´ e a paraleln´ı algoritmy a jejich sloˇ zitost
Poˇ cet procesor˚ u p je odvozen on d´elky vstupu n. p(n) = {1, c, log(n), n, n.log(n), n2 , . . . , nr , rn }. ˇ Cas v´ ypoˇ ctu t je tak´e odvozen od n a je ud´av´an v jednotk´ach (kroc´ıch). Cena algoritmu c(n) = p(n).t(n). Algoritmus s optim´aln´ı cenou je stejnˇe drah´ y jako sekvenˇcn´ı algoritmus (jde o cenu, ne rychlost) copt (n) = tseq (n). Zrychlen´ı paralelizac´ı je d´ ano vztahem tseq (n)/t(n), efektivnost pak tseq (n)/c(n), nastaven´ı je z´avisl´e na pˇr´ıpadu pouˇzit´ı. Sloˇ zitost´ı vˇetˇsinou rozum´ıme poˇcet procesor˚ u. Pˇri v´ ypoˇctu z´avislosti na d´elce vstupu je nejzaj´ımavˇejˇs´ı nejhorˇs´ı pˇr´ıpad, takˇze pokud jedna ˇc´ ast algoritmu vyˇzaduje p(n) procesor˚ u a druh´a p(n2 ) procesor˚ u, v´ ysledn´a sloˇzitost je p(n2 ).
4
Algoritmy ˇ razen´ı
ˇ Razen´ ı bere posloupnost prvk˚ u a podle relace > je seˇrad´ı. Zjednoduˇsujeme na ˇrazen´ı pomoc´ı operace porovn´ an´ı. Tak´e pˇredpokl´ ad´ ame, ˇze v posloupnosti nejsou ˇz´adn´e dva prvky rovny. Vˇsechny posloupnosti tak lze vyj´ adˇrit (m˚ uˇzeme pˇridat index - sloˇzitost O(n)). Optim´ aln´ı sloˇ zitost podle sekvenˇcn´ıho algoritmu je c(n) = O(n.log(n)). Enumeration sort: • Princip: v´ ysledn´ a pozice prvku je d´an´a poˇctem prvk˚ u, kter´e jsou menˇs´ı • Topologie: mˇr´ıˇzka n kr´ at n, ˇr´ adky a sloupce jsou bin´arn´ı stromy v poli • Procesory: registry A,B,RANK; do A,B z´apis prvku, RANK inkrementace; moˇznost poslat registr syn˚ um • Algoritmus: pomoc´ı jedn´e ˇrady se prvky porovnaj´ı (a pˇritom se mˇen´ı RANK); spr´avn´a pozice je RANK; nakonec se prvky pˇresunou stromem • Sloˇzitost: t(n) = O(log(n)) – nejrychlejˇs´ı paraleln´ı ˇreˇsen´ı; c(n) = O(n2 .log(n)) – nen´ı optim´aln´ı Odd-even transposition sort • Princip: paraleln´ı bubble-sort, porovn´avaj´ı se jen soused´e a mohou se pˇrehodit • Topologie: line´ arn´ı pole n procesor˚ u • Procesory: obsahuj´ı jedin´ y registr s hodnotou prvku • Algoritmus: na poˇc´ atku se pole napln´ı posloupnost´ı; v lich´em kroku pracuj´ı lich´e procesory, v sud´em sud´e; porovn´ a se s n´ asledn´ıkem a pˇr´ıpadnˇe prohod´ı hodnoty; algoritmus konˇc´ı po n kroc´ıch (lze urychlit testem na prohozen´ı)
3
• Sloˇzitost: t(n) = O(n) – nejrychlejˇs´ı ˇreˇsen´ı pro line´arn´ı topologii; c(n) = O(n2 ) – nen´ı ide´aln´ı Odd-even merge sort • Princip: s´ıt’ sloˇzen´ a ze speci´ aln´ıch procesor˚ u • Topologie: procesory propojeny tak, aby sloˇzen´ım jednotliv´ ych porovn´an´ı byla seˇrazen´a posloupnost • Procesory: 2 vstupy a 2 v´ ystupy, porovn´a vstupy a d´a na v´ ystupy high a low • Algoritmus: spoˇc´ıv´ a v zapojen´ı s´ıtˇe, kask´ada 1 × 1, 2 × 2, 4 × 4, . . . • Sloˇzitost: t(n) = O(log 2 (n)); c(n) = O(n.log 4 (n)) – nen´ı optim´aln´ı Merge-splitting sort • Princip: varianta odd-even sortu, kaˇzd´ y procesor ˇrad´ı kr´atkou posloupnost • Topologie: line´ arn´ı pole procesor˚ u – p(n) < n • Procesory: obsahuje m prvk˚ u, kter´e um´ı seˇradit optim´aln´ım sekvenˇcn´ım algoritmem • Algoritmus: m´ısto porovn´ an´ı soused˚ u se provede spojen´ı posloupnost´ı (O(n)) a pak rozdˇelen´ı na p˚ ul • Sloˇzitost: c(n) = O(n.log(n)) + O(n.p), optim´aln´ı pro p ≤ log(n) Pipeline merge sort • Princip: rozdˇeleno na nˇekolik krok˚ u, prvn´ı spojuje posloupnosti d´elky 1, pak 2, atd. • Topologie: lin´ arn´ı pole procesor˚ u – p(n) = log(n) + 1 • Procesory: um´ı spojovat dvˇe seˇrazen´e posloupnosti O(n) • Algoritmus: ze vstupn´ı posloupnosti se vezme prvn´ı prvek a d´a jej do jedn´e posloupnosti, druh´ y do druh´e; dalˇs´ı vybere vˇzdy nejvˇetˇs´ı prvek a prvn´ı dva d´av´a do prvn´ı posloupnosti, druh´e dva do druh´e; tˇret´ı krok tak´e bere nejvˇetˇs´ı, ale stˇr´ıd´ a posloupnosti po ˇctyˇrech, atd. • Sloˇzitost: t(n) = O(n); c(n) = O(n).O(log(n) + 1) = O(n.log(n)) – optim´aln´ı Enumeration sort podruh´ e • Princip: porovn´ an´ı se vˇsemi prvky a poˇcet menˇs´ıch urˇcuje poˇrad´ı • Topologie: line´ arn´ı pole n procesor˚ u a sbˇernice, kter´a muˇze pˇren´est jednu hodnotu • Procesory: registr C (poˇcet menˇs´ıch), X (prvek na dan´e pozici), Y (prvek posloupnosti, kter´ y se porovn´ av´ a) a Z (v´ ysledn´ a pozice) • Algoritmus: C se nastav´ı na 1; sbˇernic´ı se poˇsle hodnota X a line´arnˇe pˇres procesory Y prvn´ımu prvku; Y se posunou doprava a v dalˇs´ım prvku se poˇsle X druh´emu a Y zase line´arnˇe prvn´ımu; nepr´azdn´e registry se porovnaj´ı a pˇr´ıpadnˇe inkrementuje C; po vyˇcerp´an´ı vstupu se X poˇsle do Z procesoru, kter´ y je urˇcen C a to sbˇernic´ı (protoˇze Y se st´ ale posouv´a doprava) • Sloˇzitost: t(n) = n; c(n) = O(n2 ) – nen´ı optim´aln´ı Minimum extraction sort • Princip: stromem odeb´ır´ a vˇzdy nejmenˇs´ı prvek • Topologie: strom s n listy, log(n) + 1 u ´rovnˇemi a 2n − 1 procesory
4
• Procesory: listov´ y procesor obsahuje prvek posloupnosti, nelistov´e prvky um´ı porovnat syny • Algoritmus: napln´ı se listy; v kaˇzd´em kroku otec vybere menˇs´ı hodnotu; jakmile je v koˇrenu hodnota je to prvn´ı prvek seˇrazen´e posloupnosti • Sloˇzitost: t(n) = O(n); c(n) = O(n2 ) – nen´ı optim´aln´ı Bucket sort • Princip: stromem spojen´e procesory, kter´e ˇrad´ı menˇs´ı posloupnosti a pak spojen´ı • Topologie: strom s m listy, kde n = 2m • Procesory: listov´e procesory ˇrad´ı kr´atkou posloupnost, ostatn´ı spojuj´ı syny – O(n) • Algoritmus: – • Sloˇzitost: t(n) = O(n); c(n) = O(n.log(n)) – optim´aln´ı Median finding and splitting • Princip: dˇel´ı posloupnost medi´ anem aˇz na dvojice, kter´e porovn´a • Topologie: strom s m listy, kde n = 2m • Procesory: listov´e procesory porovnaj´ı dvojici, ostatn´ı vyberou medi´an a rozdˇel´ı posloupnost – O(n) • Algoritmus: je jasn´ y, pro v´ ybˇer medi´anu je potˇreba optim´aln´ı, napˇr. select • Sloˇzitost: t(n) = O(n); c(n) = O(n.log(n)) – optim´aln´ı
5
Algoritmy vyhled´ av´ an´ı
Vyhled´ av´ an´ı zjiˇst’uje pˇr´ıtomnost zadan´eho prvku v posloupnosti a pˇr´ıpadnˇe i jeho pozici. Optim´ aln´ı sloˇ zitost podle sekvenˇcn´ıho algoritmu je O(n) pro neseˇrazenou posloupnost – sekvenˇcn´ı vyhled´ av´ an´ı; O(log(n)) pro seˇrazenou posloupnost – bin´arn´ı vyhled´av´an´ı. N-ary search • Seˇrazeno: ano • Princip: paraleln´ı analogie k bin´ arn´ımu hled´an´ı, zjiˇst’uje se ˇc´ast, ve kter´e prvek je • Topologie: line´ arn´ı pole m procesor˚ u, kde m < n; CREW (hledan´ y prvek) • Procesory: porovn´ avaj´ı prvek na sv´em m´ıstˇe s hledan´ ym, registr, kter´ y ˇr´ık´a, na kter´e stranˇe pokraˇcovat • Algoritmus: v kaˇzd´e iteraci se nastav´ı registry, v u ´seku, kde na obou stran´ach je hodnota odliˇsn´ a se hled´ a v dalˇs´ı iteraci • Sloˇzitost: t(n) = O(logm+1 (n + 1)); c(n) = O(m.logm+1 (n + 1)) – nen´ı optim´aln´ı Unsorted search • Seˇrazeno: ne • Princip: paralelnˇe volan´ y sekvenˇcn´ı algoritmus • Topologie: line´ arn´ı pole m procesor˚ u, kde m < n • Procesory: sekvenˇcnˇe hledaj´ı prvek X s pˇridˇelenou posloupnost´ı 5
• Algoritmus: procesory naˇctou prvek do registru a provedou hled´an´ı, mohou nastavit flag nalezen´ı • Sloˇzitost: EREW – c(n) = O(m.log(m) + n); CREW – c(n) = O(n) (pokud zapisuje pouze jedin´ y procesor) Tree search • Seˇrazeno: ne • Princip: listy porovnaj´ı a v´ ysledek se propaguje stromem • Topologie: strom s 2n − 1 procesory • Procesory: listy umˇej´ı porovnat, otec logick´ y OR vysledk˚ u syn˚ u • Algoritmus: koˇren naˇcte hledan´ y prvek a stromem propaguje; listy obsahuj´ı prvky posloupnosti a porovnaj´ı; otec udˇel´ a OR • Sloˇzitost: t(n) = O(log(n)); c(n) = O(n.log(n)) – nen´ı optim´aln´ı
6
Maticov´ e algoritmy
Sloˇ zitost u maticov´ ych algoritm˚ u neb´ yv´ a zaloˇzena na poˇctu prvk˚ u, ale na poˇctu ˇr´ adk˚ u/sloupc˚ u n, tak´e vˇetˇsinou uvaˇzujeme ˇctvercov´e matice n × n. Transpozice matic m´ a sekvenˇcn´ı sloˇzitost O(n2 ). Mesh transpose • Princip: prvky se pos´ılaj´ı matic´ı na sv´a nov´a m´ısta vˇzdy v obou smˇerech • Topologie: mˇr´ıˇzka n kr´ at n procesor˚ u • Procesory: 3 registry, A obsahuje v´ ysledn´ y prvek, B prvek od prav´eho/horn´ıho souseda, C od lev´eho/doln´ıho • Algoritmus: vˇzdy nejkrajnˇejˇs´ı prvky poˇslou svou hodnotu sousedovi tak, aby dorazil na sv´e m´ısto (vˇzdy pouze horizont´ alnˇe a pak vertik´ alnˇe • Sloˇzitost: t(n) = O(n); c(n) = O(n3 ) – nen´ı optim´aln´ı EREW transpose • Princip: prvky se prohod´ı pˇr´ımo mezi sebou paralelnˇe • Topologie: (n2 − n)/2 procesor˚ u (jeden na dva prvky a bez diagon´aly) • Procesory: nejsou to ani procesory, pouze pˇrehod´ı prvky • Algoritmus: v jednom kroku se najednou paralelnˇe pˇrehod´ı potˇrebn´e prvky • Sloˇzitost: t(n) = 1 – nejrychlejˇs´ı; c(n) = O(n2 ) – optim´aln´ı N´ asoben´ı matic A(m, n) a B(n, k) d´ av´ a matici C(m, k), kde Cij =
n P
ail .blj .
l=1
Sloˇ zitost podle sekvenˇcn´ıho algoritmu je O(n3 ), ale optim´aln´ı nen´ı zn´am, pohybuje se nˇekde mezi O(n2 ) a O(n3 ). Obecn´ eˇ reˇ sen´ı paralelizuje pouze v´ yslednou matici, ale v´ ypoˇcet sumy ponech´av´a sekvenˇcn´ı. Mesh multiplication
6
• Topologie: mˇr´ıˇzka n kr´ at k procesor˚ u • Procesory: udrˇzuj´ı pr˚ ubˇeˇznou hodnotu v´ ysledn´eho prvku, na konci v´ ysledek • Algoritmus: prvky matic se pˇriv´ adˇej´ı do prvn´ıho ˇr´adku resp. prvn´ıho sloupce a posl´eze se pos´ıl´ aj´ı mezi procesory d´ ale • Sloˇzitost: t(n) = O(n); c(n) = O(n3 ) – nen´ı optim´aln´ı N´ asoben´ı matice vektorem je specializovan´ y pˇr´ıpad n´asoben´ı matic – k = 1. Linear array multiplication je specializovan´ y pˇr´ıpad mesh multiplication (vektor pˇrich´az´ı shora, matice zboku, jeden sloupec procesor˚ u). t(n) = O(n); c(n) = O(n2 ) – optim´aln´ı Tree MV multiplication • Topologie: bin´ arn´ı strom 2n − 1 procesor˚ u • Procesory: listov´e n´ asob´ı, nelistov´e sˇc´ıtaj´ı • Algoritmus: v listech je vektor, matice se pˇriv´ad´ı po ˇr´adc´ıch; v´ ysledky n´asoben´ı ˇr´adku se sˇc´ıtaj´ı otcem aˇz do koˇrene • Sloˇzitost: t(n) = O(n); c(n) = O(n2 ) – optim´aln´ı
7
Model PRAM
PRAM (Parallel Random Access Machine) je synchronn´ı model paraleln´ıho v´ ypoˇctu pomoc´ı procesor˚ u se sd´ılenou pamˇet´ı a spoleˇcn´ym programem. Alternativa k paraleln´ımu Turingovu stroji. Procesor: • Aditivn´ı a logick´e operace • Multiplikativn´ı operace • Podm´ınˇen´e skoky • Pˇr´ıstup ke sv´emu unik´ atn´ımu ˇc´ıslu (index) Pamˇ et’: • N´ ahodn´ y pˇr´ıstup pro vˇsechny procesory • Reprezentovan´ a neomezen´ ym poˇctem registr˚ u • Neomezen´ a d´elka slova (dnes nen´ı vyˇzadov´ano) • M´ ody pˇr´ıstupu EREW, CREW a CRCW V´ ypoˇ cet prob´ıh´ a synchronnˇe po kroc´ıch – ˇcten´ı, lok´aln´ı operace, z´apis. ˇ sen´ı CRCW konflikt˚ Reˇ u: 1. COMMON – vˇsechny hodnoty musej´ı b´ yt stejn´e, jinak se nezap´ıˇse 2. ARBITRARY – zap´ıˇse se libovoln´ a z hodnot 3. PRIORITY – procesory maj´ı pˇridˇelenu prioritu Broadcast je algoritmus pro EREW PRAM pro distribuci hodnoty na jednom m´ıstˇe v pamˇeti do vˇsech procesor˚ u. ˇ S´ıˇren´ı je logaritmick´e – jeden procesor pˇreˇcte, pˇred´a dalˇs´ımu, pak jsou dva, kaˇzd´ y jednomu, atd. t(n) = O(log(n)) 7
8
Suma prefix˚ u
Suma prefix˚ u (all-prefix-sums, allsums, scan) je z´akladn´ım kamenem paraleln´ıch algoritm˚ u. Je to operace, jej´ıˇz vstupem je uspoˇr´ adan´ a posloupnost a bin´ arn´ı asociativn´ı operace ⊕. V´ ysledkem je posloupnost a0 , (a0 ⊕ a1 ), (a0 ⊕ a1 ⊕ a2 ), . . .. Pouˇ zit´ı: vyhodnocov´ an´ı polynom˚ u, rychl´e sˇc´ıt´an´ı v HW, lexik´aln´ı anal´ yza a porovn´av´an´ı, ˇrazen´ı, hled´ an´ı regul´ arn´ıch v´ yraz˚ u, odstranˇen´ı oznaˇcen´ ych prvk˚ u apod. Sekvenˇ cn´ı ˇ reˇ sen´ı proch´ az´ı vˇsechny prvky a nese si meziv´ ysledek, sloˇzitost O(n). Varianty: • Scan je norm´ aln´ı suma prefix˚ u. • Prescan je rozˇs´ıˇrena o neutr´ aln´ı prvek na poˇc´atku v´ ysledku a bez posledn´ıho prvku. • Reduce je pouze hodnota posledn´ıho prvku scan. • Segmentovan´y scan je doplnˇen o pole pˇr´ıznak˚ u, kter´ y urˇcuje hranici segmentu, kaˇzd´ y segment je scanov´ an zvl´ aˇst’. Paraleln´ı reduce je moˇzno spoˇc´ıtat pomoc´ı stromu procesor˚ u, v´ ysledek je v koˇreni. t(n) = O(log(n)); c(n) = O(n.log(n)) – nen´ı optim´ aln´ı, lze vylepˇsit tak, ˇze se paralelnˇe poˇc´ıt´a reduce menˇs´ıch posloupnost´ı Algoritmy scan nen´ı nutn´e pˇr´ımo uv´ adˇet, jelikoˇz se jedn´a o prescan s pouˇzit´ım reduce. Prescan se skl´ ad´ a ze dvou ˇc´ ast´ı – upsweep a downsweep. Sloˇzitost je stejn´a jako u reduce. Upsweep je totoˇzn´ y s reduce, ale meziv´ ysledky se nezahazuj´ı. Downsweep: 1. Koˇrenu se pˇriˇrad´ı neutr´ aln´ı prvek. 2. Koˇren pˇriˇrad´ı prav´emu synovi svou hodnotu ⊕ hodnotu lev´eho syna. 3. Koˇren pˇriˇrad´ı lev´emu synovi svou hodnotu. 4. Opakuje se pro dalˇs´ı u ´rovnˇe. Packing problem bere vstupn´ı pole, kde pouze nˇekter´e hodnoty jsou d˚ uleˇzit´e a tyto shrne na poˇc´atek pole. 1. Potˇrebn´e poloˇzky se oznaˇc´ı flagem. 2. Spoˇcte se +-scan flag˚ u. 3. Kaˇzd´ y prvek s hodnotou vyˇsˇs´ı neˇz lev´ y soused se pˇresune na pozici danou touto hodnotou. Probl´ em viditelnosti – je d´ ana v´ yˇskov´ a mapa (matice) a na n´ı pozorovac´ı bod X. Je potˇreba zjistit, kter´e body jsou viditeln´e z bodu X. 1. Bod je viditeln´ y, pokud ˇz´ adn´ y bod mezi n´ım a pozorovatelem nem´a vˇetˇs´ı vertik´aln´ı u ´hel. 2. Vytvoˇr´ı se vektor v´ yˇsek bod˚ u na cestˇe paprsku. 3. Vektor v´ yˇsek se pˇrepoˇc´ıt´ a na vektor u ´hl˚ u. 4. Pomoc´ı max-prescan se spoˇcte vektor maxim´aln´ıch u ´hl˚ u.
8
5. Urˇc´ı se u ´hel studovan´eho bodu a porovn´a s maximem.
Bin´ arn´ı sˇ c´ıtaˇ cka – Carry Lookahead Parallel Binary Adder. U norm´aln´ı sˇc´ıtaˇcky paralelizaci vad´ı z´avislost na carry ze sˇc´ıt´ an´ı niˇzˇs´ıch bit˚ u. Je potˇreba carry pˇredpoˇc´ıtat. 1. Vypoˇcte se vektor s oborem hodnot ”Propagate, Stop, Generate” podle tabulky. 2. Vypoˇcte se scan nad vektorem opˇet pomoc´ı tabulky. 3. Hodnota Generate ˇr´ık´ a, ˇze na vyˇsˇs´ım bitu bude potˇreba uplatnit carry. 4. Carry je tak vypoˇcteno logaritmicky, pak je moˇzn´e seˇc´ıst v konstantn´ım ˇcase. Radix sort je zaloˇzen na dvojkov´em radix sort, tedy prvky s bitem 0 se pˇrem´ıst´ı na poˇc´atek. To se provede pro vˇsechny ˇr´ ady. Operace split je operace pˇresunut´ı prvk˚ u na poˇc´atek, implementov´ana jako scan a prescan, sloˇzitost jako scan. Quicksort pouˇz´ıv´ a segmentovan´ y scan, segmenty jsou 3 – menˇs´ı, rovn´e, vˇetˇs´ı neˇz pivot. Pivot se nepoˇc´ıt´ a, vˇetˇsinou se bere n´ ahodn´ y/prvn´ı prvek. 1. Kontroluje se, zda jiˇz nen´ı seˇrazeno (test mezi sousedy a AND-reduce v´ ysledk˚ u). 2. Vybere se pivot kaˇzd´eho segmentu, opˇet scan. Na poˇc´atku segment jeden. 3. V kaˇzd´em segmentu porovnej prvky s pivotem a rozdˇel. 4. Modifikovan´ y split pro pˇreˇrazen´ı do segmentu. 5. Rekurzivnˇe na segmenty quicksort. 6. Sloˇzitost t(n) = O(n/m.log(n) + log(m).log(n)); c(n) = O(n.log(m) + m.log(n).log(m)) – optim´ aln´ı pro mal´e m.
9
Seznamy
Line´ arn´ı seznam je modelov´ an jako pole (moˇzno pˇristoupit indexem) prvk˚ u v pamˇeti, kter´e obsahuj´ı hodnotu a index n´ asledn´ıka. Posledn´ı prvek ukazuje s´am na sebe. Predecessor computing poˇc´ıt´ a index pˇredch˚ udce v konstantn´ım ˇcase (Pred[Succ[i]] = i). List ranking pˇriˇrazuje prvk˚ um jejich vzd´ alenost od konce. Sekvenˇcn´ı sloˇzitost je O(n). V paraleln´ım prostˇred´ı se pouˇz´ıv´ a technika path doubling. Path doubling: 1. Paralelnˇe se vˇsem prvk˚ um pˇriˇrad´ı RANK (0 pro posledn´ı prvek, jinak 1). 2. Kaˇzd´ y procesor prvku v log(n) kroc´ıch se poˇc´ıt´a RANK jako RANK[i] + RANK[Succ[i]] a posune ukazatel Succ[i] = Succ[Succ[i]].
9
3. t(n) = O(log(n)); c(n) = O(n.log(n)) – nen´ı optim´aln´ı Suma suffix˚ u je obdoba sumy prefix˚ u, ale na seznamech (kde pevn´ y bod je konec). Poˇc´ıt´a se stejnˇe jako list ranking, ale pouˇzije se zadan´ a operace ⊕. Vylepˇ sen´ı list rankingu (a sumy suffix˚ u) spoˇc´ıv´a ve sn´ıˇzen´ı ceny, nˇekter´e procesory totiˇz prov´adˇej´ı zbyteˇcnou ˇ sen´ım je odpojovat procesory a t´ım sn´ıˇzit cenu. pr´ aci (poˇc´ıtaj´ı jiˇz spoˇc´ıtan´e vˇeci nebo cykl´ı na konci). Reˇ Nejprve kaˇzd´ y procesor dostane vzd´ alenost 1, pak pracuje kaˇzd´ y druh´ y a zv´ yˇs´ı ji na 2 pak kaˇzd´ y ˇctvrt´ y a opˇet zv´ yˇs´ı. V rekonstrukˇcn´ı f´ azi se pouze pˇriˇc´ıtaj´ı meziv´ ysledky. Probl´ em v paralelismu – jak se urˇc´ı ”kaˇzd´ y druh´ y” ? • Random mating – n´ ahodnˇe si vybere pohlav´ı, female n´asledovan´ y male se odpoj´ı • Optimal list ranking – kaˇzd´ y procesor m´a z´asobn´ık prvk˚ u, simulace random mating List coloring je obarven´ı seznamu tak, aby soused´e nemˇeli stejnou barvu. k-obarven´ı m˚ uˇze pouˇz´ıt k r˚ uzn´ ych barev. 2log(n) coloring vyuˇz´ıv´ a index procesoru k urˇcen´ı barvy. Hodnota k je index nejniˇzˇs´ıho bitu ID, ve kter´em se soused´e liˇs´ı, pak je barva C = 2k + ID[k]. k-Ruling set (mnoˇzina oddˇelovaˇc˚ u) je podmnoˇzina seznamu takov´a, ˇze ˇz´adn´e vybran´e vrcholy nesoused´ı a je mezi nimi maxim´ alnˇe k nevybran´ ych prvk˚ u. 2k-ruling set from k-coloring vybere prvek tehdy, kdyˇz jeho barva m´a menˇs´ı index neˇz pˇredch˚ udce a n´ asledn´ıka.
10
Stromy
Stromy jsou prezentov´ any podobnˇe jako seznamy, ale vazba nen´ı na n´asledn´ıka (i + 1), n´ ybrˇz na syny (2i a 2i + 1). Eulerova cesta je obecn´ y pˇr´ıpad pr˚ uchodu stromem (linearizace). Pˇrev´ad´ı strom na orientovan´ y graf (nahrad´ı hranu dvˇema opaˇcn´ ymi) → Eulerova kruˇznice. Eulerova kruˇ znice je reprezentov´ ana funkc´ı etour(e), kter´a hranˇe pˇriˇrad´ı n´asleduj´ıc´ı hranu v kruˇznici. Funkce je uloˇzena jako seznam sousednosti. Koˇ ren stromu vznikne tak, ˇze se v jednom bodˇe (koˇreni) Eulerova kruˇznice pˇreruˇs´ı. Pozice uzlu je vypoˇctena jako 2n − 2 − Rank(e), kde Rank je v´ ysledek list rankingu – O(log(n)). Vyuˇz´ıv´ a se pro zjiˇstˇen´ı rodiˇce. Tree contraction je operace pouˇzit´ a pˇri v´ ypoˇctu v´ yraz˚ u ve stromˇe. Eulerova cesta nen´ı pouˇziteln´a. Kaˇzd´ y list obsahuje operand a nelist oper´ ator. Tree contraction strom postupnˇe zmenˇsuje aˇz do jedin´eho uzlu, tedy v´ ysledku. RAKE operation odstran´ı dan´ y uzel a otce, na jehoˇz m´ısto dosad´ı sourozence s jeho podstromem. Vyuˇz´ıv´ a se pro tree contraction. Paraleln´ı RAKE nesm´ı b´ yt aplikov´ an na soused´ıc´ı uzly (konflikt), snaha co nejv´ıce RAKE najednou. 1. Oznaˇc´ıme listy zleva doprava.
10
2. Krajn´ı se vyˇrad´ı (z˚ ustanou posledn´ı). 3. Nejprve se vol´ a RAKE na lich´e a pak na sud´e listy. 4. Redukce stromu za t(n) = O(log(n)).
11
Interakce mezi procesy
Interakce mezi procesy m˚ uˇzeme rozdˇelit na kooperaci (je potˇreba synchronizace) a soupeˇren´ı (je potˇreba v´ yluˇcn´ y pˇr´ıstup). Probl´ em: jelikoˇz procesy bˇeˇz´ı paralelnˇe (popˇr. pseudoparalelnˇe), nen´ı jasn´e poˇrad´ı vykon´av´an´ı instrukc´ı obou program˚ u. Zde odkazuji na podklady pˇredmˇetu POS, tomuto t´ematu se tam vˇenuje nˇekolik kapittol, staˇc´ı si odmyslet ˇc´ asti spojen´e s OS. Oper´ ator
S> je p˚ uvodnˇe pouze teoretick´ y oper´ator, implementovan´ y ve vyˇsˇs´ıch programovac´ıch jazyc´ıch pro paraleln´ı programov´ an´ı. Jeho implementace je probl´emov´a. Zajiˇst’uje atomiˇcnost <>, oˇcek´av´ a splnˇen´ı podm´ınky B a pot´e atomicky vykon´ a sekvenci pˇr´ıkaz˚ u S. Critical Region ve vyˇsˇs´ıch jazyc´ıch jsou obalen´ı pouˇzit´ı semafor˚ u pro pˇr´ıstup ke KS, kl´ıˇcov´e slovo region a oznaˇcen´ı promˇenn´ ych shared. Probl´em, pokud se zanoˇruj´ı, pak m˚ uˇze doj´ıt ke konfliktu. Jednoduch´ a implementace (t´emˇeˇr makro). Conditional Critical Region rozˇsiˇruje koncepci o podm´ınku, pokud je stanovena dobˇre, ke kolizi nedojde. Implementace je ovˇsem velmi sloˇzit´ a. Z´ akladn´ı algoritmy (chybn´e) by cht´ıt nemˇeli, pokroˇcil´e (bez chyby) se uˇcit nebudu.
12
Pˇ red´ av´ an´ı zpr´ av
Zas´ıl´ an´ı zpr´ av je zaloˇzeno na dvou operac´ıch – send() a receive(). Zpr´avy se pos´ılaj´ı tzv. kan´ alem. Asynchronn´ı kan´ al neblokuje odes´ıl´ an´ı, data bufferuje v sobˇe, tˇeˇzko se implementuje (buffer je probl´em). Synchronn´ı kan´ al blokuje (hned nebo pokud je naplnˇen buffer), buffer m˚ uˇze b´ yt, ale je omezen, vˇetˇsinou bez bufferu, jde simulovat asynchronn´ım kan´alem (pouˇzit´ı ACK). OCCAM je programovac´ı jazyk zaloˇzen´ y na CSP (Communicating Sequential Processes). • Z´ akladem je proces, operace pˇriˇrazen´ı :=, vstup ? a v´ ystup !. • Sekvenˇcn´ı pˇr´ıkazy v odd´ılu SEQ. • Paralelnˇe prov´ adˇen´e pˇr´ıkazy v odd´ılu PAR. • Podm´ınka na z´ akladˇe vstupn´ıho kan´alu ALT. ADA je imperativn´ı objektov´ y jazyk s validaˇcn´ımi prostˇredky. M´a siln´e prostˇredky pro zas´ıl´an´ı zpr´av. • Konstrukce accept oˇcek´ av´ a pˇr´ıchod zpr´avy dan´eho jm´ena a parametr˚ u, pak zpracuje u ´kol a odeˇsle v´ ysledek.
11
• Konstrukce select oˇcek´ av´ a v´ıce typ˚ u zpr´av a pak vybere oˇsetˇruj´ıc´ı k´od. Linda je paraleln´ı programovac´ı jazyk zaloˇzen´ y na C. Je zaloˇzena na asynchron´ım zas´ıl´an´ı zpr´av pˇres glob´ aln´ı prostor zpr´ av (global space). • Tuple Space (n´ astˇenka) – glob´ aln´ı prostor zpr´av (sd´ılen´a pamˇet’). • Tuple – n-tice obsahuj´ıc´ı pole s daty (zpr´ava). • Actual field – pole zpr´ avy, kter´e je vyhodnoceno pˇred odesl´an´ım • Formal field – pole zpr´ avy, kter´e je pˇred´ano jako promˇenn´a • Vkl´ ad´ an´ı na TS prov´ adˇej´ı out a eval. Pˇrij´ım´an´ı pak in a rd. • out – generuje data (passive tuple), data vyhodnocena sekvenˇcnˇe • eval – generuje procesy (active tuple), kter´e vypoˇc´ıtaj´ı data paralelnˇe • in – pˇrijme a odebere z TS, blokuj´ıc´ı • rd – pouze pˇreˇcte z TS, blokuj´ıc´ı • Poˇzadavky na ˇcten´ı zpr´ av jsou ve tvaru ˇsablon (("x",?y,?z)).
13
Jazyky pro paraleln´ı zpracov´ an´ı
Situace: obrovsk´e s´ıtˇe poˇc´ıtaˇc˚ u propojen´e rychl´ ym spojen´ım, je moˇzn´e pouˇz´ıvat distribuovan´e v´ ypoˇcty, potˇreba jazyka a protokolu, nejpouˇz´ıvanˇejˇs´ı jsou PVM a MPI PVM (Parallel Virtual Machine) • Vytvoˇren jednou skupinou. • Distribuovan´ y operaˇcn´ı syst´em. • Pˇrenosn´ y mezi HW. • Heterogenn´ı (r˚ uzn´e moˇznosti reprezentace dat). • Velk´ a odolnost proti chyb´ am. • Dynamick´ y (pˇridat, odebrat proces, vyrovn´an´ı z´atˇeˇze, chyby). MPI (Message Passing Interface) • Vytvoˇren f´ orem firem. • Knihovna poskytuj´ıc´ı funkce. • Pˇrenosn´ y mezi HW a SW (je to knihovna). • Heterogenn´ı (zabalen´ı r˚ uzn´ ych dat do dan´ ych typ˚ u). • Zamˇeˇren na vysok´ y v´ ykon. • Pˇresnˇe definovan´e chov´ an´ı. • Statick´ y (vyˇsˇs´ı v´ ykon). • Nen´ı odolnost proti chyb´ am (neurˇcit´ y v´ ysledek). Implementace PVM 12
• D´emon, beˇz´ıc´ı na stanic´ıch. • D´emoni spolu komunikuj´ı. • Spojen´ı d´emon˚ u tvoˇr´ı virt´ aln´ı paraleln´ı stroj. • D´emon m´ a pod sebou procesy, kter´ ym je nadˇrazen. • Prvn´ı d´emon je oznaˇcen jako master. • Master se star´ a o nastaven´ı, pˇrid´ av´an´ı, hl´ıd´an´ı. Implementace MPI • Na kaˇzd´em poˇc´ıtaˇci bˇeˇz´ı procesy (jeden na CPU). • Procesy maj´ı identifikaci. • Procesy znaj´ı ID ostatn´ıch proces˚ u. • Procesy komunikuj´ı mezi sebou pˇr´ımo. • Proces neum´ı fork() (MPIv1) Message Passing v MPI • Kooperativn´ı – explicitn´ı send() a recv(). • Jednostrann´e (MPIv2) – z´ apis do pamˇeti c´ıle/ˇcten´ı zdroje Put() a Get(). • Procesy se sdruˇzuj´ı do skupin a zpr´avy do kontextu. • Komunik´ ator urˇcuje kontext a skupinu (napˇr. MPI_COMM_WORLD). • Kolektivn´ı operace – bcast() a reduce(). • Neblokuj´ıc´ı operace – Isend() a Irecv(), pak Iwait(). • MPI_Barrier() pro synchronizaci.
13
