Případové studie o Molekulový docking oooooooooooooooooooo Akcelerace mapování funkcí oooooooooooooo Molekulový docking, mapování funkcí Jiří Filipovič podzim 2010 Jiří Filipovič Molekulový docking, mapování funkcí Případové studie Molekulový docking Akcelerace mapování funkcí • oooooooooooooooooooo oooooooooooooo Případové studie Ve druhé polovině předmětu se budeme zabývat studiemi konkrétního nasazení CUDA • pro lepší představu, k čemu všemu se dají akcelerátory využít • chápeme-li práci jiných, pomůže nám to v práci vlastní • rozdílné obory často sdílí mnoho společných principů • pokusíme se o nabídku přesahující zkušenosti přednášejících • budou následovat zvané přednášky :-) □ - = = ^Q^O Jiří Filipovič Molekulový docking, mapování funkcí Případové studie Molekulový docking Akcelerace mapování funkcí 0 »0000000000000000000 oooooooooooooo Molekulový docking Problém „zadokovánf (zapadnutí, zaskočení) jedné molekuly do druhé • zpravidla dokujeme malou molekulu (ligand) do velké (receptor, většinou protein) • hledáme stabilní komplex, kde je jedna molekula navázána na druhou • zajímá nás, aby bylo navázání v aktivním místě receptoru • tím modifikujeme vlastnosti receptoru (aktivace či inhibice) Aplikace • vývoj léků • likvidace znečištění • cokoliv těžící z možnosti upravovat vlastnosti proteinů Jiří Filipovič Molekulový docking, mapování funkcí Případové studie o Molekulový docking o»oooooooooooooooooo Akcelerace mapování funkcí oooooooooooooo Molekulový docking z výpočetního hlediska Můžeme uvažovat „tvar" molekul, nebo jejich silová pole • my se budeme zabývat silovými poly Molekuly na sebe působí silou, hledáme komplex s nejnižsí potenciální energií • můžeme na mřížce předpočítat silové působení receptoru • následně můžeme hledat takové umístění ligandu, které má nejmenší energii vůči mřížce • tím redukujeme časovou složitost z 0{n ■ tri) na 0{m) pro receptor o velikosti n a ligand o velikosti m atomů (m << rí) My se budeme zabývat předpočítáním silového pole. □ - = = ^Q^O Jiří Filipovič Molekulový docking, mapování funkcí Případové studie Molekulový docking Akcelerace mapování funkcí 0 oosooooooooooooooooo oooooooooooooo Výpočet Coulombovského potenciálu Potenciál v konkrétním bodě mřížky je dán vztahem ^ 47re0e(rý)fy Kde e{r,j) je dielektrikum závislé na vzdálenosti a r,j je vzdálenost atomu od bodu mřížky. Potenciál klesá s druhou mocninou vzdálenosti - to je relativně pomalu, často se tedy počítá pro každý bod mřížky potenciál vůči všem atomům receptoru. Jiří Filipovič Molekulový docking, mapování funkcí Případové studie o Molekulový docking ooo»oooooooooooooooo Akcelerace mapování funkcí oooooooooooooo CUDA implementace Nejprve se budeme zabývat implementací s konstantním dielektrikem (tedy e(r) = k). 9 John E. Stone, James C. Phillips, Peter L. Freddolino, David J. Hardy, Leonardo G. Trabuco, Klaus Schulten. Accelerating molecular modeling applications with graphics processors. Journal of Computational Chemistry, Volume 28 Issue 16, 2008. Paralelizace • každá buňka může být zpracovávána nezávisle na ostatních Rychlostní omezení základního algoritmu • 9 aritmetických operací na jeden atom • informace o pozici buňky dány umístěním threadu • informace o atomech v 16 bytech (4 floaty - pozice a náboj) • při naivním pohledu jsme tedy omezeni rychlostí paměti □ g - = = -^c^O Jiří Filipovič Molekulový docking, mapování funkcí Případové studie o CUDA implementace Molekulový docking oooosooooooooooooooo Akcelerace mapování funkcí oooooooooooooo Omezení paměti • každý thread potřebuje přečíst 4 floaty popisující právě zpracovaný atom • v rámci warpu zpracovávají všechny thready současně stejný atom pro různé buňky • údaje o atomech slouží pouze ke čtení • ideální pro paměť konstant □ - = = ^Q^O Jiří Filipovič Molekulový docking, mapování funkcí Případové studie Molekulový docking Akcelerace mapování funkcí o ooooo»oooooooooooooo oooooooooooooo CUDA implementace Použijeme-li paměť konstant • máme zajištěný cacheovaný přístup • nevadí, že nás zajímají pouze 4 floaty • data se z globální paměti čtou nejvýše jednou projeden warp • redukuje nároky na propustnost paměti alespoň na 1/32 • počet atomů umístitelných do paměti konstant je omezen • pro více než 4096 atomů je třeba spouštět kernel vícekrát • doba spouštění je však pro takto dlouhý výpočet zanedbatelná □ - = = ^Q^O Jiří Filipovič Molekulový docking, mapování funkcí Případové studie Molekulový docking Akcelerace mapování funkcí o oooooo»ooooooooooooo oooooooooooooo První kernel loat curenergy = energygrid[outaddr] ; float coorx = gridspacing * xindex; float coory = gridspacing * yindex; float coorz = gridspacing * zindex; int atomid; float energyval =0.0f; for (atomid=0; atomid 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ů □ - = = ^Q^O Jiří Filipovič Molekulový docking, mapování funkcí Případové studie Molekulový docking Akcelerace mapování funkcí o oooooooooooooooooooo o»oooooooooooo 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 □ - = = ^Q^O Jiří Filipovič Molekulový docking, mapování funkcí Případové studie 0 Molekulový docking oooooooooooooooooooo Akcelerace mapování funkcí oo»ooooooooooo 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ézt ú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 □ - = = ^Q^O Jiří Filipovič Molekulový docking, mapování funkcí Případové studie Molekulový docking Akcelerace mapování funkcí 0 oooooooooooooooooooo ooosoooooooooo 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ů □ - = = ^Q^O Jiří Filipovič Molekulový docking, mapování funkcí Případové studie Molekulový docking Akcelerace mapování funkcí o oooooooooooooooooooo oooo»ooooooooo 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č Molekulový docking, mapování funkcí Případové studie Molekulový docking Akcelerace mapování funkcí 0 oooooooooooooooooooo ooooosoooooooo 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 □ - = = ^Q^O Jiří Filipovič Molekulový docking, mapování funkcí Jiří Filipovič Molekulový docking, mapování funkcí Případové studie o Molekulový docking oooooooooooooooooooo Někly lze optimalizovat specifické případy Akcelerace mapování funkcí ooooooo»oooooo 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 mod 4, respektive ; mod 4 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ě □ - = = ^Q^O Jiří Filipovič Molekulový docking, mapování funkcí Případové studie Molekulový docking Akcelerace mapování funkcí o oooooooooooooooooooo oooooooo»ooooo Granularita kernelů Jak implementovat komplexnější problémy řešené pomocí map • jednoduché mapované funkce jsou znovupoužitelné • mapování komplexní funkce lze pak řešit jako sérii mapování jednoduchých funkcí A je to efektivní? • kernel by měl dělat ideálně dost práce na to, aby výpočet překryl paměťové operace • u malých datových elementů problém s nízkým poměrem aritmetických operací k paměťovým Takže všechno do jednoho kernelu? • rozdílné paměťové nároky a para lei izovatelnost v rozdílných částech výpočtu degradují výkon □ - = = ^Q^O Jiří Filipovič Molekulový docking, mapování funkcí Případové studie 0 Molekulový docking oooooooooooooooooooo Akcelerace mapování funkcí ooooooooo»oooo Hledání efektivní granularity Hledání efektivního rozdělení práce do kernelů je složité • nelze plně předem odhadnout • manuální experimentování velmi složité • náchylné na chyby • příliš mnoho možností Dekom pozice-fúze • problém dekomponujeme do jednoduchých základních operací • základní operace implementujeme jako samostatné kernely • jednotlivé kernely následně můžeme fúzovat do větších □ g - = = -0*3.0 Jiří Filipovič Molekulový docking, mapování funkcí Případové studie Molekulový docking Akcelerace mapování funkcí o oooooooooooooooooooo oooooooooo»ooo Dekom pozice-fúze Výhody a omezení • implementované funkce jsou znovupoužitelné • menší náchylnost k chybám (fúze je relativně mechanická) • balancování bohatosti implementací funkcí a dosažitelného výkonu • stále velké množství rozdělení problému do kernelů Automatizace • fúze se tvoří docela mechanicky - automatizovatelná úloha □ - = = ^Q^O Jiří Filipovič Molekulový docking, mapování funkcí Jiří Filipovič Molekulový docking, mapování funkcí Případové studie o Molekulový docking oooooooooooooooooooo Akcelerace mapování funkcí oooooooooooo«o Generátor fúzí Základní schéma generátoru fúzí • problém zadefinován jako sekvence volání funkcí v jednoduchém imperativním jazyce • kód se přeloží do DAG zachycující předávání dat mezi funkcemi • nad grafem je vygenerován prostor fúzí a jejich implementací (linearizace, alokace paměti a použité varianty funkcí) • je provedena predikce výkonu každé implementace fůze • Je vygenerován kód fůzí a jejich volání • s nejlepším odhadem výkonu • pro několik nadějných s automatickým benchmarkingem □ - = = -0*3*0 Jiří Filipovič Molekulový docking, mapování funkcí Případové studie Molekulový docking Akcelerace mapování funkcí 0 OOOOOOOOOOOOOOOOOOOO 0000000000000» Ukázka odhadu výkonu Odhad výkonu a naměřené časy pro rovnici X = \\A-B ■ v\\2-(C ■ D + C) (1) fusions configuration predicted measured granularity { \\A-B-v\\2 } ■ { (C-D + C) } 8.683 ns 8.077 ns {3 3 1} {5 5 5} \\{A-B-v}\\2- {(C-D+C)} 9.165 ns 8.343 ns {3 3} 1 {5 5 5} \\A-B-v\\2- { (C-D + C) } 9.454 ns 8.967 ns 3 1 1 {5 5 5} { \\A.B.v\\2.{CD + C) } 9.869 ns 9.263 ns {3 3 1 5 5 5} no fusion 14.751ns 13.663 ns 3 115 5 5 Jiří Filipovič Molekulový docking, mapování funkcí