Készítette: Trosztel Mátyás Konzulens: Hajós Gergely
Monte Carlo Markov Chain MCMC során egy megfelelően konstruált Markov-lánc segítségével mintákat generálunk. Ezek eloszlása követi a céleloszlást. A mintavételezett értékekből becsüljük a keresett mennyiséget.
A sorrendezések tere felett lépked. Ez a tér sokkal kisebb és kevésbé „tüskés”, így gyorsabb konvergenciát biztosít a stacionárius eloszláshoz. X2
X4
X2
X3
X2
X4
X4
X3
X1
≺
X3 X1
G1,≺
X1
G2,≺
Mennyire jó a sorrendezésünk?
Ahol a score() azt a valószínűséget adja meg hogy D adat mellett Xi változónak PaG(Xi) a szülői halmaza. A szülői halmazok megválasztása független egymástól, ezért:
Ahol U≺ a sorrendezéssel kompatibilis szülői halmazok halmaza
A sorrendezések tere n! méretű, ezért zárt formában csak kevés változóra tudnánk kiszámolni. Itt jön segítségünkre az MCMC algoritmus. A Markov-láncot úgy hozzuk létre, hogy a stacionárius eloszlása P(D|≺) legyen. Ezek után bármilyen f(≺) függvény várható értékét meg tudjuk határozni:
Ahol T az iterációk száma
Globális cache építés MPI segítségével -> ~ score számítás párhuzamosítása 139 változó, futási idő
10000 lépés
találat valószínűség
lokális
13 568s
99,01%
eloszott (6 klienssel)
5 938s
99,61%
elosztott (12 klienssel)
5 349s
99,80%
Adat- és feladat párhuzamos modell Az ISO C99 szabvány részhalmaza
Heterogén platform támogatás
Az OpenCL elemei
◦ párhuzamos kiegészítésekkel ◦ ◦ ◦ ◦
Többmagos CPU-k Grafikus hardver (GPU) Jelfeldolgozó processzorok (DSP) Cell/B.E. processzor
◦ ◦ ◦ ◦
Platform modell Végrehajtási séma Memória modell Program modell
Cache miss minimalizálása ◦ Folytonos adatszerkezetek (felejtsük el az OOP-t) ◦ Az adat tömb belefér az L3 cache-be -> egyszerre több score-t számoljunk, ne csak szükség esetén.
Vektoros (SIMD) utasításkészlet kihasználása (SSE) ◦ Gyors load/store biztosítása.
Egy feladatra több speciális kernel. Futásidejű fordítás. Jobb optimalizáció. ◦ ◦ ◦ ◦
Ciklus kifejtés (unroll) Elágazás megszüntetése (GPU-n különösen drága) Szükséges regiszterek csökkentése -> Külön kernel 1,2,…,k szülő számú score kiszámításához.
Optimális globális memória elérés biztosítása ◦ 64B-os igazítás, folytonos olvasás. ◦ (random memória elérés ~16x lassabb mint az ideális)
CPU: 1load MMX regiszterbe (SSE) GPU: 1 32B tranzakció ushort16-ba
Adat tömb: d1,1
d1,2
d1,3
d1,4
d1,L
Padding 64B
X1
d2,1
d2,2
d2,3
d2,4
d1,L
Padding 64B
X2
d3,1
d3,2
d3,3
d3,4
d1,L
Padding 64B
X3
dn,1
dn,2
dn,3
dn,4
dn,L
Padding 64B
Xn
D1
D2
D3
D4
DL
Eredeti c++: 3ms/score OpenCL CPU: 0.025ms/score (AMD Phenom II X4 @4.0Ghz) 1 magra vetítve: 0.1ms -> 30x gyorsulás OpenCL GPU: 0.11ms/score (AMD Radeon 4850) 27x gyorsulás
◦ Nagy feltételes eloszlás táblák -> register spilling ◦ Kevés és egyszerű műveletek -> memória késleltetés nem fedhető el hatékonyan
Párhuzamosítás: Markov-láncok ◦ CPU: Ha több mag van mint lánc akkor kihasználatlan. ◦ GPU: nagyon kevés szál, optimálisan >1000 szál kell
Párhuzamosítás: Ordering változó score ◦ Függetlenül számolható ◦ CPU: ok ◦ GPU: random memória olvasás kevés szál -> a szülői halmazok mentén is tudunk párhuzamosítani.
X2
X2
Cache-elt értékek X4
X4
Cache-elt értékek
X3
Szál 1
X3
X1
Szál 2
X1
Szál 5
X6
Szál 3
X6
Szál 6
X5
Szál 4
X5
Szál 7
X7
Szál 8
X8
Szál 9
X7
Cache-elt értékek X8
1. Lánc
2. Lánc
Az MPI verzió futási idejének fele score számítással telt. Ezt jelentősen sikerült gyorsítani -> 2x gyorsulás. Ordering párhuzamos számítása -> ?x gyorsulás. (~CPU mag/Markov-lánc)
Szülő halmaz -> (0,C(N,k)+C(N,k-1)+…C(N,0)) l-binomiális ábrázolás pl. (l=k=4) m = 26 = C(6,4) + C(5,3) + C(2,2) Ez a {6,5,1,0} m = 126 = C(9,4) -> {8,7,6,5} Visszafelé: pl. {1,7,6,2} = {7,6,2,1} -> C(7,4) + C(6,3) + C(3,2)
X2
X2
X4
X4
X3
X5
X1
X1
X6
X6
X5
X3
X7
X7
X8
X8
Két tetszőleges változót felcserél a sorrendezésben.
X2
X4
Nem változnak a szülői halmazok. Nem változik a score.
X3
X1
X6
Csak itt változnak a szülői halmazok.
Ezekre kell újraszámolni a score-t!
X5
X7
Nem változnak a szülői halmazok.
X8
Nem változik a score.
X2
X4
Két részre vágja a sorrendezést és a két halmaz sorrendjét felcseréli.
X5
X7
X3
X8
X1
X2
X6
X4
X5
X3
X7
X1
X8
X6
Mindenhol változás történt a szülői halmazokban
Mindenhol újra kell számolni a score-t!
Csak 32B, 64B, 128B, (256B) tranzakciók.
64B igazított 128B igazított
szálak
Optimális elérés: maximális sávszélesség
64B igazított 128B igazított
szálak
1db 64B tranzakció
Nem igazított elérés
64B igazított 128B igazított
szálak
1db 128B tranzakció 1db 64B + 1db 32B ha átlóg a 128B határon Nagy sávszél pazarlás!
Stride x=3.
64B igazított 128B igazított
szálak
1db 128B + 1db 64B tranzakció Nagyon rossz kihasználtság nagy x esetén!
NDRange Gy
Feladat egység
Feladat egység
Feladat egység
Munkacsoport méret Sx
Munkacsoport méret Sy
NDRange Gx
Feladat egység
OpenCL eszköz Számító egység
Számító egység
Privát mem
Privát mem
Privát mem
Privát mem
PE 1
PE M
PE 1
PE M
Lokális mem
Lokális mem Globális/Konstans memória cache
Globális memória Konstans memória
Hoszt <-> VRAM adatmozgatás
Kevés privát memória
Divergens szálakat kerülni kell
◦ Amit lehet tároljuk a GPU-n és dolgozzuk is fel ott. ◦ Async elérés. ◦ Rövid, egyszerű kernelek
◦ Probléma felbontása. De megéri?
Indítási overhead Lassú double számítás
Optimális memória elérés
Sok szál
◦ „Cél GPU”, de még ez sem az igazi. ◦ Ahol csak lehet használjunk float típust. Mixed precision ◦ Sokszor nehéz.
◦ A globális ram elérése lassú, hogy ezt elfedjük sok szál szükséges (több ezer).
