Závěrečná zpráva projektu „Experimentální výpočetní grid pro numerickou lineární algebru“ Ing. Ivan Šimeček Ph.D., Zdeněk Buk
[email protected], bukz1fel.cvut.cz
Červen, 2012
1
Zadání
Paralelní zpracování dat je často jedinou možnou metodou zvyšování výpočetního výkonu algoritmů. Programy jsou často upravovány tak, aby jistou míru paralelizace podporovaly. Programy pro vědeckotechnické výpočty často používají numerické knihovny pro lineární algebru se standardním rozhraním (BLAS, LAPACK) pro většinu svých výpočtů a prováděním těchto rutin stráví většinu doby běhu. Pro urychlení celého programu je tedy důležité maximálně urychlit hlavně tyto rutiny. Řešením je poslání dat na specializovaný výpočetní grid, zde se provede potřebný výpočet (tzn. rutiny z knihovny), poté je výsledek zaslán zpátky uživateli. Dalším novým trendem v urychlení zpracování je možnost provádět negrafické (rozuměj matematické) výpočty na grafických kartách. Grafické karty mají dechberoucí poměr výkonu a ceny a umožňují tak postavit levný klastr se slušným výpočetním výkonem.
2
Cíle
Celý projekt je řešen v rámci dvou podprojektů: „CUDA Networks“ a „EGNLA“(Experimental grid for numerical linear algebra). Ač mají oba podprojekty některé věci společné (distribuované počítání, využití GPU), vývoj probíhal odděleně. Důvodem bylo, že první jmenovaný se musel přizpůsobit vnitřní struktuře systému Mathematica na rozdíl od druhého, jehož návrh byl plně v naší režii.
2.1
CUDA Networks
Cílem podprojektu „CUDA Networks“ je vytvoření platformy pro simulaci populací rekurentních neuronových sítí, přístupných uživatelům systému Wolfram Mathematica v režimu klient-server. Serverová část realizuje vlastní
1
simulaci neuronových sítí na GPU. Klientská část zprostředkovává rozhraní mezi serverovou částí a prostředím Wolfram Mathematica. Takže cíle tohoto podprojektu jsou: • Simulace množiny (populace) sítí, umožňující využití simulátoru v evolučních algoritmech • Využití architektura client-server tak, aby pracovní stanice, kde budou výsledky simulace použity, nemusela být vybavena výkonnou grafickou kartou a veškeré výpočty probíhaly na výpočetním serveru. • Volba vhodné platformy (AMD vs. NVidia, CUDA vs. OpenCL).
2.2
EGNLA
Cíle podprojektu „EGNLA“ jsou: 1. Implementace paralelní verze rutin pro výpočty na grafických kartách. 2. Úprava rozhraní některých rutin z matematických knihoven. Pokud uživatel potřebuje provést nějaký výpočet, klientská část (přesněji heuristika uvnitř) vyhodnotí, zda se vyplatí poslat výpočet na grid (či to spočítat lokálně), pokud ano, zašle vstupní data na grid a počká na zaslané výsledky. 3. Vytvořit experimentální výpočetní grid, který bude podporovat výše uvedenou službu. Grid bude tvořen malým dedikovaným klastrem a dále nededikovanými částmi tvořenými nevyužitými výpočetními prostředky (např. počítače ve školních učebnách mimo výuku).Výpočet je možno provádět na CPU nebo na GPU (procesoru grafické karty)
3 3.1
Postup a způsob řešení CUDA Networks
Pro volby vhodné implementační platformy byly realizované výkonové testy. Výsledkem byla volba platformy CUDA, která vykazovala podstatně menší režii výpočtů. Implementace serverové i klientské části je realizována v jazyce C/C++. Pro komunikaci mezi výpočetním prostředím Wolfram Mathematica a naší klientskou aplikací je využita technologie MathLink. Simulátor implementuje plně rekurentní heterogenní neuronovou síť. Jedná se univerzální topologii, schopnou simulovat jakékoliv propojení neuronů (každá taková síť je podgrafem plně propojeného symetrického orientovaného grafu), kdy každý neuron může mít unikátní aktivační funkci. Pro učení neuronových sítí byl implementován gradientní algoritmus Realtime Recurrent Learning. Tento algoritmus může být využit jako lokální 2
učení v hybridním evolučním algoritmu. Pro podporu evolučního učení nabízí simulátor možnost akcelerace celé skupiny nezávislých sítí (populace jedinců). Pro práci z prostředí Wolfram Mathematica jsou k dispozici funkce, které transformují datové typy systému Wolfram Mathematica do C/C++ a zabezpečují komunikaci se serverovou částí simulátoru. Client Machine
Server Machine
CPU
CPU
GPU
Mathematica
Server program MathLink
Client Program
TCP/IP
Memory
Service procedures Memory
Neural Networks Memory
Obrázek 1: Struktura aplikace.
3.2 3.2.1
EGNLA První etapa
Na začátku byl zprovozněn pouze server služby. Byly na něm nainstalovány volně stažitelné implementace knihoven pro numerickou lineární algebru (GOTO a ATLAS), dále implementace knihovny pro výpočty na grafických kartách (CUBLAS). Byla vytvořena základní verze klientské i serverové části rozhraní k těmto knihovnám, byly na ní provedeny zátěžové testy sloužící k stanovení parametrů heuristiky v klientské části, která vyhodnocuje, zda se vyplatí použít nelokální výpočet. 3.2.2
Druhá etapa
Následně byly zprovozněny počítače tvořící malý výpočetní klastr. Na tomto klastru byly vyvíjeny vlastní paralelní implementace některých rutin pro výpočty na grafických kartách. Dále byl implementován plugin do algebraického SW Mathematica. 3.2.3
Konfigurace testovacího clusteru
Cluster se skládá z hlavního uzlu (alpha) za kterým jsou přes gigabytový switch připojeny ve vnitřní síti další čtyři uzly (beta, gamma, delta, epsilon). Dostali jsme přiděleny pouze dvě internetové adresy a podle toho jsme museli zasíťovat cluster: První adresu jsme použili pro uzel alpha (gpgpu-fit.cvut.cz) přes který se následně přistupuje na další uzly. Druhou adresu jsme použili 3
pro elektrickou zásuvku (sprinx.fit.cvut.cz), která napájí uzel alpha. Tím ho můžeme restartovat v případě potřeby. Ve vnitřní síti je pak připojena další internetová zásuvka pro případný restart vnitřního uzlu. Pro potřeby testování se uzly clusteru liší svou hardwarovou konfigurací. Některé mají horší CPU, další více paměti. Uzly napájí zásuvky ovladatelné přes internet. Současná konfigurace clusteru: • alpha: Intel Core
[email protected], 4GB RAM, NVIDIA GeForce GTX 480 • beta: Intel Core
[email protected], 4GB RAM, NVIDIA GeForce GTX 480 • gamma: Intel Core
[email protected], 4GB RAM, NVIDIA GeForce GTX 470 • delta: Intel Core2
[email protected], 4 GB RAM, NVIDIA GeForce GTX 470 • epsilon: Intel Core
[email protected], NVIDIA GeForce GTX 590, 24GB RAM • Ostatní zařízení: – gigabytový switch zajišťující komunikaci ve vnitřní síti clusteru – 2 elektrické zásuvky ovládané pře internet (webové rozhraní), které umožňují kdykoli restartovat libovolný uzel clusteru. Uzel alpha poskytuje uzlům clusteru následující služby: • authorizace (uživatelské účty jsou sdílené) • NFS server (home adresáře jsou sdílené) • DHCP server pro přidelování IP adres ve vniřní síti (podle MAC adresy) • Routování a NAT (umožňuje přístup uzlům na Internet) • cache pro Ubuntu balíky (rychlejší instalace software) • CUDA SDK (všechny uzly používají stejnou verzi) 3.2.4
Třetí etapa
Proběhly výkonnostní testy a odlazování celého systému. Byla analyzována podpora dalších knihoven např. GMP, FFTW, PETSc apod. Byly navrženy způsoby jak vhodným způsobem komprimovat komunikaci server-klient a obráceně zejména pro zasílání velkých řídkých matic.
4
3.3
Poznatky z provozu
V současné době dochází k přetížení uzlů. Zejména front-end uzlu alpha. Zátěž dosahuje vysokých hodnot a paměti na grafické kartě není dost pro běžící úlohy. Cluster je umístěn v neklimatizované místnosti, což bylo nejspíše příčinou poměrně častých výpadků uzlů.
4
Zdůvodnění změn v projektu
V průběhu řešení projektu se narazilo na několik problémů, které nebylo možno v průběhu projektu vyřešit:
4.1
Možnost zapojení počítačů v učebnách
Možnost zapojení počítačů v učebnách do výpočtu byla sice navržena, ale nebyla realizována z několika důvodů: • Přísná bezpečnostní politika FIT ČVUT, která omezuje možnosti komunikace výpočetních uzlů mimo doménu FIT a obecně běh neprověřených služeb na školních počítačích. • Tyto počítače jsou určeny primárně pro výuku. Bohužel při provádění kódu v CUDA API dochází k citelnému snížení rychlosti běhu OS pro ostatní uživatele. • Komunikační knihovna MPI nepodporuje tuto dynamickou rekonfiguraci, muselo by dojít k jejímu výraznému přepsání, což by vysoce překračovalo možnosti řešitelského týmu. • Tyto počítače jsou v nočních hodinách (ale i během dne) vypínány, což by způsobovalo problémy, protože aplikace neobsahuje podporu checkpointingu.
4.2
Měření parametrů propojovací sítě
Bylo plánováno periodické měření rychlosti a latence jednotlivých spojů. Toto ale zvyšuje zbytečně komunikační zatížení jednotlivých spojení proto je použita jiná metoda: při ustavení spojení je zjišťována pouze latence a rychlost je nastavena na danou defaultní hodnotu. Teprve při zaslání větších datových struktur je změřena skutečná rychlost spojení.
4.3
Vnitřní logika programu
Bylo nutné přeprogramování některých částí kódu, neboť došlo ke změně celkové koncepce výpočtu na gridu: v původní koncepci byly přenášeny sítí všechny vstupní operandy a výsledky pro každou operaci zvlášť. Provádění 5
veškerých operací bylo striktně odděleno a bylo blokující. Toto ale vedlo k velkému zatížení sítě a malé efektivitě nasazení gridu (byl využitelný jen pro malou množinu operací). Pro minimalizaci vlivu zpoždění a propustnosti sítě byl celý koncept gridu přepracován. Nyní si grid umožňuje ukládat i mezivýsledky a pořadí vyhodnocení není dáno programově, ale datovými závislostmi, což i zvýší míru paralelismu v provádění. Ale tento koncept selhává, pokud se v metodě vyskytují např. dvě stejné matice,ale každá z jiné iterace. Proto je nutno povolit řízení zamykání uživateli gridu.
5
Konkrétní výstupy
5.1
Deklarované
Hmatatelné výsledky projektu budou: • Pro projektu vzniknou stránky. • Pro programy vzniklé během řešení projektu vzniknou stránky na serveru SourceForge. • Pro členy sdružení bude k dispozici nová služba. Novinky a pokyny budou zveřejňovány na výše uvedené stránce. • Výsledky projektu (vytvoření gridu, paralelní GPU algoritmy) budou prezentovány na tuzemských (SNA, MEMICS) i zahraničních (SYNASC, PPAM) konferencích • Plugin do SW Mathematica bude zveřejněn na diskuzním fóru věnované tomuto programu.
5.2
Publikované
Výsledky dosažené v rámci řešení tohoto projektu byly publikovány na těchto konferencích: • O myšlence gridu byly publikovány 3 články: 1. na tuzemské konferenci "Seminář numerické analýzy"(SNA’11), 2. na tuzemské konferenci "MEZINÁRODNÍ KONFERENCE PREZENTACE MATEMATIKY ’11"(ICPM ’11), 3. na zahraniční konferenci "11th International Conference on Applied Mathematics"(APLIMAT’2012). Tento příspěvek byl vybrán i do časopisu (APLIMAT Journal). • O použití CUDA Networks proběhla přednáška [3] a dále vyzvaná přednáška [4].
6
• O řešení problémů souvisejících s gridem byly publikovány tyto příspěvky: 1. na tuzemské konferenci SNA12: "Modular Arithmetic for Solving Linear Equations on the GPU", 2. na tuzemské konferenci SNA12: "Space-efficient sparse matrix storage formats with 8-bit indices", 3. na tuzemské konferenci ICPM11: "Improvement of shortest path algorithms through graph partitioning", 4. na prestižní zahraniční konferenci HPCC2012: "Space-efficient sparse matrix storage formats for massively parallel systems"
5.3
Ostatní dosažené
• Pro projektu vznikly stránky, http://shimi.webzdarma.cz/vyzkum/egnla/egnla.html které byly následně převedeny na server SourceForge: https://sourceforge.net/p/egnla/ • Plugin do SW Mathematica je připraven ke zveřejnění v Mathematica repository, až bude tato služba zahájena. • Členové sdružení mohou novou službu (po stažení) využívat na svém klastru. Zakoupený klastr je umístěna v doméně FIT ČVUT a proto musí respektovat její bezpečnostní politiku, klastr je možno používat jen po předchozí domluvě a vyjasnění postupů.
6 6.1
Dosažené cíle, závěr a přínosy CUDA Networks
Všechny cíle projektu byly splněny. Simulátor neuronových sítí včetně učícího algoritmu, který z hlediska paralelizace výpočtů na GPU představoval nejobtížnější úkol, byl otestován a shledán funkčním. V rámci projektu vznikla platforma pro výpočty akcelerované na GPU s využitím technologie CUDA, umožňující uživatelům počítat v režimu clientserver. Uživatelé mají možnost výpočty zadávat a zpracovávat ve vysokoúrovňovém jazyce a prostředí systému Wolfram Mathematica.
6.2
EGNLA
Téměř všechny cíle projektu byly splněny, některé se ukázaly jako nerealizovatelné. Oproti zadání byl v rámci projektu navíc vyvinut řešič soustav lineárních rovnic v přesné aritmetice akcelerovaný pomocí GPU a některé pokročilé metody komprese velkých řídkých matic. Dosahované zrychlení je 7
pro některé operace vysoké (až 20),ale bohužel to je spíš výjimka. GPU má proti CPU ohromnou výkonnost v jednoduché přesnosti, ale ve dvojité přesnosti už není výkonnostní nárůst tak patrný. Dále je pro GPU neefektivní, pokud je nastává nepřímý přístup do datových struktur (např. u násobení řídké matice hustým vektorem apod.). Byly upraveny/implementovány nejběžnější operace s vektory a maticemi (hustými i řídkými). To umožňuje návrh a implementaci různých iterativních metod pro řešení velkých řídkých soustav lineárních rovnic (jako CG,BiCG apod.)
7
Další využitelnost a možnosti vývoje
7.1
CUDA Networks
Aktuální rozvoj technologií umožňuje zjednodušení implementace. Systém Wolfram Mathematica v poslední verzi implementuje přímou podporu CUDA a OpenCL do výpočetního jádra i možnost načítání vlastních dynamických knihoven v C/C++ přímo do běžícího výpočetního jádra. Ačkoliv by implementace simulátoru s využitím těchto možností byla snazší (např. režii okolo GPU, transformace dat atd. řeší nyní přímo systém Wolfram Mathematica), naše řešení stále nabízí nezanedbatelnou výhodu v možnosti spustit FrontEnd systému Wolfram Mathematica, výpočetní kernel a akcelerovaný GPU simulátor neuronových sítí každý na samostatném počítači a snadno tak rozložit výkonové požadavky.
7.2
EGNLA
Vývoj EGNLA bude dále pokračovat formou bakalářských, diplomových případně doktorandských prací na následující témata: 7.2.1
Checkpointing
Aplikace zatím postrádá možnost uložení všech datových struktur (checkpointing mechanismus). 7.2.2
Reakce na signály
Aplikace zatím postrádá schopnost reagovat na signály v rámci OS, která by vedly k např. uložení datových struktur. 7.2.3
Dedikovaný server
Je zvažována možnost instalace služby na některý dedikovaný server a provoz řídit plánovačem, ale je obtížné (někdy i nemožné) odhadnout dobu výpočtu
8
pro zařazení do správné fronty. Vzhledem k dynamicky měnícímu se vytížení je těžké určit dobu, za kterou bude naplánovaný výpočet opravdu spuštěn. 7.2.4
Jiné programové řešení
Aplikace je zatím navržena jako jeden proces ve kterém pro jednotlivé spojení vznikají vlákna, stejně tak pro výpočty vznikají nová vlákna. Ale jakákoliv chyba vede ukončení proces a tudíž i celé aplikace. 7.2.5
Grafové algoritmy
Grid by bylo vhodné rozšířit o podporu alespoň základních grafových algoritmů. Jako obtížnou se ukázala integrace s existujícími programy pro grafové algoritmy z důvodu neexistence standardizovaného formátu pro reprezentaci grafů. 7.2.6
Bezpečnost nebo fair-user policy
Autentizace není uživatelů služby není zatím prováděna. Není prováděno žádné šifrování, je kladen velký důraz na rychlost, navíc se nepředpokládá zasílání nějakých citlivých dat. Není zatím plánována žádná fair-user policy, grid je navržen spíše jako experimentální. Toto by bylo řešeno v rámci jeho případného dalšího rozvoje. 7.2.7
Řešič soustav lineárních rovnic
Systém zatím postrádá řešič soustav lineárních rovnic. Zajímavé možnosti v tomto směru nabízí knihovna MAGMA.
8
Tisková zpráva
Výsledkem řešení projektu Cesnetu „Experimentální výpočetní grid pro numerickou lineární algebru“ je • vytvoření platformy pro simulaci populací rekurentních neuronových sítí, přístupných uživatelům systému Wolfram Mathematica v režimu klient-server. Aktuální verze je k dispozici na http://evolution. felk.cvut.cz/cuda/ • vytvoření programu pro distribuované výpočty na grafických kartách. Aktuální verze je k dispozici na http://shimi.webzdarma.cz/vyzkum/ egnla/egnla.html
9
Reference [1] Z. Buk and M. Šnorek. Hybrid evolution of heterogeneous neural networks. In V. Kůrková, R. Neruda, and J. Koutník, editors, Artificial Neural Networks - ICANN 2008 , 18th International Conference, Prague, Czech Republic, September 3-6, 2008, Proceedings, Part I, volume 5164 of Lecture Notes in Computer Science, pages 426–434, Berlin, Heidelberg, 2008. Springer-Verlag. [2] Z. Buk and M. Šnorek. Continual Evolution Algorithm for Building of ANN-based Models. In Proceedings of the 6th EUROSIM Congress on Modelling and Simulation, volume 2007, Ljubljana, Slovenia, 2007. [3] Z. Buk and M. Šnorek. High-performance implementation of Recurrent Neural Networks on Graphics Processing Units. In Proceedings of the 7th EUROSIM Congress on Modelling and Simulation, volume 2: full papers, pages 1312–1315, Prague, Czech Republic, Sept. 2010. Czech Technical University in Prague. [4] Z. Buk. Akcelerace vědecko-technických výpočtů v systému Mathematica pomocí technologie nVidia CUDA. Ústav Fyziky, Filozofickopřírodovědecká fakulta, Slezská univerzita v Opavě, 2011. [5] R. J. Williams and D. Zipser. A Learning Algorithm for Continually Running Fully Recurrent Neural Networks, 1989.
10
