13.8.2015
Jedna z našich úloh zpracovává velké množství dat. Nejde o nic složitého - jde o jednoduchou statistiku: průměr, medián, standardní odchylka a rozložení pravděpodobností podle různých skupin. Množství dat může být skutečně úctyhodné, naštěstí však stále v možnostech běžného PC (od jednotek miliónů až do stovek miliónů údajů). I když úzkým hrdlem je zde většinou přesun dat z disku do paměti počítače, zanedbat se při současném způsobu zpracování nedá ani doba skutečného výpočtu v procesoru počítače. Ta se nyní pohybuje v produkční verzi aplikace kolem dvou vteřin. Nevypadá to jako něco strašného, ale prakticky to dokáže uživatele naprosto odradit od interaktivní práce s aplikací.
Snažil jsem se proto nastudovat postupy, které by vedly k větší efektivitě výpočtů. Nejdůležitějším výpočetním prvkem v počítači je procesor, dnes vesměs vícejadrový - vícejádrové procesory se dnes montují už i do mobilních telefonů. Dalším výkonným výpočetním prvkem v počítači je grafická karta.
Nějaké zkušenosti s programováním pro více jader už jsem stačil nasbírat. Ve svém pracovním stroji mám procesor s osmi jádry a ve svých aplikacích dovedu všechna jádra docela slušně prohnat. Nadešel pro mě čas prozkoumat i možnosti grafických karet.
Každá grafická karta nabízí programátorovi několik výpočetních jednotek, které mohou pracovat paralelně, a různé množství paměti. Množství výpočetních jednotek určuje rychlost výpočtů, množství paměti pak určuje, kolik údajů mohu zpracovat najednou.
Grafické karty jsem otestoval dvě:
| Typ karty | Výpočetní jednotky | Velikost paměti |
|---|---|---|
| AMD HD 5450 | 2 | 512 MB |
| AMD Radeon R7 260X | 14 | 2048 MB |
Pro výpočty lze použít dvě různá prostředí: OpenCL a Cuda. Prostředí Cuda je specifické pro grafické karty NVidia, OpenCL by pak mělo mít podporu obou výrobců grafických karet, AMD i NVidia. Prostředí se svými možnostmi asi příliš neliší. Protože mám kartu od AMD, nezbylo mi nic jiného, než použít OpenCL. K této volbě bych ale sáhnul i v případě NVidia karet. Vyvíjím aplikace pro své zákazníky a chci, aby jim to běhalo bez ohledu na výrobce počítače.
Aplikace se programují v jazyce C. OpenCL umožňuje použít i C++, ale tuhle možnost jsem nezkoušel. Prostředí je poměrně specifické - většinou lze použít pouze float hodnoty (přesnost cca 6 desetinných míst) místo hodnot double (dvojnásobná přesnost). Někdy je nutné na to pamatovat.
Zpracování dat v prostředí OpenCL je poměrně specifické a probíhá v několika typických krocích:
Data je pochopitelně potřeba načíst například z databáze. Součástí mohou být různé konverze, typicky se data konvertují do různých čtveřic float hodnot. Grafická karta je určená ke zpracování grafických dat v 3D prostoru, kde se typicky vyskytují tři souřadnice (x, y, z) a někdy k tomu přistupuje i čtvrtá hodnota (w). Pro data se alokuje voláním funkcí OpenCL buffer, do kterého je potřeba data naskládat. Stejným způsobem se může alokovat buffer pro výstupní data. Pro řadu úloh bývá vstupní i výstupní buffer stejně velký, někdy však mohou být výstupní data menší (zredukovaná), nebo se přepíšou data vstupní. Při redukcích se často postupuje v několika iteracích, takže během výpočtu může být potřeba buffery alokovat několikrát.
Data z paměti počítače se po sběrnici PCIe přesunou do paměti grafické karty. Při větším objemu dat může být právě přesun časově hodně náročný. I jednoduchý, naivní výpočet ukazuje, že při rychlosti 8GB/s (rychlost PCIe 2.0) je minimální doba přesunu 500MB zhruba 65 ms.
Jakmile jsou data v přesunutá do grafické karty, je možné spustit výpočet. Program určený pro grafickou kartu se obvykle vytváří v jazyce C. Zvláštností je, že program se překládá v rámci přípravy přímo překladačem určeným pro použitou grafickou kartu. Jde skutečně o překlad do strojového kódu karty - není to překlad do bytekódu (jako u jazyka Java) nebo interpretace (PHP). Překlad se dělá pouze jednou, při spuštění aplikace, doba překladu se proto do celkové doby zpracování nemusí započítávat.
Program pro grafickou kartu je sice napsaný v jazyce C, ale musí respektovat specifika paralelního programování a použitými postupy se jen stěží podobá programům pro běžné procesory. Jednotlivá výpočetní vlákna na sebe nevidí, nemohou zapisovat na stejné místo v paměti, výpočty probíhají v rámci skupiny (například 256 vláken), v rámci které je potřeba výpočet synchronizovat. Dobře naprogramovaný výpočet však může probíhat v porovnání s PC velmi rychle.
Po dokončení výpočtu je data nutné přesunout zpět do RAM počítače. Zde je opět limitujícím faktorem především rychlost sběrnice PCIe. Řada paralelních algoritmů data nedokáže nijak zredukovat, takže z grafické karty se často tahá stejný objem dat, jaký do výpočtu vstupoval.
Jakmile data dostane k dispozici opět počítač, je nutné data zkonvertovat do požadované podoby. U některých algoritmů může být konverze jednoduchá - redukce dat může vytvořit z celé vstupní množiny jediné číslo. Jindy může být konverze náročnějsí - je potřeba projít výstupní buffer stejně veliký, jako vstupní data, a vyzobat z nich požadované výsledky.
V rámci statistického zpracování se neděje obvykle nic složitého. Velmi názorný je v tomto ohledu jazyk SQL:
select avg(value), stddev(value) from data;
Celý vstupní soubor dat je v tomto případě redukovaný na jedinou hodnotu průměru a jedinou hodnotu standardní odchylky.
Stejný výpočet v jazyce C je trochu náročnější o výpočet odchylky, ale i zde je možné data zredukovat v rámci jediného průchodu cyklem:
double sum = 0;
double sum2 = 0;
for (int i=0; i<data.size(); i++) {
sum += data[i];
sum2 += data[i] ^ 2;
}
double avg = sum / data.size();
double stddev = sqrt ( (sum2 - (sum * sum / data.size())) / data.size() );
Stejný výpočet implementovaný v grafické kartě je řádové složitější, ale vede k jediné hodnotě v rámci celého vstupního souboru. Data se díky tomu přesouvají pouze do grafické karty, zpět se přesouvá jen silně redukované množství dat. V grafické kartě se provádí kód uvedený v cyklu, kód za cyklem je potřeba provést až v procesoru po získání zredukované hodnoty sum a sum2.
Pro výpočet v grafické kartě se pro tento typ úloh typicky používá algoritmus Reduce. Ten je velmi dobře zpracovaný a známý, na internetu lze nalézt velké množství příkladů a návodů.
Stejného výsledku lze dosáhnout i algoritmem Scan, ale použití tohoto algoritmu nemusí být efektivní z důvodu rozsáhlého výstupního souboru dat.
Ve statistice se však vyskytuje další typ úloh, který je na zpracování mnohem náročnější. Zápis v SQL je opět velmi jednoduchý a názorný:
select key, avg(value), stddev(value) from data group by key;
V jazyce C je výpočet o cosi složitější, ale stále relativně dobře čitelný (používám kontejnery z Qt). Probíhají zde dvě iterace: poprvé se prochází cele vstupní pole dat a hodnoty se načítají do tabulek organizovaných podle skupiny, podruhé se procházejí zredukované hodnoty a počítají se výsledné hodnoty pro každou skupinu. Doba zpracování druhé iterace však může být bezvýznamná v porovnání s dobou potřebnou pro zpracování první iterace.
QHash<int, double> num;
QHash<int, double> sum;
QHash<int, double> sum2;
for (int i=0; i<data.size(); i++) {
int key = data[i].key;
double value = data[i].value;
num[key] += 1;
sum[key] += value;
sum2[key] += value * value;
}
QHash<int, double> avg;
QHash<int, double> stddev;
QHash<int, double> iterator(sum);
while (iterator.hasNext()) {
iterator.next();
int key = iterator.key();
avg[key] = sum[key] / num[key];
stddev[key] = sqrt ( (sum2[key] - (sum[key] * sum[key] / num[key])) / num[key]);
}
Pro výpočet v grafické kartě už nelze použít algoritmus Reduce, místo toho je nutné sáhnout po algoritmu Scan. Implementace obou algoritmů v grafické kartě je velmi podobná, zásadně se však oba algoritmy liší ve výstupních datech. Zatímco algoritmus Reduce produkuje jedinou hodnotu, výstupní data algoritmu Scan jsou stejně velká jako data vstupní. Zdvojnásobuje se tak doba potřebná pro přesuny dat mezi pamětí počítače a pamětí grafické karty. Navíc data jsou různě rozházená ve výstupním poli dat a v počítači je stejně nutné projít celé výstupní pole a vyzobat pouze požadované hodnoty. Jedna kompletní iterace nad daty v počítači (jazyk C) tak byla nahrazena jiným postupem: přesun dat do grafické karty, výpočet v grafické kartě, přesun do počítače a nakonec kompletní iterace nad výstupními daty.
Jistě jste si všimli, že jsem v předchozí části neuvedl žádný příklad programu pro grafickou kartu. Má to dva důvody:
Složitost celé implementace výpočtu je při použití OpenCL o jeden až dva řády složitější. Kde je použitý jediný iterační cyklus v jazyce C na několika málo řádcích, tam je v případě OpenCL nutné napsat několik set řádků kódu (400...500) pro nalezení grafické karty, překlad programu pro grafickou kartu, alokaci bufferů, přesuny dat a výsledné zpracování dat.
Algoritmy pro paralelní zpracování navíc bývají jen obtížně čitelné. Google v tomto ohledu není příliš nápomocný - praktických zkušeností s paralelním programováním je mezi programátory velice málo. Je proto nemožné programovat stylem "opíšu to ze stackoverflow". Algoritmy je často nutné dobře pochopit a přiznám se, že i mě přemýšlení často bolí, obtěžuje a zdržuje od placené práce.
K dispozici bývají na internetu často jen akademické práce popisující paralelní algoritmy. Akademický jazyk má svá specifika a pro prakticky založeného programátora může být implementace podle akademického popisu náročná.
Tento text píšu řadu týdnů po svých experimentech s OpenCL, přesné hodnoty ode mne proto nečekejte. V grafické kartě jsem testoval pouze algoritmus Reduce. Doba zpracování se pohybovala přibližně v těchto rozmezích:
Stejný výpočet (jedna iterace v počítači) přitom trval kolem 100 ms.
Zde se tedy z hlediska výkonu přesun výpočtu do grafické karty rozhodně nevyplatil, i když samotný výpočet zvládla grafická karta více než třikrát rychleji.
Algoritmus Scan v této situaci ani nemělo cenu testovat, protože by se daly očekávat hodnoty tohoto typu:
V počítači lze přitom očekávat časy kolem 150...200 ms.
Z hlediska výkonu proto nemá grafická karta pro naše statistické výpočty opodstatnění.
Před tím, než uvěříte tomu, co zde píšu, vás musím upozornit, že moje praktické zkušenosti s programováním v OpenCL spočívají v lopotném průzkumu bojem, nemám za sebou žádnou smysluplnou aplikaci využívající paralelní výpočty v grafické kartě.
A nyní už můj závěr: Snažit se využít grafickou kartu pro urychlení statistických výpočtů je ztrátou času. Ačkoliv grafická karta dokáže počítat ve srovnání s procesorem skutečně velmi rychle, výsledný čas zpracování je silně ovlivněn přesuny dat mezi pamětí počítače a pamětí karty.
Výsledná složitost je o jeden až dva řády vyšší. Úměrně tomu klesá čitelnost kódu. I když je možné potřebnou režii uklidit do různých knihoven nebo tříd (v C++), stále zde zůstává složitost a nečitelnost paralelních algoritmů.
Podstatná je i dostupnost programátorů zvládajících paralelní algoritmy. Nedokážu nyní najít zdroj informace, ve které jsem se dočetl, že zkušenosti s paralelními algoritmy má jen asi jedna setina programátorů. Je nepochybné, že takový programátor si své znalosti nechá dobře zaplatit, a potom stojí za zváženou, jestli prostě není jednodušší a levnější koupit výkonnější počítač.
Při svých experimentech jsem se snažil využít grafickou kartu například při astronomických výpočtech. Zde je zrychlení velmi markantní. Zatímco výpočet v CPU trval kolem 10 ms, stejný výpočet v grafické kartě zabral obvykle méně než 1 ms. Je nutno podotknout, že soubor dat zde není nijak rozsáhlý a v aplikaci, pro kterou je výpočet určen, nehraje 10 ms roli. Výpočet se navíc nijak výrazně neliší od výpočtu v procesoru počítače, jednotlivé vstupní údaje jsou totiž na sobě zcela nezávislé.
Pokud chci počítač trochu potrápit, sáhnu tradičně po N-Body problému - jde o numerický výpočet gravitačních interakcí mezi velkým množstvím těles. Pro grafickou kartu jsem výpočet programovat nemusel, našel jsem příklad přímo v materiálech od AMD. Zde je výpočet více než 40× rychlejší, než na osmijádrovém procesoru. A to i přes to, že se data po každé iteraci přesunou z karty do paměti počítače a potom přes OpenGL zpět do grafické karty.
I pro grafickou kartu tak lze najít třídu úloh, kde je výpočet mnohem efektivnější. Většinou jde o takové úlohy, kde se postupnými iteracemi modifikují vstupní data a ta pak vstupují do další iterace - typicky fyzikální simulace.
khronos.org
developer.amd.com
Návrhové vzory a algoritmy, Cuda
Algoritmus Reduce
Algoritmus Scan