Csoportos üzenetszórás optimalizálása klaszter rendszerekben

Csoportos üzenetszórás optimalizálása klaszter rendszerekben Juhász Sándor, Csikvári András Budapesti Műszaki és Gazdaságtudományi Egyetem Villamosmérnöki és Informatikai Kar Automatizálási és Alkalmazott Informatikai Tanszék 1111 Budapest, Goldmann György tér 3. IV. em. E-mail: [email protected]

Kivonat A klaszterek, bár jelentős vetélytársai a hagyományos szuperszámítógépeknek, a kommunikációs alrendszerek sebessége területén még lemaradásban vannak, mivel a klaszterek csomópontjainak összekapcsolásánál használt általános célú kommunikációs elemek kisebb sávszélességet biztosítanak a drágább, speciálisan egy adott feladatra kifejlesztett társaiknál. Cikkünk a klaszter kommunikáció egy részterületével, a csoportos kommunikációs primitívek működésének gyorsításával foglalkozik. A különálló számítógépekből felépített klaszter rendszerekben a csomópontok együttműködésének megkönnyítésére különféle üzenetkezelő könyvtárak (pl. PVM, MPI) állnak rendelkezésre, melyek az üzenetküldés és fogadás mellett összetett csoport kommunikációs elemeket (ún. kommunikációs primitíveket) is biztosítanak a felettük működő programok számára. A kommunikációs primitívek hatékonyságát jelentősen befolyásolja a kommunikációs topológia (egy-több, fa, több-több), a szinkron vagy aszinkron végrehajtás, de akár a kommunikációs megoldás szimmetriája is. Cikkünkben az üzenetszórás (broadcast) primitív különféle klaszterekben gyakran használt implementációit vizsgáljuk meg alaposabban, majd bemutatunk egy, a hagyományostól lényegesen eltérő új algoritmust, mely az üzenetek részekre bontásával és szimmetria kialakításával tovább növeli a kommunikáció teljesítményét. Az újfajta algoritmus egy egy-mindenkinek (broadcast) típusú üzenetszórás primitívet definiál, mely az eddig ismert, különféle architektúrákban (lánc, hiperkocka, fa) megvalósítható O(n), O(dn1/d), O(logbn) komplexitású megoldásokkal szemben a klaszter architektúrában szoftveresen biztosítja a résztvevő csomópontok számától elvileg független, O(1) komplexitást, melyet eddig csak hardver támogatással lehetett elérni. A fent bemutatott megoldás alkalmazhatóságát mérésekkel illusztráljuk, melyek során az összehasonlítási alapot a számunkra elérhető leggyorsabb üzenetkezelő könyvtár implementáció (MPICH) saját üzenetszórás primitívje szolgáltatja. A cikkben leírt eredmények közvetlenül felhasználhatók a csoport kommunikációs primitívek teljesítményének növelésére, így közvetve hozzájárulnak a klaszter környezetben futó elosztott algoritmusok futási idejének javításhoz is.

I.

Bevezető

taszkok

A szabványos hálózati elemekből és személyi számítógépekből felépített klaszterek a hagyományos szuperszámítógépeknél olcsóbb alternatívát kínálnak a nagy számítási igényű feladatok elvégzésére, ráadásul a szabványos, redundáns elemekből felépülő klaszterekben a hibatűrés és a léptékezés megoldása lényegesen egyszerűbb. Számos előnyük ellenére a klaszterek nem szorították ki teljesen az egyéb típusú, kivétel nélkül drágább számítási teljesítményt nyújtó megoldásokat (SMP, NUMA, MMP és vektor szuperszámítógépek). Ennek egyik oka [1] a klaszterek kommunikációs alrendszerének relatív lassúsága, hiszen az általános célú kommunikációs elemek kisebb átbocsátó képességet biztosítanak drágább, speciálisan egy adott feladat elvégzésére kifejlesztett társaiknál, így a klasztereken futó az elosztott algoritmusok tervezésében kritikus szerephez jut a kommunikációs minta tervezése és a feldolgozás granularitás megfelelő nagyságának biztosítása [2]. A különálló számítógépekből felépített klaszter rendszerekben a csomópontok együttműködését szabványos hálózati kommunikációs közeg felett kell megszervezni. Ennek megkönnyítésére a különféle üzenetkezelő könyvtárak (pl. PVM [3], MPI [4][5]) az alapvető üzenetküldés és fogadás kommunikációs alapelemek mellett összetett csoport kommunikációs elemeket (ún. kommunikációs primitíveket) is biztosítanak a felettük működő programok számára. A kommunikációs primitívek hatékonyságát jelentősen befolyásolja a kommunikációs topológia (egytöbb, fa, tórusz, hiperkocka), a szinkron vagy aszinkron végrehajtás, de akár a kommunikációs megoldás szimmetriája is. A kommunikációs primitívek alapvető típusai az 1. ábrán láthatók. A különféle csoport kommunikációs funkciók megvalósítása az adott rendszerben jelentősen befolyásolja az adott könyvtárt használó alkalmazások teljesítményét. A kommunikáció maximális sebességét alapvetően meghatározzák az összekapcsoló hálózat olyan fizikai jellemzői, mint a késleltetés, a maximális sávszélesség, és a topológia. Számos kutatási eredmény [6][7][8] utal azonban arra, hogy a mai gyors hálózatok mellett a párhuzamos alkalmazások teljesítménye nem elsősorban a hardver, hanem sokkal inkább a szoftver korlátoktól függ. Különösen igaz ez a kisebb (16kB-nál rövidebb) üzenetekre, ahol a felhasználó alkalmazások között mérhető átviteli időnek csupán töredékét teszi ki a adatok hálózati közegen való átjutás ideje. A mai tipikus klaszter A0 A1 A2 A3 A0 B0 C0 D0 konfigurációk Fast Ethernet, Gigabit Ethernet, ATM vagy broadcast B0 B1 B2 B3 A0 B1 C1 D1 Myrinet [9] kapcsolatot használnak, és a csomópontok aktív hálózati kapcsolókon (switching hub) keresztül egy C0 C1 C2 C3 A0 B2 C2 D2 ütközésmentes, virtuális crossbar rendszerben D0 D1 D2 D3 A0 B3 C3 D3 kommunikálnak. A megbízható adatátvitel biztosításához scatter A0 A1 A2 A3 A0 B0 C0 D0 a fizikai hálózat fölé különféle többrétegű hálózati B0 B1 B2 B3 A1 B1 C1 D1 protokollokat (pl. TCP/IP) implementálnak. Az ilyen gather protokollok működtetése során a csomópontok számos C0 C1 C2 C3 A2 B2 C2 D2 protokollhoz kapcsoló üzenetet is kénytelenek küldeni, és D0 D1 D2 D3 A3 B3 C3 D3 szükség lehet az adatok többszöri másolására is a rétegek A0 A0 B0 C0 D0 között. Az érintett rétegek, az adatmásolások és a allgather kontextus váltások száma, az operációs rendszer különféle B0 A0 B0 C0 D0 időzítési és ütemezési mechanizmusai szintén közvetlenül C0 A0 B0 C0 D0 hozzájárulnak az overhead növekedéséhez [10]. Ha az D0 D1 D2 D3 A0 B0 C0 D0 adatcserében résztvevő csomópontok nem közvetlenül kapcsolódnak egymáshoz, akkor jelentős késleltetést A0 A1 A2 A3 A0 B0 C0 D0 alltoall okozhat az útvonalválasztó algoritmus és az érintett B0 B1 B2 B3 A1 B1 C1 D1 állomások is. Ilyen esetekben a célállomás C0 C1 C2 C3 A2 B2 C2 D2 visszajelzésének megérkezéséig számos másolatot kell D0 D1 D2 D3 A3 B3 C3 D3 fenntartani ugyanarról az adatról, mely a memória 1. ábra. Csoport kommunikációs primitívek erőforrások fogyasztásával jár, és így tovább lassíthatja a működést.

A fenti tulajdonságok egyértelműen meghatározzák a pont-pont kapcsolatokon keresztülmenő üzenetek sebességét. A különféle csoport kommunikációs primitívek megvalósítása elsősorban a pont-pont kapcsolatokra épül, azonban a belső struktúrájuktól függően lehetőség nyílhat bizonyos párhuzamosítások alkalmazására. A párhuzamosítások az egyszerű üzenetátvitel sebességétől függetlenül tovább gyorsíthatják a működést, illetve segítségével jobban kiegyenlíthetővé válik a terhelés. Elterjedten használják azt a módszert, hogy az üzenetek begyűjtését és szétosztását nem egy irányító szerepet játszó központi elem vezérli, hanem mellette több közbenső csomópont is részt vesz az adott művelet megszervezésében. A folyamatban résztvevő csomópontok gyűrű, fa, különféle dimenzió számú hiperkocka vagy más architektúrába rendeződhetnek. Az egyes kommunikációs primitívek eltérő természetük miatt különféle módon párhuzamosíthatók, melynek hatásfokát lényegesen befolyásolja a hardver összeköttetések típusa és topológiája. A csoport kommunikációs primitívek közül kiemelkedik az üzenetszórás (broadcast) funkció optimalizálásának fontossága, mivel ez, amellett, hogy önmagában is gyakran használják, más kommunikációs primitívek (allgather, alltoall, és az 1. ábrán nem szereplő, szinkronizálásra szolgáló barrier illetve az egyszerű feldolgozási művelettel összekapcsolt adatgyűjtést végrehajtó allreduce primitívek) alapvető építőkövéül is alkalmazható, így működésének optimalizálása egyszerre több funkciót is felgyorsít. Cikkünk az üzenetszórás (broadcast) primitív különféle megvalósításainak kérdéskörével foglalkozik, különös tekintettel a klaszter környezetben történő megvalósítás lehetőségeire. A tipikus klaszteres környezetben a csomópontok aktív hálózati eszközökön (switching hub) keresztül kapcsolódnak össze, így az ezek a kommunikáció szempontjából egy virtuális crossbar rendszert alkotnak. Ilyen összekapcsoló rendszer mellett a különféle kommunikációs megoldások és topológiák hatása –bizonyos határok között– hardver átalakítások nélkül is vizsgálható. Cikkünk első részében megvizsgáljuk az üzenetszórás primitív implementációjának különféle lehetőségeit, és bemutatunk egy, a hagyományostól lényegesen eltérő új algoritmust is, mely az üzenetek részekre bontásával és kommunikáció szimmetriájának kialakításával tovább növeli a kommunikáció teljesítményét. Az újfajta algoritmus egy olyan üzenetszórás típusú primitívet definiál, mely az eddig ismert, különféle architektúrákban (lánc, hiperkocka, fa) megvalósítható O(n), O(dn1/d), O(logbn) komplexitású megoldásokkal szemben a klaszter architektúrában szoftveresen biztosítja a résztvevő csomópontok számától elvileg független, O(1) komplexitást, melyet eddig ilyen környezetben csak hardver támogatás mellett lehetett elérni. A cikkünk második fejezetében bemutatjuk az üzenetszórás megvalósítására eddig használt módszereket, elemezzük a hardver támogatáson alapuló megoldások lehetőségeit és korlátjait, kitérve néhány egészen friss fejlesztés ismertetésére is. A harmadik fejezet a kutató csoportunk által kifejlesztett új megoldás ismertetését és elemzését tartalmazza, részletesen bemutatva, hogy a mindennapos klaszter környezetekben használt eszközökön hogyan valósítható meg szoftverből a csomópontok számától független üzenetszórási idő. A csomópontok számától való elvi függetlenség azonban még nem elegendő a gyakorlati felhasználáshoz, hanem az is fontos, hogy a gyakorlati jelentőséggel rendelkező paraméter tartományokban (csomópontszám, üzenetméret) az algoritmus valóban felülmúlja teljesítményben, skálázhatóságban és hordozhatóságban az eddigi megvalósításokat. A negyedik fejezetben az általunk kifejlesztett algoritmus alkalmazhatóságát egy teszt rendszerben elvégzett konkrét méréssorozat segítségével illusztráljuk. A mérésekhez az összehasonlítási alapot a számunkra elérhető leggyorsabb üzenetkezelő könyvtár implementáció (NT-MPICH v1.3.0 [11]) saját üzenetszórás primitívje szolgáltatja. Végül cikkünk egy összefoglalással zárul, mely áttekinti a bemutatott algoritmus előnyeit és használhatóságának korlátait, összehasonlítva az általunk bemutatott módszert a széles körben használt egyéb szoftver megoldásokkal és a hardver alapú fejlesztésekkel is. Bemutatjuk az eredményeink gyakorlati felhasználásának lehetőségeit és kitérünk a közeljövő kutatási terveire is.

II.

Az üzenetszórás megvalósításának különféle módszerei

Az a megfelelő teljesítményű elosztott alkalmazások egyszerű elkészítéséhez elengedhetetlen a rugalmas, skálázható és nagy teljesítménnyel rendelkező kommunikáció primitívek használata. Ebben a fejezetben a különféle üzenetszórási módszereket a fent említett három szempont alapján jellemezzük és hasonlítjuk össze egymással. A rugalmasságot a megoldás implementációjának egyszerűségével, hordozhatóságával és a megbízhatóság (hibatűrés, sorrendben és csakis egyszer történő kézbesítés) megvalósíthatóságával mérjük. A nagyobb teljesítmény érdekében az üzenetkezelő könyvtárak (pl. MPI szabvány [4]) csak azt írják elő, hogy a kollektív hívások blokkolóak, vagyis a hívóra eső kommunikációs rész elvégzéséig a hívás nem térhet vissza, azt viszont már nem, hogy a teljes kollektív kommunikáció befejeződésig várnia kellene (kivétel az éppen a szinkronizálásra szolgáló barrier primitív). Az előbbi feltétel miatt a teljesítményt az algoritmus teljes futási ideje mellett a kezdeményező csomóponton mért minimális elvi késleltetéssel is jellemezzük. A teljes futási időt az üzenetméret és csomópontok számának függvényében megadott aszimptotikus komplexitás függvénnyel jellemezzük. Az aszimptotikus komplexitás számításánál a széles körben elterjedt, az üzenethossz függvényében lineáris modellt [2][6][7][12][13][14][15] alkalmazzuk, és feltételezve, hogy a küldéshez és a fogadáshoz a teljes hálózati sávszélesség rendelkezésre áll (teljesítmény felső korlátja). A skálázhatóság fogalma az algoritmus a teljesítményének a csomópontok számától függő változását jellemzi [2][16]. Ezt általánosságban jól leírja a teljesítmény jellemzésével kapcsolatban már említett komplexitás függvény, de emellett figyelembe kell venni a központi elemek jelenlétét is, mert ezek bizonyos körülmények között könnyen szűk keresztmetszetté válhatnak. II.1

Üzenetszórás szoftveres módszerei

A különféle kommunikációs primitívek optimális megvalósíthatóságát erősen befolyásolja az alatta található hardver összekapcsolási topológia (közösen használt busz, hierarchikus busz, fa, gyűrű, hipertórusz, hiperkocka, crossbar). A klaszter architektúrák olcsó hardver felépítése a bennük használt szabványos feldolgozó és hálózati elemeknek köszönhető. A hálózati technológia mai fejlettségi szintjén a széles körben elterjedt, a nagy sávszélességű eszközök (100 Mbit/s Fast Ethernet, Gigabit Ethernet) ára hasonló, sőt egyes esetekben alacsonyabb is a régi kisebb sávszélességű eszközöknél, és aktív hálózati kapcsolók (switching hub, router) sem növelik jelentősen a teljes hardver árát. A fenti okok miatt a mai klaszterekben szinte kizárólag nagy sávszélességű, teljesen kapcsolt kommunikációs hálózatot használnak, hiszen így az ütközések elkerülésével tovább növelhető a kritikus kommunikációs teljesítmény. A hálózati kapcsolókhoz egyesével közvetlenül kapcsolódó csomópontok lényegében egy virtuális crossbar topológia felett működnek, ahol az egyes csomópontok elérésének sebességében nincs lényeges különbség egészen addig, míg az aktív hálózati eszközök az aktuális forgalmat különösebb késleltetés nélkül képesek továbbítani (a nagy forgalom esetén a megnövekedő késleltetés oka a pufferekben való sorban állás, és a teli pufferek miatt eldobott csomagok lehetnek). A továbbiakban vizsgálódásunkat –gyakorlati jelentősége miatt– teljes egészében az ilyen virtuális crossbar topológiára korlátozzuk. A virtuális crossbar hálózat felett létező különféle üzenetszórási algoritmusokat a 2. ábrán foglaltuk össze. Ezek közül legegyszerűbb az egy pontból kiinduló üzenetszórás, ahol a forrás csomópont az összes partnerének maga küldi el a szétosztásra szánt üzenetet. A módszer előnye, hogy pontosan követi az üzenetszórás elvi koncepcióját (egy csomópont adatát mindenkihez eljuttatja), ezért könnyen érthető, könnyen implementálható és a hibakeresést is jelentősen leegyszerűsíti. Az egyszerű pont-pont kapcsolatok feletti implementáció a hibatűrés és a hordozhatóság megvalósítását is megkönnyíti. Egyszerűsége és rugalmassága miatt sok korai (1990es évek közepe) üzenetkezelő könyvár megvalósítás (MPICH [17], LAM/MPI [18]) implementálta így az üzenetszórást klaszter rendszerekben. Mivel akkoriban –alacsony ára miatt– széles körben alkalmazták az osztottan használt (Ethernet) busz hálózati topológiát, ez az implementáció előnyös

volt a hálózati ütközések elkerülése szempontjából is, mivel csak egy adó csomópont volt a rendszerben (és még egy kis forgalmú, aki éppen a nyugtákat küldte). c)

a) egyetlen központból kiinduló üzenetszórás b) bináris fa topológiára épülő üzenetszórás c) hiperkocka topológiára épülő üzenetszórás

0 1 2

3

a)

b)

0

5

6

....

5

5 6

5 6

6

6

6

7

3

7

7 8

6 4

4

5

2

2 3

4

4

4

7

1

2

3

3

0 5

1

2

3

7

8

7 8

8

4 9

n 3

4

4

5

4

5

5

6

7

8

9

9

2. ábra. Különféle gyakori üzenetszórási topológiák áttekintése Az üzenetszórás primitív teljes lefutásának tc ideje p darab fogadó csomópont esetén, feltételezve, hogy az n méretű üzenet elküldési ideje n*td, és a üzenetküldés késletetése a küldő csomóponton t0: tc ( n, p) = p (t0 + ntd ) ⇒ O ( p )

(1)

Ennek alapján látható, hogy az üzenetszórás ideje a csomópontok számának növelésével lineárisan nő. Ez a megoldás viszonylag kis teljesítményt biztosít, különösen, ha azt is figyelembe vesszük, hogy végig a forrás csomópont üzenetszóró függvénye vezérli a műveletet, ezért annak teljes befejeződéséig nem is térhet vissza. A feladatok egyoldalú elosztása (a forrás végig dolgozik, míg a többiek alig) és a fogadó csomópontok számával lineárisan növekvő futási idő a skálázhatóságot is jelentősen korlátozza. A futási idő lineáris komplexitása lényegesen csökkenthető a 2.b ábrán látható fa struktúra alkalmazásával. Ekkor kihasználva, hogy aki már megkapta az üzenetet az újabb forrásként szolgálhat, az eredeti forrás és a többi közvetítő csomópont csupán két szomszédjának küldi el az üzenetet, és üzenet teljes szétosztása az ábrán látható lépések szerint alakul. Ha egyetlen üzenet küldése teljesen leköti a fizikai sávszélességet, akkor a második küldését csak az első befejezése után érdemes indítani annak érdekében, hogy a következő szint egyik csomópontja minél előbb tovább küldhesse az üzenetet. Ha a csomópontokhoz előre rögzített azonosítókat rendelünk, akkor a saját sorszáma alapján minden csomópont tudja, hogy merre kell továbbítania az üzenetet. A csomópontokat úgy célszerű megszámozni, hogy a helyeket az elérhetőség sorrendjében töltjük fel. Ha a csomópontok előre elrendezése túlságosan rugalmatlan, akkor a hasznos üzenettel együtt minden köztes csomópont megkapja a célcsomópontok listáját (a forrásnál az összes többi csomópont), és az üzenet továbbküldésénél listájának felét balra, másik felét jobbra küldi tovább. Ha nem osztható a célcsomópontok száma kettővel, akkor a gyorsabb (a 2.b ábrán a bal) ág felé eggyel több csomópontot küld. Ilyenkor az üzenetszórás ideje az (1) formulában használt jelölésekkel: tc ( n, p) = 2 * log 2 ( p + 2) − 2 * (t0 + ntd ) ⇒ O (log 2 p )

(2)

A formulában a log2(p+2) tag a lényeges, mely jelzi, hogy ilyen elrendezés esetén szintenként 2 egységgel nő a küldés ideje. A szekvenciális küldéssel szemben a módszer előnye a jóval kisebb komplexitásában rejlik, ugyanakkor az első csomópont már két üzenet elküldése után szabaddá válik, és megkezdheti más feladatok elvégzését. A broadcast primitív ilyen módon történő implementálását tartalmazzák a mostani MPI ajánlások [4], és több újabb üzenetkezelő könyvtár, mint pl. a MagPIe [19] is. A széleskörű elterjedtség mögött az áll, hogy a nagyobb kiterjedésű hálózatok szintén fa struktúrájúak, és a topológiák illeszkedése nagyobb teret biztosít az alsó szinteken egyre növekvő számú üzenet küldés párhuzamosítására.

A fizikailag is hiperkocka vagy hipertórusz összeköttetésben álló csomópontokra kidolgozott broadcast eljárások szintén alkalmazhatók virtuális crossbar összeköttetésű klaszter rendszerekben. Lényeges különbség azonban, hogy az üzenetek a különféle irányokba nem egyszerre, hanem csak egymás után indíthatók (2.c ábra). A módszer előnye, hogy a kezdő csomópont nem csupán 2, hanem a megvalósított hiperkocka dimenzió számával (d) megegyező párhuzamos ágat indít, így gyorsabb az algoritmus felfutása p függvényében. A klaszterekben előnyt jelenthet, hogy az algoritmus futása során a párhuzamosság mértékét korlátozza a hiperkocka keresztmetszete p(d-1)/d, amit helyesen megválasztva a hálózati kapcsoló pufferei nem telítődnek. Természetesen a párhuzamosság mértékének korlátozása az aszimptotikus komplexitás csökkenésével is jár a fa struktúrához képest. Az algoritmus futási ideje az (1) formulában használt jelölésekkel, ha az első d-1 darab dimenzió méretét a n1/d lefelé kerekítésével határozzuk meg:





tc ( n, p) = d d p + 1 − 2 * (t0 + ntd ) ⇒ O ( dp1 / d )

(3)

A 3. ábrán összehasonlítottuk a különféle üzenetszórási módszerek klaszteres implementációjának futási idejét. Bár a bináris fa aszimptotikusan (nagy p-kre) nyilvánvalóan gyorsabb, látható hogy az általánosan elterjedt, kisebb méretű klaszterekben akár a háromdimenziós kocka implementáció is gyorsabb lehet. Ennek ellenére ezt a topológiát klaszterekben egyáltalán nem használják, mert implementációja bonyolultabb, kevésbé skálázható, és a jelenleg használt hálózati kapcsolatok topológiája sem illeszkedik erre a sémára. Fontos megjegyezni, hogy a fa és a hiperkocka séma is rugalmatlanabb a központosított megoldásnál, mivel vagy előre ki kell jelölni a csomópontok helyét a topológiában, vagy az üzenettel együtt továbbítani kell, hogy merre kell tovább adni az üzenetet. Az első megoldás megnehezíti a dinamikusan változó, tetszőleges processz halmaznak történő üzenetszórást, míg a második többletadatok továbbításával jár, ami kis üzenetek esetén akár a hasznos üzenet méretét is meghaladhatja. lépésszám

Központból vezérelt

Bináris fa

3D kocka

25

20

15

10

5

0 1

6

11

16

21

26

31

36

41

46

51

56

61

66

fogadó csomópontok száma

3. ábra. Különféle üzenetszórási módszerek klaszteres implementációjának futási ideje

II.2

Üzenetszórás hardver támogatással

Az előző megoldások követték az MPI szabvány [4] azon ajánlását, hogy a csoport kommunikációs primitívek implementációi az üzenetkezelő könyvtár pont-pont üzenet átviteli függvényeire épüljenek. Bár ez nem feltétlenül a leghatékonyabb megoldás, azonban nagyban elősegíti az összetett csoport primitívek gyors és hordozható implementálást (más hardver platform esetén csak a pont-pont kommunikációt kell újra megírni). Természetesen a nagyobb implementációs ráfordítás és a hordozhatóság feladása árán a teljesítmény tovább növelhető. A hagyományos Ethernet szabvány különféle sebességű változatai mellett az újonnan fejlesztett, kis (<10μs) késleltetésű, nagy (több Gbps) sávszélességű, a klaszterekben is egyre elterjedtebben használt új hálózati szabványok (SCI [19], Quadrics [21], InfiniBand [22]) az üzenetszórás megvalósításához hardver támogatást is nyújtanak. Több új nagy teljesítményű MPI implementáció [23][24][25] is úgy ér el nagy skálázhatóságot és jelentős teljesítmény növekedést, hogy a hardver támogatást kihasználva a forrás csomópont egyetlen üzenetet küld, és annak szétosztásáról és célba juttatásáról már az aktív hálózati elemek gondoskodnak. Ezzel a módszerrel az üzenetszórás ideje a csomópontok számától elvileg függetlenné válik, így lényegesen jobb skálázhatóság és teljesítmény érhető el, mint az előzőleg bemutatott szoftveres, pont-pont kommunikációra épülő megoldások esetén. A hardver broadcast primitívre épülő megoldásnak a platform függőség és hordozhatóság megszűnése mellett egyéb hátrányai is vannak. A hardver broadcast használata esetén minden csomópont pontosan ugyanazt az üzenetet kapja, ezért a megbízhatóságot (hibatűrés, egyszeri és sorrendben történő továbbítás), a nagy üzenetek kezelését és a tetszőleges processzcsoport felé történő üzenetküldést a szoftver rétegekben kell megoldani [25]. A megbízhatóság kérdéskörével számos tanulmány foglalkozott [27][28][29][30]. A probléma lényege, hogy a megbízható, sorrendben történő üzenettovábbításhoz nem elegendő az üzenet elküldése, hanem elengedhetetlenül szükséges a fogadó csomópontok egyfajta visszajelzése (acknowledgement, nyugta) is. A visszajelzések eljuttatása a forrás csomópontba azonban hagyományos pont-pont kapcsolattal történik, vagyis a forrásnak fel kell készülnie az összes partnerétől érkező válaszok fogadására, melyek bár kis méretűek, de a csomópontok számával együtt lineáris növekvő mennyiségben érkeznek (ACK elárasztás problémája [30]). Szintén külön nehézséget jelent, hogy bármelyik csomópont visszajelzésének elmaradása vagy negatív visszajelzése esetén az összes többi csomópontot hátráltatva az adott csomagot újra kell küldeni. Emellett, mivel a hardver broadcast mindenkinek egyforma csomagot küld, így a kommunikációnak mindenhol egyszerre –a leglassabb fogadó tempójában– kell előrehaladnia. Egy ilyen protokoll implementálása olyan komoly nehézséget vagy teljesítmény csökkenést jelenthet, hogy bizonyos implementációk, mint pl. a QSW [24] saját MPICH [17] implementációja, a HP Alaska MPI implementációja, vagy Chen és társainak IP multicast-ra épülő [25] implementációja –bízva a hálózati átvitel hibamentességében– nem is támogatják a megbízható átvitelt. A probléma mértéke jelentősen csökkenthető, ha ritkább és időben később történő nyugtázás (lazy-acknowledgement) is megengedett, vagy ha a nyugta begyűjtést nem csak egyedül a forrás csomópont végzi, hanem a fogadók csoportokat alkotnak, és minden csoportban egy kitüntetett csomópont végzi a nyugták begyűjtést és továbbítást a forrás csomóponthoz (kétszintű fa) [29]. Ez a kitüntetetett csomópont a csoporton belül elvégezheti a hiányzó csomagok újraküldését is (természetesen, csak ha neki magának sikerült megkapnia azt), lényegesen skálázhatóbbá téve a megbízható kommunikációt is. A csoportok kialakítása természetesen többlet adminisztrációt igényel. Ezt a módszer például a [26] implementációban is használják. A hardver broadcast segítségével kiküldhető csomagok mérete korlátozott, ezért a nagy üzeneteket kisebb csomagok formájában kell továbbítani. Itt a gondot az okozza, hogy a nagy üzenetek fogadására nem feltétlenül elegendő mindenhol a közvetlenül rendelkezésre álló pufferek mérete, így valahogyan érzékelni kell a partnerek fogadóképességének mértékét pl. egy csúszó ablakos megoldással, és a teljes átvitel sebességét a leglassabb fogadó tempójához kell szinkronizálni. Ezek a módszerek is visszajelzést igényelnek a partnerektől, sőt minden egyes partner

folyamatos adminisztrálásának terhét is a forrásra rója, mely már szintén nem független a csomópontok számától. Az üzenetkezelő könyvtárakban a processzek tetszőleges kommunikációs csoportokat (MPI kommunikátorok) kialakíthatnak, azonban hardver broadcast megoldások a konkrét hálózati típustól függően különféle korlátozásokkal járnak (pl. Ethernet: csak egy teljes hálózati szegmens címezhető, vagy Quadrics: a gyors távoli DMA átvitel használatához a megcímzett processzeknek folyamatos virtuális címtartományba kell esniük). Ilyen esetekben néha különféle hardver és szoftver átkonfigurálásokkal és trükkökkel a probléma megoldható, de gyakran előfordul, hogy az összes broadcast üzeneteket minden csomópontnak le kell nyelnie, és saját hatáskörében (processzor idejében) kell eldöntenie, hogy az adott csomag tartalma őt is ténylegesen érinti-e. A hardver támogatást kihasználó megoldásokról általában elmondható, hogy a pont-pont kapcsolatra épülő változatoknál lényegesen jobb teljesítményt és skálázhatóságot képesek nyújtani, de a csomópontok számától független elvi komplexitás a gyakorlati megvalósításokban nem feltétlenül, illetve csak komoly kompromisszumok árán (korlátozott méretű üzenetek, nem megbízható implementáció) teljesíthető. A hardver támogatás használata jelentősen megnöveli az implementáció bonyolultságát, és kivétel nélkül a hordozhatóság teljes elveszítésével jár. II.3

A különféle módszerek összehasonlítása

Az 1. táblázatban összefoglaltuk a fent bemutatott szoftver és hardver megoldások különféle tulajdonságait. A táblázat utolsó sorában a következő pontban bemutatásra kerülő szimmetrikus üzenetszóró algoritmusunk tulajdonságait is feltüntettük. Látható, hogy nincs olyan módszer, mely minden szempontból felülmúlná a többit, így az adott követelményektől (csomópontok száma, üzenetméret, hordozhatóság) függően kell az optimálisat kiválasztani. A következő pontban bemutatásra kerülő szimmetrikus algoritmus célja, hogy kis (néhányszor tíz) csomópont esetén, a gyakorlatban leggyakrabban használt üzenetméretek esetén [31] egy gyors csomópontok számától független, hordozható megoldást biztosítson.

üzenetszórás típusa központi bináris fa hiperkocka hardver alapú szimmetrikus

rugalmasság klaszteres implementálás bonyolultsága

egyszerű közepes összetettebb bonyolult közepes

teljesítmény

hordozhatóság (op. rendszer, hálózat típusok)

megbízhatóság megvalósítása

egyszerű közepes közepes nincs közepes

egyszerű egyszerű egyszerű bonyolult egyszerű

késleltetés a forrásnál

n üzenet 2 üzenet d üzenet 1 üzenet 1 üzenet

skálázhatóság

teljes futási idő

(futási idő változás további hozzáadott csomópontokkal)

O(n) O(log2n) O(dn1/d) O(1) O(1)

rossz jó jó kitűnő korlátozott

1. táblázat. Különféle üzenetszórási módszerek összehasonlítása

III.

Résztvevők számától független üzenetszórás

A ma használatos üzenetkezelő könyvtárak, bár lehetőséget adnak az üzenet aszinkron módon történő kezelésre is, alapjaiban szinkron kommunikációs mintát követnek. A II.1 pontban bemutatott algoritmusok feltételezik, hogy a különféle üzenetek kommunikációs lépései kizárólag egymás után következhetnek, és nagy hangsúly helyeznek az alacsony kezdeti késleltetések biztosítására (az előző formulákban t0-lal jelölve). A kezdeti késleltetés és különféle szoftverből származó veszteségek [6][7] kiválóan eltakarhatók a több párhuzamos üzenet egyidejű továbbításával [8]. A párhuzamos üzenetek küldésének alapvető feltétele az üzenetkezelés aszinkron módon történő megvalósítása. A fizikai sávszélesség túllépése azonban aszinkron üzenetkezeléssel sem lehetséges, és ráadásul önmagában az (1),(2),(3) formulákból származtatott aszimptotikus komplexitást sem befolyásolja, legfeljebb a t0 késleltetés hatásának csökkentésében segíthet. Az általunk kidolgozott új algoritmus az aszinkron adatátvitel és az üzenet darabolás módszerének kombinációjával egy olyan szimmetrikus kommunikációs mintát alakít ki a csomópontok között, mely szoftveres módon teszi elvileg lehetővé a résztvevő csomópontok számától független komplexitású üzenetszórás megteremtését. Az algoritmus működése a következő: a forrás csomóponton adott a szétküldése szánt n byte hosszúságú üzenet, és a fogadó csomópontok címeinek p hosszúságú listája. A forrás csomópont az üzenetek p egyenlő részre osztja, a kerekítési hibák elkerülésére a következő képlet szerint:  (i − 1) * n  i. darab címe :   p  

 i * n   (i − 1) * n  i. darab hossza :  −  p  p   

(4)

ahol i egy futóindex [1,p] értelmezési tartománnyal. A forrás csomópont az i. üzenetdarabot az i. célcsomópontnak továbbítja, kiegészítve azt egy üzenetszórás típusjelzéssel, egy egyedi id azonosítóval, az eredeti üzenet n hosszával és a forráson kívüli összes célcsomópont címének listájával. Mind az i darab üzenettöredék elküldésével a forrás csomópont a ráeső feladatot elvégezte. A fogadó csomópontok feladata a rájuk eső üzenetrész fogadása a forrás csomóponttól, majd annak szétküldése az összes többi csomópontnak. Ennek érdekében a fogadó csomópontok az üzenetszórás típusú üzeneteket a következőképpen dolgozzák fel: 1. Ha egy új id azonosítóval rendelkező üzenet érkezik, akkor létrehoznak egy puffert az id azonosítóhoz tartozó üzenet darabok összeállítására, és a megérkezett darabot a helyére másolják. Az üzenetdarab helye a (4) formula alapján határozható meg, i, p és n ismeretében. A beérkező üzenet közvetlenül tartalmazza az n-et, és a p megegyezik a csomópont lista hosszával. Mivel minden üzenet küldője a kommunikációs alrendszerből lekérdezhető, ezt a címet a listában megkeresve az i érték is megkapható. 2. Ha a fogadó csomópont olyan id azonosítóval rendelkező üzenetszórás típusú üzeneteket kap, mellyel már előzőleg találkozott, akkor az id-hez tartozó pufferbe bemásolja az új darabot az előző pontban leírtak szerint. 3. Speciális eset, amikor az i. csomópont az i. üzenetet fogadja, mivel ez közvetlenül a forrás csomóponttól származik. Mivel a küldő csomópont nem szerepel a szétküldött csomópontlistában, ebből a fogadó csomópont tudni fogja, hogy ez az üzenet az ő darabja. Ezt a darabot úgy másolja be a helyére, hogy a csomópont listában a saját címét keresi meg, és ennek a helye alapján határozza meg a puffer címzéséhez szükséges i értéket. A másolás mellett a megkapott csomópontlistán is végighalad, és az összes többi csomópontnak változtatás nélkül szétküldve a kapott üzenetet. Mivel a többi csomópont számára a küldő már ez a csomópont lesz, a listabeli helye alapján azok is a helyére tudják illeszteni a kapott darabot. Az algoritmus leírása jól mutatja, hogy a darabok megkapásának sorrendje tetszőleges, arra semmiféle megkötést nem kell tenni. A célcsomópontokon az utolsó üzenetdarab fogadásával és helyére illesztésével helyre áll az eredeti üzenet, és így itt is befejeződik az üzenetszórási algoritmus.

a)

b)

4. ábra. A szimmetrikus üzenetszórás algoritmus kommunikációs mintája a) a forrás csomópontban, b) egy célcsomópontban A leírásból és a 4. ábra rajza jól mutatja, hogy az üzenetszórás algoritmus végrehajtásában minden célcsomópont egyformán, teljesen szimmetrikus módon vesz részt. Az algoritmus futási ideje, aktív kapcsoló elemmel (switching hub) összekapcsolt csomópontok között ideális esetben a következőképpen alakul: ha a darabolásból és az extra információk továbbításából származó overhead-től eltekintünk, akkor a forrás csomópontnak lényegében minden esetben egy n hosszúságú üzenetet kell, a célcsomópontok számától függően darabolva továbbítania. Ha a párhuzamos üzenetküldés a kezdeti t0 késleltetés elteltével a kimeneti kapcsolat teljes fizika sávszélességét képes kihasználni, akkor az utolsó darab küldése a csomópontok számától függetlenül t0+ntd idő alatt megtörténik. Mind a p célcsomópont az üzenetnek egy n/p méretű darabját kapja meg, melyet p-1 további csomópontnak kell tovább küldenie. Ez ideális sávszélesség kihasználás mellett t0+ (p-1)ntd /p késleltetéssel jár. Az i. csomópont utoljára, ntd idő után kapja meg a saját szétküldendő üzenetét, így kommunikációjának befejezése: tc ( n, p) = t0 + ntd + t0 +

 ( p − 1)ntd 1 = 2t0 + ntd  2 −  ⇒ O (1) p p 

(5)

vagyis az algoritmus futási ideje a csomópontok számától aszimptotikusan független, bár a gyakorlatban használt kis értékeknél számíthatunk némi növekedésre, hiszen a végrehajtási idő hiperbolikusan közelíti a végső értéket. A kezdeti növekedést azonban ellensúlyozza, hogy az aszinkron üzenetküldés hatékonysága a párhuzamos üzenetek számával nő, ezért az elvileg gyorsabb kis célcsomópont számnál kevésbé számíthatunk a sávszélesség teljes kihasználására és t0 idők teljes átfedésére. Bár a p növelésével egyre több adminisztrációt (másolás, csomagképzés, protokollok csomagokhoz kapcsolódó overhead-je), elegendően nagy n (p*csomagméret) esetén ezek a hatások nem olyan jelentősek, hiszen a nagy üzeneteket amúgy is sok csomagra kell szétbontani, legfeljebb a darabolás határai néhány (p) helyen módosulnak. Ha a protokollt nem rögzített szerepű csomópontokkal, hanem üzenetszórásonként dinamikusan változó taszk halmazra implementáljuk, akkor kisebb n és nagyobb p értékek használata mellett figyelembe kell venni az adminisztrációs többletköltségeket is (a szimmetrikus protokoll üzenet darabonkénti overhead-je). Ha egy tipikus implementációban üzenet valós hossza (n) és az azonosító (id) 4 byte-on, egy csomópont címe pedig 8 byte-on továbbítható, és minden elküldött üzenetre alacsonyabb protokoll szinteken 16 byte extra adminisztráció esik, akkor p csomópont esetén a küldendő hossz növekedése: ∆n = p ( 4 + 4 + p * 8 + 16) = 32 p + 8 p 2

(6)

ez p=5 esetén 520, p=10 esetén 1120, p=20 esetén 3840, p=100 esetén 83200 extra byte átvitelét jelenti az eredeti n-hez képest. Ez nyilván korlátozza a skálázhatóságot és a hatékonyan használható üzenet méreteket, azonban vegyük észre, hogy ha még 50%-os overhead esetén is az (5) formula alapján számított időt csak másfélszeresére növeli, vagyis 3ntd lesz, ami egy 3 mélységű fa t0=0 melletti késleltetésének felel meg. Egy ilyen fa 14 cél csomópontot tartalmaz, míg a p=14 esetén Δn=2464, vagyis 5kB fölötti üzenetméret esetén a szimmetrikus algoritmus lesz előnyben. Ha t0 >0, akkor a szimmetrikus algoritmus előnye tovább nő (hiszen ebben csak két egymásra épülő szint van), és szintén előnyt jelent, hogy a csoportok dinamikus kialakításhoz más algoritmusoknál is szükséges lehet a csomópont lista továbbítására, illetve ha a szerepek előre hozzárendelhetők a csomópontokhoz (pl. egyszer az inicializálás során), akkor a szimmetrikus algoritmus is mentesül a (6) képletben leírt adminisztrációs tehertől. A módszer használatának további korlátjai vannak. Semmilyen csomópontszám esetén nem érdemes túl kicsi üzenet méretek mellett alkalmazni, mivel a hálózati protokoll hatékonysága a keretméret (pl. Ethernet ~1,5kB) alatti csomagméret esetén jelentősen csökken. Az ilyen esetekben a szimmetrikus módszer első fázisa –a központi üzenetszórásban leírtak szerint– akár a teljes üzenetet is kioszthatja ugyanannyi idő alatt, a második fázis használata csak az erőforrásokat pazarolná. A túl nagy csomópontszám és üzenetméret próbára teheti a hálózati kapcsoló kapacitását is, mely nem föltétlenül képes az összes portján föllépő maximális be- és kimenő terheléssel egyszerre megbirkózni. Mivel az algoritmus futása során mindenki mindenkinek folyamatosan adatokat továbbít, az esetleges ütközések elkerülésére a switchnek pufferelni kell, azonban memória erőforrásai nyilván végesek. A fenti korlátozások miatt, az algoritmustól gyakorlatban egyéb implementációkat felülmúló teljesítményt csak kis (néhányszor tíz csomópont) méretű klaszterekben, a néhány kB méret fölötti üzenettartományban várhatunk. A hatékonyan használható maximális üzenetméretet és csomópontszámot kapcsolóelem(ek) portszáma és minősége határozza meg. Mivel az algoritmus futása során minden csomópont egyenletesen termeli és nyeli az üzeneteket, ha a hálózati kapcsoló elbírja egyszerre minden portján a maximális forgalmat, akkor a hatékonyan küldhető üzenetek méretnek elvi korlátja nincs. Több hálózati kapcsoló együttes használata esetén közöttük a csomóponthoz kapcsolódó portoknál lényegesen nagyobb forgalom generálódik. Az algoritmus implementációjánál a fa és a hiperkocka típusú implementációhoz hasonlóan külön mechanizmussal (pl. szinkronizálás a következő üzenet előtt) gondoskodni kell csomópontok közötti üzenetsorrend betartásáról. Ha ugyanis az első csomópont végzett a feladatával, az nem jelenti, hogy mindenki megkapta az üzenetet, így elvileg egy újabb üzenet megelőzhetné a régebben feladottat. Az algoritmus, többi szoftveres implementációhoz hasonlóan, megbízható pont-pont alapú kommunikációkra épül, így az ideiglenes kommunikációs zavarokra nem érzékeny. A fa és hiperkocka topológiához hasonlóan, ha valamelyik csomópont meghibásodik, akkor elképzelhető, más csomópontok sem kapják meg az üzenetet. Az ilyen esetek kezeléséről külön mechanizmusokkal kell gondoskodni. Összefoglalva tehát, ebben a fejezetben bemutatásra került az üzenetszórásnak egy új szoftveres megvalósítási módszere, mely a többi szoftveres módszerekhez hasonlóan egyszerűen megvalósítható, hibatűrő, hordozható és rugalmasan konfigurálható, ugyanakkor futási ideje a hardverből támogatott módszerek O(1) komplexitásával vetekszik. További előny a kommunikáció szimmetriából fakadó automatikus terhelés elosztás. Az algoritmus fontos korlátja, hogy csak crossbar vagy virtuális crossbar összekapcsoló hálózat felett működik hatékonyan, és a hálózati kapcsoló elemek fizikai paraméterei jelentősen korlátozhatják skálázhatóságát és a hatékonyan alkalmazható üzenetméreteket is.

IV.

Teljesítmény mérések

IV.1 Alapelvek Az előző pontban bemutatott algoritmus megvalósíthatóságát és gyakorlati használhatóságát egy teszt implementáció elkészítésével demonstráltuk. Viszonyítási alapul a széles körben használt fa topológiájú üzenetszórást választottuk. Annak érdekében, hogy a mérések minél pontosabban tükrözzék algoritmus teljesítményét, az összehasonlító mérések során mind a hardver, mind a szoftver hardver környezetet változatlanul hagytuk. A mérésnek fontos részét képezi a mérési tartomány megválasztása. Vetter és Mueller az valós MPI alkalmazások kommunikációs mintájának tanulmányozásakor [31] során arra az eredményre jutottak, hogy az MPI kollektív kommunikációs műveletei tipikusan kis méretű üzenetekkel dolgoznak. Ennek fő magyarázata, hogy a klaszterekben olyan algoritmusokat célszerű alkalmazni, melyek minél inkább a minimálisra korlátozzák a számítási teljesítményhez képes viszonylag drága kommunikáció mennyiségét. Természetesen a kommunikációs minta, és az átviendő minimális adatmennyiség nem csupán a szándéknak, hanem az elvégzendő feladatnak is függvénye. A klaszterek teljesítmény tesztelésére széles körben használt NAS párhuzamos tesztkészlet (NPB) [32] úgy oldja meg a fenti problémát, hogy több különféle, kommunikációs mintájában lényegesen különböző számítási magot (kernel) használ a tesztek során, melyek öt különféle probléma méretre futtathatók. A klaszteres implementációban a különféle magok futása során használt üzenetméretek előfordulását a 2. táblázatban gyűjtöttük össze [10]. Látható, hogy egészen kicsi üzenetek is nagyszámban fordulnak elő, valamint az is, hogy az SP tesztkészlet kivételével minden esetben az üzenetek nagy része a 10 kB alatti mérettartományba esik. mérettartomány (byte)

IS (Integer Sorting)

MG (Multi Grid)

CG (Conjugate Gradient)

SP (Scalar Pentadiagonal)

EP (Embassingly Parallel)

LU (Lower Upper)

egész rendezés

3D skalár Poisson egyen-let megoldása

mátrix sajátérték becslés konjugált gradiens módszerrel

egyenlet megoldás multiparticionálás módszerrel

véletlenszámokra épülő normál eloszlású számpárok

egyenlet megoldás szukcesszív túlrelaxálás módszerével

x<101 101 ≤ x < 102 102 ≤ x < 103 103 ≤ x < 104 104 ≤ x < 105 x ≥ 105

2 560 0 0 300 0 2 560

760 8 960 9 920 11 520 9 664 1 952

124 800 2 400 0 0 0 93 600

0 0 0 0 57 600 96 000

60 30 0 0 0 0

0 60 300 000 900 000 0 12 000

2. táblázat. Az NPB tesztkészleteinek üzenetszáma különféle mérettartományokban A különféle okokból fellépő futási idő ingadozások kiegyenlítésére a későbbiekben bemutatandó mérési eredményének kialakításához a minden mérési pontban 10 mérést végeztünk, és ezek számtani közepét vettük az adott pontban érvényes mérési eredménynek. A méréseknél az Intel Pentium processzorok RDTSC utasításán alapuló időmeghatározást [33] használtunk, melynek alapja a processzor egyik belső regiszterének kiolvasása, melynek minden órajel ciklusban eggyel növekszik az értéke. A processzor órajel frekvenciájának ismeretében kis költséggel és nagy pontossággal meghatározható a regiszter két lekérdezése között eltelt idő. Ezen a módszeren alapul a több programozási könyvtár időlekérdező függvénye, és egyes szerzők [23] méréseikben közvetlenül magát a gépi utasítást is használják. Méréseink során 15 darab egyforma, 2.26 GHz-es Pentium IV processzorral és 256 MB memóriával ellátott PC használtunk, melyekben 100 Mbit-es, Ethernet hálózati protokoll szerint működő Intel 82801DB PRO/100 VE hálózati kártyák voltak. A csomópontok egy 3Com SuperStack 4226T típusú hálózatai kapcsolón (switching hub) keresztül voltak összekapcsolva. A mérések során a számítógépeken Windows XP operációs rendszer futott, és az MPICH Windows NT operációs rendszerre készült implementációját használtuk (NT-MPICH v1.3.0 [11]).

IV.2 A fa topológiájú és a szimmetrikus üzenetszórás összehasonlítása A bemutatott szimmetrikus üzenetszórási módszerrel elérhető teljesítményt egy összehasonlító méréssorozattal demonstráltuk. Kétféle mérést végeztünk, egyikben az NT-MPICH könyvtár saját broadcast hívásának idejét mértük, mely fa topológián alapul, és a hívás a csomópontokon csak a teljes üzenetszórás befejeződése után tér vissza. A második méréssorozatban ugyanennek a könyvtárnak az aszinkron hívásait alkalmazva (MPI_Irecv, MPI_Isend) implementáltuk az említett szimmetrikus üzenetszórás algoritmust. Annak érdekében, hogy a teljes eltelt időt itt is a forrás csomóponton mérhessük, az összes fogadó csomópont egy rövid nyugtaüzenet küld a forrásnak akkor, amikor a darabokból összeállította a teljes üzenetet. Az időt a forrás csomóponton az algoritmus elindításától az utolsó nyugta megérkezéséig mérjük. Annak érdekében, hogy a gyakorlatban használt gyakori üzenetméreteket a teszt során minél inkább lefedjük, a tesztek során az üzenetméretet 2 byte-tól 512 kB-ig logaritmikus skálán változtattuk. Előzetes méréseink során kiderült, hogy mindkét esetben azonos csomópontszám esetén az üzenetküldési idő az üzenetmérettel együtt lineárisan változik a méréspontok között. Mivel a mérés több nagyságrendet felölel, a mérési eredmények ábrázolásához logaritmikus skála használata a célszerű, de a komplexitás könnyebb áttekintése érdekében 5. ábrán ugyanazokat az eredményeket lineáris skálázással is feltüntettük (a lineáris skálán a legnagyobb ábrázolt üzenet mérete mindkét módszer esetében 128 kB). Minden méréssorozatban a célcsomópontok száma 2 és 14 között változott. a) futási idő

b) futási idő 2-3 1-2 0-1 -1-0 -2--1

[ms] 1000

100

10

sorozat neve

[ms] 1000

[byte]

100

10

1

1

S19 S16 S13 S10 S7 sorozat S4 neve S1

0.1

0.01 13

11

9 7 célcsomópontok száma

5

3

S19 S16 S13 S10 S7 sorozat S4

0.1

0.01 13

1

11

9

7

célcsomópontok száma

c) futási idő

5

3

neve

S1 1

d) futási idő

[ms] 48

36-48 24-36 12-24 0-12

36

24

üzenet méret

[ms] 48

S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 S11 S12 S13 S14 S15 S16 S17 S18 S19

2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131074 262146 524290

36

24

12

S16 S13 S10 S7 S4 sorozat neve S1

0 13

11

9 7 célcsomópontok száma

5

3

1

12

S16 S13 S10 S7 sorozat S4

0 13

11

9

7

célcsomópontok száma

5

3

S1

neve

1

5. ábra. A fa (a,c) és szimmetrikus (b,d) üzenetszórás algoritmus teljesítményének összehasonlítása különböző üzenetméretek és csomópontszámok esetén logaritmikus (a,b) és lineáris (c,d) skálán

Bár a kétféle algoritmus két csomópont esetén egyenértékű, hiszen ilyenkor egyetlen pontpont kommunikációt kell mindkét esetben végrehajtani, ennek ellenére a 16 kB alatti üzenetméreteknél a fa topológiának 2 csomópont esetén jelentős az előnye, ami az aszinkron üzenetküldés megvalósításának relatív lassúságára utal. Az 5. ábra diagramjai szerint a szimmetrikus algoritmus viselkedése hűen követi az elvi várakozásokat. A 4kB (S12) és a 256kB sorozat üzenet 0-50 50-100 100-150 150-200 200-250 neve méret (S18) közötti tartományban láthatóan a futási idő [byte] [ms] csomópontok számától függetlenül közel S1 2 S2 32768 azonos futási időt produkál, azonban kis 250 S3 65536 üzenetekre, ahol a jóval a maximális S4 98306 200 Ethernet csomagméret alatti üzenet S5 131074 S6 163842 darabok és a segédinformációk miatt nagy S7 196610 150 az algoritmus overhead-je, ott S8 229378 S9 262146 csomópontok számát növelve a futási S10 294914 100 időben is jelentős növekedés figyelhető S11 327682 S12 360450 meg. Nagyobb üzenetméreteknél S16 S13 393218 (példánkban 512kB, S19) a switch 50 S13 S14 425986 S10 telítődik, így az algoritmus elveszti a S15 458754 S7 S16 491522 csomópontszámtól való függetlenségét, és 0 S17 524290 S4 sorozat 14 13 12 neve 11 10 9 a fa algoritmusnál lényegesen rosszabb 8 7 6 S1 5 4 3 célcsomópontok száma 2 1 eredményeket ad. Ezt a telítődést 6. ábra. Hálózati telítődés nagy üzenetek esetén demonstrálják a 6. ábrán bemutatott futási idők. Mivel az 5. ábra alapján a kétféle topológia futási idejének összehasonlítása meglehetősen nehéz, ezért az algoritmus ajánlott működési tartományában (4 kB és 256 kB között) kiválasztottunk néhány üzenetméretet, és a 7. ábra grafikonján együtt is ábrázoltuk a két különféle módszerrel mért időeredményeket. A 7. ábrán látható, hogy a csomópontok számának növelésével az egyre mélyebb fa kialakításának költsége fokozatosan nő, és 15 csomópont esetén a szimmetrikus megoldással akár a felére is csökkenthető a futási idő. a) futási idő [ms]

b)

100

16384 fa 90

futási idő [ms] 100

65536 fa 131074 fa

80

262146 fa 16384 szimmetrikus

70

65536 szimmetrikus 60

131074 szimmetrikus 262146 szimmetrikus

50

10

40 30 20 10

1

0 1

2

3

4

5

6

7

8

9

10

11

12

13

14

célcsomópontok száma

1

2

3

4

5

6

7

8

9 10 11 12 13 14 célcsomópontok száma

7. ábra. A fa és szimmetrikus üzenetszórás teljesítményének összehasonlítása a szimmetrikus algoritmus ideális működési tartományában lineáris (a) és logaritmikus (b) skálán

IV.3 Az elvi futási idő becslés és a mérések összehasonlítása Látható, hogy szimmetrikus módszerrel megfelelő körülmények között akár 100%-os teljesítménynövekedés is elérhető a hagyományos fa struktúrához képest. A mérési eredmények azonban önmagukban az implementáció jóságáról kevés információt adnak, így érdemes azokat összevetni a módszerrel elvileg elérhető maximális teljesítménnyel. Az (5) és (6) formulák alapján az elvileg elérhető késleltetés, t0 értékét is figyelembe véve:  2p −1 tc (n, p ) = 2t0 + (n + 32 p + 8 p 2 ) td    p 

(7)

A t0 és td érték legegyszerűbben a különféle méretű üzenetek oda-vissza idejének méréséből (ún. ping-pong benchmark) határozhatók meg [14][15][34] lineáris regresszió segítségével. Az általunk használt MPI implementáció esetében ezek a konstansoknak az értéke: t0 =263 μs illetve td =0,087 μs. Az előzőekben bemutatott mérési eredmények és az elvileg elérhető teljesítmény összehasonlítása a 8. ábrán látható. Az eredmények meglehetősen jól közelítik az elvi görbéket, jelentős eltérés csak a 256 kB-os görbén látszik, ahol a telítődés nem csupán a nagy adatmennyiségnek, hanem a szerencsétlen időzítési hatásoknak is betudható, hiszen nagyobb csomópontszámnál ismét a várt eredményeket kapjuk. a) futási idő [ms] b) futási idő [ms] 60

4096 elvi 16384 elvi 65536 elvi 131074 elvi 262146 elvi 4096 mért 16384 mért 65536 mért 131074 mért 262146 mért

50 40

30 20

100

10

10 0

1 1

2

3

4

5

6

7

8

9

10 11 12 13 14 célcsomópontok száma

1

2

3

4

5

6

7

8

9

10 11 12 13 14 célcsomópontok száma

8. ábra. A szimmetrikus üzenetszórás elvi és mért teljesítményének összehasonlítása lineáris (a) és logaritmikus (b) skálán

V.

Összefoglalás

A klaszter rendszereken hatékonyan futtatható alkalmazások körének legfőbb korlátját a kommunikációs alrendszer szűk keresztmetszete jelenti, ezért számos tudományos és mérnöki erőfeszítés történik a csomópontok közötti kommunikáció felgyorsítására. Cikkünk ennek a kérdéskörnek egy részterületével foglalkozott, az önmagában és más csoport kommunikációs primitívek építőelemeként is gyakran használt, egy-mindeninek típusú üzenetszórás gyorsításának módszereit és problémáit ismertette. Mivel a mai klaszterekben a csomópontok aktív hálózati eszközökön (switching hub) keresztül kapcsolódnak össze, ezek a kommunikáció szempontjából egy virtuális crossbar rendszert alkotnak. Ezt kihasználva lehetőség nyílik a kommunikációs primitívek párhuzamosítást tartalmazó implementációira is. Az üzenetszórás primitív legelterjedtebb megvalósítása a bináris fa topológia, mely pont-pont kapcsolatokra építve lépésenként egyre több párhuzamos ágon adja tovább az információt, a célcsomópontok p számának függvényében O(log2p) komplexitású megoldást nyújtva az üzenetszórás megvalósítására. Ennél jobb, a résztvevő csomópontok számától elvileg független, O(1) komplexitást céloznak meg a hardver támogatást kihasználó megoldások, azonban ezekben

teljesítmény növekedéséért nagyobb implementációs ráfordítással és a hordozhatóság feladásával kell fizetni. Az implementációt bonyolítja, hogy a megbízhatóságot, a nagy üzenetek kezelését és a tetszőleges processz csoport felé történő üzenetküldést a szoftver rétegekben kell megoldani [25]. Cikkünkben ismertettünk egy új algoritmust, mely bizonyos korlátok között szoftverből biztosítja a csomópontok számától független üzenetszórási időt. A módszer rendelkezik a szoftver megoldások szokásos előnyeivel, azaz rugalmas, hordozható, egyszerűen implementálható, és a megbízhatóságot is automatikusan biztosítja azzal, hogy a pont-pont kommunikációs alapokra épül. Az üzenetek darabolása és a szimmetrikus aszinkron kommunikáció teljes terhelésmegosztást biztosít, és segítve a nagy teljesítmény és a skálázhatóság elérését, mely fontos előfeltétele a gyakorlati alkalmazhatóságnak. Az új szimmetrikus algoritmus alkalmazhatóságát egy konkrét tesztrendszerben elvégzett méréssorozat segítségével illusztráltuk. A mérések során megmutattuk, hogy az algoritmus teljesítménye jól közelíti az elvi várakozásokat, és az általunk ismert leggyorsabb referencia implementációhoz (NT-MPICH v1.3.0) képest a gyakorlatilag fontos üzenet és klaszter méretek egyes tartományaiban akár 100%-os teljesítmény növekedést is biztosíthat. Az algoritmus csak tejesen kapcsolt hálózatokban nyújt optimális teljesítményt, és hátránya hogy skálázhatóságát korlátozza a szűk keresztmetszetet jelentő hálózati kapcsoló teljesítménye, mely bizonyos forgalom fölött telítődik, ugrásszerűen rontva az algoritmus teljesítményét. Az algoritmust működési elvéből fakadóan nem érdemes túlságosan kis méretű (<4 kB) üzenetekre alkalmazni, mivel a hálózati protokoll hatékonysága a keretméretnél jóval kisebb üzenetekre lecsökken, és p2 nagyságrendbe eső üzenetszám adminisztrációs terhe is összemérhetővé válhat a küldés fizikai idejével. A szimmetrikus algoritmus célja, hogy kis (néhányszor tíz) csomópont esetén, a gyakorlatban gyakran használt üzenetméretek mellett gyors, hordozható és a csomópontok számától független megoldást biztosítson. A megoldás közvetlenül vagy üzenetkezelő könyvtárak implementációiban használható fel a párhuzamos algoritmusok működésének gyorsítására. Kis és nagyon nagy üzenetek gyakori használata esetén a módszert egyéb megoldásokkal (központosított vagy fa topológiájú üzenetszórás) kombinálva érdemes használni. Az üzenetszórás csoportkommunikációs primitívet cikkünkben több szempontból is tüzetesen megvizsgáltuk, azonban az elvi eredmények alátámasztására csak egyetlen konkrét implementációt mutattunk be. Folyamatban van, és a jövőre vonatkozó terveink között is szerepel a szimmetrikus üzenetszórás más protokollon (UDP), más üzenetkezelő könyvtárakkal (PVM, egyéb MPI implementáció) és más operációs rendszerre (Linux) alapuló implementációjának elkészítése, valamint az elkészítettt különféle változatok teljesítményének elemzése és összehasonlítása is.

Irodalomjegyzék [1] [2]

G. F. Pfister: In Search of Clusters, Second Edition, Prentice Hall, Upper Saddle River, New Jersey, USA, 1998. I. T. Foster: Designing and Building Parallel Programs, Addison-Wesley Inc., USA, 1995. http://www.mcs.anl.gov/dbpp/ [3] A. Geist, A. Beguelin, J. Dongarra,W. Jiang, R. Manchek, V.S. Sunderam: Parallel Virtual Machine – A User’s Guide and Tutorial for Networked Parallel Computing, MTI Press, London, UK, 1994 [4] M. Snir, S. Otto, S. Huss-Lederman, D. Walker, and J. Dongarra: MPI–The Complete Reference, Volume 1 - The MPI-1 Core, 2nd edition. The MIT Press, 1998. [5] Message Passing Interface Forum (http://www.mpi-forum.org/docs/mpi20.ps), MPI-2: Extensions to the messagepassing interface, July 1997. [6] Martin et al.: Effects of Communication Latency. Overhead and Bandwidth in a Cluster Architecture, Proc. 24th Annual International Symposium on Computer Architecture, pp. 85-97, Denver, 1997. [7] G. Chiola, G. Ciaccio: Efficient Parallel Processing on Low-Cost Clusters with GAMMA Active Ports, Parallel Computing 26, Elsevier Science, 2000, 333-354. [8] S. Juhász, H. Charaf: Exploiting Fast Ethernet Performance in Multiplatform Cluster Environment, Proc. 19th Annual ACM Symposium on Applied Computing, Nicosia, Cyprus, 2004. [9] N.J. Boden, D. Cohen, R.E. Felderman, A.E. Kulawik, C.L. Seitz, J.N. Seizovic, and W. Su. Myrinet: A Gigabitper-second Local Area Network. IEEE Micro, 15(1):29–36,February 1995. [10] M. Lobosco, V. S. Costa, C.L. de Amorim: Performance Evaluation of Fast Ethernet, Giganet and Myrinet on a Cluster, Proc. International Conference on Computational Science 2002, pp. 296-305, The Netherlands, 2002.

[11] RWTH Aachen, Lehrstuhl für Betriebssysteme: Multi-Platform MPICH. http://www.lfbs.rwth-aachen.de/mp-mpich/ [12] U. Meyer et al.: Algorithms for memory hierarchies (LNCS 2625, Springer-Verlag, Berlin, 2003), 320-354. [13] D. R. Helman, D. A. Bader, J. Jájá: Parallel algorithm for personalized communication and sorting with experimental study, Technical Report CS-TR-3549, Institute for Advanced Computer Studies, University of Maryland, 1995. [14] J.W. Baugh Jr., R.K.S. Konduri: Discrete element modeling on a cluster of workstations, Engineering with Computers 17, Springer-Verlag, London, 2001, pp. 1-15. [15] L. K. Ching, J.L. Gaudiot, L. M. Sato: Performance prediction methodology for parallel programs with MPI in NOW environments, Proc. 4th International Workshop on Distributed Computing, Calcutta, India, 2002, 268-279 [16] Barry Wilkinson, Michael Allen: Parallel programming, Prentice Hall, Upper Saddle River, New Jersey, USA, 1999. [17] W. Gropp, E. Lusk, N. Doss, and A. Skjellum: A High-Performance, Portable Implementation of the MPI Message Passing Interface Standard, Parallel Computing, 22(6), 1996. pp. 789–828 [18] Indiana University, Indiana University's Open Systems Lab: LAM/MPI, http://www.lam-mpi.org/ [19] T. Kielmann, Rutger F. H. Hofman, H. E. Bal, A. Plaat, and R. A. F. Bhoedjang: MagPIe: MPI's collective communication operations for clustered wide area systems. ACM SIGPLAN Notices, 34(8): pp. 131-140, 1999. [20] IEEE STD 1596-1992: IEEE standard for scalable coherent interface, 1993. [21] F. Petrini,W. Feng, A. Hoisie, S. Coll, and E. Frachtenberg: The Quadrics Network: High-Performance Clustering Technology, IEEE Micro, 22(1), 2002. pp. 46–57 [22] InfiniBand Trade Association. InfiniBand Architecture Specification, Release 1.0, October 24 2000. [23] J. Worringen and T. Bemmerl: MPICH for SCI-connected clusters, SCI Europe ’99, pp. 3–11, Bordeaux, France, September 1999. [24] Quadrics Supercomputers World, Ltd.: Quadrics Documentation Collection. http://www.quadrics.com/onlinedocs/Linux/html/index.html [25] H.A. Chen, Y.O. Carrasco, and A.W. Apon: MPI Collective Operations over IP Multicast. In Proceedings of the 3rd Workshop on Personal Computer-based Networks of Workstations (PC-NOW 2000), 2000. [26] W. Yu, S. Sur, D. K. Panda, R. T. Aulwes and R. L. Graham: High Performance Broadcast Support in LA-MPI over Quadrics, In Los Alamos Computer Science Institute Symposium, (LACSI'03), Santa Fe, New Mexico, Conference, PDF, BibTex, October 2003. [27] S. Floyd, V. Jacobson, C.-G. Liu, S. McCanne, and L. Zhang: A Reliable Multicast Framework for Light-Weight Sessions and Application Level Framing. IEEE/ACM Transactionson Networking, 5(6), 1997. pp. 784–803 [28] S. Coll, J. Duato, F. Petrini, and F. J. Mora: Scalable Hardware-Based Multicast Trees, Proceedings of Supercomputing ’03, November 2003. [29] S. Pingali, D. Towsley, and J. F. Kurose: A Comparison of Sender-Initiated and Receiver-Initiated Reliable Multicast Protocols, Proceedings of the Sigmetrics Conference on Measurement and Modeling of Computer Systems, ACM Press, New York, NY, USA, 1994. pp. 221–230 [30] D. Buntinas, D. K. Panda, and R. Brightwell: Application-Bypass Broadcast in MPICH over GM, International Symposium on Cluster Computing and the Grid (CCGRID ’03), May 2003. [31] J. S. Vetter and F. Mueller: Communication Characteristics of Large-Scale Scientific Applications for Contemporary Cluster Architectures, IPDPS, April 2002. [32] D.H. Bailey, J.T. Barton, T.A. Lasinski and H.D. Simon: The NAS Parallel Benchmarks, Tech. Report NASA memorandum 103863, NASA Ames Research Center, USA, July, 1993. [33] Intel Coporation: Using the RDTSC instruction for performance monitoring. 1997. http://developer.intel.com/drg/pentiumii/appnotes/rdtscpm1.htm, [34] Z. Juhász: An analytical method for predicting the performance of parallel image processing operation, Kluwer Academic Publishers, Boston, 1996. pp. 1-19