1/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Obecnější aplikované úvahy o paralelizaci Petr Holub hopet@ics.muni.cz Laboratoř pokročilých síťových technologií PV197 2012–11–05 2/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Motivace SIMD modely paralelního programování jsou tu od 60. let paměťové hierarchie jsou tu od vzniku paralelních počítačů CUDA je v podstatě variace na SIMD model s konkrétním paměťovým modelem a omezenými možnostmi synchronizace 3/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Motivace 4/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Motivace 5/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Literatura Mattson T. G., Sanders B. A., Massingill B. L., Patterns for Parallel Programming Addison-Weslay 2004. Perrin G.-R., Darte A., The Data Parallel Programming Model: Foundations, HPF Realization and Scientific Applications, Lecture Notes in Computer Science, Springer 1996. 6/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Literatura Park I. K., Singhal N., Lee M. H., Cho S., Kim C. W., “Design and Performance of Evaluation of Image Processing Algorithms on GPUs,” IEEE Transactions on Parallel and Distributed Systems, vol. 22, no. 1, pp. 91-104, January 2011. Cope B., Cheung P. Y. K., Luk W., Howes L., “Performance Comparison of Graphics Processors to Reconfigurable Logic: A Case Study”, IEEE Transactions on Copmuters, vol. 59, no. 4, April 2010 Best Practices Guide – CUDA 2.2, 2009 http://developer. download.nvidia.com/compute/cuda/2_3/toolkit/ docs/NVIDIA_CUDA_BestPracticesGuide_2.3.pdf Wil Braithwaite, “The CUDA architecture: The Art of performance optimization”, Siggraph 2009, http: //developer.download.nvidia.com/presentations/ 2009/SIGGRAPH/asia/6_cuda_optimization.pdf 7/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Přehled přednášky Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu 8/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Paralelismus v návrhu 9/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Příklady – Pozitronová emisní tomografie (EX-PET) Distribuce radioaktivního materiálu v lidském těle ◾ vyšetření postupu metabolismu, např. pro onkologická vyšetření ◾ rozptyl záření při průchodu tkáněmi ⇒ nízké rozlišení obrazu ◾ absorpce záření není v organismu homogenní ⇒ absolutní hodnoty nejsou užitečné 10/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Příklady – Pozitronová emisní tomografie (EX-PET) Zdroj: http://en.wikipedia.org/wiki/File:PET-schema.png 11/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Příklady – Pozitronová emisní tomografie (EX-PET) Zdroj: http://en.wikipedia.org/wiki/File:Viewer_medecine_nucleaire_keosys.JPG 12/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Příklady – Pozitronová emisní tomografie (EX-PET) Model těla ◾ rozsáhlý model popisující jednotlivé tkáně ◾ absorbční koeficienty pro jednotlivé „buňky“ modelu Simulace průchodu záření lidským tělem ◾ Monte Carlo raytracing ◾ náhodně zvolené body v lidském těle emitují záření (obvykle γ) ◾ sledují se rozptyl a absorpce paprsku ◾ zajímají nás paprsky dopadající na detektor Možnosti paralelizace ◾ po paprscích ⇒ dekompozice na úlohy ◾ po buňkách ⇒ dekompozice na data 13/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Příklady – Lineární algebra (EX-LA) Násobení matic a vektorů C = A ⋅ B Cij = N ∑ k=1 AikBkj ◾ O(N) násobení a O(N − 1) sčítání pro každý prvek ⇒ O(N3 ) operací ◾ existují efektivnější algoritmy Možnosti paralelizace ◾ pro jednotlivé výsledné buňky ⇒ dekompozice na úlohy ◾ pro jednotlivé oblasti zdrojových matic ⇒ dekompozice na data 14/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Příklady – Molekulová dynamika (EX-MD) Problém modelování velkých molekul per se ◾ neznáme přesné analytické řešení (dál než pro H+ 2 ) ◾ lepší aproximativní modely kvantové mechaniky škálují O(N5 ) – O(N!) Molekulová mechanika ◾ model pružinek, oscilátorů a elektrostatických potenciálů ◾ problém parametrizace ◾ problém chemické reaktivity (vznik/zánik vazeb, složitější interakce) ◾ teoreticky „vadné“ ◾ prakticky používané Problém modelování v čase ◾ interakce molekul v čase ◾ konformační chování, např. při interakci léčivo–biomolekula 15/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Příklady – Molekulová dynamika (EX-MD) Zdroj: http://en.wikipedia.org/wiki/File:MM_PEF.png 16/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Příklady – Molekulová dynamika (EX-MD) Mechanismus výpočtu 1 N : constant Positive; 3 atoms : array ( 1 .. 3, N) of Real; -- positions velocities : array ( 1 .. 3, N) of Real; 5 forces : array ( 1 .. 3, N) of Real; neighbors : array (N) of List_of_Atoms; 7 loop over time steps 9 vibrational_forces (in atoms, in out forces); rotational_forces (in atoms, in out forces); 11 neighbor_list (in atoms, out neighbors); non_bonded_forces (in atoms, in neighbors, in out forces); 13 update_atom_position_and_velocities (in out atoms, in out velocities, in forces); 15 physical_properties (in atoms, in velocities, in forces); end loop; 17/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Příklady – Molekulová dynamika (EX-MD) Problém N těles (N-body problem) ◾ teoreticky všechna tělesa interagují se všemi ⇒ N2 interakcí ◾ problém při výpočtu non_bonded_forces() ◾ řešení pomocí cut-off metody pod definovanou vzdálenost se interakce ignoruje funguje dobře pouze pro interakce 1/r2 Možnosti paralelizace ◾ jak na úlohy, tak na data 18/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Dekompozice na úlohy Pohled: dekompozice na úlohy, které mohou běžet paralelně Aspekty: ◾ flexibilita – přenositelnost na různé platformy parametrizace velikosti úloh vzhledem k počtu výpočetních jednotek a jejich architektuře (např. paměťovým modelům) ◾ efektivita – schopnost využití paralelismu vs. jeho režie rozumný poměr mezi režií úlohy (vlákna, procesu) a délkou výpočtu dostatečný počet úloh ◾ jednoduchost – ladění, udržování kódu přenos úloh ze sekvenčního prostředí (přístup OpenMP) Řešení ◾ rozdělení na úlohy s minimálními závislostmi/synchronizací ◾ rovnoměrné rozdělení úloh mezi výpočetní jednotky (load-balancing) ◾ snažit se najít co nejvíce paralelních úloh, spojit se dají později ◾ příklady: volání funkcí nezávislé smyčky dekompozice dat pro jednotlivé úlohy 19/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Dekompozice na úlohy – EX-PET Potřebujeme vygenerovat až ∼ 106 trajektorií Přiřadíme každou trajektorii jedné úloze Data ◾ informace o trajektorii (read-write) ◾ model těla (read-only) Vlastnosti + velké množství úloh + jednoduché, přímočaré na ladění a údržbu − potřeba kopírovat model těla, který může být velmi rozsáhlý − problém malého počtu výpočetních operací v porovnáním s množstím dat potřebných z paměti ◾ vhodné na architektury, kde výpočetní jednotky mají velkou a rychlou paměť (příp. i sdílenou na čtení) 20/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Dekompozice na úlohy – EX-LA Přiřadíme každou buňku Data ◾ jeden řádek a jeden sloupec z matic Vlastnosti + velké množství úloh + jednoduché, přímočaré na ladění a údržbu − problém špatného komplikovaného přístupu ke sloupcům matici lze transponovat Možnost seskupení úloh ◾ opakované využití oblastí paměti ◾ vede spíše na dekompozici podle dat 21/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Dekompozice na úlohy – EX-MD Informace o problému ◾ neighbor_list() ...trvá dlouho za předpokladu dostatečně husté simulace v časové doméně nemusíme počítat v každém kroku ◾ physical_properties() ...rychlé ◾ non_bonded_forces() SIMD smyčka – pro konkrétní atom počítáme příspěvek síly od jednotlivých započítávaných sousedů samotný jeden výpočet je jednoduchý může zahrnovat všechny atomy ◾ vibrational_forces(), rotational_forces() má smysl paralelizovat per atom 22/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Dekompozice na data Pohled: dekompozice na data, která mohou být zpracovávána paralelně ... v případě CUDA navíc i v režimu SIMD Aspekty: ◾ flexibilita možnost různé granularity dělení dat ◾ efektivita problém závislostí mezi bloky dat při různé granularitě dělení ⇒ řešení závislostí by nemělo škálovat rychleji než výpočet ⇒ řešení závislostí by nemělo trvat déle než výpočet problém vyvažování zátěže na výpočetních jednotkách SIMD/SIMT: lze pro danou dekompozici provést výpočet stejnými operacemi, nebo bude výpočet divergovat? ◾ jednoduchost datová dekompozice vede často na velmi zapeklité závislosti Řešení: ◾ rozdělení polí – např. geometrické dekompozice ◾ rekurzivní datové struktury ◾ optimalizace vzhledem k použitému paměťovému modelu 23/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Dekompozice na data – EX-PET Rozdělení modelu těla na segmenty ◾ počet segmentů ∼ počtu výpočetních jednotek ◾ každá jednotka má svoji část modelu v blízké paměti Výpočet ◾ každá výpočetní jednotka počítá trajektorii a absorpci ve svém segmentu ◾ musí určit, které další výpočetní jednotce předat výpočet ◾ problém balancování využití jednotek v případě absence práce může vygenerovat novou náhodnou emisi Vlastnosti + efektivní práce s pamětí − musí řešit předávání trajektorie mezi výpočetními jednotkami 24/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Dekompozice na data – EX-LA Rozdělení na bloky řádků matice C ◾ využití segmentu matice A jednou ◾ opakované využití celé matice B Rozdělení na bloky (podmatice) matice C ◾ dosažení jemnější granularity Vlastnosti + granularizovatelná paralelizace + možnost dostatečně malých podoblastí, které se vejdou do cache/rychlé paměti − musí správně vybírat data po sloupcích možnost transpozice matice B Reálné implementace ◾ ScaLAPACK – dělení na bloky ◾ PLAPACK y = Ax 1. rozdělí vektory y a x 2. odvodí rozdělení A 25/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Dekompozice na data – EX-MD atoms : array ( 1 .. 3, N) of Real; -- positions 2 velocities : array ( 1 .. 3, N) of Real; forces : array ( 1 .. 3, N) of Real; 4 neighbors : array (N) of List_of_Atoms; 6 loop over time steps vibrational_forces (in atoms, in out forces); 8 rotational_forces (in atoms, in out forces); neighbor_list (in atoms, out neighbors); 10 non_bonded_forces (in atoms, in neighbors, in out forces); update_atom_position_and_velocities (in out atoms, 12 in out velocities, in forces); physical_properties (in atoms, in velocities, in forces); 14 end loop; Samostatná datová dekompozice není přímočará ◾ lépe je využít rozpad datových struktur podle úloh ◾ polohy atomů – jsou potřeba všude ◾ rychlosti atomů – pouze u aktualizace ◾ síly – lze počítat lokálně a následně sčítat Symetrie v datech ◾ fij = −fji ... třetí Newtonův zákon ◾ snížení množství dat na polovinu 26/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Dekompozice na data – EX-MD Využívání symetrie molekul ◾ nalezení grupy symetrie Zdroj: http://en.wikibooks.org/wiki/Introduction_to_Mathematical_ Physics/N_body_problem_in_quantum_mechanics/Molecules 27/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Dekompozice na data – EX-MD Využívání symetrie molekul ◾ nalezení grupy symetrie Zdroj: http://chemistry.ncssm.edu/labs/molgeom/pointsym.jpg 28/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Seskupování úloh Hledání struktur/hierarchie v úlohách ◾ skupiny úloh zjednodušují plánování a snižují chybovost ◾ časové struktury/synchronizace striktní souslednost pipelining současný běh – ko-plánování zcela nezávislé úlohy ◾ závislosti mezi úlohami (možnost vyvažování zátěže výpočetních jednotek) Postupy ◾ hierarchie dekompozice ◾ sdílení omezení mezi úlohami ◾ slučování skupin: větší skupiny vedou na efektivnější plánování EX-LA ◾ seskupování do bloků ◾ skládání výsledné matice 29/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Seskupování úloh – EX-MD Seskupování podle činností ◾ výpočet sousedů ◾ aktualizace působících sil výpočty vibračních sil výpočty rotačních výpočet nevazebných interakcí ◾ aktualizace poloh a rychlostí ◾ výpočet vlastností 30/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Pořadí úloh Jaké jsou závislosti mezi úlohami? ◾ časové závislosti ◾ datové závislosti Přístupy ◾ minimální nutná omezení – nevynucovat uspořádání, kde to není třeba ◾ čekání na potřebná data ◾ čekání na dokončení potřebných I/O operací ◾ vyjádření nezávislosti z důvodu bezpečnosti a udržovatelnosti vyjadřovat explicitně 31/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Řazení úloh – EX-MD nevazebné síly potřebují znát započítávané sousedy pozice atomů se mohou aktualizovat až jsou vypočítané síly výpočet vlastností potřebuje pozice atomů a jejich rychlosti 32/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Sdílení dat Definování přístupu k datům u souběžných jednotek ◾ lokální data ◾ globální data ◾ vyměňovaná data mezi úlohami např. okrajové buňky u konečné diferenční metody ◾ relaxování přístupu ke globálním datům ne vždy je třeba globální synchronizace vytváření lokálních kopií a jejich synchronizace minimalizace překryvů přestrukturováním úloh ◾ pipelining – paralelizace výpočtu a synchronizace/komunikace 33/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Sdílení dat Způsoby přístupu ◾ jen na čtení možno cacheovat/replikovat ◾ efektivně lokální přístup na čtení i zápis jen k disjunktnímu bloku dat možnost pozdější redukce složitější výběr prvků ◾ na čtení i zápis přístup do globální paměti vs. distribuce aktualizací 34/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Sdílení dat Způsoby přístupu ◾ akumulace/redukce paralelizace asociativních operací implementace pro CUDA: http://developer.download.nvidia.com/compute/cuda/ 1_1/Website/projects/reduction/doc/reduction.pdf ◾ jeden zapisuje, ostatní čtou lokální kopie pro zapisujícího s distribucí čtoucím 35/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Sdílení dat – EX-MD možnost pravidelné replikace pozic atomů použití paralelních redukcí při sčítání sil průběžný výpočet sousedů s periodickým přenosem do výpočtu nevazebných sil 36/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Analýza návrhu Zpětná analýza návrhu ◾ poslední krok samotného návrhu ... neobjevovat chyby návrhu až hluboko v implementace ◾ máme: dekompozice podle úloh dekompozice podle dat analýzu struktury dekompozice Úvahy ◾ Je návrh vhodný pro cílovou platformu? (CUDA) máme dost paralelní práce pro všechny multiprocesory? nebudou nám výpočetní stromy divergovat pro SIMD/SIMT? máme dobře namapované úlohy na mřížku? využívá úloha dobře paměťové hierarchie (registry/lokální paměť/globální paměť/cachování read-only dat, zarovnávané adresování, konflikty)? umíme pipeliningem (pomocí spouštění jiných warpů) maskovat latenci pamětí a synchronizaci? máme pro to dost vláken? ◾ Je návrh stabilní, laditelný a udržitelný? řeší dobře hraniční případy? (např. vysoce asymetrické matice) 37/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Analýza návrhu – EX-LA minulá přednáška: Poučení: ◾ blokovou paralelizací jsme dosáhli největšího zrychlení 38/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Analýza návrhu – EX-PET Umíme dekomponovat na segmenty modelu + škáluje na téměř neomezený počet výpočetních jednotek − problém s předáváním stop Umíme dekomponovat na jednotlivé stopy + škáluje na téměř neomezený počet výpočetních jednotek − přístup k rozsáhlému modelu ◾ eventuální částečné zavedení lokality ◾ intuitivnější 39/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Analýza návrhu – EX-MD Umíme dekomponovat podle jednotlivých atomů podle příspěvků sil ◾ pro menší počty procesorů můžeme shlukovat úlohy Počítání nevazebných interakcí bere většinu času ◾ umíme zmenšit díky symetriím ◾ owner-computes filter – rozdělení, kdo v dané iteraci počítá a kdo lelkuje ◾ můžeme hledat efektivnější algoritmy na cut-off ◾ ... námět na další přednášku :-) 40/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Volba vzorů 41/57 Paralelismus v návrhu Modelové příklady Dekompozice problému Analýza závislostí Analýza návrhu Vzory v paralelismu Paralelismus úloh Dekompozice podle úloh ◾ potřeba vygenerovat dostatečné množství úloh Řešení závislostí: ◾ odstranitelné závislosti int ii=0, jj=0; 2 for (int i=0; i