Název: Akcelerace genetického algoritmu s využitím OpenCL
Překlad názvu: Genetic Algorithm Acceleration Using OpenCL
Autoři: Hrušovský, Marek ; Šimek, Václav (oponent) ; Jaroš, Jiří (vedoucí práce)
Typ dokumentu: Diplomové práce
Rok: 2010
Jazyk: eng
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [eng] [cze]
Tato práce se zabývá problematikou urychlování genetických algoritmů a hned v úvodu nastiňuje možnosti využití genetických algoritmů v praxi. V první kapitole je detailně rozebrán princip fungování genetického algoritmu. Tato kapitola se dále zabývá možnostmi zákódování problému, který je použit pro běh genetického algoritmu. Konkrétně je vzpomenuto binární zakódování jedince, celočíselné zakódování jedince, neceločíselné zakódování jedince a permutační zakódování jedince. Pro každý typ zakódování jsou dále představeny genetické operátory mutace, křížení a selekce. Důraz je kladen na permutační genetické operátory OX a PMX. Další kapitola se zabývá možnostmi paralelizace genetického algoritmu. Další kapitola představuje nový standard jménem OpenCL, který umožňuje snadnou paralelizaci výpočtú s využitím různých typů procesorů v ten samý čas. OpenCL taktéž zjednodušuje programování pro grafické karty. Další kapitola navrhuje možnost, jak urychlit výpočet genetického algoritmu s využitím grafické karty a jazyka OpenCL. Pro urychlení byl zvolen permutační genetický algoritmus "problém N-dam", který je náročný na paměť grafické karty. Tato kapitola rozebírá technické specifikace grafické karty, které jsou nevyhnutelné k určení maximální velikosti šachovnice. V kapitole je analyzována správná práce s pamětí grafické karty, která je nevyhnutelná k dosažení urychlení zvoleného genetického algoritmu. Jsou zde taky nastíněny dva generátory náhodných čísel, které jsou součástí testů. Následující kapitola detailně popisuje fungování navržené paralelizace genetického algoritmu. Jsou zde porovnány dvě metody evaluace jedince a je popsán způsob testování a vyhodnocování výsledků. Předposlední kapitola porovnává časovou náročnost generátorů náhodných čísel. Bylo zjištěno, že generátor HybridTaus je o 20 rychlejší o proti generátoru XORshift na GPU. Na CPU byl naopak rychlejší generátor XORshift. Generátor XORshift je na GPU 20 krát rychlejší a generátor HybridTaus je dokonce až 80 krát rychlejší. Dále byly porovnány evaluační funkce. Bylo zjištěno, že GPU běh je 800 krát rychlejší oproti běhu na CPU. Paměťově náročná evaluační metoda byla schopná dosáhnout jenom dvojnásobné zrychlení. Kapitola dále porovnává funkce křížení. PMX dosáhlo zrychlení maximálně o 100 a i to v případech, které nejsou atraktivní pro řešení problému N-dam (N>20). V případe OX je možné dosáhnout zrychlení až o 1100. Také v tomto případě jsou atraktivní hodnoty pouze do 500. Testy, které vyhodnocují běh celého GA, ukázaly, že GPU verze je zhruba dvojnásobně rychlejší. Malé zrychlení bylo způsobeno operátorem selekce a funkcí křížení. This thesis tries to accelerate genetic algorithm (GA) using OpenCL standard. Acceleration is important for the industry that solves complex problems suitable for GA. The first part of the work contains theoretical background that is needed to understand the topic of parallelization GA and the OpenCL standard. The N-queens problem was chosen to demonstrate the capabilities of accelerating permutation genetic algorithm using the OpenCL standard. The designed model uses for acceleration two GPU cards. The last part of the work deals with benchmarking the parts that are important for GA. One random generator on the GPU is approximately 80 times faster than parallel version on the CPU. One evaluation method can be up to 8000 times faster on the GPU than on the CPU. The crossover functions did not obtain any significant speed-up. However, the parts are capable to obtain speed-ups but due to selection and crossover genetic algorithm operator the whole run of parallel GA on the GPU is maximally twice as fast as on the CPU.
Klíčová slova: Genetic algorithm; GPU; HybridTaus Random Generator; N-Queens Problem; NVIDIA GTX285; OpenCL; OpenMP; OX; Parallel Genetic Algorithm; Permutation Crossover; PMX; Threads.; XORshift Random Generator; generátor náhodných čísel HybridTaus; generátor náhodných čísel XORshift; Genetický algoritmus; GPU; NVIDIA GTX285; OpenCL; OpenMP; OX; Paralelní genetický algoritmus; Permutační křížení; PMX; Problém N-dam; vlákna.

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/54389

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-237246


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Vysoké učení technické v Brně
Vysokoškolské kvalifikační práce > Diplomové práce