DocumentCode :
2089351
Title :
Architecture-based Performance Evaluation of Genetic Algorithms on Multi/Many-core Systems
Author :
Zheng, Long ; Lu, Yanchao ; Ding, Mengwei ; Shen, Yao ; Minyi Guoz ; Guo, Minyi
fYear :
2011
fDate :
24-26 Aug. 2011
Firstpage :
321
Lastpage :
334
Abstract :
A Genetic Algorithm (GA) is a heuristic to find exact or approximate solutions to optimization and search problems within an acceptable time. We discuss GAs from an architectural perspective, offering a general analysis of GAs on multi-core CPUs and on GPUs, with solution quality considered. We describe widely-used parallel GA schemes based on Master-Slave, Island and Cellular models. Then, based on the multi-core and many-core architectures, especially the thread organization, memory hierarchy, and core utilization, we analyze the execution speed and solution quality of different GA schemes theoretically. Finally, we can point to the best approach to use on multi-core and many-core systems to execute GAs, so that we can obtain the highest quality solution at a cost of the shortest execution time. Furthermore, there are three extra contributions. Firstly, during our analysis and evaluation, we not only focus on the execution speed of different schemes, but also take the solution quality into account, so that our findings will be more useful in practice. Secondly, during our optimization of an Island scheme on GPUs, we find that the GPU architecture actually alters the scheme, making it become the Cellular scheme, which leads to big changes in solution quality and optimization results. Finally, we calculate the GPU speedup based on a comparison between the best scheme on a GPU and the best one on a CPU, rather than between an optimized one on the GPU and the worst one on a CPU, so that the speedup we calculate is more reasonable and a better guide to practical decisions.
Keywords :
computer architecture; computer graphic equipment; coprocessors; genetic algorithms; multiprocessing systems; search problems; GA; GPU architecture; architectural perspective; architecture based performance evaluation; core utilization; genetic algorithms; manycore architectures; manycore systems; memory hierarchy; multicore architectures; multicore systems; optimization problems; search problems; thread organization; Conferences; Scientific computing;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computational Science and Engineering (CSE), 2011 IEEE 14th International Conference on
Conference_Location :
Dalian, Liaoning
Print_ISBN :
978-1-4577-0974-6
Type :
conf
DOI :
10.1109/CSE.2011.65
Filename :
6062894
Link To Document :
بازگشت