PARALELNÍ PROCESY A PROGRAMOVÁNÍ

´ Í PARALELNÍ PROCESY A PROGRAMOVAN 12 Paraleln´ı algoritmy - paraleln´ı prefixov´ e souˇ cty Ing. Michal Bliˇ zn ˇ´ ak, Ph.D.

Zl´ın 2013

Tento studijn´ı materi´ al vznikl za finanˇcn´ı podpory Evropského sociáln´ıho fondu (ESF) a rozpoˇctu ˇceské republiky v rámci ˇreˇsen´ı projektu: CZ 1.07/2.2.00/15.0463, MOD´ ´ ´ ˚ ´ ERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD

OBSAH

1

Obsah 1 Motivace pro paralelizaci redukce

3

2 Sekvenˇ cn´ı a paraleln´ı redukce

3

3 Sekvenˇ cn´ı a paraleln´ı prefixov´ a redukce 3.1 Sekvenˇcn´ı prefixov´ y souˇcet . . . . . . . . . . . . . . . . . . . . . . 3.2 Paraleln´ı prefixov´ y souˇcet na CdTn . . . . . . . . . . . . . . . . . 3.3 Paraleln´ı prefixov´ y souˇcet na Qn . . . . . . . . . . . . . . . . . . 3.4 Paraleln´ı prefixov´ y souˇcet na EREW PRAM . . . . . . . . . . . 3.4.1 Neˇsk´ alovan´ y paraleln´ı prefixov´ y souˇcet na EREW PRAM ˇ alovan´ 3.4.2 Sk´ y paraleln´ı prefixov´ y souˇcet na EREW PRAM . 3.5 Segmentov´ y paraleln´ı prefixov´ y souˇcet . . . . . . . . . . . . . . .

3 4 5 6 6 6 6 9

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

4 Aplikace paraleln´ı prefixov´ e redukce 9 4.1 Zhuˇst’ovac´ı problém a paraleln´ı PrefixSort . . . . . . . . . . . . . . . . . . . . . . . . 9 4.2 Binárn´ı sˇc´ıtaˇcka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4.3 Paraleln´ı QuickSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 5 Kontroln´ı ot´ azky

´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463

13

OBSAH

ˇ Y ´ OBSAH PREDN ˇ ´ SKY ˇ STRUCN A Motivace pro paralelizaci redukce Sekvenˇcn´ı a paraleln´ı redukce Sekvenˇcn´ı a paraleln´ı prefixov´ a redukce Aplikace paraleln´ı prefixové redukce

MOTIVACE Redukce a prefixové redukce jsou jednˇemi z nejˇcastˇeji pouˇz´ıvan´ ych (a implementovan´ ych) paraleln´ıch algoritm˚ u slouˇz´ıc´ıch jako základ dalˇs´ıch, sloˇzitˇejˇs´ıch algoritm˚ u. V této pˇrednáˇsce se seznám´ıme se z´ akladn´ımi vlastnostmi a implementacemi redukˇcn´ıch algoritm˚ u na r˚ uzn´ ych paraleln´ıch systémech.

CÍL Seznámit se se z´ akladn´ımi vlastnostmi a implementaˇcn´ımi aspekty nˇekter´ ych paraleln´ıch redukˇcn´ıch algoritm˚ u.


2

Motivace pro paralelizaci redukce

1

3

Motivace pro paralelizaci redukce

Obecná redukce prvk˚ u mnoˇziny/pole je velmi ˇcast´ ym algoritmick´ ym problémem. Operátorem redukce m˚ uˇzeme ch´ apat témˇeˇr jakoukoliv (matematickou) operaci schopnou zredukovat 2 operandy do jedné v´ ysledkové hodnoty. Typicky se m˚ uˇze jednat o souˇcet nebo násoben´ı, obecnˇe vˇsak lze redukˇcn´ı operátor nadefinovat libovoln´ ym zp˚ usobem (napˇr. slouˇcen´ı bitmap, souˇcet prvk˚ u v´ıcerozmˇern´ ych pol´ı, atd.). Je zˇrejmé ˇze ˇcasov´ a sloˇzitost redukce se bude u ´zce odv´ıjet o od ˇcasové sloˇzitosti samotného redukˇcn´ıho oper´ atoru. Je-li ˇcasová sloˇzitost redukˇcn´ıho operátoru dostateˇcnˇe vysok´ a, b´ yvá v´ yhodné redukci v´ıce prvk˚ u paralelizovat, ˇc´ımˇz lze dosáhnout zaj´ımavého (ideálnˇe lineárn´ıho) zrychlen´ı. Samozˇrejmˇe je nutné br´ at v u ´vahu vhodnou granularitu a ˇskálovatelnost problému.

2

Sekvenˇ cn´ı a paraleln´ı redukce

Obecnou redukci v´ıce operand˚ u lze definovat následovnˇe: ’ Necht je d´ ano vstupn´ı pole X = {x0 , x1 , ..., xn−1 } prvk˚ u mnoˇziny D a binárn´ı operace ⊕ nad D. Pak c´ılem redukce je vypoˇc´ıtat hodnotu S = x0 ⊕ x1 ⊕ ... ⊕ xn−1

(1)

napˇr´ıklad tak, je je uvedeno v algoritmu 1. Algoritmus 1 Trivi´ aln´ı sekvenˇcn´ı redukce S←0 for i = 0 to n − 1 do S = S ⊕ X[i] end for Doln´ı i horn´ı mez tohoto problému je SL(n) = SU (n) = Θ(n), je-li problém ˇreˇsen sekvenˇcnˇe. Vhodnou paralelizac´ı redukce vˇsak lze celou operaci provést v ˇcase O(log n) pˇri zachován´ı cenové optimality, jak bylo diskutov´ ano v kapitole zab´ yvaj´ıc´ı se anal´ yzou ˇcasové sloˇzitosti paraleln´ıch algoritm˚ u. Pˇr´ıklady implementace paraleln´ı redukce na r˚ uzn´ ych paraleln´ıch systémech jsou uvedeny na obrázku 1. Jak je patrné, vˇsechny systémy byly schopny z redukovat 8 hodnot, ve 3 kroc´ıch, ˇcili v logaritmickém ˇcase. Pseudok´ od paraleln´ı redukce implementované na EREW PRAM je uveden v algoritmu 2. Algoritmus 2 Trivi´ aln´ı paraleln´ı redukce for j = 1, ..., dlog ne do sequentially for all i = 0 to n − 1 step 2j do in parallel Pi : X[i] = X[i] ⊕ X[i + 2j−1 ] end for end for S ← X[0]

3

Sekvenˇ cn´ı a paraleln´ı prefixov´ a redukce

Prefixová redukce (prefixov´ y souˇcet) je zobecnˇen´ım redukce diskutované v kapitole 2 a má stejné ˇcasové charakteristiky. Zat´ımco u klasické redukce je v´ ysledkem operace pouze jedna hodnota, u prefixové redukce n hodnot dostaneme po ukonˇcen´ı v´ ypoˇctu n v´ ysledk˚ u. ´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463

Sekvenˇcn´ı a paraleln´ı prefixová redukce

4

Obrázek 1: Implementace paraleln´ı redukce na r˚ uzn´ ych typech paraleln´ıch systém˚ u [1] . Mˇejme vstupn´ı pole X = x0 , x1 , ..., xn−1 z mnoˇziny D a asociativn´ı binárn´ı operaci ⊕ nad D. V´ ystupem v´ ypoˇctu je stejnˇe velké pole Y , kde yi je rovno redukci poˇcáteˇcn´ıch i hodnot z X. ˇ u Cili ´kolem je vypoˇc´ıtat pole Y = y0 , y1 , ..., yn−1 vˇsech prefix˚ u pole X tak, ˇze yi = x0 ⊕ x1 ⊕ ... ⊕ xi , jak je naznaˇceno no obr´ azku 2.

Obr´ azek 2: Vstup a v´ ystup prefixové redukce [1] . Pro jednoduchost budeme v dalˇs´ıch kapitolách jako redukˇcn´ı operátor uvaˇzovat souˇcet, nebude-li ˇreˇceno jinak.

3.1

Sekvenˇ cn´ı prefixov´ y souˇ cet

ˇ Sekvenˇcn´ı prefixov´ y souˇcet je velmi triviáln´ım algoritmem a nepotˇrebuje bliˇzˇs´ıho zkoumán´ı. Casov´ a sloˇzitost je opˇet Θ(n) a jeho pseudok´ od je uveden v algoritmu 3. Algoritmus 3 Sekvenˇcn´ı prefixov´ a redukce Require: i : int; sum, X[n], Y[n] : D sum ← X[0]; Y [0] ← sum for i = 1 to n − 1 do sum = sum ⊕ X[i] Y [i] ← sum end for



3.2

5

Paraleln´ı prefixov´ y souˇ cet na CdTn

Implementace paraleln´ıho prefixového souˇctu (PPS) na topologii d-´ arn´ıho stromu CdTn je jiˇz daleko zaj´ımavˇejˇs´ı. Pˇredpokl´ adejme ICNW nepˇr´ımého stromu kde koncové listové uzly obsahuj´ı hodnoty, z nichˇz má b´ yt spoˇcten PPS. Pak PPS N vstupn´ıch hodnot v listech binárn´ıho stromu CBT v´ yˇsky h(CBT ) lze vypoˇc´ıtat ve 2h(CBT ) kroc´ıch. Je-li CBT u ´pln´ y, pak PPS potˇrebuje O(log N ) krok˚ u. Celá operace PPS se na CBT rozloˇz´ı do nˇekolika vzestupných a sestupných vln. Kaˇzdá vzestupná vlna vygeneruje dalˇs´ı vzestupnou vlnu (pokud jsme jiˇz nedosáhli koˇrene stromu) a h(CBT ) sestupn´ ych vln.

Obr´ azek 3: Vzestupné a sestupné vlny na CdT [1] . Pˇri vzestupné vlnˇe se rodiˇcovskému listu odes´ılá souˇcet hodnot pˇricházej´ıc´ıch od syn˚ u. Zároveˇ n je generována sestupn´ a vlna tak, jak je patrné z obrázku 3. Hodnoty, které v rámci sestupn´ ych vln doraz´ı aˇz ke koneˇcn´ ym list˚ um jsou pˇriˇcteny k jejich aktuáln´ı hodnotˇe. Po doznˇen´ı vˇsech vln obsahuj´ı koncové listové uzly kompletn´ı PPS. Cel´ y algoritmus je ilustrován na obrázku 4.

Obr´ azek 4: Paraleln´ı prefixov´ y souˇcet na CBT [1] .



3.3

6

Paraleln´ı prefixov´ y souˇ cet na Qn

Paraleln´ı prefixov´ y souˇcet na hyperkrychli je implementován jako jednoduché rozˇs´ıˇren´ı algoritmu vys´ılán´ı vˇsichni-ke-vˇsem. Pˇredpokl´ adejme ˇze PPS bude sˇc´ıtat N hodnot. Dále pˇredpokládejme binárn´ı hyperkrychli Qn kde n = dlog N e. PPS pak bude pomoc´ı algoritmu 4 spoˇc´ıtán v ˇcase O(log N ). Princip v´ ypoˇctu je jednoduch´ y. Kaˇzd´ y procesor Pi bude obsahovat dva pomocné registry: zelený a ˇzlutý. Nejprve budou oba registry v daném procesoru inicializovány stejnou vstupn´ı hodnotou. Poté následuje n paraleln´ıch f´ az´ı, ve kter´ ych si procesory vzájemnˇe vymˇen´ı obsahy zelen´ ych registr˚ u a pˇriˇctou je k obsah˚ um sv´ ych vlastn´ıch zelen´ ych registr˚ u. Procesor, kter´ y má v rámci dimenze, po které data putovala, vyˇsˇs´ı adresu, pˇriˇcte pˇr´ıchoz´ı hodnotu také ke svému ˇzlutému registru. Po vykonán´ı vˇsech n f´ az´ı, pˇri kter´ ych byla data zas´ılána postupnˇe pˇres vˇsechny dimenze, budou ˇzluté registry procesor˚ u obsahovat kompletn´ı hodnoty PPS. Adresy konkrétn´ıch procesor˚ u pˇredstavuj´ı indexy v´ ysledk˚ u v pomyslném v´ ystupn´ım poli. Algoritmus 4 Paraleln´ı prefixov´ y souˇcet na Qn Require: i : int; zeleny, zluty, X[N] : D for all Pi , i = 0, ..., 2n − 1 do in parallel zeleny ← zluty ← X[i] for j = 0 to n − 1 do sequentially send zelenyi → Pi XOR 2j receive novyzeleny ← Pi XOR 2j zelenyi = zelenyi + novyzeleny if i XOR 2j < i then zlutyi = zlutyi + novyzeleny end if end for end for Cel´ y postup je ilustrov´ an na obr´ azku 5.

3.4

Paraleln´ı prefixov´ y souˇ cet na EREW PRAM

V pˇr´ıpadˇe paraleln´ıho prefixového souˇctu na EREW PRAM si budeme demonstrovat dva typy vhodn´ ych algoritm˚ u. V prvn´ım pˇr´ıpadˇe se bude jednat o neˇ sk´ alovan´ y PPS kde pˇredpoklád´ ame, ˇze paraleln´ı systém disponuje stejn´ ym mnoˇzstv´ım procesor˚ u, jako je poˇcet sˇc´ıtan´ ych hodnot. Je zˇrejmé, ˇze takov´ y algoritmus bude cenovˇe neoptimáln´ı a tud´ıˇz neefektivn´ı a proto si zde uvedeme také optimáln´ı ˇ sk´ alovan´ y PPS. 3.4.1

Neˇ sk´ alovan´ y paraleln´ı prefixov´ y souˇ cet na EREW PRAM

Mˇejme n procesor˚ u P0 , ..., Pn−1 a pole X = x0 , ..., xn−1 uloˇzené ve sd´ılené pamˇeti M [0], ..., M [n−1]. Kaˇzd´ y Pi má pomocn´ y registr yi . Neˇsk´ alovan´ y v´ ypoˇcet PPS na EREW PRAM s ˇcasovou sloˇzitost´ı O(log n) je uveden v algoritmu 5 a jeho pr˚ ubˇeh je ilustrován na obrázku 6. 3.4.2

ˇ alovan´ Sk´ y paraleln´ı prefixov´ y souˇ cet na EREW PRAM

Jak je patrné z obr´ azku 6, velké mnoˇzstv´ı procesor˚ u nemá v pr˚ ubˇehu neˇskálovaného EREW PRAM PPS dostatek uˇziteˇcné pr´ ace, ˇc´ımˇz za pˇredpokladu malé ˇcasové sloˇzitosti redukˇcn´ı operace nar˚ ust´ a pod´ıl paraleln´ı reˇzie ve v´ ypoˇctu a t´ım i paraleln´ı cena. Abychom dosáhli efektivn´ı paralelizace, bude zapotˇreb´ı zvolit lepˇs´ı granularitu a t´ım zajistit dostatek práce pro vˇsechny procesory v pr˚ ubˇehu celého v´ ypoˇctu. O to se snaˇz´ı ˇsk´ alovan´ a varianta EREW PRAM PPS. ´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463


7

Obr´ azek 5: Paraleln´ı prefixov´ y souˇcet na Qn [1] .

Obr´ azek 6: Neˇsk´ alovan´ y paraleln´ı prefixov´ y souˇcet na EREW P RAM [1] . Uvaˇzujme vstupn´ı pole X = {x0 , x1 , ..., xn−1 } a p procesor˚ u P0 , ..., Pp−1 . Necht’ q = np . Rozdˇel´ıme X do p subpol´ı X0 , ..., Xp−1 po q prvc´ıch a pˇridˇel´ıme kaˇzdé Xi pˇr´ısluˇsnému Pi . V prvn´ı f´ azi kaˇzd´ y Pi vypoˇcte prefixov´ y souˇcet nad Xi sekvenˇcnˇe. Tato fáze zabere O( np ) krok˚ u. Ve druhé f´ azi bude vypoˇcten prefixov´ y souˇcet nad prav´ ymi krajn´ımi hodnotami vˇsech p subpol´ı Xi . Jelikoˇz je poˇcet subpol´ı stejn´ y jako poˇcet procesor˚ u, lze tuto fázi implementovat pomoc´ı neˇskálovaného EREW PRAM PPS a provést ji v O(log p) kroc´ıch. V závˇereˇcné tˇret´ı f´ azi bude ke vˇsem hodnotám subpol´ı Xi , i = 1, ..., p−1 s v´ yjimkou nejpravˇejˇs´ıho prvku pˇriˇctena hodnota nejpravˇejˇs´ıho prvku subpole Xi−1 . Tato operace bude trvat opˇet O( np ) krok˚ u. Po této operaci bude pole X obsahoval kompletn´ı PPS vˇsech vstupn´ıch hodnot. Celková ˇcasov´ a n sloˇzitost v´ ypoˇctu bude T (n, p) = O( p + log p), coˇz za pˇredpokladu n p zaruˇcuje cenovou opti´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463


Algoritmus 5 Neˇsk´ alovan´ y paraleln´ı prefixov´ y souˇcet na EREW P RAM Require: i, j : int; yi , M[n] : D for all Pi , i = 0 to n − 1 do in parallel yi ← M [i] end for for j = 0 to dlog ne − 1 do sequentially for all Pi , i = 2j to n − 1 do in parallel yi = yi + M [i − 2j ] end for for all Pi , i = 2j to n − 1 do in parallel M [i] = yi end for end for malitu v´ ypoˇctu i pˇri n´ızké ˇcasové sloˇzitosti redukˇcn´ı operace. Pseudokód ˇsk´ alovaného PPS na EREW PRAM je uveden v algoritmu 6. ˇ alovan´ Algoritmus 6 Sk´ y paraleln´ı prefixov´ y souˇcet na EREW P RAM Require: i, j : int; Si [q], X[n], Z[p] : D for all Pi , i = 0 to p − 1 do in parallel Pi sekvenˇcnˇe v´ ypoˇcte pole Si = prefixov´ y souˇcet nad Xi Z[i] ← Si [q − 1] end for vˇsechny Pi vypoˇctou paralelnˇe PPS nad Z pomoc´ı algoritmu 5. for all Pi , i = 1 to p − 1 do in parallel for j = 0 to j < q − 1 do Si [j] = Si [j] + Z[i − 1] end for Si → Xi end for Pr˚ ubˇeh algoritmu 6 je ilustrov´ an na obrázku 7.

ˇ alovan´ Obr´ azek 7: Sk´ y paraleln´ı prefixov´ y souˇcet na EREW P RAM [1] .


8

Aplikace paraleln´ı prefixové redukce

3.5

9

Segmentov´ y paraleln´ı prefixov´ y souˇ cet

Segmentov´ y paraleln´ı prefixov´ y souˇcet (SPPS) je takovou modifikac´ı základn´ıho algoritmu, kdy je vstupn´ı pole o velikosti n rozdˇeleno na s nestejnˇ e velk´ ych segment˚ u Si a prefixové souˇcty jsou spoˇcteny pro segmenty. Tabulka 1: Vstupn´ı a v´ ystupn´ı pole segmentového PS Vstup Výstup

|2 |2

1 3

3 6

5 11

|2 |2

7 9

3 12

|9 |9

4 13

5 18

6 24

|2 |2

8 10

4 14

3 17

1| 18 |

Znaménko | u operand˚ u v tabulce 1 pˇredstavuje krajn´ı hodnoty u hranic segment˚ u. ˇ sen´ı tohoto problému je nˇekolik. Uvaˇzujme p jako poˇcet procesor˚ Reˇ u Pi . Je-li s = p pak lze jednotlivé segmenty Si pˇridˇelit procesor˚ um Pi , které nad nimi spoˇctou prefixov´ y souˇcet v ˇcase Θ(qi ) kde qi je poˇcet prvk˚ u v segmentu Si . Jelikoˇz maj´ı segmenty obecnˇe r˚ uznou velikost (a v extrémn´ım pˇr´ıpadˇe budou vˇsechny prvky obsaˇzeny v jednom segmentu), bude celkov´ y ˇcas v´ ypoˇctu T (n, p) = Θ(max{qi }) = O(n). Je-li n = p pak lze SPPS vypoˇc´ıst v celkovém ˇcase T (n, p) = O(log n) pomoc´ı algoritmu 5 a modifikovaného oper´ atoru ⊕ jehoˇz chován´ı je popsáno v tabulce 2. Tabulka 2: Modifikovan´ y redukˇcn´ı operátor ⊕ a a

4

b a⊕b |(a ⊕ b)

b |b b

Aplikace paraleln´ı prefixov´ e redukce

V´ yznam prefixového souˇctu (PS) nen´ı ani tak v implementaci samotného algoritmu ale v tom, ˇze PS slouˇz´ı jako z´ aklad dalˇs´ıch, sloˇzitˇejˇs´ıch algoritm˚ u. V následuj´ıc´ıch kapitolách si pˇredstav´ıme nˇekteré z nich.

4.1

Zhuˇ st’ovac´ı probl´ em a paraleln´ı RadixSort

Jednou z typick´ ych aplikac´ı PS je implementace zhuˇst’ovac´ıho problému zm´ınˇeného v kapitole pojednávaj´ıc´ı o smˇerov´ an´ı v ICNW. Uvaˇzujme, ˇze jist´ a podmnoˇzina z p procesor˚ u pˇripojen´ ych ke vstup˚ um nepˇr´ımé v´ıcestupˇ nové s´ıtˇe typu n-rozmˇern´ y mot´ ylek oBFn m´ a paket, kter´ y je nutno dopravit na druhou v´ ystupn´ı stranu s´ıtˇe tak, aby i-t´ y paket, poˇc´ıt´ ano na vstupech odshora, skonˇcil na i-tém v´ ystupn´ım vodiˇci shora. D´ıky aplikaci PPS lze u zhuˇst’ovac´ıho problému rychle (v ˇcase O(log p)) spoˇc´ıst indexy c´ılov´ ych uzl˚ u, tak jak je naznaˇceno na obr´ azku 8. Kaˇzd´ y uzel, kter´ y drˇz´ı paket bude obsahovat také hodnotu 1 ve vstupn´ım poli PPS, uzel bez paketu bude obsahovat hodnotu 0. Z tˇechto hodnot bude spoˇcten PS (napˇr. pomoc´ı PPS implementovaného na stromˇe vnoˇreného do mot´ ylka) ˇc´ımˇz bude po závˇereˇcné normalizaci index˚ u kaˇzd´ y uzel vˇedˇet, kam má poslat sv˚ uj paket, aby byly na konci permutace zhuˇstˇeny do horn´ı poloviny s´ıtˇe. Samotn´ y zhuˇst’ovac´ı problém je pak základem dalˇs´ıho algoritmu urˇceného pro paraleln´ı tˇr´ıdˇen´ı binárn´ıch hodnot nazvaného RadixSort. Principem algoritmu je postupné tˇr´ıdˇen´ı na základˇe zkoumán´ı hodnot bit˚ u jednotliv´ ych ˇr´ ad˚ u. Necht’ X je posloupnost n k-bitov´ ych ˇc´ısel, nult´ y bit je vpravo. RadixSort je tˇr´ıdic´ı algoritmus, kter´ y nen´ı zaloˇzen na porovn´ av´ an´ı dvojice ˇc´ısel, ale na permutaci, kterou znaˇc´ıme Split(X,i): ˇc´ısla s ´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463


10

Obrázek 8: Zhuˇst’ovac´ı problém na oBFn . a) poˇcáteˇcn´ı hodnoty pˇr´ıznak˚ u a jeden moˇzn´ y nepˇr´ım´ y strom, b) pole pˇr´ıznak˚ u po PPS, c) koneˇcné hodnoty index˚ u c´ılov´ ych ˇrádk˚ u [1] . nulov´ ym i-t´ ym bitem jsou zhuˇstˇena doleva, ˇc´ısla s jedniˇckov´ ym i-t´ ym bitem jsou zhuˇstˇena doprava tak, jak je ilustrov´ ano na obr´ azku 9. Algoritmus 7 Implementace paraleln´ıho tˇr´ıdˇen´ı RadixSort Require: i : int; X[0, ..., 2k − 1] : D for i = 0 to k − 1 do sequentially Split(X,i) end for

Obrázek 9: Implementace paraleln´ıho RadixSortu pomoc´ı zhuˇst’ovac´ıho problému [1] .

4.2

Bin´ arn´ı sˇ c´ıtaˇ cka

Dalˇs´ı z moˇzn´ ych aplikac´ı PS je rychl´ a binárn´ı sˇc´ıtaˇcka. Mˇejme 2 n-bitov´ a bin´ arn´ı slova kter´ a chceme seˇc´ıst po bitech a p = n procesor˚ u. D´ıky existenci pˇrenosu mezi vyˇsˇs´ımi ˇr´ ady pˇri sˇc´ıt´ an´ı bit˚ u binárn´ıch slov je doln´ı i horn´ı sekvenˇcn´ı mez tohoto ´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463


11

problému SL(n) = SU (n) = Θ(n). Paralelizac´ı jsme schopni tento problém vyˇreˇsit v ˇcase T (n, p) = O(1) + O(log n). Princip algoritmu je následuj´ıc´ı: Mˇejme dvˇe bin´ arn´ı slova o velikosti n organizovaná jako bitová pole X = {x0 , ..., xn−1 } a Y = {y0 , ..., yn−1 }. V´ ystupem bude souˇcet tˇechto slov uloˇzen´ y v n-bitovém slovu Z = {z0 , ..., zn−1 }. Postup v´ ypoˇctu bude n´ asleduj´ıc´ı: 1. Vˇsechny procesory Pi vypoˇctou paralelnˇe obsah slova B = {b0 , ..., bn−1 } tak, ˇze porovnaj´ı bity xi a yi pomoc´ı n´ıˇze uvedeného pˇredpisu: (

bi =

(g)enerate , (s)top

if xi = yi = 1

if xi = yi = 0, (p)ropagate

jinak.

Doba trv´ an´ı této operace bude T (n, p) = O(1). 2. Pomoc´ı PPS a oper´ atoru ⊕ z tabulky 3 nad polem B vypoˇcti pole B 0 v ˇcase T (n, p) = O(log n). Tabulka 3: Modifikovan´ y redukˇcn´ı operátor pro binárn´ı sˇc´ıtaˇcku ⊕ s p g

s s s g

p s p g

g s g g

3. Vˇsechny procesory Pi vypoˇctou pˇrenosové slovo C = {c0 , ..., cn−1 } tak, ˇze c0 = 0 a ci = 1 ⇐⇒ b0i−1 = g v ˇcase T (n, p) = O(1). 4. Vˇsechny procesory Pi vypoˇctou v´ ysledné slovo Z = {z0 , ..., zn−1 } tak, ˇze zi = xi ⊕ yi ⊕ ci kde operátor ⊕ pˇredstavuje bin´ arn´ı souˇcet bez pˇrenosu. Doba této operace bude T (n, p) = O(1). Cel´ y algoritmus je ilustrov´ an na obrázku 10.

Obr´ azek 10: Implementace paraleln´ı binárn´ı sˇc´ıtaˇcky [1] .

4.3

Paraleln´ı QuickSort

Vyuˇzit´ı SPPS si uk´ aˇzeme na pˇr´ıkladu jedné z moˇzn´ ych implementac´ı paraleln´ıho tˇr´ıdic´ıho algoritmu QuickSort. Pˇredpokl´ adejme nesetˇr´ıdˇené pole A[n] a p = n procesor˚ u. Princip ˇcinnosti algoritmu je pak následuj´ıc´ı: ´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463


Algoritmus 8 Implementace paraleln´ıho tˇr´ıdic´ıho algoritmu QuickSort pomoc´ı SPPS Require: i : int; e: bool; A[n], Sn [n], F [n], bs : D start: for all i = 0 to n − 2 do in parallel fi = (a + i ≤ ai+1 ) end for Proved’ paraleln´ı redukci hodnot fi pomoc´ı operace AND a v´ ysledek uloˇz do e. if e = T RU E then EXIT end if for all aktu´ aln´ı segmenty S v A do in parallel vyber pivot bs ← Si [0] poˇsli bs vˇsem procesor˚ um uvnitˇr segmentu. for all ai ∈ S do in parallel gi = (ai <> bs ), kde gi ∈ {0 <0 ,0 =0 ,0 >0 } /* kaˇzdý S rozdˇel´ıme na 3 podsegmenty S< , S= a S> */ pomoc´ı SPPS vypoˇcti nové indexy prvk˚ u ai : gi =0 <0 uvnitˇr vˇsech S poˇsli hodnoty maxim´ aln´ıho indexu (= S< ) uvnitˇr vˇsech S. /* |S< je rovno indexu zaˇc´ atku S= */ pomoc´ı SPPS vypoˇcti nové indexy prvk˚ u ai : gi =0 =0 uvnitˇr vˇsech S poˇsli hodnoty maxim´ aln´ıho indexu (= S= ) uvnitˇr vˇsech S. /* |S< + |S= je rovno indexu zaˇc´ atku S> */ pomoc´ı SPPS vypoˇcti nové indexy prvk˚ u ai : gi =0 >0 uvnitˇr vˇsech S permutac´ı segmentu S vytvoˇr 3 nové segmenty S = {S< |S= |S> } end for end for goto start


12

Kontroln´ı otázky

5

13

Kontroln´ı ot´ azky • Jak´ y je rozd´ıl mezi redukc´ı a prefixovou redukc´ı? • Uved’te alespoˇ n 3 pˇr´ıklady implementace paraleln´ı redukce na r˚ uzn´ ych typech paraleln´ıch systému. • Uved’te alespoˇ n 3 pˇr´ıklady implementace paraleln´ı prefixové redukce na r˚ uzn´ ych typech paraleln´ıch systému. • Jak´ y je princip segmentové paraleln´ı prefixové redukce? • Uved’te nˇekteré moˇzné aplikace paraleln´ı prefixové redukce.


REFERENCE

Reference ˇ [1] Pavel Tvrd´ık. Paraleln´ı systémy a algoritmy. Vydavatelstv´ı CVUT, Praha, 2005.


14

PARALELNÍ PROCESY A PROGRAMOVÁNÍ

Recommend Documents