Original title: Akcelerace genetického algoritmu s využitím GPU
Translated title: The GPU-Based Acceleration of the Genetic Algorithm
Authors: Pospíchal, Petr ; Šimek, Václav (referee) ; Jaroš, Jiří (advisor)
Document type: Master’s theses
Year: 2009
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Tento text představuje diplomovou práci se zaměřením na akceleraci Genetických algoritmů s použitím grafických čipů. První část popisuje Genetické algoritmy a s ním související populaci, chromozom, křížení, mutaci a selekci. Další část je věnována možnostem využití grafických karet jako prostředku pro obecné výpočty, kde jsou popsány jak možnosti programovatelné grafické pipeline s použitím DirectX/OpenGL a Cg, tak specializované knihovny pro GPGPU se zaměřením na architekturu CUDA. Další kapitola se zaměřuje na návrh implementace s použitím GPU, popsány jsou PGA modely a dílčí problémy, jako jsou rychlé řazení a generování náhodných čísel. Následují detaily implementace -- migrace, křížení a selekce mapovaná na CUDA softwarový model. Závěrem je provedeno srovnání rychlosti a kvality CPU a GPU části. This thesis represents master's thesis focused on acceleration of Genetic algorithms using GPU. First chapter deeply analyses Genetic algorithms and corresponding topics like population, chromosome, crossover, mutation and selection. Next part of the thesis shows GPU abilities for unified computing using both DirectX/OpenGL with Cg and specialized GPGPU libraries like CUDA. The fourth chapter focuses on design of GPU implementation using CUDA, coarse-grained and fine-grained GAs are discussed, and completed by sorting and random number generation task accelerated by GPU. Next chapter covers implementation details -- migration, crossover and selection schemes mapped on CUDA software model. All GA elements and quality of GPU results are described in the last chapter.
Keywords: EA; Evolutionary algorithm; Function optimisation; GA; General purpose computation on graphics card; Genetic algorithm; GPGPU; GPU; graphic card; nVidia CUDA; Parallel Genetic algorithm; PGA; Pixel shader; EA; Evoluční algoritmy; GA; Genetický algoritmus; GPGPU; GPU; grafická karta; nVidia CUDA; obecné výpočty na grafické kartě; Optimalizace funkce; Paralelní Genetické algoritmy; PGA; Pixel shader

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/53926

Permalink: http://www.nusl.cz/ntk/nusl-236783


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Master’s theses