|
|
The Parallel Genetic Algorithm for Multicore Systems
Vrábel, Lukáš ; Šimek, Václav (oponent) ; Jaroš, Jiří (vedoucí práce)
Genetic algorithm is a powerful optimization and search method successfully used in practice to solve many different problems. Underlying concept is based on the evolutionary mechanics observed in nature. As the GAs are computationaly intense applications, it is natural that there are many efficient methods for parallelization of these algorithms. However, most of these methods deal with supercomputers or large computer clusters with specialized hardware, as these were the most common parallel architectures in the past. With modern-day computers the trend in personal computer design is also moving towards parallel architectures bringing small and cheap parallel multicore processors. That's why it is imperative to have efficient methods to exploit capabilities of this system. This document presents prototypes of new methods of parallel genetic algorithms designed especially for these multiprocessor computers with shared memory.
|
|
|
Efektivní implementace genetického algoritmu s využitím vícejádrových CPU
Kouřil, Miroslav ; Žaloudek, Luděk (oponent) ; Jaroš, Jiří (vedoucí práce)
Tato práce se zabývá akcelerací pokročilého genetického algoritmu. Pro implementaci byly zvoleny diskrétní i spojitá varianta genetického algoritmu typu UMDA. Hlavní částí akcelerace bylo využití SSE sady. Pomocí této sady byly zrychleny zejména funkce pro výpočet fitness a vzorkování nové populace. Dále byl implementován pseudonáhodný generátor čísel, který také pracuje s SSE sadou. Po této implementaci dosáhla diskrétní varianta algoritmu zrychlení 4,6. Na závěr byly algoritmy upraveny pro využití systému OpenMP, který umožňuje spouštění bloků programu ve více vláknech. Ukázalo se, že pro paralelní zpracování se příliš nehodí spojitá verze algoritmu, neboť její činnost je relativně jednoduchá. Oproti tomu diskrétní verze algoritmu jsou pro paralelizaci velmi vhodné, implementované verze dosáhly celkového zrychlení 4,9 a 7,2.
|
|
|
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.
|
|
|
Využití GPU pro akceleraci optimalizace systému vodních děl
Marek, Jan ; Petrlík, Jiří (oponent) ; Jaroš, Jiří (vedoucí práce)
Tato práce se zabývá optimalizací řízení zásobní funkce vodohospodářských soustav. Vycházíme z dizertační práce Ing. Pavla Menšíka Ph.D., Automatizace řešení zásobní funkce vodohospodářské soustavy. Jako optimalizační metoda byla zvolena diferenciální evoluce. Daná metoda bude implmentována sekvečne a poté paralelizována nejdříve na procesoru a poté na GPU
|
|
| |
|
|
Paralelizace ultrazvukových simulací s využitím lokální Fourierovy dekompozice
Dohnal, Matěj ; Hrbáček, Radek (oponent) ; Jaroš, Jiří (vedoucí práce)
Tato práce přináší návrh nové metody pro distribuovaný výpočet 3D Fourierovy transformace s využitím lokální 3D dekompozice domény, popis její implementace a srovnání s dosud běžně používanou metodou globální 1D dekompozice domény. Nová metoda byla navržena, implementována a testována především pro budoucí použití v simulačním programu k-Wave, ale nic nebrání jejímu použití v jiných aplikacích. Implementace prokázala svoji efektivitu na superpočítači Anselm při testování na až 2048 jádrech, kde je až 3krát rychlejší než globální 1D dekompozice za cenu nepřesnosti výpočtu v řádu 10-5, neboť se podařilo významně snížit režii výpočtu v podobě komunikace mezi procesy. Na konci práce je diskutováno, jak lze s metodou výpočtu Fourierovy transformace využívající lokální dekompozici domén dosáhnout co nejlepších výsledků z hlediska přesnosti i rychlosti výpočtu, zároveň jsou zmíněny i její limity.
|
|
|
Paralelizace faktorizace celých čísel z pohledu lámání RSA
Breitenbacher, Dominik ; Henzl, Martin (oponent) ; Homoliak, Ivan (vedoucí práce)
Práce se zabývá faktorizací celých čísel. Faktorizace je nejznámější a nejpoužívanější metodou kryptoanalýzy RSA. V rámci této práce byla vybrána a implementována faktorizační metoda zvaná SIQS. I když se jedná o nejrychlejší metodu (do 100 dekadických číslic), není možné ji efektivně počítat v polynomiálním čase, a tak se hledají různé možnosti, jak tuto metodu co nejvíce urychlit. Jako první se nabízí paralelizace. K tomuto účelu bylo využito OpenMP. Další možností je optimalizace kódu. Cílem této práce je také ukázat, jak jednoduše lze v mnoha případech využít paralelizace kódu a dále, jak díky podrobné analýze kódu lze dosáhnout poměrně velkého urychlení. Použitá metodika iteračního provádění optimalizací se ukázala jako velmi účinná. Touto metodikou byla implementace SIQS vylepšena tak, že faktorizace byla urychlena až 100-krát, v některých částech kódu dokonce ještě více.
|
|
|
Techniky paralelního zpracování výpočtů
Vodák, René ; Hasmanda, Martin (oponent) ; Lattenberg, Ivo (vedoucí práce)
Práce pojednává o technikách paralelního zpracování výpočtů. Je proveden rozbor nejvýznamnějších knihoven pro paralelizaci včetně knihoven pro paralelizaci na GPU v grafických kartách a provedeno porovnáním rychlostí výpočtu těchto knihoven ve Visual Studiu 2010 na základě jednoduché aplikace hledající prvočísla na třech různých hardwarových počítačových sestavách. S pomocí knihovny OpenCL, která dosáhla nejlepšího výsledku, jsou vytvořeny dvě aplikace - program pro zdokonalené vyhledávání prvočísel pomocí Eratosthenova síta a program pro výpočet integrálu funkce lichoběžníkovou metodou.
|
|
|
Aplikace využívající paralelní zpracování pro kryptografické výpočty
Šánek, Jaromír ; Martinásek, Zdeněk (oponent) ; Hajný, Jan (vedoucí práce)
Tato práce se zabývá paralelním programováním a modulárním mocněním. Vprvní části je srovnána rychlost funkcí modulárního mocnění zrůzných knihoven C/C++ na CPU. V druhé části se práce zabývá technologií CUDA, je zde změřena rychlost funkce modulárního mocnění zupravené knihovny LibTomMath pro technologii CUDA na GPU a porovnána srychlostí stejné funkce běžící na CPU. Poslední část je věnována implementaci aplikací „Klient –Server“ pro výpočet revokační funkce protokolu HM12.
|
|
|
Možnosti realizace paralelně zpracovávaných úloh v programovacích jazycích
Zejda, Václav ; Ondroušek, Vít (oponent) ; Houška, Pavel (vedoucí práce)
Tato práce se zabývá problematikou realizace paralelně zpracovávaných úloh v různých programovacích prostředích. První část je věnována obecnému úvodu do paralelizace. Uvádí zejména kdy se vyplatí paralelizovat, jaké typy paralelizace se používají a rozdíly v použité architektuře. V dalších částech jsou již popsány jednotlivé způsoby a prostředky používané pro tvorbu aplikací s podporou paralelismu. Od doplňků pro klasické programovací rozhranní (C/C++, .NET), přes tvorbu aplikací v grafických vývojových prostředích až po rozhranní využívající vedle procesoru počítače (CPU) i procesory grafických karet (GPU).
|
host ::
RSS.