Adatfolyam alapú RACER tömbprocesszor és algoritmus implementációs módszerek valamint azok alkalmazásai parallel, heterogén számítási architektúrákra
Rák Ádám Témavezet®: Dr. Cserey György
2014 szeptember 22.
Rák Ádám
Kit¶zött feladatok - motiváció
Moore törvény: a magok száma is exponenciálisan n® Sokmagos SIMD rendszereket nehéz programozni GPU, FPGA, Cell BE, Intel MIC Az OpenCL nem oldja meg a párhuzamosítási problémát Matematikailag megalapozott módszerre van szükség Megfelel® reprezentáció esetén automatikus párhuzamosítás is lehetséges
Rák Ádám
Kit¶zött feladatok
Módszer keresése az algoritmus párhuzamosításra Párhuzamosítható algoritmus osztályok Hatékony tömbprocesszor architektúrák keresése konkrét problémák vizsgálata
Rák Ádám
Kit¶zött feladatok
Módszer keresése az algoritmus párhuzamosításra Párhuzamosítható algoritmus osztályok Hatékony tömbprocesszor architektúrák keresése konkrét problémák vizsgálata
Rák Ádám
Használt vizsgálati módszerek
Statikus ciklus szerkezetek analízise Polihedrális megközelítés Ciklusok mint sokdimenziós konvex testek Adat és vezérlési folyam analízise
for ( int i = 0; i < n ; i ++) for ( int j = 0; j < m ; j ++) { int sum = array [ i ][ j ]; if ( i > 0) sum += array [i -1][ j ]; if ( j > 0) sum += array [ i ][ j -1] ; if ( i > 0 and j > 0) sum -= array [i -1][ j -1] ; array [ i ][ j ] = sum ; }
Rák Ádám
Megismert és használt GPU rendszerek
Gépi kódú programozás Részletes hardver ismeretek NVIDIA GeForce8 NVIDIA Fermi NVIDIA Kepler AMD(ATI) R800(Evergreen) AMD(ATI) R900(NI Cayman) AMD(ATI) R1000(Southern Islands GCN)
Rák Ádám
Integrál levezetésben alapul vett algoritmusok
Két-elektron integrál Folytonos hullámfüggvények és diszkrét mátrixok közötti kapcsolat Leginkább számításigényes számolni Kvantumkémiában alapvet®
Boys Pople-Hehre Obara-Saika-Schlegel Head-Gordon-Pople McMurchie-Davidson Az ezekre épül® MD-PRISM, HGP-PRISM Gauss-Rys kvadratúra
Rák Ádám
Megismert kvantumkémiai algoritmusok
Önkonzisztens Mez® (Self Consistent Field : SCF) Hartree-Fock S¶r¶ség Funkcionál Elmélet (Density Functional Theory : DFT) Møller-Plesset Perturbációs Elmélet (Møller-Plesset Perturbation Theory : MPPT) Kon guráció interakció (Con guration Interaction : CI) Csatolt Csoport számítás (Coupled Cluster computation : CC)
Rák Ádám
I. Téziscsoport
Tézis Megmutattam, hogy sokmagos rendszerek programozása során a klasszikus statikus polihedrális reprezentáción felül, megvalósítható a dinamikus ciklusok és dinamikus vezérl® szerkezetek polihedrális reprezentációja is. Dinamikus polihedronok esetén formalizmust adtam arra, hogy hogyan érdemes kezelni a memória hozzáférési mintázatot. De niáltam azokat az algoritmus osztályokat, melyeket hatékonyan lehet kezelni módszereimmel.
A cél, lehet®vé tenni az automatikus párhuzamosítást Manuálisan is hatékonyak lehetnek a módszerek Automatikusan párhuzamosítható algoritmus osztály b®vítése Memória hozzáférés sebességének javítása
Rák Ádám
I. Téziscsoport
Rák Ádám
I. Téziscsoport
Ciklusszerkezeteket geometriailag tudunk átalakítani Kib®vítettem a reprezentációt, hogy bizonyos dinamikus vezérl® szerkezetek is reprezentálhatóak legyenek
Rák Ádám
I. Téziscsoport
Az általam adott formalizmus támpontot nyújt a GPU local memory hatékony kezelésére A módszer jelent®sen lecsökkenti a keresési teret, így akár automatikusan bejárható Rák Ádám
II. Téziscsoport
Tézis Egy új adatfolyam elv¶ párhuzamos számítógépes architektúrát (RACER) terveztem, melyben a funkciók az eddigi megoldásoknál hatékonyabban vannak szétosztva a memória és a feldolgozó egységek között és ennek a megvalósításához a párhuzamosítás kiterjed a memóriára is.
A memória aktív számítási egység, de azt csinálja amire a leghatékonyabb A számítási egységek így sokkal egyszer¶bbek, és jóval kevesebb helyi memóriát tartalmaznak Magas számítási er® és magas memóriamozgatási sebesség egyszerre elérhet®
Rák Ádám
II. Téziscsoport
Adatfolyam alapú adatfeldolgozó tömbprocesszor A program helyben marad, az adatfolyam mozog A program el®ször az adatfolyammal jön, amit követ az adat Vezérl® szerkezeteket adatfolyam vezérelt multiplexerekkel lehet megvalósítani Rák Ádám
II. Téziscsoport
1. Altézis Megmutattam, hogy vezérl®elektronika és huzalozás egyszer¶sége és lokalitása miatt, integrált áramköri megvalósítás esetén a felület 57-72%-át a feldolgozó aritmetikai egységek foglalják el, ezzel adott felületen az egyik legmagasabb aritmetikai s¶r¶ség érhet® el a GPU architektúrákhoz viszonyítva.
Egyszer¶bb, aszinkron órajel Lokális huzalozás, mivel az architektúra lokális Kevés lokális memória a feldolgozó elemekben Nagy számítási kapacitás kis felületen
Rák Ádám
II. Téziscsoport
2. Altézis Megmutattam hogy a RACER képes hatékonyan megoldani a Mandelbrot és Conway's életjáték algoritmusok végrehajtását is, miközben általános architektúra marad. Az implementált algoritmusokkal demonstráltam az architektúra m¶köd®képességét, valamint bizonyítottam, hogy az architektúra Turing-teljes.
Egy algoritmus lehet memória és/vagy számítás intenzív A RACER memóriája kizárólag a memória intenzív feladatokat tudja hatékonyan végrehajtani A RACER tömbprocesszorra kizárólag a számítás intenzív részeket tudja hatékonyan végrehajtani Így ideálisan lehet szétosztani az algoritmust részeire
Rák Ádám
II. Téziscsoport: Szimuláció
Mandelbrot példaprogram, iteratív megoldás NVIDIA Tesla GPU C2050: 1.5ns / pixel Teljes RACER tömbprocesszor: 0.2ns / pixel Feladat jól illeszkedik mindkét architektúrához Közel 100% kihasználtság mindkét esetben lehetséges
Rák Ádám
ábra: Bemeneti memória kiürülése, és kimeneti memória betölt®dése az órajelciklusok függvényében
Rák Ádám
III. Téziscsoport
Tézis Az általam kidolgozott módszereket felhasználtam kvantumkémiai integrál számítási algoritmusok gyorsítására és párhuzamosítására, különös tekintettel a Single Instruction Multiply Data (SIMD) architektúra kompatibilitásra. GPU architektúrára meta algoritmust (BRUSH) terveztem, ami kiválasztja az integrálokhoz tartozó optimális számítási útvonalat. Megmutattam, hogy speciális kontrakciók esetén konstans behelyettesítés és terjesztés hatékony az ilyen architektúrákon.
A két-elektron integrálok számolása alapvet® és gyakran sebesség meghatározó lépés a kvantum kémiában Els®sorban SIMD vektorgépekre koncentráltam elterjedtségük miatt GPU, Intel MIC Rák Ádám
III. Téziscsoport
Két-elektron integrál 2
ϕak (r) = (rx − Ax )ax (ry − Ay )ay (rz − Az )az e −αk |r−A| Z Z 1 ϕcm (r2 )ϕdn (r2 )d r1 d r2 [ak bi |cm dn ] = ϕak (r1 )ϕbl (r1 ) |r1 − r2 | r1
r2
Improprius integrál: végtelen téren értelmezve, altéren felveszi a végtelen értéket
1 0
Két térkoordináta szerinti integrál, azaz 6 tengely mentén A Gauss függvény integrálja sorfejtéssel könny¶, de az anguláris polinom ezt jelent®sen megnehezíti
Rák Ádám
III. Téziscsoport
PRISM Gauss integrál számító algoritmust vettem alapul Magas szinten az algoritmus lényege, hogy egy körmentes gráfon megoldási utakat keres. Egy út ebben a gráfban felel meg egy rekurzív levezetésnek Kib®vítettem ezt a gráfot a GPU-nak megfelel®en GPU esetén a rekurzió fordítási idej¶ levezetése az el®nyös a SIMD rendszer miatt
Rák Ádám
Eredmények alkalmazási területei - I. Téziscsoport
Program párhuzamosítás GPU és FPGA rendszerekre Automatikusan párhuzamosító fordítóprogramok Program algoritmus osztályának automatikus detektálása A II. téziscsoportban de niált architektúra programozásának segítése A III. téziscsoport témájában
Rák Ádám
Eredmények alkalmazási területei - II. Téziscsoport
Gra kus 3D megjelenítés Sugárkövetés (raytracing) Strukturálatlan griden tudományos számítások Kvantumkémia Adatbázisok feldolgozása
Rák Ádám
Eredmények alkalmazási területei - III. Téziscsoport Két-elektron integrál számításának gyorsítása GPU-kon A numerikus kvantumkémia számos algoritmusának gyorsítása
Rák Ádám
Folyóirat publikációk
A. Rák and G. Cserey, The BRUSH algorithm for two-electron integrals on
GPU, MATCH Communications in Mathematical and in Computer Chemistry, 2014. submitted. A. Rák and G. Cserey, Macromodeling of the memristor in SPICE, IEEE
Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 29, no. 4, pp. 632636, 2010. A. Rák, G. Gandhi, and G. Cserey, Chua's circuit topology evolution using
genetic algorithm, International Journal of Bifurcation and Chaos, vol. 20, no. 3, pp. 687696, 2010. A. Rák, G. B. Soós, and G. Cserey, Stochastic bitstream based CNN and its
implementation on FPGA, International Journal of Circuit Theory and Applications, vol. 37, no. 4, pp. 587612, 2009. G. B. Soós, A. Rák, J. Veres, and G. Cserey, GPU boosted CNN simulator library for graphical ow based programmability, EURASIP Journal on Advances in Signal Processing, 2009. Article ID 930619, 11 pages doi:10.1155/2009/930619.
Rák Ádám
Konferencia publikációk
A. Rák, G. Feldhoer, G. B. Soós, and G. Cserey, Standard C++
Compiling to GPU with Lambda Functions, in Proceedings of 2010
International Symposium on Nonlinear Theory and its Applications (NOLTA 2010), (Krakow, Poland), 2010. A. Rák, G. Feldhoer, G. B. Soós, and G. Cserey, Standard c++
compiling to GPU, in 3rd HUNGARIAN-SINGAPOREAN WORKSHOP
on SYSTEMS BIOLOGY and COMMUNICATION SYSTEMS, (Budapest, Hungary), 2010. A. Rák, G. Feldhoer, G. B. Soós, and G. Cserey, CPU-GPU hybrid
compiling for general purpose: Case studies, in Proceedings of 12th
International Workshop on Cellular Neural Networks and their Applications, CNNA 2010, (Berkeley, USA), Feb. 2010. G. Cserey, A. Rák, B. Jákli, and T. Prodromakis, Cellular neural networks with memristive cell devices, in Proceedings of 17th IEEE International
Conference on Electronics, Circuits, and Systems, ICECS 2010, (Athens, Greece), pp. 938941, Dec. 2010.
Rák Ádám
Konferencia publikációk
G. B. Soós, A. Rák, J. Veres, and G. Cserey, GPU powered CNN simulator (SIMCNN) with graphical ow based programmability, in
Proceedings of 11th International Workshop on Cellular Neural Networks and their Applications, CNNA 2008, (Santiago de Compostela, Spain), pp. 163168, 2008. G. J. Tornai, G. Cserey, and A. Rák, Spatial-temporal level set algorithms on CNN-UM, in Proceedings of 2008 International Symposium on
Nonlinear Theory and its Applications, NOLTA 2008, (Budapest, Hungary), pp. 696699, 2008.
Rák Ádám
Szabadalmak
A. Rák and G. Cserey, Számítógépes architektra és feldolgozási eljárás.
Hungarian patent (beadott PCT), 2012. A. Rák, and Feldhoer, G., and Soós, G.B. and Höltzl, T., and Oroszi, B.
and Cserey, György, Eljárás és rendszer integrál kiszámításának párhuzamos architektúra szálára való leképezésére. Hungarian and PCT patent, 2012. 2013. G. Cserey and A. Rák, High accuracy time-to-digital converter on FPGA. Hungarian patent, 2009. A. Rák, G. Cserey, and B. Jákli, Eszköz és eljárás mért jel id®beliségének
meghatározására. PCT patent, 2013.
Rák Ádám
GPU H.264 teszteredmények
Egyszerre valós id®ben transzkódolható képfolyamok száma:
25fps
X264, Intel i7 960
Saját implementáció GTX 580-on
Bejöv® képfolyamok
12
22
48
88
800x600 Kimen® képfolyamok 640x480(QP=26) 640x480(QP=28) 320x240(QP=26) 160x120(QP=26)
Egy bemeneti képfolyamból több kódolódik Különböz® felbontásúak és min®ség¶ek a kimen® képfolyamok Valós idej¶, 25 kép/másodperces feldolgozás
Rák Ádám
GPU H.264 teszteredmények
25fps
X264, Intel i7 960
Saját implementáció GTX 580-on
Bejöv® képfolyamok
10
18
40
72
960x720 Kimen® képfolyamok 640x480(QP=26) 640x480(QP=28) 320x240(QP=26) 160x120(QP=26)
Rák Ádám
RACER VLSI implementációs becslések
Technológiai
Órajel
méret
frekvencia
Felület
Összes
Órajel elosztó
fogyasztás
fogyasztása
90nm
400MHz
561mm
90nm
600MHz
564mm
2
224W
42W
2
454W
81W
65nm
500MHz
355mm
2
226W
34W
65nm
600MHz
369mm
2
280W
65nm
700MHz
436mm
2
330W
Dupla pontosságú
Feldolgozó
Összeköt®
felület aránya
felület aránya
819GFLOPS
72%
21%
1229GFLOPS
72%
21%
1024GFLOPS
70%
21%
46W
1229GFLOPS
67%
20%
60W
1434GFLOPS
57%
17%
sebesség
InCyte programmal készült becslések Az órajelek a fogyasztás alapján lettek megválasztva Az órajel elosztó hálózat valószín¶leg kivonható a teljes fogyasztásból Magas a felületaránya a feldolgozó egységeknek
Rák Ádám
RACER becslések összehasonlítása GPU-kkal
GPU
Technológiai
Legközelebbi
Egyszeres pontosságú
Dupla pontosságú
Fogyasztás
név
méret
becslésre használt méret
gyorsulás
gyorsulás
aránya
Radeon HD 2900XT
80nm
90nm
1.7×
6.9×
1.05
Radeon HD 4870
55nm
65nm
1.2×
1.5×
2.1
GeForce 8800 GTS
65nm
65nm
2.3×
4.6×
2.5
A nagyobb felületaránynak köszönhet®en nagyobb csúcsteljesítmény Nagyobb a fogyasztás is mert több mag dolgozik egyszerre
Rák Ádám
