´ ´I PARALELN´I PROCESY A PROGRAMOVAN 6 Anal´ yza sloˇ zitosti algoritm˚ u - cena, pr´ ace a efektivita 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 Kvalitativn´ı mˇ eˇ r´ıtka paralelizace algoritmu 1.1 Cena algoritmu . . . . . . . . . . . . . . . . 1.2 Paraleln´ı pr´ ace . . . . . . . . . . . . . . . . 1.3 Efektivita algoritmu . . . . . . . . . . . . . 1.3.1 Brent˚ uv simulaˇcn´ı princip . . . . . . 1.3.2 Izoefektivita paraleln´ıho algoritmu . 1.3.3 Absolutnˇe minim´ aln´ı paraleln´ı ˇcas . 1.3.4 Karp-Flattova metrika . . . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
2 Pˇ r´ıklad anal´ yzy paraleln´ıho algoritmu 3 Kontroln´ı ot´ azky
´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
3 3 3 3 5 5 7 7 9 12
OBSAH
ˇ Y ´ OBSAH PREDN ˇ ´ SKY ˇ STRUCN A Kvalitativn´ı mˇeˇr´ıtka paralelizace algoritmu Pˇr´ıklad anal´ yzy paraleln´ıho algoritmu
MOTIVACE Anal´yza sloˇzitosti algoritm˚ u umoˇzn ˇuje zjistit ˇcasov´e a pamˇet’ov´e charakteristiky jednotliv´ ych algoritm˚ u. Na z´ akladˇe tˇechto anal´ yz lze urˇcit vhodnost jednotliv´ ych algoritm˚ u pro ˇreˇsen´ı konkr´etn´ıch u ´loh a tak´e to, zda m´a smysl urˇcit´ y algoritmus implementovat. Tato kapitola pojedn´ av´ a o anal´ yze ˇcasov´e a pamˇet’ov´e sloˇzitosti sekvenˇcn´ıch a paraleln´ıch algoritm˚ u a o moˇznostech urˇcen´ı kvalitativn´ıch mˇeˇr´ıtek paraleln´ıch algoritm˚ u.
C´IL Nauˇcit se stanovit cenu, pr´ aci a efektivitu paraleln´ı algoritmu a prozkoumat jeho ˇsk´alovatelnost.
´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
2
Kvalitativn´ı mˇeˇr´ıtka paralelizace algoritmu
1
3
Kvalitativn´ı mˇ eˇ r´ıtka paralelizace algoritmu
Stanoven´ım zrychlen´ı paraleln´ıho algoritmu jeho anal´ yza zdaleka nekonˇc´ı. Dalˇs´ımi d˚ uleˇzit´ ymi mˇeˇr´ıtky kvality paralelizace je cena, pr´ace a zejm´ena efektivita nov´eho paraleln´ıho algoritmu. Vyj´adˇren´ım a zkoum´ an´ım tˇechto mˇeˇr´ıtek lze zjistit, zda byla paralelizace algoritmu provedena optim´alnˇe a u ´ˇcelnˇe. Tak´e je zapotˇreb´ı prozkoumat, zda je dan´ y paraleln´ı algoritmus dostateˇcnˇe ˇsk´alovateln´ y, tzn. zda lze mˇenit poˇcet v´ ypoˇcetn´ıch jednotek (CPU) pod´ılej´ıc´ıch se na v´ ypoˇctu podle potˇreb tak, aby nebyla negativnˇe ovlivnˇena jak cena, tak i efektivita paraleln´ıho algoritmu. N´asleduj´ıc´ı kapitoly popisuj´ı stanoven´ı jednotliv´ ych kvalitativn´ıch mˇeˇr´ıtek paralelizace a ukazuj´ı tak´e dalˇs´ı metody vhodn´e ke zjiˇstˇen´ı pˇr´ıˇcin jej´ı pˇr´ıpadn´e neefektivnosti.
1.1
Cena algoritmu
Cena paraleln´ıho algoritmu vyjadˇruje jak´ ych n´aklad˚ u jsme museli vynaloˇzit na dosaˇzen´ı konkr´etn´ıho paraleln´ıho ˇcasu a je definov´ ana jako K CA (n) = C(n, p) = p · T (n, p)
(1)
Obecnˇe lze ˇr´ıci, ˇze C K (n, p) = Ω(SU K (n)) Definice 1 M˚ uˇzeme-li tvrdit, ˇze C K (n, p) = O(SU K (n)), pak je paraleln´ı algoritmus cenovˇ e optim´ aln´ı.
1.2
Paraleln´ı pr´ ace
Pr´ace paraleln´ıho algoritmu pˇredstavuje celkov´ y poˇcet aktivnˇe pracuj´ıc´ıch procesor˚ u ve vˇsech kroc´ıch paraleln´ıho algoritmu. Oznaˇcme t0 = T (n, p), pak paraleln´ı pr´aci definujeme jako WAK (n) = W (n, p) = N1 + N2 + ... + Nt0
(2)
kde Ni je poˇcet aktivnˇe pracuj´ıc´ıch procesor˚ u v kroku i = 1, 2, ..., t0 . Je zˇrejm´e, ˇze W (n, p) ≤ C(n, p), jelikoˇz C(n, p) zahrnuje tak´e zah´alej´ıc´ı procesory. V praxi se pro urˇcen´ı kvality paraleln´ıho algoritmu uv´ad´ı sp´ıˇse C(n, p), protoˇze jeho hodnota l´epe reflektuje celkov´e vyt´ıˇzen´ı paraleln´ıho syst´emu. To je d´ano t´ım, ˇze zah´alej´ıc´ı procesory nen´ı vˇzdy moˇzn´e z d˚ uvodu architektonick´eho omezen´ı paraleln´ıho syst´emu uvolnit pro dalˇs´ı vyuˇzit´ı a proto je hodnota W (n, p) pˇr´ıliˇs optimistick´ a. Definice 2 Plat´ı-li tvrzen´ı, ˇze W K (n, p) = O(SU K (n)), pak lze paraleln´ı algoritmus povaˇzovat za pracovnˇ e optim´ aln´ı.
1.3
Efektivita algoritmu
Jednou z nejd˚ uleˇzitˇejˇs´ıch metrik kvality paraleln´ıho algoritmu je jeho efektivita, kterou lze ch´ apat jako m´ıru vyt´ıˇzen´ı procesor˚ u. Efekticitu paraleln´ıho algoritmu oznaˇcujeme jako K EA (n)
(3)
E(n, p)
(4)
nebo zjednoduˇsenˇe
a lze ji vyj´ adˇrit vztahem
´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
Kvalitativn´ı mˇeˇr´ıtka paralelizace algoritmu
4
SU K (n) C K (n, p)
(5)
SU K (n) S(n, p) · T (n, p) S(n, p) = = ≤1 C K (n, p) p · T (n, p) p
(6)
E(n, p) = Vztah 5 lze rozvinout jako E(n, p) =
coˇz znamen´ a, ˇze efektivitu paraleln´ıho algoritmu lze ch´apat tak´e jako jeho zrychlen´ı na procesor a jej´ı hodnota bude vˇzdy ≤ 1 (v ide´ aln´ı pˇr´ıpadˇe = 1 pro paraleln´ı algoritmy s line´arn´ım zrychlen´ım). Z toho vypl´ yv´ a, ˇze algoritmus je cenovˇ e optim´ aln´ı ⇔ m´a line´ arn´ı zrychlen´ı ⇔ m´a konstantn´ı efektivitu. Obecnˇe lze v souladu s Amdahlov´ ym efektem ˇr´ıci, ˇze rostouc´ı velikost probl´emu n a pˇri zachov´ an´ı konstantn´ı hodnoty poˇctu procesor˚ u p m´a tendenci zvyˇsovat zrychlen´ı paraleln´ıho algoritmu a t´ım tak´e jeho efektivitu. Naopak, ne´ umˇern´e zvyˇsov´an´ı poˇctu procesor˚ u m´a za n´asledek r˚ ust paraleln´ı reˇzie a t´ım tak´e sn´ıˇzen´ı zrychlen´ı a efektivity. Typick´e pr˚ ubˇehy paraleln´ıho ˇcasu, zrychlen´ı a efektivity jsou zobrazeny na obr´ azku 1.
Obr´ azek 1: Typick´e pr˚ ubˇehy T (n, p), E(n, p) a S(n, p) v z´avislosti na zmˇenˇe n Zdroje neefektivity paraleln´ıho algoritmu mohou b´ yt • nedostatek uˇ ziteˇ cn´ e pr´ ace pro dan´ y poˇcet procesor˚ u, • velk´ e komunikaˇ cn´ı n´ aklady v porovn´an´ı s v´ ypoˇcetn´ı sloˇzitost´ı, • velk´ a synchronizaˇ cn´ı reˇ zie, • ˇ spatn´ a distribuce pr´ ace (nerovnomˇern´e rozdˇelen´ı pr´ace) mezi procesory. Neefektivitu paraleln´ıho algoritmu lze odstranit dvoj´ım zp˚ usobem: technologicky a algoritmicky. Technologick´ y pˇr´ıstup zahrnuje • pouˇzit´ı rychlejˇs´ıho komunikaˇcn´ıho HW, • zmenˇsen´ı SW komunikaˇcn´ı reˇzie, • pˇrekr´ yv´ an´ı komunikaˇcn´ıch a v´ ypoˇcetn´ıch operac´ı. Algoritmick´ y pˇr´ıstup zahrnuje • respektov´ an´ı ˇ sk´ alovatelnosti probl´emu volnou vhodn´e granularity, ´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
Kvalitativn´ı mˇeˇr´ıtka paralelizace algoritmu
5
• dobr´e statick´e mapov´ an´ı algoritmu na paraleln´ı architekturu, • rovnomˇern´e statick´e rozdˇelen´ı v´ ypoˇcetn´ı z´atˇeˇze, • vhodn´e pˇredˇrazov´ an´ı komunikaˇcn´ıch operac´ı pˇred m´ısta v programu, kde jsou vymˇen ˇovan´ a data potˇreba. Je zˇrejm´e, ˇze vyuˇzit´ı algoritmick´eho pˇr´ıstupu bude ve vˇetˇsinˇe pˇr´ıpad˚ u v´ yhodnˇejˇs´ı; n´aklady na u ´pravu a optimalizaci paraleln´ıho algoritmu budou menˇs´ı neˇz n´aklady na u ´pravu (upgrade) v´ ypoˇcetn´ıho HW. Z algoritmick´ ych moˇznost´ı sn´ıˇzen´ı neefektivity paraleln´ıho algoritmu se pak nejˇcastˇeji vyuˇz´ıv´ a moˇznosti vhodn´eho ˇ sk´ alov´ an´ı paraleln´ıho algoritmu. ˇ alovatelnost´ı paraleln´ıho algoritmu budeme rozumˇet jeho schopnost pˇrizp˚ Sk´ usobit se mˇen´ıc´ımu poˇctu procesor˚ u nebo velikosti ˇreˇsen´eho probl´emu pˇri udrˇzen´ı co nejlepˇs´ı efektivity. 1.3.1
Brent˚ uv simulaˇ cn´ı princip
V pˇr´ıpadˇe, ˇze n´ aˇs paraleln´ı algoritmus pouˇz´ıv´a neprakticky velk´e mnoˇzstv´ı´a procesor˚ u, lze jeho ˇsk´alov´an´ım sn´ıˇzi cenu a t´ım zv´ yˇsit jeho efektivitu. Je-li poˇcet procesor˚ u menˇs´ı neˇz stupeˇ n paralelizmu a pˇredpokl´ ad´ ame-li n´ızk´e komunikaˇcn´ı reˇzie, m˚ uˇzeme pouˇz´ıt Brent˚ uv simulaˇ cn´ı princip, podle kter´eho nem˚ uˇze m´ıt simulace ˇr´adovˇe horˇs´ı ani pr´aci ani cenu. Vˇ eta 1 Uvaˇzujme probl´em K o velikosti n ˇreˇsiteln´y v t paraleln´ıch kroc´ıch na pP procesorech pˇri zanedb´ an´ı komunikaˇcn´ı reˇzie. Necht’ mi je poˇcet operac´ı v kroku i. Pak W (n, p) = ti=1 mi a staˇc´ı p = maxti=1 mi procesor˚ u, ˇc´ımˇz dostaneme C(n, p) = pt = maxti=1 mi t. Uvaˇzujme p0 procesorov´y poˇc´ıtaˇc M s p0 < p t´ymiˇz procesory. Jestliˇze lze u M t´eˇz ignorovat komunikaˇcn´ı reˇzie jako u K, lze tent´yˇz v´ypoˇcet na M prov´est v T (n, p0 ) paraleln´ıch kroc´ıch, kde T (n, p0 ) = W (n, p)/p0 + t
(7)
D˚ ukaz 1 Paraleln´ı kroky se simuluj´ı postupnˇem kdy kaˇzd´y i-t´y krok, ve kter´em je nutn´e prov´est mi operac´ı, lze na M simulovat v dmi /p0 e kroc´ıch. Celkov´ a doba simulace proto bude T (n, p0 ) =
t t t X X X dmi /p0 e = (mi /p0 ) + t = (mi )/p0 + t = W (n, p)/p0 + t i−1
i=1
(8)
i=1
a d´ ale W (n, p0 ) = W (n, p) C(n, p0 ) = p0 T (n, p0 ) ≤ W (n, p) + pt = W (n, p) + C(n, p)
(9)
V´ yznam Brentova simulaˇcn´ıho principu spoˇc´ıv´a v tvrzen´ı, ˇze neprakticky velk´e mnoˇzstv´ı procesor˚ u lze libovolnˇe sniˇzovat, pˇriˇcemˇz doba v´ ypoˇ ctu poroste nejv´ yˇ se u ´ mˇ ernˇ e a celkov´ a pr´ ace, cena i efektivita z˚ ust´ avaj´ı ˇ r´ adovˇ e stejn´ e. Zvol´ıme-li pro simulaci vhodn´ y menˇs´ı poˇcet procesor˚ u, m˚ uˇze pˇri zachov´ an´ı stejn´e pr´ ace cena algoritmu dokonce klesnout, protoˇze budou pouˇzit´e procesory v´ıce vyt´ıˇzeny. U algoritmu, u nichˇz nelze zanedbat komunikaˇcn´ı reˇzie je toto zapotˇreb´ı br´at v u ´vahu. 1.3.2
Izoefektivita paraleln´ıho algoritmu
Jak jiˇz bylo zm´ınˇeno, pˇri n´ avrhu paraleln´ıho algoritmu je pro udrˇzen´ı konstantn´ı efektivity zapotˇreb´ı spr´avnˇe volit granularitu, tj. mus´ıme zvolit spr´avn´ y pomˇer mezi poˇctem procesor˚ u p a velikost´ı ˇreˇsen´eho probl´emu n. K tomu n´am m˚ uˇze pomoci tzv. izoefektivn´ı metrika. Jedn´ a se ´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
Kvalitativn´ı mˇeˇr´ıtka paralelizace algoritmu
6
o metriku ˇsk´ alovatelnosti paraleln´ıho syst´emu, ˇcili jeho schopnosti zvyˇsovat v´ ykon pˇri zvyˇsov´ an´ı poˇctu procesor˚ u. Z Amdahlova efektu vypl´ yv´ a, ˇze zrychlen´ı je rostouc´ı funkc´ı velikosti ˇreˇsen´eho probl´emu n. Aby byla zachov´ana konstantn´ı efektivita E(n, p), pˇri rostouc´ım p mus´ı r˚ ust tak´e n. Rychlost tohoto r˚ ustu lze vyj´ adˇrit pomoc´ı izoefektivn´ı funkce. Uvaˇzujme vztah mezi paraleln´ım a sekvenˇcn´ım ˇcasem algoritmu ˇreˇs´ıc´ım stejn´ y probl´em pT (n, p) = T (n, 1) + κ(n, p)
(10)
kde T (n, p) je paraleln´ı ˇcas, T (n, 1) je sekvenˇcn´ı ˇcas a κ(n, p) je celkov´a paraleln´ı reˇzie. Paraleln´ı ˇcas pak lze vyj´ adˇrit jako T (n, p) =
T (n, 1) + κ(n, p) p
(11)
Dosad´ıme-li vztah 11 do vztahu pro vyj´adˇren´ı zrychlen´ı algoritmu, dostaneme S(n, p) ≤
SU (n) T (n, 1) pT (n, 1) ≤ ≤ T (n, p) T (n, p) T (n, 1) + κ(n, p)
(12)
Vyj´adˇr´ıme-li efektivitu algoritmu pomoc´ı vztahu 12, dostaneme E(n, p) ≤
T (n, 1) 1 1 S(n, p) ≤ ≤ ≤ κ(n,p) κ(n,p) p T (n, 1) + κ(n, p) 1 + T (n,1) 1 + SU (n)
(13)
Izoefektivn´ı funkci lze pot´e odvodit n´asledovnˇe T (n, 1) ≥ E(n, p)(T (n, 1) + κ(n, p)) T (n, 1)(1 − E(n, p)) ≥ κ(n, p)E(n, p) E(n,p) T (n, 1) ≥ 1−E(n,p) κ(n, p) T (n, 1) ≥ c · κ(n, p)
(14)
kde c je konstanta c=
E(n, p) 1 − E(n, p)
(15)
Z odvozen´ı 14 vypl´ yv´ a, ˇze pˇri zmˇenˇe p (a t´ım p´adem i celkov´e paraleln´ı reˇzie) se mus´ı zmˇenit i n, aby platila dan´ a nerovnice a efektivita z˚ ustala zachov´ana konstantn´ı. To znamen´a, ˇze zmˇen´ı-li κ(n,p0 ) 0 se p na p , mus´ı se zmˇenit tak´e n o n´ asobek κ(n,p) . Pro dobˇre ˇsk´alovateln´e paraleln´ı algoritmy mus´ı b´ yt tato zmˇena minim´ aln´ı, protoˇze i jejich paraleln´ı reˇzie by mˇela b´ yt co nejniˇzˇs´ı. Probl´em stanoven´ı horn´ı a doln´ı meze vhodn´eho poˇctu procesor˚ u lze vyj´adˇrit pomoc´ı izoefektivn´ıch funkc´ı ψ1 a ψ2 . Definice 3 Necht’ je d´ ana konstanta 0 < E0 < 1. Pak • ψ1 je asymptoticky minim´ aln´ı funkce takov´ a, ˇze ∀np = Ω(ψ1 (p)) : E(np , p) ≥ E0
(16)
ˇcili ψ1 ud´ av´ a asymptoticky nejmenˇs´ı instanci probl´emu, kter´ a je na dan´em poˇctu procesor˚ u ˇreˇsiteln´ a s konstantn´ı efektivitou.
´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
Kvalitativn´ı mˇeˇr´ıtka paralelizace algoritmu
7
• ψ2 je asymptoticky maxim´ aln´ı funkce takov´ a, ˇze ∀pn = O(ψ2 (n)) : E(n, pn ) ≥ E0
(17)
ˇcili ψ2 ud´ av´ a asymptoticky nejvˇetˇs´ı poˇcet procesor˚ u, kter´y jeˇstˇe poskytuje ˇreˇsen´ı dan´e instance probl´emu s konstantn´ı efektivitou. Funkce ψ2 (n) je inverzn´ı k funkci ψ1 (p). Menˇs´ı (pomalu rostouc´ı) funkce ψ1 (p) ˇr´ık´a, ˇze syst´em je l´epe ˇsk´alovateln´ y. Pro funkci ψ2 (n) je tvrzen´ı opaˇcn´e. 1.3.3
Absolutnˇ e minim´ aln´ı paraleln´ı ˇ cas
Pro zjiˇstˇen´ı optim´ aln´ıho poˇctu procesor˚ u, kter´e jsou schopny probl´em dan´e velikosti vyˇreˇsit v absolutnˇe minim´ aln´ım ˇcase lze pouˇz´ıt n´asleduj´ıc´ı postup. Jak jiˇz bylo zm´ınˇeno v´ yˇse a jak je patrn´e na obr´azku 2, pˇrid´av´an´ım nadmˇern´eho poˇctu procesor˚ u m˚ uˇzeme doc´ılit nejen poklesu zrychlen´ı, ale dokonce tak´e prodluˇzov´an´ı ˇcasu ˇreˇsen´ı. Toho m˚ uˇzeme vyuˇz´ıt k tomu, abychom pomoc´ı derivace pr˚ ubˇehu paraleln´ıho ˇcasu nalezli optim´aln´ı poˇcet procesor˚ u popt pouˇzit´ ych pro ˇreˇsen´ı probl´emu dan´e velikosti.
Obr´ azek 2: Typick´e pr˚ ubˇehy T (n, p) v z´avislosti na zmˇenˇe n a p Uvaˇzujme rovnici ∂T (n, p) |p=popt = 0 ∂p
(18)
Jej´ım ˇreˇsen´ım z´ısk´ ame optim´ aln´ı poˇcet procesor˚ u popt pro dan´ y algoritmus a velikost probl´emu. 1.3.4
Karp-Flattova metrika
Chceme-li zjistit pˇ r´ıˇ cinu neefektivity paraleln´ıho algoritmu, m˚ uˇzeme pouˇz´ıt Karp-Flattovu metriku, kter´ a umoˇzn ˇuje urˇcit, zda je neefektivita zp˚ usobena velkou sekvenˇ cn´ı sloˇ zkou fσ paraleln´ıho algoritmu ˇci jeho nadmˇ ernou reˇ zi´ı κ(n, p). Karp-Flattova metrika stanovuje tzv. experiment´ alnˇ e urˇ cen´ y pomˇ er sekvenˇ cn´ı sloˇ zky e. Z pr˚ ubˇehu hodnoty e pˇri vzr˚ ustaj´ıc´ım p lze vyvodit pˇr´ıˇcinu neefektivity: • je-li e konstantn´ı, je pˇr´ıˇcinou neefektivity velk´a sekvenˇcn´ı sloˇzka, • je-li e rostouc´ı, je pˇr´ıˇcinou neefektivity nadmˇern´a paraleln´ı reˇzie. ´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
Kvalitativn´ı mˇeˇr´ıtka paralelizace algoritmu
8
Uvaˇzujme T (n, p) = σ(n) + φ(n) p + κ(n, p) T (n, 1) = σ(n) + φ(n)
(19)
Experiment´ alnˇe urˇcen´ y pomˇer sekvenˇcn´ı sloˇzky lze vyj´adˇrit jako e=
σ(n) + κ(n, p) ⇒ σ(n) + κ(n, p) = T (n, 1)e T (n, 1)
(20)
Po dosazen´ı do 19 a u ´pravˇe dostaneme vyj´adˇren´ı paraleln´ıho ˇcasu T (n, p) = T (n, 1)e +
T (n, 1)(1 − e) p
(21)
Uvaˇzujme S(n, p) =
T (n, 1) ⇒ T (n, 1) = S(n, p)T (n, p) T (n, p)
(22)
Pak po zjednoduˇsen´ı vztahu T (n, p) = S(n, p)T (n, p)e +
S(n, p)T (n, p)(1 − e) p
(23)
dostaneme experiment´ alnˇe urˇcen´ y pomˇer sekvenˇcn´ı sloˇzky e=
Pˇ r´ıklad 1
1 S(n,p)
1−
−
1 p
(24)
1 p
Experiment´ aln´ı cestou jsme pˇri anal´ yze paraleln´ıho algoritmu z´ıskali tabulku Tabulka 1: Experiment´alnˇe zjiˇstˇen´e S(n, p) a pr˚ ubˇeh e p S(n,p) e
2 1.82 0.1
3 2.5 0.1
4 3.08 0.1
5 3.57 0.1
6 4.00 0.1
7 4.38 0.1
8 4.71 0.1
Hodnota e v tabulce 1 je konstantn´ı coˇz znamen´a, ˇze pˇr´ıˇcinou neefektivity zkouman´eho algoritmu je velk´a sekvenˇcn´ı sloˇzka fσ . Pˇ r´ıklad 2
Experiment´ aln´ı cestou jsme pˇri anal´ yze paraleln´ıho algoritmu z´ıskali tabulku Tabulka 2: Experiment´alnˇe zjiˇstˇen´e S(n, p) a pr˚ ubˇeh e p S(n,p) e
2 1.87 0.07
3 2.61 0.075
4 3.23 0.08
5 3.73 0.085
6 4.14 0.09
7 4.46 0.095
8 4.71 0.1
Hodnota e v tabulce 2 je rostouc´ı coˇz znamen´a, ˇze pˇr´ıˇcinou neefektivity zkouman´eho algoritmu je velk´a paraleln´ı reˇzie κ(n, p).
´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
Pˇr´ıklad anal´ yzy paraleln´ıho algoritmu
2
9
Pˇ r´ıklad anal´ yzy paraleln´ıho algoritmu
Vˇsechny doposud diskutovan´e aspekty anal´ yzy paraleln´ıho algoritmu si demonstrujme na pˇr´ıkladu zkoum´an´ı postupu paraleln´ı redukce mnoˇziny hodnot. Uvaˇzujme paraleln´ı redukci mnoˇziny n ˇc´ısel na p procesorov´em stroji kde p = n dle sch´ematu na obr´azku 3, kde jednotliv´e ˇr´ adky pˇredstavuj´ı paraleln´ı f´aze algoritmu.
Obr´ azek 3: Sch´ema paraleln´ı redukce Pˇredpokl´ adejme, ˇze operace souˇctu i pˇrenosu dat mezi procesory trv´a 1 ˇcasovou jednotku. Paraleln´ı v´ ypoˇcet probˇehne v log n iterac´ıch (paraleln´ıch f´az´ıch), kaˇzd´ y bude trvat 2 jednotky ˇcasu. Paraleln´ı algoritmus m´ a ˇcasovou sloˇzitost T (n, p) = 2 log n = Θ(log n)
(25)
Horn´ı mez sekvenˇcn´ıho algoritmu ˇreˇs´ıc´ıho stejn´ y probl´em je SU (n) = T (n, 1) = 2(n − 1) = 2n − 2 = Θ(n)
(26)
Z´akladn´ı charakteristiky algoritmu jsou pak n´asleduj´ıc´ı: C(n, p) = Θ(n · log(n)) W (n, p) = (
(27)
n n n n + ) + ( + ) + ... + (1 + 1) = 2n − 2 = Θ(n) 2 2 4 4
(28)
S(n, p) = Θ(
n ) log n
(29)
E(n, p) = Θ(
1 ) log n
(30)
Z v´ yˇse uveden´eho je patrn´e, ˇze algoritmus je ˇ casovˇ e i pracovnˇ e optim´ aln´ı, nen´ı vˇ sak cenovˇ e optim´ aln´ı, coˇz je d´ ano nedostatkem uˇziteˇcn´e pr´ace pro vˇsechny procesory (viz. obr´ azek 3). Pokusme se proto sn´ıˇzit paraleln´ı cenu algoritmu jeho vhodn´ ym ˇsk´alov´an´ım. Uvaˇzujme tedy modifikaci algoritmu paraleln´ı redukce n hodnot na v´ ypoˇcetn´ım stoji s p0 < n procesory. V tom pˇr´ıpadˇe existuj´ı nejm´enˇe dva zp˚ usoby simulace: 1. Pˇriˇrazen´ı simulovan´ ych procesor˚ u po ˇr´adc´ıch, coˇz znamen´a, ˇze kaˇzd´ y z p0 procesor˚ u provede n ˇcinnost p0 simulovan´ ych procesor˚ u v jedn´e paraleln´ı f´azi, jak je ilustrov´ano na obr´azku 4. Doba trv´an´ı jedn´e paraleln´ı f´ aze je pn0 a poˇcet paraleln´ıch f´az´ı je p0 . Z´avˇerem z˚ ustane v posledn´ım n aktivn´ım procesoru p0 meziv´ ysledk˚ u, kter´e je potˇreba redukovat sekvenˇcnˇe, coˇz zabere ˇcas pn0 . Celkov´ y paraleln´ı ˇcas t´eto simulace je ´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
Pˇr´ıklad anal´ yzy paraleln´ıho algoritmu
n n n T (n, p0 ) = ( 0 ) log p0 + 0 = Θ( 0 log p0 ) p p p
10
(31)
Obr´ azek 4: Simulace pˇriˇrazov´an´ı po ˇr´adc´ıch 2. Pˇriˇrazen´ı simulovan´ ych procesor˚ u po sloupc´ıch, coˇz znamen´a, ˇze kaˇzd´ y z p0 procesor˚ u provede n n 0 sekvenˇcn´ı redukci p0 hodnot v ˇcase p0 , ˇc´ımˇz dostaneme p meziv´ ysledk˚ u, kter´e pak lze paralelnˇe zredukovat v log p0 paraleln´ıch f´ az´ıch v ˇcase log p0 . Postup je ilustrov´an na obr´azku 5. Celkov´ y paraleln´ı ˇcas t´eto simulace je T (n, p0 ) =
n n + log p0 = Θ( 0 + log p0 ) 0 p p
(32)
Obr´ azek 5: Simulace pˇriˇrazov´an´ı po sloupc´ıch Paraleln´ı cena simulace pˇriˇrazov´ an´ı po ˇr´adc´ıch je C(n, p) = Θ(n · log p0 ), coˇz st´ale nen´ı cenovˇe optim´aln´ı. Paraleln´ı cena simulace pˇriˇrazov´ an´ı po sloupc´ıch je C(n, p) = Θ(n+p0 ·log p0 ), coˇz za pˇredpokladu 0 0 n >> p · log p je C = Θ(n). V tomto pˇr´ıpadˇe se jiˇz jedn´a o cenovˇe optim´aln´ı paraleln´ı algoritmus. Nyn´ı se pokusme pomoc´ı izoefektivn´ı funkce stanovit vhodnou granularitu algoritmu. S(n, p) = E(n, p) =
T (n, 1) = T (n, p)
n p0
n + log p0
n 1 1 1 S(n, p) = = = 0 ·log p0 = 0 0 p κ(n,p) κ(n,p) p n + p · log p 1+ n 1 + T (n,1) 1 + SU (n)
Ze vztahu 34 vypl´ yv´ a, ˇze κ(n, p) = p0 · log p0 . Vyj´adˇr´ıme-li izoefektivn´ı funkci jako ´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
(33) (34)
Pˇr´ıklad anal´ yzy paraleln´ıho algoritmu
T (n, 1) ≥ c · κ(n, p) n ≥ c · p0 · log p0
11
(35)
pak z nerovnice vypl´ yv´ a, ˇze zmˇen´ı-li se p0 na p00 , mus´ı se pro zachov´an´ı konstantn´ı efektivity 00 p00 zmˇenit tak´e n a to o n´ asobek pp0 ·log ·log p0 . Na z´avˇer si stanovme absolutn´ı minim´aln´ı ˇcas simulovan´eho algoritmu. Jak jiˇz bylo zm´ınˇeno, lok´ aln´ı operace a komunikace stoj´ı 2 jednotky ˇcasu. Derivujme paraleln´ı ˇcas podle p0 T (n, p) = ∂T (n,p0 ) ∂p0 ∂T (n,p0 ) ∂p0
= =
n 0 p0 + 2 · log p −n + p20 = 0 p02 2p0 −n =0 p02
(36)
odtud popt =
n 2
(37)
Dosazen´ım z´ısk´ ame minim´ aln´ı paraleln´ı ˇcas Tmin (n, popt ) = 2 + 2 · log n2 Tmin (n, popt ) = 2 + 2(log n + log 12 ) Tmin (n, popt ) = 2 · log n = Θ(log n)
´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
(38)
Kontroln´ı ot´azky
3
12
Kontroln´ı ot´ azky • Co vyjadˇruje cena a pr´ ace paraleln´ıho algoritmu? • Co vyjadˇruje efektivita paraleln´ıho algoritmu? Jak´e maxim´aln´ı a minim´aln´ı hodnoty efektivity m˚ uˇze paraleln´ı algoritmus dos´ ahnout? • Co je to ˇsk´ alovatelnost paraleln´ıho algoritmu? • Jak´e by mˇely b´ yt ide´ aln´ı pr˚ ubˇehy graf˚ u zrychlen´ı a efektivity dobˇre ˇsk´alovateln´ ych paraleln´ıch algoritm˚ u? • Co je to granularita paraleln´ıho algoritmu? • Co vyjadˇruje izoefektivita paraleln´ıho algoritmu? Jak ji definujeme? • Co vyjadˇruje Karp-Flattova metrika paraleln´ıho algoritmu?
´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
