Akcelerace mapování funkcí ooooooooo Fúze kernelů oooooooo Automatizace fúzí ooooooooooooo Výsledky a další práce ooooooo Mapované funkce, fúze kernelů Jiří Filipovič podzim 2011 Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí Fúze ke rn e lil Automatizace fúzí Výsledky a další práce ♦OOOOOOOO OOOOOOOO OOOOOOOOOOOOO OOOOOOO Definice map map(r,/.!,..,/.„) aplikuje n-ární funkci f(k,..,ln) na seznam(y) vstupních elementů L\,.., Ln, n > 1. • f nazýváme mapovaná funkce » jednotlivé instance f jsou nezávislé - triviální paralelizace • avšak potenciálně problematická implementace f Naše aplikace • per-element výpočty v metodě konečných prvků Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí Fúze kernelů OÍOOOOOOO oooooooo Automatizace fúzí OOOOOOOOOOOOO Výsledky a další práce OOOOOOO Paralelní granularita Paralelní granularita • samotný map nám pro velké problémy poskytuje dostatečný stupeň paralelismu • co když jsou ale nároky na on-chip paměťové zdroje funkce f příliš vysoké? • paměťové nároky f lze snížit paralelizací • je-li f paralelní, může ji provádět blok threadů • to ale vyžaduje paralelizovatelnost na dostatečný počet vláken Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí Fúze kernelů Automatizace fúzí Výsledky a další práce oo«oooooo oooooooo ooooooooooooo ooooooo Středně-zrnný paralelismus Problematické mapované funkce • nelze efektivně řešit v jednom threadu (příliš mnoho on-chip zdrojů) • nelze efektivně řešit v bloku (příliš málo paralelizovatelné) Středně-zrnná implementace • navrhli jsme zavést úroveň paralelismu mezi thready a bloky • f je paralelizována na více threadů, ale více instancí f je počítáno v bloku • jednoduché pravidlo • složitější implementace Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí OOO0OOOOO Fúze kernelů OOOOOOOO Automatizace fúzí OOOOOOOOOOOOO Výsledky a další práce OOOOOOO Přístup do sdílené paměti Přístup do sdílené paměti je v případě středně-zrnných implementací složitější • broadcast v rámci funkce není broadcast v rámci half-warpu (problém odpadá u Fermi) • konflikty bank mohou vznikat mezi funkcemi • složité vyčíslení stupně konfliktu Zamezení konfliktů bank mezi funkcemi » padding mezi datovými elementy • prokládané uložení datových elementů Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí Fúze kernelů Automatizace fúzí Výsledky a další práce oooo«oooo oooooooo ooooooooooooo ooooooo Násobení malých čtvercových matic 1 thread na 1 element výsledné matice, více matic v bloku • všechny thready zpracovávající řádek C čtou stejnou hodnotu z A • všechny thready zpracovávající sloupec C čtou stejnou hodnotu z B • pro matice velikosti nedělitelné 16 požadavek na více broadcastů • problém pro c.c. 1.x • konflikty mezi instancemi funkcí nenastávají Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí Fúze kernelů Automatizace fúzí Výsledky a další práce oooo»ooo oooooooo ooooooooooooo ooooooo Násobení malých čtvercových matic 1 thread na řádek výsledné matice, více matic v bloku • thready zpracovávající paralelně sloupec C čtou sloupec z A • thready zpracovávající paralelně sloupec C čtou stejnou hodnotu z B • při paddingu A a C u matic sudé velikosti žádné konflikty bank uvnitř funkcí • konflikty mezi funkcemi u c.c. 1.x • násobné broadcasty z B 1 thread na sloupec výsledné matice, více matic v bloku • stejný problém s násobnými broadcasty • navíc obtížnější vyrovnání-se s konflikty čtení z B Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapován funkcí Fúze ke rn e lil Automatizace fúzí Výsledky a další práce oooooo«oo OOOOOOOO OOOOOOOOOOOOO OOOOOOO Násobení matic per-thread 2 4 6 8 10 12 14 16 Matrix size Obrázek: GeForce 280 Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapován funkcí Fúze ke rn e lil Automatizace fúzí Výsledky a další práce ooooooo»o OOOOOOOO OOOOOOOOOOOOO OOOOOOO Násobení matic 2 4 6 8 10 12 14 16 Matrix size Obrázek: GeForce 480 Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí Fúze kernelů Automatizace fúzí Výsledky a další práce 0000000« OOOOOOOO OOOOOOOOOOOOO OOOOOOO Někly lze optimalizovat specifické případy Násobení 4x4 matic • lze obejít násobné broadcasty • při 4 threadech na funkci začneme násobit vektory dávající element (/,_/') od pozice j, respektive / počítá-li jeden thread sloupec výsledné matice • při 16 threadech na funkci začneme násobit vektory dávající element (/,_/') od pozice (/+ j) mod 4 • nefunguje obecně Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí OOOOOOOOO Fúze kernelů #0000000 Automatizace fúzí OOOOOOOOOOOOO Výsledky a další práce OOOOOOO 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č Mapované funkce, fúze kernelů Akcelerace mapování funkcí ooooooooo Fúze kernelů 0*000000 Automatizace fúzí ooooooooooooo Výsledky a další práce ooooooo 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é Dekom pozice-fúze • 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č Mapované funkce, fúze kernelů Akcelerace mapování funkcí Fúze kernelů Automatizace fúzí Výsledky a další práce OOOOOOOOO oo»ooooo OOOOOOOOOOOOO OOOOOOO Mapované funkce Naše motivace k optimalizaci paměťové lokality • per-element výpočty v metodě konečných prvků • pracují s malými datovými elementy - většina výpočtů omezena propustností paměti (např. násobení 3x3 matic) • implementace map - funkce realizující výpočet je mapována nezávisle na velké množství elementů • jednoduché fúze - implicitní globální bariéra mezi kernely provádějící map lze nahradit lokální bariérou mezi jednotlivými fúzovanými funkcemi Budeme se zabývat primárně mapováním funkcí. Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí Fúze kernelů Automatizace fúzí Výsledky a další práce OOOOOOOOO 000*0000 ooooooooooooo ooooooo 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í kernelů, maskování latence) Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí ooooooooo Fúze kernelů 0000*000 Automatizace fúzí ooooooooooooo Výsledky a další práce ooooooo 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č Mapované funkce, fúze kernelů Akcelerace mapování funkcí ooooooooo Fúze kernelů ooooocoo Automatizace fúzí ooooooooooooo Výsledky a další práce ooooooo Omezení zrychlení Rozdílné nároky na paralelismus • každá instance mapované 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č Mapované funkce, fúze kernelů Akcelerace mapování funkcí Fúze kernelů OOOOOOOOO OOOOOOÍO Automatizace fúzí ooooooooooooo Výsledky a další práce OOOOOOO 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č Mapované funkce, fúze kernelů Akcelerace mapování funkcí ooooooooo Fúze kernelů ooooooo* Automatizace fúzí ooooooooooooo Výsledky a další práce ooooooo Vztah výkonu a zvýšené alokace paměti Sčítání 3x3 matic pomocí 3 threadů. Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí Fúze kernelů Automatizace fúzí Výsledky a další práce OOOOOOOOO OOOOOOOO «000000000000 ooooooo Schéma kompilátoru Co kompilátor potřebuje? • knihovnu elementárních funkcí (v CUDA) • vysokoúrovňový kód 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 vysokoúrovň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 vybrat nejvýkonnější implementaci/implementace • vygenerovat CUDA kód s fúzema Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí ooooooooo Fúze kernelů oooooooo Automatizace fúzí 0*00000000000 Výsledky a další práce ooooooo Příklad vysokou rovnováho kódu Funkci f : F = ||A • B • cj|2 • (D • E + D), kde A, B jsou 3x3 matice, c vektor velikosti 3 a D, E 5 x 5 matice zapíšeme v našem jazyce jako: MATRIX3x3 A, B, Ml; MATRIX5x5 D, E, F, M2, M3; VECT0R3 c, vl ; SCALAR sl; input A, B, c, D, E; Ml — mmul33(A, B); // Mt = A ■ B vl — mvmul33 (Ml , c ) ; // Vl - = Ml ■ c sl = venorm3 ( vl ) ; // si - -- \M |2 M2 — mmul55(D, E); // M2 = D ■ E M3 — madd55(M2, D) ; // M3 = M2 + D F - = smmul55(M3, sl); // F = M3 ■ Sl return F; Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí ooooooooo Fúze kernelů oooooooo Automatizace fúzí oo«oooooooooo Výsledky a další práce ooooooo Kód převedený na DAG Obrázek: Kód převedený na DAG <|> <|> i -oc^o Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí OOOOOOOOO Fúze kernelů OOOOOOOO Automatizace fúzí ooo»ooooooooo Výsledky a další práce OOOOOOO Elementární funkce mají předepsanou strukturu „load-compute-store" • fúze realizujeme serializací funkcí a odstranění přebytečných load a store rutin • v současném stavu vývoje pouze přenos dat přes sdílenou paměť Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí Fúze kernelů Automatizace fúzí Výsledky a další práce ooooooooo oooooooo oooo«oooooooo ooooooo Generování kódu II Každá funkce pracuje s různými vstupy a výstupy v různé paralelní granularitě • knihovna obsahuje vedle kódu elementárních funkcí také metadata • umožňují silnou typovou kontrolu • generátor kódu dokáže spojovat funkce s rozdílnými nároky na paralelismus přepočítáním koordinát threadu a omezením paralelismu pro některé fúzované funkce Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí Fúze kernelů Automatizace fúzí Výsledky a další práce ooooooooo oooooooo ooooo»ooooooo ooooooo Predikce výkonu Hlavní myšlenka • změříme rychlost rutin v simulovaném prostředí fúze • pro měnící-se dodatečnou alokaci sdílené paměti • pro rozdílné velikosti bloku GPU dokáží překrývat paměťové přenosy a výpočty • pro každou fúzi tedy odhadujeme výkon jako maximum ze sumy časů výpočetních rutin a sumy časů rutin kopírujících data • pokud dochází k přepočítání souřadnic threadu, přičítáme k času konstantu aproximující čas tohoto přepočítání V současnosti zanedbáváme • nedokonalé překrytí výpočtu a paměťových přenosů při redukovaném paralelismu • režii nepracujících threadů • celkový mix funkcí ve fúzi (ovlivňuje možnosti GPU přepínat warpy) < i ► i -00.0 Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí Fúze kernelů Automatizace fúzí Výsledky a další práce ooooooooo oooooooo oooooo«oooooo ooooooo Prostor optimalizací Optimalizace mají mnoho stupňů volnosti • fúzovatelné podgrafy DAGu tvoří fúze • linearizace fúzí určuje pořadí volání funkcí ve fúzi a tím i spotřebu paměti • implementace elementárních funkcí ve fúzi (spolu s předchozím implementace fúze) • kombinace implementací fúzí určuje, které fúze použijeme Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí Fúze kernelů OOOOOOOOO OOOOOOOO Automatizace fúzí Výsledky a další práce OOOOOOO0OOOOO OOOOOOO Fúze Podgrafy DAGu, pro které platí • neexistuje cesta, která vede ven z fúze a zase se do ní vrací Fúzí je velké množství • v nejhorším případě 0(2^' ), v nejlepším 0{\n2 ) Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí OOOOOOOOO Fúze kernelů OOOOOOOO Automatizace fúzí oooooooo«oooo Výsledky a další práce OOOOOOO Fúze - prořezávání prostoru Fúze musí tvořit souvislou komponentu • jinak nešetříme datové přenosy Velikost fúzí lze omezit • čím větší fúze, tím méně ušetříme paměťových přenosů přidáním další funkce • s velikostí fúze roste šance, že nepůjde implementovat efektivně • omezení velikosti na k funkcí snižuje složitost nejhoršího případu na Elo OT') • výrazně zjednoduší prohledávání prostoru implementaci fúzí Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí Fúze kernelů Automatizace fúzí Výsledky a další práce ooooooooo oooooooo ooooooooo»ooo ooooooo Linearizace fúze Každá fúze obsahuje podgraf DAGu, pro implementaci je třeba určit pořadí spouštění funkcí • to je důležité, jelikož ovlivňuje množství alokované on-chip paměti • máme až 0(| V|!) linearizací, pro každou z nich existuje exponenciálně mnoho možností jak alokovat paměť Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí Fúze kernelů Automatizace fúzí Výsledky a další práce OOOOOOOOO OOOOOOOO 0000000000*00 ooooooo Linearizace fúze - prořezávání prostoru Vybereme linearizaci s nejnižším dolním odhadem alokované paměti • jedná se tedy o aproximaci, nepostihneme fragmentaci paměti • pro vybranou linearizaci spočítáme precizně alokaci paměti pomocí branch-and-bound algoritmu v 0(mn) kde m je celková velikost alokované paměti a n počet funkcí V praxi • linearizaci bývá výrazně méně, než určuje horní mez • před branch-and-bound algoritmem najdeme počáteční řešení polynomiálním greedy algoritmem, ten často najde optimum • i ve zlomyslném případě je řešení dosažitelné díky omezení velikosti fúzí Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí Fúze kernelů Automatizace fúzí Výsledky a další práce ooooooooo oooooooo ooooooooooo«o ooooooo Výběr implementací elementárních funkcí Dále je třeba vybrat konkrétní implementace elementárních funkcí • projdeme všechny přiřazení konkrétních implementací elementárních funkcí: f3"=0 kde #//je počet implementací /-té funkce • pro každé přiřazení odhadneme výkon pomocí predikce výkonu Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí Fúze kernelů Automatizace fúzí Výsledky a další práce OOOOOOOOO OOOOOOOO 000000000000« ooooooo Výběr kombinací fúzí Máme-li seznam implementací fúzí s odhadem jejich výkonu, je ještě zapotřebí určit, které budou použity • ze všech kernelů (implementace fúzí a samostatné elementární funkce) vybíráme ty, které dohromady tvoří celý DAG a maximalizujeme odhadnutý výkon • problém pokrytí množin • řešeno pomocí lineárního programování Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí Fúze kernelů Automatizace fúzí Výsledky a další práce OOOOOOOOO OOOOOOOO OOOOOOOOOOOOO •OOOOOO Přesnost predikce 1400 1200 - 1000 800 600 400 200 Estimated o Measured + Fusions implementations (sorted by real time) Obrázek: Přesnost predikce výkonu jednotlivých fúzí pro demonstrační příklad, pro GTX480. m -00,0 Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí Fúze kernelů Automatizace fúzí Výsledky a další práce ooooooooo oooooooo ooooooooooooo ocooooo Celková úspěšnost výběru implementací I 50 100 150 200 250 Mapped Function Implementations 300 Obrázek: Reálná rychlost generovaných implementací demonstračního příkladu pro GTX480. m -00,0 Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí Fúze kernelů Automatizace fúzí Výsledky a další práce OOOOOOOOO OOOOOOOO OOOOOOOOOOOOO OOÍOOOO Celková úspěšnost výběru implementací II rychlost pořadí výběru 1. 1 2. 49 3. 2 4. 7 5. 29 Tabulka: Pořadí výběru pěti nejrychlejších implementací Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí Fúze kernelů Automatizace fúzí Výsledky a další práce OOOOOOOOO OOOOOOOO OOOOOOOOOOOOO 000*000 Ukázka vybraných fúzí fúze granularita {\\A-B-v\\2}-{{C-D+C)} {3 3 1} {5 5 5} \\{A-B-v} ||2- { (C-D + C) } {3 3} 1 {5 5 5} \\A-B-v\\2- { {C-D + C) } 3 1 1 {5 5 5} { \\A-B-v\\2-{C-D+C) } {3 3 1 5 5 5} \\A ■ B ■ v\\2 ■ (C ■ D + C) 3 115 5 5 Tabulka: Vybrané fúze seřazené dle rychlosti Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí Fúze kernelů Automatizace fúzí Výsledky a další práce ooooooooo oooooooo ooooooooooooo oooo«oo Rozšíření kompilátoru Generování efektivnějšího kódu • vyjádření vztahu threadů k přistupovaným datům • předávání dat pomocí registrů • vynechání synchronizace • složitější predikce výkonu • optimalizace mimo bloky (DAG) • unrolling for cyklů • paralelní běh nezávislých kernelů a přenosů paměti Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí Fúze kernelů ooooooooo oooooooo Automatizace fúzí OOOOOOOOOOOOO Výsledky a další práce OOOOOÄO Rozšíření kompilátoru Efektivnější výběr rychlých implementací • odhad překryvu paměťových operací a výpočtu • analytický výpočet doby paměťových přenosů • redukce systematické chyby u benchmarkingu jednoduchých kernelů Spousta další implementační práce směrem k produkční verzi :-). Jiří Filipovič Mapované funkce, fúze kernelů Akcelerace mapování funkcí Fúze kernelů Automatizace fúzí Výsledky a další práce OOOOOOOOO OOOOOOOO OOOOOOOOOOOOO 000000« Rozšíření kompilátoru Samotné mapování má relativně širokou aplikaci • díky obtížné synchronizaci mezi bloky se jedná o přirozený model pro GPU • nejsme nutně omezeni na malé datové struktury • součet velkých vektorů lze vyjádřit jako mapování mnoha součtů malých vektorů Velmi zajímavé rozšíření aplikace přinášejí redukce • vyžadují globální bariéru, výsledek redukce tedy nelze použít ve stejné fúzi • nejnáročnější první iteraci však můžeme fúzovat s mapovanou funkcí (redukujeme zvlášť výsledek každé instance mapované funkce) • mapovania redukce nám umožní fúzovat BLAS rutiny Jiří Filipovič Mapované funkce, fúze kernelů