|
|
Distributed Ray Tracing v rozumném čase
Slovák, Radek ; Polok, Lukáš (oponent) ; Herout, Adam (vedoucí práce)
Práce se zabývá zobrazovací metodou distribuovaného sledování paprsku se zaměřením na optimalizace této metody. Metoda poskytuje generování velmi kvalitních a částečně realistických obrazů pomocí simulace některých vlastností světla distribucí světelných paprsků. Daní za realističnost některých efektů je i v dnešní době vysoká výpočetní náročnost. Práce rozebírá teorii a problematiku s tím spojenou. Velký prostor je pak věnovaný optimalizacím této metody jako je hledání nejbližšího průsečíku pomocí kd-stromu, kvazi náhodné generování vzorků s rychlejší konvergencí, použití instrukční sady SSE a rychlý průsečík paprsku s trojúhelníkem. Tyto optimalizace přinesly značné urychlení. V rámci práce jsou diskutované metody naimplementovány. Při implementaci se klade také důraz na praktickou použitelnost zahrnující generování pokročilejších animací a univerzální popis objektů.
|
|
|
Ray-tracing s využitím SSE
Skoták, Jakub ; Švub, Miroslav (oponent) ; Havel, Jiří (vedoucí práce)
Metoda Ray-tracingu je jedna z realistických metod počítačové visualizace. Tato metoda je vysoce výpočetně náročná a neexistuje pro ni hardwarový akcelerátor. Tato práce popisuje urychlení ray tracingu za použití instrukčního souboru SSE.
|
|
| |
|
|
Ray-tracing s využitím SSE
Kučera, Jiří ; Herout, Adam (oponent) ; Havel, Jiří (vedoucí práce)
Tato práce se zabývá využitím SSE instrukcí k akceleraci výpočtů probíhajících při ray-tracingu. Aby bylo možné SSE instrukce co nejefektivněji použít, bylo zvoleno současné sledování čtyř paprsků uzavřených v jednom svazku. Byla provedena vektorizace algoritmů použitých v ray-tracingu a také bylo navrženo a implementováno řešení rozpadu svazku paprsků. Provedenými testy pak byla sledována doba renderování obrazu pro případ, kdy jsou všechny paprsky pohromadě, ale také pro případ, kdy se ve svazku nachází pouze jeden paprsek.
|
|
|
Knihovna operací nad konečnými automaty
Bartůněk, Petr ; Puš, Viktor (oponent) ; Kaštil, Jan (vedoucí práce)
Tato práce se zabývá dvěma základními operacemi nad konečnými automaty. Determinizací nedeterministických konečných automatů a minimalizací deterministických konečných automatů. Pro obě tyto operace jsem navrhoval sekvenční algoritmy, které jsou paralelizovatelné. Zabývám se hledáním zrychlení především pomocí SSE instrukcí nebo pomocí knihovny openMP. Trendem dnešní doby je především zvyšování počtu procesorů, proto budu navrhovat paralelní algoritmy pro více procesorů. Při hledání optimálního řešení budu zkoumat další možnosti, jak dosáhnout zrychlení, např. efektivním uložením datových struktur v paměti.
|
|
| |
|
|
Paralelizace ultrazvukových simulací pomocí 2D dekompozice
Nikl, Vojtěch ; Dvořák, Václav (oponent) ; Jaroš, Jiří (vedoucí práce)
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.
|
|
|
Akcelerace vektorových a krytografických operací na platformě x86-64
Šlenker, Samuel ; Martinásek, Zdeněk (oponent) ; Balík, Miroslav (vedoucí práce)
Cieľom práce bolo naštudovať a následne spracovať porovnanie starších a novších vektorových výpočtových jednotiek moderných mikroprocesorov na platforme x86-64. Práca mala poskytnúť prehľad najrýchlejších výpočtov vektorových operácií s maticami a vektormi spolu s príslušnými zdrojovými kódmi. Ďalej bola jej zameraním oblasť autentizovaného šifrovania, konkrétne blokovej šifry AES pracujúcej v operačnom móde Galois Counter Mode a pojednanie o možnostiach inštrukčných sád pre podporu kryptografie.
|
|
|
Decompilation of Specialized and Advanced Instruction Sets
Holub, Juraj ; Kolář, Dušan (oponent) ; Křivka, Zbyněk (vedoucí práce)
Nowadays, the process of analyzing malicious software is an important part of information technologies. One of the crucial techniques is decompilation of malicious binary programs. The decompilation is a complex process, and there are multiple projects with such a goal. The project RetDec aims to develop retargetable and flexible decompiler. The goal of this research is to improve the decompilation of advanced instruction sets for architecture x86. The new optimization for FPU register stack manipulation is designed, and the support of FPU and SSE instruction set translation is extended. The new extensions are implemented and tested in the manner of decompilation efficiency and quality.
|
|
|
Paralelizace ultrazvukových simulací pomocí 2D dekompozice
Nikl, Vojtěch ; Dvořák, Václav (oponent) ; Jaroš, Jiří (vedoucí práce)
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.
|
host ::
RSS.