Csoportos üzenetszórás optimalizálása klaszter rendszerekben Készítette:
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
Tartalom n
Kommunikációs alrendszer klaszterekben n n
n
Broadcast hagyományos megvalósításai n
n n n
szűk keresztmetszet csoport kommunikációs primitívek központosított, fa, hiperkocka
Szimmetrikus, aszinkron algoritmus Teljesítmény vizsgálat Összefoglalás Networkshop 2004
2004.04.06.
Kommunikáció klaszterekben Jelentőség n
Klaszterek n n n
n
Nagyobb teljesítmény olcsóbban Kommunikáció lassúsága szűk keresztmetszet Csak nagy granularitású feladatokra alkalmazható
Kommunikáció korlátai n
A hardver n
n n
n
Késletetetések nagyobb része a szoftver rétegekben n
n
új technológiák (ATM, SCI, Fast Ethernet, Gigabit Ethernet, Myrinet, Quadrics, Infiniband) teljesen kapcsolt (fully-switched) topológia sávszélesség jelentősége kicsi operációs rendszer, üzenetkezelő alrendszer, protokoll stack
Cél: kommunikáció sebességének növelése az üzenet kezelő rendszer szintjén Networkshop 2004
2004.04.06.
Kommunikáció klaszterekben Üzenetkezelő rendszerek n
De facto szabványok: PVM, MPI n
n
n
Csoportkommunikáció gyorsítása n n
n
Cél: forráskód szinten hordozható párhuzamos programok Az üzenetkezelő rendszert minden architektúrára ki kell fejleszteni Pont-pont üzenetek gyorsítása Jobb algoritmusok
Broadcast jelentősége n n
Gyakran használt Más primitívek alkotó része (allgather, alltoall, barrier, allreduce)
taszkok
adatok A0 A1 A2 A3
broadcast
A 0 B0 C 0 D 0
B0 B1 B2 B3
A 0 B1 C 1 D 1
C0 C1 C2 C3
A 0 B2 C 2 D 2
D0 D1 D2 D3
A 0 B3 C 3 D 3
A0 A1 A2 A3
scatter
B0 B1 B2 B3 C0 C1 C2 C3
A 1 B1 C 1 D 1
gather
D0 D1 D2 D3 A0
A 0 B0 C 0 D 0
A 2 B2 C 2 D 2 A 3 B3 C 3 D 3
allgather
A 0 B0 C 0 D 0
B0
A 0 B0 C 0 D 0
C0
A 0 B0 C 0 D 0
D0 D1 D2 D3
A 0 B0 C 0 D 0
A0 A1 A2 A3
alltoall
A 0 B0 C 0 D 0
B0 B1 B2 B3
A 1 B1 C 1 D 1
C0 C1 C2 C3
A 2 B2 C 2 D 2
Networkshop 2004 D0 D1 D2 D3
A 3 B3 C 3 D 3 2004.04.06.
Broadcast megvalósításai Hagyományos módszerek
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
2 4
5
6
....
5
5 6
5 6
6
6
7
6
3
7
7 8
3
7
8
7 8
8
4 9
n 3
O(n)
4
5
2 6
3
4
4
4
7
1
2
3
3
0 5
1
2
4
4
5
4
5
5
O(log2n)
6
7
8
9
9
O(d d n )
kompexitás virtuális crossbar hálózati topológia esetén Networkshop 2004
2004.04.06.
Broadcast megvalósításai
Különféle módszerek összehasonlítása n
Hardver támogatás kihasználása elvileg O(1) koplexitás, a leggyorsabb megoldás, de SW-ből: n n n
megbízhatóság kezelése (acknowledgement protokollok, ACK flooding) hosszú üzenetek kezelése (darabolás, küldés a leglassabb cél tempójában) üzenetszórás tetszőleges csoportnak (trükkök, vagy mindenki válogat)
ü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ű Networkshop 2004
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 2004.04.06.
Szimmetrikus, aszinkron algoritmus Alapvető tulajdonságok n
SW implementáció előnyei n n n n
n
egyszerű megvalósítás tetszőleges üzenetméret és csomópontszám hordozható, plattform független alapvető küldés-fogadásra épül, megbízható átvitel nem igényel külön munkát
Emellett viszont n
O(1) komplexitás HW támogatás nélkül, a switching hub kihasználásával Networkshop 2004
2004.04.06.
Szimmetrikus, aszinkron algoritmus Algoritmus leírás n
2 átlapolódó fázis n
n a)
a forrás p részre bontja a szétküldendő üzenetet, és minden célnak elküldi egy darabját a cél csomópontok saját darabjaikat átküldik az összes többi célcsomópontnak
b)
Networkshop 2004
2004.04.06.
Szimmetrikus, aszinkron algoritmus n méretű szétküldésének analízise n n n
1. fázis utolsó csomagja: t0+ntd 2. fázis minden csomópontja: t0+ (p-1)ntd /p Teljes futási idő lényegében két üzenet ideje:
( p − 1)ntd 1 tc (n, p ) = t0 + ntd + t0 + = 2t0 + ntd 2 − ⇒ O (1) p p n
n
(~p2 db n/p méretű üzenet)
Lehetséges problémák n
n
túl kicsi üzenetek overheadje (n/p kisebb a keretméretnél) switch telítődése, vagy az aszinkron implementáció problémái Networkshop 2004
2004.04.06.
Teljesítmény vizsgálat Teszt környezet n
Plattform (15 egyforma csomópont) n n n n
n
IBM Pentium IV processzor (2.26 GHz) Intel 82801DB PRO/100 VE hálózati adapter 3Com SuperStack 4226T (100 Mbit Ethernet switch) Windows XP operációs rendszer
Szoftver környezet n
n
RWTH Aachen, Lehrstuhl für Betriebssysteme: Multi-Platform MPICH http://www.lfbs.rwth-aachen.de/mp-mpich/ A beépített bináris fa strutúrájú broadcast és a szimmetrikus aszinkron algoritmus összehasonlítása (MPI_Irecv, MPI_Isend) Networkshop 2004
2004.04.06.
A fa (a,c) és szimmetrikus (b,d) üzenetszórás algoritmus teljesítményének összehasonlítása logaritmikus (a,b) és lineáris (c,d) skálán a) futási idő
b) futási idő 2-3 1-2 0-1 -1-0 -2--1
[ms] 1000
100
1000
10
1
1
S19 S16 S13 S10 S7 sorozat S4 neve S1
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
S1 3
neve
1
d) futási idő
[ms] 48
36-48 24-36 12-24 0-12
36
24
üzenet méret [byte]
100
10
0.1
sorozat neve
[ms]
[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
7 Networkshop 2004 célcsomópontok száma 9
5
3
S1 1
neve
2004.04.06.
Teljesítmény vizsgálat
Összehasonlítás azonos ábrában a) futási idő [ms]
b)
100
futási idő [ms] 100
16384 fa 90
65536 fa 131074 fa
80
262146 fa 16384 szimmetrikus
70
65536 szimmetrikus 60
131074 szimmetrikus 262146 szimmetrikus 10
50 40 30 20 10
1
0 1
2
3
4
5
6
7
8
9
10
11
12 13
1
14
célcsomópontok száma
Networkshop 2004
2
3
4
5
6
7
8
9 10 11 12 13 14 célcsomópontok száma
2004.04.06.
Összefoglalás n n
n
Cél a klaszterek kommunikációjának javítása Cikk: csoportkommunikáció gyorsítása az új üzenetszórási módszerrel Aszinkron, szimmetrikus algoritmus n n n n
n
hordozható, skálázható egyszerűen implementálható akár 100% teljesítmény növekedés üzenetkezelő könyvtárba építve a régi kódok újraírás nélkül is gyorsulnak kis (<4k) üzenetekre nem érdemes alkalmazni Networkshop 2004
2004.04.06.
Kérdések
Networkshop 2004
2004.04.06.
