´ ´I PARALELN´I PROCESY A PROGRAMOVAN 8 Paraleln´ı v´ ypoˇ cetn´ı modely Ing. Michal Bliˇ zn ˇ´ ak, Ph.D.
Zl´ın 2013
Tento studijn´ı materi´ al vznikl za finanˇcn´ı podpory Evropsk´eho soci´aln´ıho fondu (ESF) a rozpoˇctu ˇcesk´e republiky v r´amci ˇreˇsen´ı projektu: CZ 1.07/2.2.00/15.0463, MOD´ ´ ´ ˚ ´ ERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD
OBSAH
1
Obsah 1 Parallel Random Access Machine (PRAM) model 1.1 Vlastnosti PRAM modelu . . . . . . . . . . . . . . . 1.2 Omezen´ı PRAM modelu . . . . . . . . . . . . . . . . 1.2.1 Soubˇeˇzn´ y pˇr´ıstup do sd´ılen´e pamˇeti . . . . . 1.3 V´ ypoˇcetn´ı s´ıla PRAM podmodel˚ u . . . . . . . . . . 1.4 Cena, optimalita a efektivnost PRAM algoritm˚ u . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
3 4 4 4 5 6
2 Simulace velk´ eho PRAM na mal´ em PRAM
6
3 Simulace silnˇ ejˇ s´ıho PRAM na slabˇ s´ım PRAM
7
4 Asynchronn´ı PRAM (APRAM) model 9 4.1 APRAM v´ ypoˇcet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4.2 V´ ykonostn´ı parametry modelu APRAM . . . . . . . . . . . . . . . . . . . . . . . . . 10 5 Kontroln´ı ot´ azky
´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
11
OBSAH
ˇ Y ´ OBSAH PREDN ˇ ´ SKY ˇ STRUCN A Parallel Random Access Machine (PRAM) model Simulace velk´eho PRAM na mal´em PRAM Simulace silnˇejˇs´ıho PRAM na slabˇs´ım PRAM Asynchronn´ı PRAM (APRAM) model
MOTIVACE Paraleln´ı v´ypoˇcetn´ı modely slouˇz´ı jako teoretick´e r´amce stanovuj´ıc´ı podm´ınky pro v´ ypoˇcet ˇcasov´e sloˇzitosti paraleln´ıch algoritm˚ u, kterou kromˇe poˇctu procesor˚ u a povahy algoritmu ovlivˇ nuje tak´e pouˇzit´ a pamˇet’ov´ a architektura a zp˚ usob pˇr´ıstupu do sd´ılen´ ych pamˇet’ov´ ych oblast´ı. Tato kapitola pojedn´ av´ a o modelu PRAM a jeho vlastnostech a deriv´atech.
C´IL Obezn´amit se s v´ ypoˇcetn´ım modelem PRAM a jeho z´akladn´ımi vlastnosti. Pochopit, jak jednotliv´e podmodely PRAM ovlivˇ nuj´ı ˇcasovou a prostorovou sloˇzitost paraleln´ıho algoritmu.
´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
2
Parallel Random Access Machine (PRAM) model
1
3
Parallel Random Access Machine (PRAM) model
PRAM model je jednoduch´ y model SIMD SMP syst´emu. Vych´az´ı z klasick´eho RAM (Random Access Machine) modelu, kter´ y je definov´an tˇemito vlastnostmi [1]: • Z´akladem RAM je v´ ypoˇ cetn´ı jednotka s uˇzivatelsky definovan´ ym programem. • Pro ˇcten´ı vstupn´ıch dat pouˇz´ıv´ a vstupn´ı p´ asku a pro z´apis v´ ystupn´ıch dat v´ ystupn´ı p´ asku. • Poˇcet lok´ aln´ıch pamˇet’ov´ ych bunˇek je neomezen´ y. • Pamˇet’ov´e buˇ nky jsou schopny obsahovat ˇc´ısla neomezen´ e velikosti. • Syst´em podporuje instrukce pro aritmetick´e, logick´e a I/O operace a vˇetven´ı toku programu. • V´ ypoˇcet zaˇcne prvn´ı instrukc´ı a skonˇc´ı po proveden´ı instrukce HALT. • Vˇsechny instrukce trvaj´ı jednotkov´ y ˇcas bez ohledu na d´elku operand˚ u. ˇ • Casov´ a sloˇ zitost je definov´ ana jako poˇcet proveden´ ych instrukc´ı. • Pamˇ et’ov´ a sloˇ zitost je definov´ ana jako poˇcet pouˇzit´ ych pamˇet’ov´ ych bunˇek. PRAM model je zobecnˇen´ım RAM modelu; m´ısto jednoho procesoru bude pouˇzito v´ıce procesor˚ u pˇripojen´ ych ke spoleˇcn´e pamˇeti. Tyto procesory budou pracovat synchronnˇe jako u SIMD poˇc´ıtaˇce. Dalˇs´ı vlastnosti specifick´e pro PRAM model jsou: • PRAM obsahuje neomezen´ y poˇcet procesor˚ u P1 , P2 , ..., Pp . • Pamˇet’ je tvoˇrena neomezen´ ym poˇctem sd´ılen´ ych pamˇet’ov´ ych bunˇek M [1], M [2], ..., M [n]. • Kaˇzd´ y Pi m´ a vlastn´ı neomezenou lok´ aln´ı pamˇ et’ a zn´a sv˚ uj index i. • Kaˇzd´ y procesor m˚ uˇze pˇristupovat to kter´ekoliv sd´ılen´e pamˇet’ov´e buˇ nky v jednotkov´ em ˇ case. • Vstup a v´ ystup PRAM algoritmu se skl´ad´a z n/n0 poloˇzek uloˇzen´ ych ve sd´ılen´e pamˇeti. • PRAM instrukce tvoˇr´ı vˇzdy 3-f´ azov´e cykly: ˇ data ze sd´ılen´e pamˇeti do sv´eho registru 1. Cti 2. Proved’ lok´ aln´ı v´ ypoˇcet 3. Zapiˇs data ze sv´eho registru do sd´ılen´e pamˇeti • Procesory prov´ adˇej´ı tyto PRAM instrukce synchronnˇ e. • Konflikty soubˇeˇzn´eho ˇcten´ı ˇci z´ apisu do sd´ılen´e pamˇeti je zapotˇreb´ı explicitnˇe oˇsetˇrit. • Procesory mohou komunikovat pouze ˇcten´ım/z´apisem do sd´ılen´e pamˇeti. • P1 m´a speci´ aln´ı aktivaˇ cn´ı registr obsahuj´ıc´ı nejvyˇsˇs´ı index aktivn´ıho procesoru: 1. Na poˇc´ atku je aktivn´ı pouze P1 2. P1 spoˇc´ıt´ a poˇcet poˇzadovan´ ych aktivn´ıch procesor˚ u a nastav´ı aktivaˇcn´ı registr 3. Pot´e zaˇcnou prov´ adˇet sv´e programy ostatn´ı aktivn´ı procesory • V´ ypoˇcet bˇeˇz´ı aˇz do doby, kdy se P1 zastav´ı (v t´e dobˇe jiˇz budou vˇsechny ostatn´ı procesory neaktivn´ı) • Paraleln´ı ˇ casov´ a sloˇ zitost je rovna ˇcasu v´ ypoˇctu P1 . • Prostorov´ a sloˇ zitost je rovna poˇctu pouˇzit´ ych pamˇet’ov´ ych bunˇek. ´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
Parallel Random Access Machine (PRAM) model
1.1
4
Vlastnosti PRAM modelu
Aˇckoliv PRAM model ignoruje urˇcit´ a omezen´ı a detaily niˇzˇs´ıch vrstev paraleln´ıho syst´emu, je pro tv˚ urce paraleln´ıch algoritm˚ u d˚ uleˇzit´ y, protoˇze: • je pˇ rirozen´ y, nebot’ poˇcet operac´ı proveden´ ych v jednom cyklu na p procesorech je nejv´ yˇse p. • je v´ ypoˇ cetnˇ e siln´ y, nebot’ jak´ ykoliv procesor m˚ uˇze ˇc´ıst ˇci zapisovat do sd´ılen´e pamˇet’ov´e buˇ nky v jednotkov´em ˇcase. • je jednoduch´ y, nebot’ zanedb´ av´ a komunikaˇcn´ı a synchronizaˇcn´ı reˇzie. • m˚ uˇze slouˇzit jako zkuˇ sebn´ı model - neexistuje-li pro dan´ y probl´em rozumn´ y/efektivn´ı PRAM model, nem´ a smysl se snaˇzit vym´ yˇslet rozumn´ y/efektivn´ı ˇreˇsen´ı na re´aln´em paraleln´ım syst´emu. • je uˇ ziteˇ cn´ y, nebot’ je idealizac´ı existuj´ıc´ıch paraleln´ıch poˇc´ıtaˇc˚ u se sd´ılenou pamˇet´ı (SMP).
1.2
Omezen´ı PRAM modelu
Prakticky pouˇziteln´e PRAM algoritmy mus´ı poˇc´ıtat s omezen´ımi, kter´ ymi je nutn´e korigovat nˇekter´e velkorys´e pˇredpoklady z´ akladn´ıho PRAM modelu a to zejm´ena: • Omezen´ı velikosti slova: velikost slova procesor˚ u nebo pamˇet’ov´a buˇ nky je omezena. • Mal´ e PRAM: poˇcet procesor˚ u je v re´aln´em svˇete omezen. Pokud je poˇcet procesor˚ u PRAM modelu vyˇsˇs´ı, fyzick´e procesory se mus´ı mezi nimi ”pˇrep´ınat”v reˇzimu sd´ılen´ı ˇcasu. • PRAM s malou pamˇ et´ı: poˇcet bunˇek sd´ılen´e pamˇeti je omezen. • Konflikty pˇ r´ıstupu do pamˇ eti: pro souˇcasn´ y pˇr´ıstup z v´ıce procesor˚ u do jedn´e sd´ılen´e pamˇet’ov´e buˇ nky jsou definov´ any jasn´e omezuj´ıc´ı podm´ınky, kter´ ym se budeme vˇenovat v n´asleduj´ıc´ı kapitole. 1.2.1
Soubˇ eˇ zn´ y pˇ r´ıstup do sd´ılen´ e pamˇ eti
Z hlediska nutnosti oˇsetˇren´ı soubˇeˇzn´eho pˇr´ıstupu ke sd´ılen´ ym pamˇet’ov´ ym buˇ nk´am bylo definov´ ano ’ nˇekolik podmodel˚ u stanovuj´ıc´ıch podm´ınky omezuj´ıc´ı soubˇeˇzn´e pˇr´ıstupy k jedn´e pamˇet ov´e buˇ nce. Jedn´a se o podmodely ˇ adn´ • Exclusice Read Exclusive Write (EREW) PRAM - Z´ ym dvˇema procesor˚ um nen´ı povoleno ˇc´ıst ani zapisovat do t´eˇze pamˇet’ov´e buˇ nky souˇcasnˇe. • Concurent Read Exclusive Write (CREW) PRAM - Souˇcasn´e ˇcten´ı t´eˇze pamˇet’ov´e buˇ nky je povole, zapisovat vˇsak m˚ uˇze v dan´ y okamˇzik pouze jeden procesor. ˇ ıst sd´ılenou pamˇet’ovou buˇ • Exclusive Read Concurent Write (ERCW) PRAM - C´ nku m˚ uˇze v dan´ y omakˇzik pouze jeden procesor, souˇcasn´e z´apisy do sd´ılen´e pamˇeti je povoleno v´ıc procesor˚ um. • Concurent Read Concurent Write (CRCW) PRAM - Jsou povolena jak souˇcasn´ a ’ ˇcten´ı, tak i z´ apisy do sd´ılen´e pamˇet ov´a buˇ nky. Je zˇrejm´e ˇze pˇr´ıpady soubˇeˇzn´eho z´apisu (Concurent Write) je nutn´e d´ale upˇresnit pomoc´ı rozˇsiˇruj´ıc´ıch podmodel˚ u: ´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
Parallel Random Access Machine (PRAM) model
5
• Prioritn´ı (Priority) CRCW - Procesor˚ um jsou pˇridˇeleny pevn´e priority a fyzick´ y z´apis je povolen pouze procesoru s nejvyˇsˇs´ı prioritou ve skupinˇe ˇzadatel˚ u. • N´ ahodn´ y (Arbitrary) CRCW - Ukonˇcit z´apis je povoleno n´ahodnˇe vybran´emu procesoru. • Shodn´ y (Common) CRCW - Existuje-li v´ıce ˇz´adost´ı o z´apis do dan´e pamˇet’ov´e buˇ nky, mus´ı b´ yt zapisovan´ a hodnota ve vˇsech ˇz´adostech shodn´a. V´ yˇse uveden´e podmodely ovlivˇ nuj´ı tak´e celkov´ y paraleln´ı ˇcas algoritmu. Uved’me si jednoduch´ y pˇr´ıklad. Pˇ r´ıklad Uvaˇzujme p procesorov´ y PRAM kde p < n a pole n nesetˇr´ıdˇen´ ych hodnot uloˇzen´ ych ve ´ sd´ılen´e pamˇeti obsahuj´ıc´ı n r˚ uzn´ ych poloˇzek. Procesor P1 vlastn´ı hodnotu x. Ukolem je ozn´ amit procesoru P1 , zda se hodnota x nal´ez´ a ve vstupn´ım poli. 1. EREW PRAM algoritmus: (a) Procesor P1 rozeˇsle procesor˚ um P2 , ..., Pp hodnotu x v log p kroc´ıch pomoc´ı bin´ arn´ı distribuce kopi´ı. (b) Kaˇzd´ y procesor provede lok´ aln´ı hled´an´ı v dn/pe poloˇzk´ach v dn/pe kroc´ıch. (c) Kaˇzd´ y procesor nastav´ı pˇr´ıznak Nalezeno a vˇsechny procesory povedou paraleln´ı redukci hodnot tˇechto pˇr´ıznak˚ u pomoc´ı bin´arn´ıho redukˇcn´ıho stromu v ˇcase O(log p). Celkov´ y paraleln´ı ˇcas je tedy T (n, p) = O(log p + n/p). ˇ sen´ı je podobn´e jako u EREW podmodelu pouze s t´ım 2. CREW PRAM algoritmus: Reˇ rozd´ılem, ˇze procesory P2 , ..., Pn si mohou naˇc´ıst hledanou hodnotu soubˇeˇznˇe ze sd´ılen´e pamˇet’ov´e buˇ nky v ˇcase O(1). Paraleln´ı ˇc´ as z´ avˇereˇcn´e redukce vˇsak z˚ ust´av´a stejn´ y a pro se nemˇen´ı ani asymptotick´e vyj´adˇren´ı celkov´eho paraleln´ıho ˇcasu, kter´e je tedy stejnˇe jako minule T (n, p) = O(log p+n/p). 3. Shodn´ y CRCW PRAM algoritmus: V t´eto modifikaci trv´a tak´e z´avˇereˇcn´ y krok algoritmu konstantn´ı ˇcas O(1) nebot’ ty procesory, kter´e nastavily pˇr´ıznak Nalezeno na hodnotu 1, mohou prov´est z´ apis do sd´ılen´e v´ ysledkov´e pamˇet’ov´e buˇ nky procesoru P1 souˇcasnˇe v jednom kroku. Celkov´ y paraleln´ı ˇcas pot´e bude T (n, p) = O(n/p), ˇc´ımˇz jsme se dostali k optim´aln´ımu ˇreˇsen´ı.
1.3
V´ ypoˇ cetn´ı s´ıla PRAM podmodel˚ u
Jak bylo patrn´e z pˇr´ıkladu v kapitole 1.2.1, omezen´ı uvalen´a na jednotliv´e podmodely PRAM ovlivˇ nuj´ı tak´e ˇcasovou sloˇzitost algoritm˚ u a proto m˚ uˇzeme hovoˇrit o v´ ypoˇcetn´ı s´ıle jednotliv´ ych PRAM podmodel˚ u. Definice 1 PRAM podmodel A je v´ ypoˇ cetnˇ e silnˇ ejˇ s´ı neˇz podmodel B, ps´ ano A ≥ B, jestliˇze jak´ykoliv algoritmus napsan´y pro PRAM poˇc´ıtaˇc B pobˇeˇz´ı na stejnˇe velk´em PRAM poˇc´ıtaˇci A beze zmˇeny a s t´ımt´eˇz paraleln´ım ˇcasem. Lemma 1 Prioritn´ı CRCW ≥ N´ ahodn´y CRCW ≥ Shodn´y CRCW ≥ CREW ≥ EREW
´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
Simulace velk´eho PRAM na mal´em PRAM
1.4
6
Cena, optimalita a efektivnost PRAM algoritm˚ u
Definice 2 Necht’ K je probl´em s mnoˇzinou vstupn´ıch dat o velikosti n. Pˇredpokl´ adejme, ˇze K lze ˇreˇsit na p-procesorov´em PRAM poˇc´ıtaˇci algoritmem A v ˇcase T (n, p). Pak ˇrekneme, ˇze 1. A je efektivn´ı, jestliˇze T (n, p) = O(logO(1) n) a C(n, p) = O(SU (n) logO(1) n) 2. A je cenovˇ e optim´ aln´ı, jestliˇze T (n, p) = O(logO(1) n) a C(n, p) = O(SU (n)) 3. A je plnˇ e paraleln´ı, jestliˇze T (n, p) = O(1) a p = O(SU (n)) Plnˇe paraleln´ı algoritmy jsou tedy cenovˇe optim´ aln´ı.
2
Simulace velk´ eho PRAM na mal´ em PRAM
Model PRAM neomezuje n´ avrh´ aˇre paraleln´ıch algoritm˚ u ani z hlediska poˇctu procesor˚ u ani z hlediska poˇctu sd´ılen´ ych pamˇet’ov´ ych bunˇek. Situace se vˇsak m˚ uˇze radik´alnˇe zmˇenit pˇri implementaci takov´eho PRAM algoritmu na re´aln´em PRAM poˇc´ıtaˇci (SMP), kter´ y nedisponuje potˇrebn´ ym poˇctem procesor˚ u nebo bunˇek sd´ılen´e pamˇeti. V takov´em pˇr´ıpadˇe je potˇreba pˇristoupit k simulaci velk´eho PRAM poˇc´ıtaˇce na mal´em. Vˇ eta 1 Pˇredpokl´ adejme, ˇze p0 < p. Uvaˇzujme algoritmus A, kter´y bˇeˇz´ı na p-procesorov´em PRAM v t kroc´ıch. Pak lze A simulovat na p’-procesorov´em PRAM v t0 = O(t · p/p0 ) kroc´ıch za pˇredpokladu, ˇze velikost sd´ılen´e pamˇeti je stejn´ a. D˚ ukaz. 1. Rozdˇelme p simulovan´ ych procesor˚ u do p0 skupin o velikosti p/p0 . 2. Pˇriˇrad’me kaˇzd´emu z p0 simuluj´ıc´ıch procesor˚ u jednu skupinu. 3. Kaˇzd´ y simuluj´ıc´ı procesor simuluje jeden krok sv´e skupiny procesor˚ u: (a) proveden´ım nejdˇr´ıve vˇsech jej´ıch operac´ı READ a lok´aln´ıch v´ ypoˇct˚ u, (b) proveden´ım jejich operac´ı WRITE pot´e. D˚ uleˇzit´ ym d˚ usledkem je, ˇze • Kaˇzd´ y PRAM algoritmus s cenou C(n, p) lze prov´est sekvenˇcnˇe v ˇcase T (n, 1) = C(n, p). • Pokud jsme navrhli PRAM algoritmus s cenou C(n, p) = o(SU (n)), pak jsme automaticky navrhli nov´ y nejlepˇs´ı sekvenˇcn´ı algoritmus. V pˇr´ıpadˇe, ˇze omezen´ı re´ aln´eho PRAM poˇc´ıtaˇce spoˇc´ıv´a v nedostateˇcn´em velikosti sd´ılen´e pamˇeti, je moˇzn´e chybˇej´ıc´ı pamˇet’ov´e buˇ nky simulovat v lok´aln´ı pamˇeti procesor˚ u. Simuluj´ıc´ı procesory tak budou simulovat jak procesory p˚ uvodn´ı, tak tak´e chybˇej´ıc´ı velkou sd´ılenou pamˇet’ pomoc´ı sv´ ych mal´ ych lok´ aln´ıch pamˇet´ı. Vˇ eta 2 Pˇredpokl´ adejme, ˇze m0 < m a uvaˇzujme algoritmus A, kter´y bˇeˇz´ı na p-procesorov´em PRAM s m pamˇet’ov´ymi buˇ nkami v t kroc´ıch. Pak lze A simulovat na p’ = max(p, m’)-procesorov´em PRAM s m’ pamˇet’ov´ymi buˇ nkami v t0 = O(t · m/m0 ) kroc´ıch. ´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
Simulace silnˇejˇs´ıho PRAM na slabˇs´ım PRAM
7
D˚ ukaz. Pamˇet’ov´e buˇ nky simulovan´eho a simuluj´ıc´ıho poˇc´ıtaˇce budeme oznaˇcovat M [1, ..., m] a M 0 [1, ..., m0 ]. 1. Rozdˇelme m simulovan´ ych sd´ılen´ ych pamˇet’ov´ ych bunˇek do m0 souvisej´ıc´ıch u ´sek˚ u Si o ve0 likosti m/m . 2. Kaˇzd´ y simuluj´ıc´ı procesor Pi0 , 1 ≤ i ≤ p, bude simulovat Pi p˚ uvodn´ıho PRAM. 3. Kaˇzd´ y simuluj´ıc´ı procesor Pi0 , 1 ≤ i ≤ m0 , uloˇz´ı poˇc´ateˇcn´ı obsah Si do sv´e lok´aln´ı pamˇeti a bude pouˇz´ıvat M 0 [i] jako pomocnou pamˇet’ovou buˇ nku pro simulov´an´ı pˇr´ıstupu k buˇ nk´am Si . 4. Simulace jedn´e p˚ uvodn´ı operace READ: Kaˇzd´ y procesor Pi0 , i = 1, ..., max(p, m0 ), opakuje pro k = 1, ..., m/m0 : (a) je-li i ∈ 1, ..., m0 , zapiˇs hodnotu k-t´e buˇ nky sv´eho u ´seku Si do M 0 [i]. (b) je-li i ∈ 1, ..., p a v nˇejak´em M 0 [j] se objevila hodnota, kterou by simulovan´ y procesor Pi ˇcetl v tomto simulovan´em kroku, pˇreˇcti ji. 5. Lok´aln´ı v´ ypoˇcetn´ı krok procesoru Pi , i = 1, ..., p, je simulov´an procesorem Pi0 v jednom kroku. 6. Simulace jedn´e operace WRITE je analogick´a simulaci operace READ. ˇ Casov´ a sloˇzitost simulace pak plyne z faktu, ˇze jeden krok p˚ uvodn´ıho algoritmu je simulov´ an v 0 0 0 0 t = O(m/m ) + 1 + O(m/m ) = O(m/m ) kroc´ıch.
3
Simulace silnˇ ejˇ s´ıho PRAM na slabˇ s´ım PRAM
Jak jiˇz bylo zm´ınˇeno v kapitole 1.3, r˚ uzn´e podmodely PRAM maj´ı r˚ uznou v´ ypoˇcetn´ı s´ılu. Pˇri n´avrhu paraleln´ıho algoritmu se m˚ uˇze st´at, ˇze v´ ypoˇcetn´ı s´ıla pouˇzit´eho podmodelu je vyˇsˇs´ı, neˇz v´ ypoˇcetn´ı s´ıle re´ aln´eho PRAM poˇc´ıtaˇce, napˇr. pokud HW poˇc´ıtaˇce neum´ı oˇsetˇrit konflikty pˇr´ıstupu do sd´ılen´ ych pamˇet’ov´ ych bunˇek. V takov´em pˇr´ıpadˇe je nutn´e pˇrikroˇcit k SW ˇreˇsen´ı konfliktn´ıch situac´ı, tj. k simulaci v´ ypoˇcetnˇe silnˇejˇs´ı PRAM podmodelu na v´ ypoˇcetnˇe slabˇs´ım PRAM poˇc´ıtaˇci. Vzhledem k tomu, ˇze moˇzn´ ych simulaˇcn´ıch kombinac´ı je velk´e mnoˇzstv´ı, zamˇeˇr´ıme se na extr´emn´ı pˇr´ıpad simulace v´ ypoˇcetnˇe nejsilnˇejˇs´ıho prioritn´ıho CRCW PRAM na v´ ypoˇcetnˇe nejslabˇs´ım EREW PRAM. Uved’me si dvˇe moˇzn´e simulaˇcn´ı metody. Vˇ eta 3 Uvaˇzujme Prioritn´ı CRCW PRAM s prioritn´ım syst´emem zaloˇzen´ym na indexov´ an´ı procesor˚ u a to takov´ym, ˇze procesory s niˇzˇs´ım indexem maj´ı vyˇsˇs´ı prioritu. Jeden krok p-procesorov´eho Prioritn´ıho CRCW PRAM s m buˇ nkami sd´ılen´e pamˇeti lze simulovat na p-procesorov´em EREW PRAM s m · p buˇ nkami sd´ılen´e pamˇeti v t0 = O(log p) kroc´ıch. D˚ ukaz. 1. Kaˇzd´ y procesor Pk , k = 1, ..., p, v Prioritn´ım CRCW je simulov´an EREW procesorem Pk0 . 2. Kaˇzd´a buˇ nka sd´ılen´e pamˇeti M [i], i = 1, ..., m, v Prioritn´ım CRCW je simulov´ ana polem p bunˇek sd´ılen´e pamˇeti M 0 [i, k], k = 1, ..., p, na EREW. M 0 [i, 1] hraje roli M [i]. M 0 [i, 2], ..., M 0 [i, p] jsou pomocn´ e buˇ nky organizovan´e jako vnitˇ rn´ı uzly u ´ pln´ eho bin´ arn´ıho stromu Ti s p listy, i = 1, ..., m. V´ yˇska stromu Ti je dlog pe. 3. Simulace kroku prioritn´ı WRITE. Kaˇzd´ y EREW procesor mus´ı zjistit, zda je procesorem s nejmenˇs´ım indexem v r´ amci skupiny procesor˚ u, ˇz´adaj´ıc´ıch o z´apis do t´eˇze buˇ nky. Pokud ano, je v´ıtˇezem skupiny a m˚ uˇze prov´est z´apis. Postup je n´asleduj´ıc´ı: ´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
Simulace silnˇejˇs´ıho PRAM na slabˇs´ım PRAM
8
(a) Vˇsechny buˇ nky pomocn´ ych pol´ı M 0 [i, ∗] maj´ı nastaven´ y pˇr´ıznak s na pr´ azdn´y. (b) Pokud chce Pk zapisovat do M [i], procesor P 0 [k] se stane aktivn´ım a stane se k-t´ ym listem stromu Ti . V´ı, zda je prav´ ym ˇci lev´ ym listem vzhledem ke sv´emu rodiˇci, tj. dan´e buˇ nce pomocn´eho pole M 0 [i, ∗]. (c) Kaˇzd´ y aktivn´ı lev´ y procesor uloˇz´ı sv´e ID do rodiˇcovsk´e buˇ nky ve sv´em stromˇe, nastav´ı jej´ı pˇr´ıznak s na obsazen´ a a z˚ ustane aktivn´ı. (d) Kaˇzd´ y aktivn´ı prav´ y procesor zkontroluje svou rodiˇcovskou buˇ nku. Je-li s = pr´ azdn´ a, uloˇz´ı do n´ı sv´e ID, nastav´ı s na obsazen´ a a z˚ ustane aktivn´ı. V opaˇcn´em pˇr´ıpadˇe se pˇrepne do stavu neaktivn´ı. (e) Toto se opakuje log p-kr´ at na dalˇs´ıch hladin´ach stromu. (f) Procesor, kter´emu se podaˇrilo postoupit do koˇrene Ti se st´av´a v´ıtˇezem, kter´ y m˚ uˇze zapsat do M 0 [i, 1]. Procesory, kter´e pouˇz´ıvaly strom Ti ho pak mus´ı proj´ıt dol˚ u v opaˇcn´em poˇrad´ı a vynulovat pˇr´ıznak s. 4. Simulace kroku Prioritn´ı READ je podobn´a. (a) Paralelnˇe se provedou stejn´e pr˚ uchody stromy Ti smˇerem nahoru, aby se urˇcili v´ıtˇezov´e ve skupin´ ach. (b) V´ıtˇezov´e pˇreˇctou hodnotu z bunˇek M 0 [∗, 1]. (c) Bˇehem zpˇetn´eho pr˚ uchodu stromy Ti smˇerem dol˚ u si procesory, kter´e prohr´aly, kromˇe nastavov´ an´ı pˇr´ıznaku s kop´ıruj´ı naˇctenou hodnotu. Druh´ y simulaˇcn´ı algoritmus m´ a stejnˇe jako pˇredchoz´ı optim´aln´ı ˇcasovou sloˇzitost (i kdyˇz skryt´ a konstanta je vˇetˇs´ı), ale vyˇzaduje pomocn´e pole, kde staˇc´ı pouze jedna buˇ nka na jeden simulovan´ y procesor. Vˇ eta 4 Uvaˇzujme Prioritn´ı CRCW PRAM, kde procesory s niˇzˇs´ım indexem maj´ı vyˇsˇs´ı prioritu. Jeden krok Prioritn´ıho CRCW PRAM s p procesory a m buˇ nkami sd´ılen´e pamˇeti lze simulovat na EREW PRAM s p procesory a m + p buˇ nkami sd´ılen´e pamˇeti v t0 = O(log p) kroc´ıch. D˚ ukaz. 1. Kaˇzd´ y procesor Pk , k = 1, ..., p, v Prioritn´ım CRCW je simulov´an EREW procesorem P 0 k. 2. Kaˇzd´a buˇ nka M [i], i = 1, ..., m, v Prioritn´ım CRCW je simulov´ana EREW buˇ nkou M 0 [i]. 3. EREW pouˇz´ıv´ a pomocn´ e pole A s p buˇ nkami. 4. Chce-li Pk pˇr´ıstup do M [i], procesor Pk0 zap´ıˇse do buˇ nky A[k] dvojici (i, k), v opaˇcn´em pˇr´ıpadˇe zap´ıˇse dvojici (0, k). 5. Vˇsech p procesor˚ u provede paraleln´ı setˇr´ıdˇen´ı pole A podle index˚ u procesor˚ u lexikograficky vhodn´ ym EREW algoritmem s ˇcasovou sloˇzitost´ı O(log p)). 6. Kaˇzd´ y Pk0 pˇripoj´ı k buˇ nce A[k] pˇr´ıznak s, kde: je-li prvn´ı poloˇzka dvojice A[k] bud’ rovna 0 nebo je-li shodn´a s prvn´ı poloˇzkou 0 pˇredchoz´ı dvojice A[k-1], s= 1 jinak. Dalˇs´ı kroky se liˇs´ı podle toho, zde simulujeme WRITE nebo READ. ´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
Asynchronn´ı PRAM (APRAM) model
9
7. Prioritn´ı WRITE: (a) Kaˇzd´ y Pk0 pˇreˇcte trojici (i, j, s) ze sv´e buˇ nky A[k] a zap´ıˇse ji do A[j] (tato permutace je bezkonfliktn´ı). V tomto okamˇziku m´a kaˇzd´ y procesor Pk0 ve sv´e buˇ nce A[k] zpˇet svoji trojici (∗, k, ∗). (b) Kaˇzd´ y Pk0 pˇreˇcte trojici (i, k, s) ze sv´e buˇ nky A[k]. Je-li s = 1, stal se v´ıtˇezem a m˚ uˇze zapsat do M [i] svoji hodnotu. 8. Prioritn´ı READ: (a) Kaˇzd´ y Pk0 pˇreˇcte trojici (i, j, s) ze sv´e buˇ nky A[k]. (b) Kaˇzd´ y Pk0 s s = 1 pˇreˇcte hodnotu vi z M 0 [i] a uloˇz´ı ji do trojice (i, j, vi ). Jelikoˇz ale d´ıky pˇredchoz´ımu tˇr´ıdˇen´ı doˇslo k permutaci trojic, nen´ı prozat´ım v A[k] jeho vlastn´ı v´ ysledek. (c) S´emantika operace Prioritn´ı READ je takov´a, ˇze kaˇ zd´ y, kdo poˇz´adal o ˇcten´ı, by mˇel obsah poˇzadovan´e buˇ nky dostat. Vzhledem k tomu, ˇze sousedn´ı buˇ nky v setˇr´ıdˇen´em poli A obsahuj´ı poˇzadavky na stejn´e pamˇet’ov´e buˇ nky, provedou vˇsechny procesory pomoc´ı EREW algoritmu bin´ arn´ıho zdvojov´ an´ı jednoduˇse rozkop´ırov´an´ı trojice (i, ∗, vi ) do vˇsech (i, ∗, 0) v O(log p) kroc´ıch. nky A[k] a uloˇz´ı ji do A[j]. T´ım se poˇzadavek (d) Kaˇzd´ y Pk0 pˇreˇcte trojici (i, j, vi ) ze sv´e buˇ dost´ av´ a do buˇ nky sv´eho p˚ uvodce. y ˇz´ adal o READ si pˇreˇcte hodnotu vi z trojice (i, k, vi ) ze sv´e buˇ nky A[k]. (e) Kaˇzd´ y Pk0 , kter´
4
Asynchronn´ı PRAM (APRAM) model
Re´aln´e paraleln´ı poˇc´ıtaˇce se vetˇsinou od idealizovan´eho PRAM modelu liˇs´ı v nˇekolika d˚ uleˇzit´ ych skuteˇcnostech: jednak jejich procesory nepracuj´ı synchronnˇe a nav´ıc pˇr´ıstup do sd´ılen´e pamˇeti je ˇcasovˇe n´aroˇcnˇejˇs´ı neˇz pˇr´ıstup do lok´ aln´ıch registr˚ u. Z tohoto d˚ uvodu je uˇziteˇcn´e m´ıt k dispozici model, kter´ y bude l´epe reflektovat moˇznosti re´aln´ ych poˇc´ıtaˇc˚ u. T´ım m˚ uˇze b´ yt napˇr´ıklad model APRAM (Asynchronous PRAM), kter´ y se od klasick´eho PRAM odliˇsuje tˇemito vlastnostmi: • procesory pracuj´ı asynchronnˇe, • procesory je potˇreba explicitnˇe synchronizovat, • a doba pˇr´ıstupu do sd´ılen´e pamˇeti nen´ı jednotkov´a.
4.1
APRAM v´ ypoˇ cet
APRAM v´ ypoˇcet m˚ uˇze prov´ adˇet instrukce 4 typ˚ u: 1. Glob´ aln´ı ˇ cten´ı - pˇreˇcte obsah sd´ılen´e pamˇet’ov´e buˇ nky do lok´aln´ı pamˇeti. 2. Lok´ aln´ı v´ ypoˇ cet - provede jakoukoliv RAM instrukci s operandy a v´ ysledky uloˇzen´ ymi v lok´aln´ı pamˇeti. 3. Glob´ aln´ı z´ apis - zap´ıˇse hodnotu z lok´aln´ı pamˇeti do sd´ılen´e pamˇeti. 4. Bari´ erov´ a synchronizace - kaˇzd´ y proces se v bodˇe bari´ery zastav´ı aˇz do doby, neˇz k n´ı doraz´ı vˇsechny zb´ yvaj´ıc´ı procesy, pro kter´e byla bari´era definov´ana. V´ypoˇcet na APRAM je pak definov´ an jako posloupnost asynchronnˇe prov´ adˇen´ych glob´ aln´ıch f´ az´ı oddˇelen´ych bari´erovou synchronizac´ı. V r´ amci dan´ych glob´ aln´ıch f´ az´ı mus´ı b´yt z´ apis do sd´ılen´ych pamˇet’ov´ych bunˇek exkluzivn´ı. ´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
Asynchronn´ı PRAM (APRAM) model
4.2
10
V´ ykonostn´ı parametry modelu APRAM
Sloˇzitost jednotliv´ ych APRAM operac´ı je n´asleduj´ıc´ı: • Sloˇzitost lok´ aln´ı operace je 1. • Sloˇzitost glob´ aln´ı operace ˇcten´ı nebo z´apisu je obecnˇe d. Pro jednoduchost pˇredpokl´ad´ ame, ˇze d ≥ 2 je konstanta. • Sloˇzitost implementace bari´ery b(p) je vˇzdy neklesaj´ıc´ı funkc´ı p, kde d ≤ b(p) ≤ p. Typick´e hodnoty jsou b(p) = Θ(d log p) pro implementaci pomoc´ı bin´arn´ıho redukˇcn´ıho stromu nebo b(p) = Θ(d · p) pro implementaci pomoc´ı centr´aln´ıho ˇc´ıtaˇce [1]. • k po sobˇe jdouc´ıch operac´ı glob´ aln´ıho ˇcten´ı nebo z´apisu m´a sloˇzitost d + k − 1, ne d · k, jak by se dalo pˇredpokl´ adat, coˇz odr´ aˇz´ı vlastnosti souˇcasn´ ych sbˇernicov´ ych syst´em˚ u [1].
´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
Kontroln´ı ot´azky
5
11
Kontroln´ı ot´ azky • Co je to v´ ypoˇcetn´ı model PRAM a k ˇcemu slouˇz´ı? • Jak´e rozliˇcujeme v´ ypoˇcetn´ı podmodely PRAM z hlediska ˇr´ızen´ı soubˇeˇzn´eho pˇr´ıstupu k pamˇet’ov´ ym buˇ nk´ am? • Jak´ ym zp˚ usobem ovlivˇ nuje simulace vˇetˇs´ıho PRAM na menˇs´ım ˇcasovou a pamˇet’ovou sloˇzitost algoritmu? • Jak´ ym zp˚ usobem ovlivˇ nuje simulace silnˇejˇs´ıho PRAM na slabˇs´ım ˇcasovou a pamˇet’ovou sloˇzitost algoritmu?
´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
REFERENCE
Reference ˇ [1] Pavel Tvrd´ık. Paraleln´ı syst´emy a algoritmy. Vydavatelstv´ı CVUT, Praha, 2005.
´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
12
