Original title: Efektivní implementace genetického algoritmu s využitím vícejádrových CPU
Translated title: The Efficient Implementation of the Genetic Algorithm Using Multicore Processors
Authors: Kouřil, Miroslav ; Žaloudek, Luděk (referee) ; Jaroš, Jiří (advisor)
Document type: Master’s theses
Year: 2010
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
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. This diploma thesis deals with acceleration of advanced genetic algorithm. For implementation, discrete and continuos versions of UMDA genetic algorithm were chosen. The main part of the acceleration is the utilization of SSE instruction set. Using this set, the functions for calculating fitness and new population sampling were accelerated in particular. Then the pseudorandom number generator that also uses SSE instruction set was implemented.  The discrete algorithm reached the speed of up to 4,6 after this implementation. Finally, the algorithms were modified so that the system  OpenMP could be used, which enables the running of blocks of code in more threads. The continuous version of algorithm is not convenient for parallelization, because computational complexity of that algorithm is low. In comparison, the discrete versions of algorithm are really appropriate for parallelization. Both the implemented versions reached the total acceleration of up to 4,9 and 7,2. 
Keywords: Advanced evolutionary algorithms; Amdahl's law; EDA; Flynn's taxonomy; Gustafson's law; OpenMP; Parallelization; SIMD; SSE; UMDA; Amdahlův zákon; EDA; Flynnova klasifikace; Gustafsonův zákon; OpenMP; paralelizace; Pokročilé evoluční algoritmy; SIMD; SSE; UMDA

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

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


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