Název:
Paralelizace ultrazvukových simulací pomocí 2D dekompozice
Překlad názvu:
Parallelization of Ultrasound Simulations Using 2D Decomposition
Autoři:
Nikl, Vojtěch ; Dvořák, Václav (oponent) ; Jaroš, Jiří (vedoucí práce) Typ dokumentu: Diplomové práce
Rok:
2014
Jazyk:
cze
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [cze][eng]
Tato práce je součástí projektu k-Wave, což je simulační nástroj akustické tomografie sloužící k simulaci a rekonstrukci akustických vlnových polí a jeho hlavním přínosem je plánování ultrazvukových operací lidské tkáně, např. nádoru na mozku. Dopředné simulace jsou založeny na řešení k-prostorové pseudospektrální časové domény. Simulace jsou časově a výpočetně velice náročné. Simulace probíhají na 3D maticích, které reprezentují určité vlastnosti reálné tkáně, např. hustotu absorbce nebo rychlost šíření zvuku. K výpočtu gradientu se používá Rychlá Fourierova transformace (dále jen FFT), jejíž výpočet zabere zhruba 60% simulačního času. 3D FFT byla do této doby počítána pomocí softwarové knihovny FFTW, která interně využívá 1D dekompozici, tj. dekompozici podél jedné osy. Hlavní nevýhoda 1D dekompozice je relativně malý maximální počet výpočetních jader, přes které lze paralelizovat výpočet. Matice mají velikost řádově 1024x2048x3072, tím pádem lze efektivně paralelizovat přes maximálně 1024 jader. Dnešní superpočítače umožnují využít až stovky tisíc jader a tomu bychom se rádi přiblížili. Řešením je využití 2D dekompozice, která by teoretický maximální počet jader posunula až do řádu milionů. Její efektivní implementací se zabývá právě tato práce. 2D dekompozice je obecně paralelizována pouze pomocí MPI procesů, např. v~knihovnách PFFT nebo P3DFFT, v této práci ale využíváme pokročilejší kombinace MPI procesů a OpenMP vláken, kterou jsme nazvali hybridní 2D dekompozice (HybridFFT). Má tři hlavní části: výpočet 1D FFTs, lokální transpozice dat a globální transpozice dat. Pro výpočet sérií 1D FFT je využita knihovna FFTW.Lokální transpozice jsou implementovány pomocí blokové transpozice 2D matice, která je vektorizována pomocí SSE/AVX instrukcí. Jak 1D FFT, tak lokální lokální transpozice, jsou akcelerovány pomocí OpenMP vláken. Globální transpozice je opět implementována prostřednictvím knihovny FFTW, která při použití pokročilého plánování dokáže výrazně snížit dobu potřebnou pro její realizaci. Hlavním cílem této práce je tedy dosáhnout maximálního možného zrychlení a škálovatelnosti oproti předchozímu řešení, zároveň ale i zachovat kompatibilitu a přenositelnost. Hybridní transformace pracuje nejlépe, pokud na jednom socketu spustíme jeden MPI proces a v rámci tohoto socketu využijeme tolik vláken, kolik máme k dispozici jader. Díky tomu nemusí jádra v rámci jednoho socketu komunikovat přes MPI zprávy, ale využívají rychlejší sdílenou paměť, a zároveň je MPI komunikace efektivnější, protože máme pouze jeden MPI proces na socket a tím pádem jsou MPI zprávy vetší a je jich méně, což vede k menšímu zahlcení propojovací sítě a lepší efektivitě komunikace. Řešení bylo testováno na superpočítačích Anselm (Ostrava), Zapat (Brno) a Supernova (Wroclaw). Pro nižší počty jader, v řádu několika set, je výkon přibližně stejný nebo o pár procent lepší, než původně použitá 1D dekompozice FFTW knihovny nebo knihony PFFT a P3DFFT. Jeden z velmi dobrých výsledků je např. 512^3 FFT na 512 jádrech, kde hybridní dekompozice dosáhla času 31 ms, zatímco FFTW 39 ms a PFFT 44ms. Na stroji Anselm jsme spustili výpočet až na 2048 jádrech a škálovatelnost byla stále lineární. Nejlepší nárust výkonu oproti ostatním knihovnám by se měl projevit při počtu zhruba 8-16 tisíc jader pro kostky velikosti 1024^3, protože v této konfiguraci bude mít jeden MPI proces na starosti jednu desku matice a zároveň budou MPI zprávy dostatečně velké a v takovém počtu, že by se měla projevit lepší efektivita komunikace oproti ostatním knihovnám.
This thesis is a part of the k-Wave project, which is a toolbox for the simulation and reconstruction of acoustic wave felds and one of its main contributions is the planning of focused ultrasound surgeries (HIFU). One simulation can take tens of hours and about 60% of the simulation time is taken by the calculation of the 3D Fast Fourier transforms. Up until now the 3D FFT has been calculated purely by the FFTW library and its 1D decomposition, whose major limitation is the maximum number of employable cores. Therefore we introduce a new approach, called the 2D hybrid decomposition of the 3D FFT (HybridFFT), where we combine both MPI processes and OpenMP threads to reach as best performance as possible. On a low number of cores, on the order of a few hundreds, we are about as fast or slightly faster than FFTW and pure MPI 2D decomposition libraries (PFFT and P3DFFT). One of the best results was achieved on a 512^3FFT using 512 cores, where our hybrid version run 31ms, FFTW run 39ms and PFFT run 44ms. The most significant performance advantage should be seen when employing around 8-16 thousand cores, however we haven't had an access to a machine with such resources. Almost a linear scalability has been proven for up to 2048 employed cores.
Klíčová slova:
AVX; cluster; dekompozice; FFT; FFTW; k-Wave; MPI; OpenMP; OpenMPI; optimalizace; Rychlá Fourierova transformace; SSE; superpočítač; transpozice; vlákna; AVX; cluster; decomposition; fast Fourier transform; FFT; FFTW; k-Wave; MPI; OpenMP; OpenMPI; optimization; SSE; supercomputer; threads; transposition
Instituce: Vysoké učení technické v Brně
(web)
Informace o dostupnosti dokumentu:
Plný text je dostupný v Digitální knihovně VUT. Původní záznam: http://hdl.handle.net/11012/188799
host ::
