Úvod Optimalizace pomocí fúzí Fúzovatelnost funkcí Kompilátor Vyhodnocení 0 ooooooo ooooo OOOOOOOOOOOOOOOOfJCODOO Optimalizace CUDA kernelů pomocí fúzí aneb kterak zrychlit (izolovaně) nezrychlitelné Jiří Filipovič, Jan Fousek, Matúš Madzin 3. prosince 2012 Jiří Filipovič, Jan Fousek, Matúš Madzin Optimalizace CUDA kernelů pomocí fúzi Úvod Optimalizace pomocí fúzí Fúzovatelnost funkcí Kompilátor Vyhodnocení • OOOOOOO OOOOO 0000000000000000030000 Obsah prezentace • fúze jako optimalizační metoda • fúzovatelnost funkcí • kompilátor • aplikace na BLAS Jiří Filipovič, Jan Fousek, Matúš Madzin Optimalizace CUDA kernelů pomocí fúzi Úvod Optimalizace pomocí fúzí Fúzovatelnost funkcí O #000000 OOOOO Kompilátor Vyhodnocení 0000000000000000030000 Kernely omezené propustností paměti GPU vykoná desítky operací na přenos jednoho slova z/do globální paměti • pokud náš kernel provádí aritmetických operací méně, je rychlost jeho provádění omezena rychlostí paměti • data se zpravidla nevyskytují ve vyrovnávací paměti od předchozího běhu kernelu (ty jsou příliš malé) Důvod vzniku kernelů omezených rychlostí paměti • řešíme paměťově omezený problém (např. a + b) • z principu nelze ovlivnit • píšeme rozumně znovupoužitelný kód (např. a + b + c voláním kernelů pro součet dvou vektorů) • omezení snížíme použitím kernelu sčítajícího tři vektory, mezivýsledky zůstanou uloženy ve sdílené paměti nebo v registrech Jiří Filipovič, Jan Fousek, Matúš Madzin Optimalizace CUDA kernelů pomocí fúzi Úvod Optimalizace pomocí fúzí Fúzovatelnost funkcí Kompilátor Vyhodnocení o o»ooooo OOOOO OOOOOOOOOOOOOOOOO10DOO Fúze kernelů Máme-li sekvenci volání paměťově omezených kernelů, které si vzájemně předávají data • mohou být zpravidla nahrazeny komplexnějšími kernely, které vykazují lepší paměťovou lokalitu (některá data se předávají pomocí rychlejších on-chip pamětí) „Ruční" vývoj komplexních kernelů je dosti nákladný • mnoho kombinací, omezená znovupoužitelnost • od určitého okamžiku nemusí být provádění více výpočtů v jednom kernelů výhodné, nalezení optima složité Jak z toho ven? • implementujeme jednoduché, znovupoužitelné kernely • každý kernel volá rutiny pro načtení vstupu, výpočet a uložení výsledku • v závislosti na předávání dat tyto kernely spojujeme ve větší celky • lze provádět automaticky Jiří Filipovič, Jan Fousek, Matúš Madzin Optimalizace CUDA kernelů pomocí fúzi Úvod Optimalizace pomocí fúzí Fúzovatelnost funkcí Kompilátor Vyhodnocení O OOCOOOO OOOOO OOOOOOOOOOOOOOOOO10DOO Horní hranice zrychlení U paměťově omezených kernelů zrychlení zhruba odpovídá procentu ušetřených přenosů paměti. Např. a + b + c • 2 kernely - čtení 4 vektorů, uložení 2 • fúze - čtení 3 vektorů, uložení 1 • fúze odstraní 1/3 přenosů, tzn. 1.5x zrychlení • zrychlení může být v praxi větší (overhead spouštění kernelu, maskování latence) Jiří Filipovič, Jan Fousek, Matúš Madzin Optimalizace CUDA kernelů pomocí fúzi Úvod Optimalizace pomocí fúzí Fúzovatelnost funkcí Kompilátor Vyhodnocení O 000*000 OOOOO OOOOOOOOOOOOOOOOO10DOO Omezení zrychlení Jakmile přestane být kernel paměťově omezený • další redukce paměťových přenosů nezvyšuje rychlost výpočtu (není-li problém latence paměti) • rychlost výpočtu však může být vyšší (overhead spouštění kernelu, maskování latence, optimalizace sekvenčního kódu) Konzumace on-chip pamětí • ve fúzi může být vyšší (mezidata používané dalšími fúzovanými funkcemi) • vyšší nároky na on-chip paměti omezují dosažitelný stupeň paralelismu, může snižovat výkon Jiří Filipovič, Jan Fousek, Matúš Madzin Optimalizace CUDA kernelů pomocí fúzi Úvod Optimalizace pomocí fúzí Fúzovatelnost funkcí Kompilátor Vyhodnocení O OOOOCOO OOOOO OOOOOOOOOOOOOOOOO10DOO Omezení zrychlení Rozdílné nároky na paralelismus • každá instance funkce může běžet ve více vláknech (dosažení vhodného poměru počtu vláken ke spotřebované on-chip paměti) • pro každou fúzovanou funkci ale může být efektivní jiný počet vláken • při fúzi funkcí běžících v rozdílném počtu vláken tak musí být přepočítávány koordináty vláken a některá vlákna jsou část výpočtu nevyužita • vynutíme-li naopak stejné počty vláken pro všechny fúzované funkce, obecně nepoužíváme nejefektivnější dostupné implementace Jiří Filipovič, Jan Fousek, Matúš Madzin Optimalizace CUDA kernelů pomocí fúzi Úvod Optimalizace pomocí fúzí Fúzovatelnost funkcí Kompilátor Vyhodnocení O OOOOOÍO OOOOO OOOOOOOOOOOOOOOOO10DOO Výkon rozdílně paralelních implementací Sčítání 3x3 matic pomocí 1, 3 a 9 threadů, a s 32 floaty alokovanými navíc ke každé funkci. 20 L-^—'—'-'-'-'-1 8126 24 32 48 64 96 128 operations in block Jiří Filipovič, Jan Fousek, Matúš Madzin Optimalizace CUDA kernelů pomocí fúzi Úvod Optimalizace pomocí fúzí Fúzovatelnost funkcí Kompilátor Vyhodnocení O OOOOOO* OOOOO OOOOOOOOOOOOOOOOO10DOO Vztah výkonu a zvýšené alokace paměti Sčítání 3x3 matic pomocí 3 threadů. Jiří Filipovič, Jan Fousek, Matúš Madzin Optimalizace CUDA kernelů pomocí fúzi Úvod Optimalizace pomocí fúzí Fúzovatelnost funkcí Kompilátor Vyhodnocení o ooooooo aoooo oooooooooooooooooiodoo Automatizace fúzí Obecné kernely se fúzují špatně • libovolné mapování vláken a bloků na data • abychom mohli nechat data v on-chip paměti, musí být totožné • jak jej analyzovat? či upravit? • globální bariéra mezi běhy kernelů • nelze implementovat uprostřed běhu kernelu • lze ji nahradit lokální? či vypustit? Můžeme fúzovat kernely provádějící konkrétní funkci vyššího řádu. Jiří Filipovič, Jan Fousek, Matúš Madzin Optimalizace CUDA kernelů pomocí fúzi Úvod Optimalizace pomocí fúzí Fúzovatelnost funkcí Kompilátor Vyhodnocení O OOOOOOO 0*000 0000000000000000030000 Map Definice map • Nechť map(f, L) = [f{el),f{e„))]. • Kde L = [ei , &2, ■ ■ ■, £n] seznam n elementů 61,..., sn. • Funkce f • může být provedena více vlákny • musí být proveditelná v jednom bloku Důsledky pro fúzovatelnost • spustíme stejný počet instancí fúzovaných funkcí na blok • pak můžeme nahradit globální bariéru lokální (i-tá instance zpracovává i-tý element) • pokud zároveň předáváme data přes sdílenou paměť • není problém s mapováním vláken na data Jiří Filipovič, Jan Fousek, Matúš Madzin Optimalizace CUDA kernelů pomocí fúzi Úvod Optimalizace pomocí fúzí Fúzovatelnost funkcí Kompilátor Vyhodnocení O OOOOOOO OOÄOO 0000000000000000030000 Reduce Definice reduce • reduce{®, Ľ) = ei © e2 © • • • © e„, kde L = [ei, e2,..., e„] • © je asociativní Pro získání výsledku musíme zpracovat celý L • neobejdeme se bez globální bariéry Důsledky pro fúzovatelnost • Díky asociativitě © můžeme ale fúzovat parciální redukce • redukujeme vše, co máme lokálně dispozici • redukce je dokončena až po doběhnutí redukujícího kernelu, její výsledek tedy nemůžeme použít v kernelu, který ji provádí Mapování na data triviální • vstup redukce musí být ve sdílené paměti či registrech, pak lze redukovat vše v bloku Jiří Filipovič, Jan Fousek, Matúš Madzin Optimalizace CUDA kernelu pomocí fúzi Úvod Optimalizace pomocí fúzí Fúzovatelnost funkcí Kompilátor Vyhodnocení o ooooooo ooo«o OOOOOOOOOOOOOOOOO10DOO Vyjádření BLAS funkcí jako map a reduce BLAS (Basic Linear Algebra Subprograms) • standard pro knihovny implementující základní funkce z lineární algebry na maticích a vektorech • hojně využívaný (nejen) ve vědeckém software • obecně velmi dobře optimalizované implementace • jakékoliv zrychlení zajímavé Výkon některých funkcí omezený rychlostí paměti • BLAS-1 (vektor-vektor), lze vyjádřit pomocí map a reduce • BLAS-2 (matice-matice), část lze vyjádřit pomocí vnořených map a reduce Sekvence volání BLAS-1 a BLAS-2 lze zrychlit fúzema • není možno v izolovaných BLAS funkcích • obecné zrychlení BLAS, navíc obecnou metodou Jiří Filipovič, Jan Fousek, Matúš Madzin Optimalizace CUDA kernelů pomocí fúzi Úvod Optimalizace pomocí fúzí Fúzovatelnost funkcí Kompilátor Vyhodnocení O OOOOOOO OOOO* OOOOOOOOOOOOOOOOOXDOO Příklad vyjádření BLAS-2 funkce Násobení matice vektorem y = Ax vyjádříme jako y = map(reduce(+, map(-, A,, x)), A) kde A = [Ai,.. .,Am], A; = [aiA,af>] a x = [xi,... ,xn]. Pozn. proč ne y = map(dotprod(Ai,x), A)l Jiří Filipovič, Jan Fousek, Matúš Madzin Optimalizace CUDA kernelů pomocí fúzi Úvod Optimalizace pomocí fúzí Fúzovatelnost funkcí Kompilátor Vyhodnocení O OOOOOOO OOOOO »000000000000000010000 Schéma kompilátoru Co kompilátor potřebuje? • knihovnu elementárních funkcí (v CUDA) • script definující sekvenci jejich volání Co musí udělat? • analýzu kódu • správně rozpoznat, jaké má k dispozici funkce a jak je použít • přečíst vysokourovňový kód a na jeho základě vybudovat DAGy volání a předávání parametrů • optimalizace • prohledat a prořezat prostor fúzí nad každým DAGem • pro každou fúzi prohledat a prořezat prostor jejích implementací • na základě predikce výkonu zkombinovat implementace fúzí a nefúzovaných kernelů pro maximalizaci výkonu • vygenerovat CUDA kód s fúzema Jiří Filipovič, Jan Fousek, Matúš Madzin Optimalizace CUDA kernelů pomocí fúz Úvod Optimalizace pomocí fúzí Fúzovatelnost funkcí Kompilátor Vyhodnocení O OOOOOOO OOOOO OÄOOOOOOOOOOOOOO0B3DOO GEMVER B <— A + uiVi + l/2 v J x