´ ´I PARALELN´I PROCESY A PROGRAMOVAN 9 Propojovac´ı s´ıtˇ e (ICNW) 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
1 Propojovac´ı s´ıtˇ e (ICNW) 1.1 Z´akladn´ı pojmy a terminologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Z´akladn´ı poˇzadavky na propojovac´ı s´ıtˇe . . . . . . . . . . . . . . . . . . . . . . . . .
3 3 5
Obsah
2 Z´ akladn´ı typy topologi´ı 2.1 Striktnˇe ortogon´ aln´ı topologie . . . . . . . . . . . . . 2.1.1 Qn , n-rozmˇern´ a bin´ arn´ı hyperkrychle . . . . . 2.1.2 M (z1 , z2 , ..., zn ), n-rozmˇern´a mˇr´ıˇzka . . . . . 2.1.3 T (z1 , z2 , ..., zn ), n-rozmˇern´ y toroid . . . . . . 2.2 Hyperkubick´e topologie . . . . . . . . . . . . . . . . 2.2.1 CCCn , kruˇznice propojen´e krychl´ı dimenze n 2.2.2 wBFn , zabalen´ y mot´ ylek dimenze n . . . . . 2.2.3 oBFn , obyˇcejn´ y mot´ ylek dimenze n . . . . . . 2.3 Stromov´e topologie . . . . . . . . . . . . . . . . . . . 2.4 Posuvn´e topologie . . . . . . . . . . . . . . . . . . . 2.4.1 SEn , orientovan´ a Shuffle-Exchange s´ıt’ . . . . 2.4.2 dBd,n , orientovan´ a de Bruijnova s´ıt’ . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
3 Kontroln´ı ot´ azky
´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
5 6 6 7 8 8 8 9 10 10 11 12 12 13
OBSAH
ˇ Y ´ OBSAH PREDN ˇ ´ SKY ˇ STRUCN A Z´akladn´ı pojmy, terminologie a poˇzadavky Z´akladn´ı typy topologi´ı ICNW - Striktnˇe ortogon´ aln´ı topologie - Hyperkubick´e topologie - Stromov´e topologie - Posuvn´e topologie
MOTIVACE Propojovac´ı s´ıtˇe (ICNW) jsou jednou ze z´akladn´ıch komponent architektury paraleln´ıch poˇc´ıtaˇc˚ u a slouˇz´ı k propojen´ı jednotliv´ ych v´ ypoˇcetn´ıch uzl˚ u MIMD syst´em˚ u. Jejich topologie a vlastnosti do znaˇcn´e m´ıry ovlivˇ nuj´ı z´akladn´ı charakteristiky cel´eho paraleln´ıho syst´emu. V t´eto kapitole si pop´ıˇseme nejˇcastˇeji pouˇz´ıvan´e propojovac´ı s´ıtˇe.
C´IL Sezn´amit se s z´ akladn´ımi topolegiemi propojovac´ıch s´ıt´ı paraleln´ıch syst´emu, jejich vlastnostmi a poˇzadavky na nˇe kladen´ ymi.
´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
2
Propojovac´ı s´ıtˇe (ICNW)
1
3
Propojovac´ı s´ıtˇ e (ICNW)
Propojovac´ı s´ıtˇe paraleln´ıch poˇc´ıtaˇc˚ u se dˇel´ı na dva z´akladn´ı typy: • pˇ r´ım´ e s´ıtˇ e, • nepˇ r´ım´ e s´ıtˇ e (smˇerovaˇce). Pˇr´ım´e s´ıtˇe obsahuj´ı pˇr´ım´e komunikaˇcn´ı linky propojuj´ıc´ı smˇerovaˇce jednotliv´ ych v´ ypoˇcetn´ıch uzl˚ u, kdeˇzto nepˇr´ım´e s´ıtˇe jsou sloˇzeny z mnoˇziny vz´ajemnˇe propojen´ ych smˇerovaˇc˚ u kde pouze nˇekter´e (koncov´e) smˇerovaˇce jsou propojeny s v´ ypoˇcetn´ımi uzly. Lze ˇr´ıci, ˇze u pˇr´ım´ ych s´ıt´ı je poˇcet smˇerovaˇc˚ u roven poˇctu v´ ypoˇcetn´ıch uzl˚ u, kdeˇzto u nepˇr´ım´ ych s´ıt´ı je poˇcet smˇerovaˇc˚ u obecnˇe vˇetˇs´ı, neˇz poˇcet v´ ypoˇcetn´ıch uzl˚ u. Aby bylo moˇzn´e vytv´ aˇret optim´ aln´ı paraleln´ı algoritmy pro MIMD syst´emy, je nutn´e tak´e optim´alnˇe navrhnout topologii propojovac´ı s´ıtˇe tak, aby umoˇzn ˇovala implementaci efektivn´ıch smˇerovac´ıch algoritm˚ u. Z toho d˚ uvodu je zapotˇreb´ı definovat model topologie propojovac´ı s´ıtˇe, na z´akladˇe kter´eho budou dan´e algoritmy vytv´aˇreny. Pro matematick´ y popis topologie propojovac´ıch s´ıt´ı lze pouˇz´ıt nˇekter´e poznatky a pojmy z teorie graf˚ u [1], jak je uvedeno v n´asleduj´ıc´ı kapitole.
1.1
Z´ akladn´ı pojmy a terminologie
Uzel Uzel grafu popisuj´ıc´ıho topologii propojovac´ı s´ıtˇe pˇredstavuje konkr´etn´ı v´ ypoˇcetn´ı uzel paraleln´ıho poˇc´ıtaˇce, tj. jeden nebo v´ıce procesor˚ u s lok´aln´ı pamˇet´ı a komunikaˇcn´ı smˇerovaˇc. Hrana Hrana grafu popisuje komunikaˇcn´ı linku (sbˇernici, s´ıt’ov´e propojen´ı) mezi dvˇema uzly. Abeceda Uzly jsou znaˇceny pomoc´ı ˇretˇezc˚ u nad urˇcitou abecedou. Obecnou d-´arn´ı abecedu definujeme jako mnoˇzinu symbol˚ u Zd = {0, 1, ..., d − 1}. Mnoˇzina vˇsech n-znakov´ ych d-´arn´ıch ˇ pouˇz´ıvanou abecedou je bin´arn´ı abeceda Z2 = β, napˇr. ˇretˇezc˚ u kde n ≥ 1 se znaˇc´ı Zdn . Casto Z23 = β 3 = {000, 001, 010, 011, 100, 101, 110, 111}. Graf Graf G je urˇcen´ y mnoˇzinou uzl˚ u V (G) a hran E(G), znaˇceno G = (V (G), E(G)). Podgraf (Subgraf ) E(H) ⊂ E(G). Propojen´ y graf
Graf H je podgrafem grafu G, znaˇceno H ⊂ G, plat´ı-li V (H) ⊂ V (G) a
Vˇsechny p´ ary vrchol˚ u jsou spojen´e cestou P .
Delka cesty len(P )
Poˇcet hran v cestˇe.
Vzd´ alenost mezi vrcholy distG (u, v) Pr˚ umˇ er grafu ∅(G)) Stupeˇ n uzlu Stupeˇ n grafu
Nejmenˇs´ı d´elka cesty mezi vrcholy u a v.
Maxim´ aln´ı vzd´alenost mezi dvˇema vrcholy grafu G.
Stupeˇ n uzlu grafu degG (u) je poˇcet propojen´ ych soused˚ u uzlu u. Stupeˇ n grafu deg(G) je definov´an jako max({degG (u); u ∈ V (G)}).
´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
Propojovac´ı s´ıtˇe (ICNW)
4
k-regul´ arn´ı graf Graf oznaˇc´ıme jako k-regul´ arn´ı jestliˇze jeho maxim´aln´ı stupeˇ n ∆(G) je roven jeho minim´aln´ımu stupni δ(G) je rovno k, tj. vˇsechny uzly grafu maj´ı stupeˇ n k. Hamiltonovsk´ y graf Graf je oznaˇcen jako hamiltonovsk´ y obsahuje-li uzavˇrenou cestu nebo kruˇznici (hamiltonovskou kruˇznici) vedenou pˇres vˇsechny jeho uzly. Bipartitn´ı graf Graf je oznaˇcen jako bipartitn´ı, jestliˇze lze oznaˇcit jeho uzly dvˇema barvami tak, ˇze ˇz´adn´ y uzel nem´ a souseda stejn´e barvy. Pˇr´ıklady bipartitn´ıch graf˚ u jsou uvedeny na obr´azku 1.
Obr´ azek 1: Bipartitn´ı grafy Souvislost grafu Je to minim´ aln´ı poˇcet uzl˚ u (uzlov´ a symetrie) nebo hran ( hranov´ a symetrie) jejichˇz odebr´ an´ım dojde k rozpojen´ı grafu. Bisekˇ cn´ı ˇ s´ıˇ rka Hranov´ a bwe (G) nebo uzlov´a bwv (G) bisekˇcn´ı ˇs´ıˇrka grafu pˇredstavuje nejmenˇs´ı poˇcet hran nebo uzl˚ u, jejichˇz odebr´ an´ım rozdˇel´ıme graf na 2 stejn´e podgrafy, jak je vidˇet na obr´ azku 2.
Obr´ azek 2: Bisekˇcn´ı ˇs´ıˇrka grafu Kart´ ezsk´ y souˇ cin graf˚ u Kart´ezsk´ y souˇcin graf˚ u G a H vznikne tak, ˇze vˇsechny vrcholy grafu G nahrad´ıme grafem H a propoj´ıme stejnolehl´e vrcholy nov´ ych instanc´ı grafu G podle topologie grafu H, jak je ilustrov´ ano na obr´ azku 3.
Obr´ azek 3: Kart´ezsk´ y souˇcin graf˚ u Symetrick´ y graf Graf oznaˇc´ıme jako hranovˇe/uzlovˇe symetrick´ y, lze-li pohl´ıˇzet na jeho topologii z libovoln´e hrany/uzlu vˇzdy stejnˇe. Pˇr´ıklady symetrick´ ych graf˚ u jsou uvedeny na obr´azku 4.
´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
Z´akladn´ı typy topologi´ı
5
Obr´ azek 4: Symetrick´e grafy Izomorfn´ı grafy Dva grafy jsou izomorfn´ı, pokud maj´ı stejn´ y poˇcet uzl˚ u a lze je jejich posunem ztotoˇznit, jak je ilustrov´ ano na obr´ azku 5.
Obr´azek 5: Izomorfn´ı grafy Jsou-li uzly obou graf˚ u nav´ıc stejnˇe pojmenov´any, mluv´ıme o autoizomorfn´ım grafu.
1.2
Z´ akladn´ı poˇ zadavky na propojovac´ı s´ıtˇ e
Na propojovac´ı s´ıtˇe jsou kladeny tyto obecn´e poˇzadavky, jejichˇz splnˇen´ı umoˇzn ˇuje efektivn´ı a bezpeˇcnou komunikaci mezi propojen´ ymi • Mal´ y a konstantn´ı stupeˇ n uzlu. V´ yrobnˇe a finanˇcnˇe m´enˇe n´aroˇcn´e ˇreˇsen´ı, protoˇze celou ’ s´ıt lze sestavit pomoc´ı jednoho typu smˇerovaˇce. • Mal´ y pr˚ umˇ er a mal´ a pr˚ umˇ ern´ a vzd´ alenost. D´ıky menˇs´ı rozloze s´ıtˇe je moˇzn´e zajistit rychlejˇs´ı komunikaci. • Symetrie. Snazˇs´ı n´ avrh komunikaˇcn´ıch algoritm˚ u. • Hierarchick´ a rekurzivita. Graf obsahuje instance sebe sama (subgrafy) ˇc´ımˇz se usnadˇ nuje tvorba algoritm˚ u dynamicky distribuuj´ıc´ıch pr´aci uvnitˇr s´ıtˇe. • Vysok´ a souvislost. S´ıt’ je odolnˇejˇs´ı v˚ uˇci poruch´am. • Vysok´ a bisekˇ cn´ı ˇ s´ıˇ rka. S rostouc´ı bisekˇcn´ı ˇs´ıˇrkou se zvyˇsuje tak´e pˇrenosov´a kapacita s´ıtˇe. • Podpora pro smˇ erov´ an´ı a kolektivn´ı operace. Topologie s´ıtˇe a jej´ı HW by mˇela umoˇzn ˇovat implementaci jednoduch´ ych smˇerovac´ıch algoritm˚ u. • Vnoˇ ritelnost a simulace. Topologie s´ıtˇe by mˇela umoˇznit vnoˇren´ı (simulaci) jin´ ych topologi´ı.
2
Z´ akladn´ı typy topologi´ı
V t´eto kapitole se budeme zab´ yvat zejm´ena pˇr´ım´ ymi propojovac´ımi s´ıtˇemi. Topologie tˇechto s´ıt´ı lze rozdˇelit do nˇekolika skupin: • Striktnˇe ortogon´ aln´ı topologie • Hyperkubick´e topologie • Stromov´e topologie • Posuvn´e topologie ´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
Z´akladn´ı typy topologi´ı
2.1
6
Striktnˇ e ortogon´ aln´ı topologie
Mezi striktnˇe ortogon´ aln´ı topologie patˇr´ı zejm´ena hyperkrychle, mˇr´ıˇzka a toroid. Spoleˇcn´ ym znakem tˇechto s´ıt´ı je ortogonalita a znaˇcen´ı uzl˚ u pomoc´ı adres, jeˇz se od sv´ ych soused˚ u liˇs´ı v jedn´e souˇradnici o jedniˇcku, popˇr. pouze v jednom bitu. 2.1.1
Qn , n-rozmˇ ern´ a bin´ arn´ı hyperkrychle
Obr´ azek 6: 4-rozmˇern´a hypekrychle Q4 Tabulka 1: Vlastnosti hyperkrychle V (Qn ) = β n E(Qn ) = {hx, negi (x)i; x ∈ V (Qn ), 0 ≤ i < n} φ(Qn ) = n bwe (Qn ) = 2n−1
|V (Qn )| = 2n |E(Qn )| = n2n−1 deg(Qn ) = {n}
Qn je uzlovˇe i hranovˇe symetrick´ a, hierarchicky rekurzivn´ı topologie, kde kaˇzdou vyˇsˇs´ı dimenzi lze zkonstruovat pomoc´ı kart´ezsk´eho souˇcinu subgraf˚ u stejn´e topologie o niˇzˇs´ıch dimenz´ıch. Jednotliv´e uzly grafu jsou znaˇceny pomoc´ı bin´arn´ıch slov kde d´elka slova je rovna dimenzi hyperkrychle. Jak tak´e vypl´ yv´ a z konstrukce mnoˇziny jejich hran, adresy vˇsech sousedn´ıch uzl˚ u se od sebe liˇs´ı pr´avˇe v jednom bitu, coˇz vˇse usnadˇ nuje tvorbu smˇerovac´ıch a vnoˇrovac´ıch algoritm˚ u. V´ yhodou t´eto topologie je mal´ y pr˚ umˇer s´ıtˇe, velk´a bisekˇcn´ı ˇs´ıˇrka a velk´a souvislost. S´ıt’ nav´ıc umoˇzn ˇuje vnoˇren´ı t´emˇeˇr jak´ekoliv jin´e topologie. Nev´ yhodou hyperkrychle je pouze ˇca´steˇcn´a ˇsk´alovatelnost (pro vytvoˇren´ı topologie s dimenz´ı o 1 vyˇsˇs´ı je zapotˇreb´ı dvojn´ asobn´ y poˇcet uzl˚ u) a pˇredevˇs´ım rostouc´ı stupeˇ n uzlu/s´ıtˇe, coˇz znamen´ a, ˇze pˇri zvˇetˇsov´ an´ı dimenze s´ıtˇe bude zapotˇreb´ı komunikaˇcn´ı HW s vyˇsˇs´ım poˇctem I/O kan´al˚ u. Komerˇcnˇe vyr´ abˇen´e paraleln´ı poˇc´ıtaˇce vyuˇz´ıvaj´ıc´ı tuto topologii byly napˇr´ıklad nCUBE, iPSC/2, iPSC/860, a CM-2 [1].
´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
Z´akladn´ı typy topologi´ı
2.1.2
7
M (z1 , z2 , ..., zn ), n-rozmˇ ern´ a mˇ r´ıˇ zka
Obr´ azek 7: 3-rozmˇern´a mˇr´ıˇzka M (3, 3, 2)
Tabulka 2: Vlastnosti mˇr´ıˇzky V (M (...)) = {(a1 , a2 , .., an ); 0 ≤ ai ≤ zi − 1∀i ∈ {1, .., n}} E(M (...)) = {h(.., ai , ..), (..ai + 1, ..)i; 0 ≤ ai ≤ zi − 2} P φ(M (...)) = ni=1 (zi − 1) deg(M (...)) = {n, .., n + j}, j = |{zi ; zi > 2}|
Q |V (M (...))| = ni=1 zi P Q |E(M (...))| = ni=1 (zi − 1) nj=1,j6=i zj Qn bwe (M (...)) = ( i=1 zi )/ maxi zi
M (z1 , z2 , ..., zn ) je hierarchicky rekurzivn´ı topologie, kter´a nen´ı regul´arn´ı a tud´ıˇz ani uzlovˇe a a hranovˇe symetrick´ a. Jednotliv´e uzly jsou znaˇceny pomoc´ı kart´ezsk´ ych souˇradnic, kde se soused´e v dan´e dimenzi liˇs´ı pouze o jedniˇcku. V kaˇzd´e mˇr´ıˇzce lze nal´ezt subgrafy stejn´e topologie o stejn´e dimenzi, ale s niˇzˇs´ımi hodnotami jednotliv´ ych dimenz´ı. Nejˇcastˇeji pouˇz´ıvan´e topologie tohoto typu jsou 2-D a 3-D mˇr´ıˇzky. Topologie m´ a velk´ y pr˚ umˇer a optim´aln´ı souvislost. Hodnota bisekˇcn´ı ˇs´ıˇrky je z´avisl´a na poˇctu a rozmˇeru jednotliv´ ych dimenz´ı. Mˇr´ıˇzka je ˇc´ astˇeˇcnˇe ˇskolovateln´ a (l´epe neˇz hyperkostka). Mezi komerˇcn´ı paraleln´ı poˇc´ıtaˇce s mˇr´ıˇzkovou topologi´ı patˇr´ı napˇr´ıklad Intel Paragon (2-D), MIT J-Machine (3-D) [1].
´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
Z´akladn´ı typy topologi´ı
2.1.3
8
T (z1 , z2 , ..., zn ), n-rozmˇ ern´ y toroid
Obr´ azek 8: 3-rozmˇern´ y toroid T (3, 3, 2)
Tabulka 3: Vlastnosti toroidu V (T (...)) = V (M (...)) E(T (...)) = {h(.., ai , ..), (..ai ⊕ 1, ..)i; 0 ≤ ai ≤ zi } P φ(T (...)) = ni=1 bzi /2c deg(T (...)) = {2n}
|V (T (...))| = |V (M (...))| Q |E(T (...))| = n × ni=1 zi bwe (T (...)) = 2bwe (M (...))
Toroid se liˇs´ı od mˇr´ıˇzky pouze t´ım, ˇze kaˇzd´a line´arn´ı ˇrada uzl˚ u je spojena do kruˇznice pˇrid´ an´ım jedn´e hrany spojuj´ıc´ı koncov´e uzly ˇrady (obaluj´ıc´ı hrana). Stejnˇe jako mˇr´ıˇzky i toroidy jsou nejˇcastˇeji pouˇz´ıvan´e jako 2-D nebo 3-D. D´ıky pˇrid´ an´ı obaluj´ıc´ı hrany se oproti mˇr´ıˇzce st´av´a toroid regul´arn´ı, uzlovˇe symetrickou topologi´ı. Toroid je hierarchicky rekurzivn´ı (vznik´a kart´ezsk´ ym souˇcinem kruˇznic), nelze jej vˇsak dekomponovat na menˇs´ı subgrafy se stejnou dimenz´ı (dojde k rozpojen´ı kruˇznic). Oproti mˇr´ıˇzce m´ a toroid poloviˇcn´ı pr˚ umˇer a dvojn´asobnou bisekˇcn´ı ˇs´ıˇrku. Toroidy byly a jsou hojnˇe vyuˇz´ıv´ any v komerˇcn´ıch masivnˇe paraleln´ıch poˇc´ıtaˇc´ıch. Zmiˇ nme napˇr´ıklad T3D a T3E firmy SGI/Cray, nebo IBM BlueGene [1].
2.2
Hyperkubick´ e topologie
Hyperkubick´e topologie vych´ az´ı z bin´ arn´ı hyperkrychle a snaˇz´ı se vyˇreˇsit jej´ı nejvˇetˇs´ı nev´ yhodu spoˇc´ıvaj´ıc´ı v logaritmicky rostouc´ım stupni uzlu s rostouc´ı dimenz´ı hyperkrychle. N´ami diskutovan´e hyperkubick´e topologie ˇreˇs´ı tento probl´em rozvinut´ım vrchol˚ u hyperkrychle do kruˇznice nebo line´arn´ıho pole. Takto vznikl´e topologie mohou b´ yt regul´arn´ı s konstantn´ım stupnˇem uzlu, jsou optim´ aln´ı z hlediska pr˚ umˇeru s´ıtˇe a maj´ı velmi dobrou bisekˇcn´ı ˇs´ıˇrku. Na druhou stranu maj´ı zhorˇsenou ˇc´asteˇcnou ˇsk´ alovatelnost. 2.2.1
CCCn , kruˇ znice propojen´ e krychl´ı dimenze n
Topologie CCCn vznikne z hyperkrychle o dimenzi n rozvinut´ım jej´ıch vrchol˚ u do kruˇznic tvoˇren´ ych n uzly. Vrcholov´e znaˇcen´ı uzl˚ u CCCn se skl´ad´a z kruˇznicov´eho indexu uzlu a hyperkubick´e adresy
´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
Z´akladn´ı typy topologi´ı
(a) CCC3
9
(b) CCC4
Obr´azek 9: CCCn Tabulka 4: Vlastnosti CCCn V (CCCn ) = {(i, x); 0 ≤ i < n ∧ x ∈ β n } E(CCCn ) = {h(i, x), (i ⊕n 1, x)i, h(i, x), (i, negi (x))i; (i, x) ∈ V (CCCn )} φ(CCCn ) = (2n − 2) + bn/2c pro n > 3, φ(CCC3 ) = 6 deg(CCCn ) = 3
|V (CCCn )| = n2n |E(CCCn )| = n2n−1 + n2n bwe (CCCn ) = 2n−1
kruˇznice. Hodnota kruˇznicov´eho indexu z´aroveˇ n ud´av´a, jak´e dimenze hyperkrychle dan´ y uzel propojuje. Topologie je uzlovˇe symetrick´ a, nen´ı vˇsak hranovˇe symetrick´a, protoˇze v s´ıti existuj´ı dva typy hran: kruˇznicov´e a hyperkubick´e. Jak je patrn´e z obr´azku 9 i z tabulky 4, topologie je 3-regul´ arn´ı, tj. kaˇzd´ y uzel m´ a pouze 3 sousedy bez ohledu na dimenzi s´ıtˇe. Graf CCCn je hamiltonovsk´ y, nen´ı vˇsak hierarchicky rekurzivn´ı. Doposud nebyl sestrojen ˇz´ adn´ y komerˇcn´ı paraleln´ı poˇc´ıtaˇc s touto topologi´ı. 2.2.2
wBFn , zabalen´ y mot´ ylek dimenze n
Topologie wBFn je podobn´ a CCCn s t´ım rozd´ılem, ˇze m´a vˇetˇs´ı poˇcet hran a tud´ıˇz menˇs´ı pr˚ umˇer a vˇetˇs´ı bisekˇcn´ı ˇs´ıˇrku. Rozd´ıl v konstrukci hran spoˇc´ıv´a v tom, ˇze hyperkubick´e hrany nepropojuj´ı protˇejˇs´ı uzly ve stejn´e dimenzi, ale v dimenzi o jedniˇcku vyˇsˇs´ı modulo poˇcet dimenz´ı, jak je patrn´e z tabulky 5.
(a) wBF3
(b) wBF4
Obr´azek 10: wBFn ´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
Z´akladn´ı typy topologi´ı
10
Tabulka 5: Vlastnosti wBFn V (wBFn ) = {(i, x); 0 ≤ i < n ∧ x ∈ β n } E(wBFn ) = {h(i, x), (i ⊕n 1, x)i, h(i, x), (i ⊕n 1, negi (x))i|(i, x) ∈ V (wBFn )} φ(wBFn ) = 2n + bn/2c deg(wBFn ) = 4
(a) oBF3
|V (wBFn )| = n2n |E(wBFn )| = n2n+1 bwe (wBFn ) = 2n
(b) BF4
Obr´azek 11: oBFn S´ıt’ vykazuje konstantn´ı stupeˇ n uzl˚ u (je 4-regul´arn´ı) a nen´ı hranovˇe symetrick´a. Graf wBFn je hamiltonovsk´ y, nen´ı vˇsak hierarchicky rekurzivn´ı. Stejnˇe jako v pˇr´ıpadˇe CCCn ani tato topologie nebyla doposud pouˇzita pro fyzickou realizaci komerˇcn´ıho paraleln´ıho poˇc´ıtaˇce. 2.2.3
oBFn , obyˇ cejn´ y mot´ ylek dimenze n Tabulka 6: Vlastnosti oBFn V (oBFn ) = {(i, x); 0 ≤ i ≤ n ∧ x ∈ β n } E(oBFn ) = {h(i, x), (i + 1, x)i, h(i, x), (i + 1, negi (x))i|i < n} φ(oBFn ) = 2n deg(oBFn ) = {2, 4}
|V (oBFn )| = (n + 1)2n |E(oBFn )| = n2n+1 bwe (oBFn ) = 2n
Topologie oBFn vznikne tak, ˇze rozdˇel´ıme p˚ uvodn´ı kruˇznici (subgraf hyperkubick´eho uzlu) v uzlu 0 a ten zdvoj´ıme, ˇc´ımˇz vznikne pro kaˇzd´ y uzel n-rozmˇern´e zdrojov´e hyperkrychle line´arn´ı pole o n + 1 uzlech. Posledn´ı, dodateˇcn´ y uzel se star´a o pˇrechod do nejvyˇsˇs´ı dimenze hyperkrychle, jak je patrn´e z obr´ azku 11. oBFn nen´ı ani symetrick´ y, ani regul´arn´ı, je ale hierarchicky rekurzivn´ı. Je bipartitn´ı, nen´ı vˇsak hamiltonovsk´ y. Na rozd´ıl od dvou pˇredchoz´ıch sestersk´ ych topologi´ı, oBFn byl pouˇzit pro konstrukci paraleln´ıho poˇc´ıtaˇce.
2.3
Stromov´ e topologie
Strom je sice ide´ aln´ı datovou a algoritmickou strukturou, vzhledem ke sv´ ym vlastnostem se vˇsak pˇr´ıliˇs nehod´ı pro realizaci fyzick´e ICNW. Hlavn´ım probl´emem je velmi mal´a souvislost a bisekˇcn´ı ˇs´ıˇrka (v obou pˇr´ıpadech prakticky rovna 1), coˇz znamen´a, ˇze s´ıt’ je n´achyln´a k fat´aln´ım poruch´ am (rozpojen´ı) a zahlcen´ı komunikaˇcn´ıch linek u koˇrenov´eho uzlu (vˇsechny listy lev´eho podstromu ´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
Z´akladn´ı typy topologi´ı
(a) CBT4
11
(b) CBT5
Obr´azek 12: CBTn komunikuj´ı s listy prav´eho podstromu pouze prostˇrednictv´ım linek koˇrenov´eho uzlu). S´ıt’ typu kompletn´ı bin´ arn´ı strom o v´yˇsce n - CBTn je zobrazena na obr´azku 12. Z´akladn´ı vlastnosti obecn´eho stromu jsou pak uvedeny v tabulce 7. Tabulka 7: Vlastnosti CTd,n V (CTd,n ) = ∪ni=0 Zdi E(CTd,n ) = {hx, xai|len(x) < n ∧ a ∈ Zd } φ(CTd,n ) = 2n deg(CTd,n ) = {1, d, d + 1}
n+1
|V (CTd,n )| = d d−1−1 |E(CTd,n )| = |V (CTd,n )| − 1 bwe (CTd,n ) = 1
´ Uvahy o vylouˇcen´ı, nebo alespoˇ n minimalizaci neˇz´adouc´ıch vlastnost´ı t´eto s´ıtˇe vedly k nˇekolika modifikac´ım stromov´e topologie. Pro ilustraci si uved’me alespoˇ n tˇri takov´e: • Tlust´ y strom je topologi´ı zaloˇzenou na stromov´e topologii s t´ım rozd´ılem, ˇze poˇcet linek spojuj´ıc´ı koˇren podstromu s jeho rodiˇcem je roven poˇctu list˚ u cel´eho podstromu. • Zabalen´ y strom je takov´ a topologie, kdy ve stromˇe existuj´ı tak´e linky propojuj´ıc´ı sousedn´ı uzly ve stejn´e u ´rovni stromu (vˇcetnˇe krajn´ıch) uzl˚ u. • Mˇ r´ıˇ zka strom˚ u vznikne slouˇcen´ım nˇekolika strom˚ u takov´ ym zp˚ usobem ˇze koncov´e listy strom˚ u pˇredstavuj´ıc´ıch sloupce mˇr´ıˇzky jsou ztotoˇznˇeny s koncov´ ym uzly strom˚ u pˇredstavuj´ıc´ımi ˇr´ adky mˇr´ıˇzky. Vˇsechny tyto (a dalˇs´ı podobn´e) modifikace vedly z n´ar˚ ustu bisekˇcn´ı ˇs´ıˇrky a souvislosti stromov´e topologie a zmenˇsen´ı jej´ıho pr˚ umˇeru, ˇc´ımˇz bylo dosaˇzeno vyˇsˇs´ı spolehlivosti s´ıtˇe i jej´ı datov´e propustnosti. Na z´akladˇe tlust´ eho stromu byl zkonstruov´an napˇr. paraleln´ı poˇc´ıtaˇc CM-5 [1].
2.4
Posuvn´ e topologie
Hlavn´ım specifikem posuvn´ ych topologi´ı je zp˚ usob konstrukce hran grafu. Oproti pˇredchoz´ım typ˚ um, kde byly adresy sousedn´ıch uzl˚ u poˇc´ıt´any pˇrev´aˇznˇe pomoc´ı operac´ı negace ˇci inkrementace, jsou u posuvn´ ych topologi´ı pouˇzity sp´ıˇse operace posunu a rotace. V´ ysledn´e topologie pot´e obsahuj´ı velk´e mnoˇzstv´ı kruˇznic, coˇz ovlivˇ nuje jejich z´akladn´ı vlastnosti. Mezi posuvn´e topologie patˇr´ı s´ıtˇe Shuffle-Exchange (SE), de Bruijnova a Kautzova s´ıt’. Charakteristick´e vlastnosti posuvn´ ych topologi´ı jsou: ´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
Z´akladn´ı typy topologi´ı
12
• logaritmick´ y pr˚ umˇer a konstantn´ı stupeˇ n uzlu, • optim´aln´ı souvislost, • velk´a bisekˇcn´ı ˇs´ıˇrka, • jednoduch´e smˇerovac´ı algoritmy, • nesymetrick´e topologie, • hierarchicky nerekurzivn´ı topologie. 2.4.1
SEn , orientovan´ a Shuffle-Exchange s´ıt’
Hrany grafu t´eto topologie jsou tvoˇreny pomoc´ı dvou operac´ı: shuffle (prom´ıch´ an´ı, σ(x)) a exchange (z´ amˇena, neg0 (x)), coˇz pˇredstavuje rotaci o jeden bit doleva a inverzi nejniˇzˇs´ıho v´ yznamov´eho bitu v bin´arn´ı adrese uzlu. Pro kaˇzd´ y uzel grafu tak vzniknou dvˇe hrany - jedna pomoc´ı operace shuffle a druh´a pomoc´ı operace exchange, jak je patrn´e z tabulky 8 a obr´azku 13.
010
000
011
001
110
100
111
101
Obr´azek 13: SEn Tabulka 8: Vlastnosti SEn V (SEn ) = β n E(SEn ) = {hx → neg0 (x)i, hx → σ(x)i; x ∈ β n } φ(SEn ) = 2n − 1 deg(SEn ) = {2}
2.4.2
|V (SEn )| = 2n |E(SEn )| = 2n+1 n bwe (SEn ) = Θ( 2n )
dBd,n , orientovan´ a de Bruijnova s´ıt’
V pˇr´ıpadˇe dBruijnovy posuvn´e s´ıtˇe se adresy sousedn´ıch uzl˚ u konstruuj´ı pomoc´ı operace posunu λ(x, a) o jednu pozici doleva, kde na posledn´ı m´ısto vloˇz´ıme nov´ y znak abecedy. Kaˇzd´ y uzel tak bude m´ıt d soused˚ u pro d-´ arn´ı abecedu, kde na prvn´ı (pravou) pozici postupnˇe vloˇz´ıme vˇsechny znaky abecedy pouˇzit´e pro konstrukci adres uzl˚ u. Z toho mimo jin´e vypl´ yv´a, ˇze v pˇr´ıpadˇe de Bruijnovy s´ıtˇe lze pro adresy uzl˚ u pouˇz´ıt libovolnou abecedu. Vlastnosti s´ıtˇe jsou uvedeny v tabulce 9. Zaj´ımavost´ı je, ˇze de Bruijnova s´ıt’ dB2,16 byla pouˇzita pro konstrukci poˇc´ıtaˇce vesm´ırn´e sondy Galileo ob´ıhaj´ıc´ı planetu Jupiter [1]. ´ ´ ´ ˚ ´ MODERNIZACE VYUKOV YCH MATERIAL U A DIDAKTICKYCH METOD CZ.1.07/2.2.00/15.0463
Kontroln´ı ot´azky
13
110 111
101
011
010
001
100 000
Obr´azek 14: dBd,n Tabulka 9: Vlastnosti dBd,n V (dBd,n ) = Zdn E(dBd,n ) = {hx → λ(x, a)i; x ∈ Zdn , a ∈ Zd φ(dBd,n ) = n = logd N deg(dBd,n ) = {d}
3
|V (dBd,n )| = dn |E(dBd,n )| = dn+1 n bwe (dBd,n ) = Θ( dn )
Kontroln´ı ot´ azky • Co je to ICNW a k ˇcemu slouˇz´ı? • Jak´e poˇzadavky klademe na ICNW paraleln´ıch syst´em˚ u? • Jak´e jsou z´ akladn´ı typy ICNW? • Jak´e jsou z´ akladn´ı vlastnosti ICNW a jak´ y maj´ı vliv na kvalitativn´ı mˇeˇr´ıtka paraleln´ıch algoritm˚ u?
´ ´ ´ ˚ ´ 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
14
