Architecture-based performance evaluation of genetic algorithms on multi/many-core systems

Long Zheng, Yanchao Lu, Mengwei Ding, Yao Shen, Minyi Guoz, Song Guo

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

12 Citations (Scopus)

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.
Original languageEnglish
Title of host publicationProc. - 14th IEEE Int. Conf. on Computational Science and Engineering, CSE 2011 and 11th Int. Symp.on Pervasive Systems, Algorithms, and Networks, I-SPAN 2011 and 10th IEEE Int. Conf. IUCC 2011
Pages321-334
Number of pages14
DOIs
Publication statusPublished - 23 Nov 2011
Externally publishedYes
Event14th IEEE Int. Conf. on Computational Science and Engineering, CSE 2011, the 11th International Symposium on Pervasive Systems, Algorithms, and Networks, I-SPAN 2011, and the 10th IEEE Int. Conf. on Ubiquitous Computing and Communications, IUCC 2011 - Dalian, Liaoning, China
Duration: 24 Aug 201126 Aug 2011

Conference

Conference14th IEEE Int. Conf. on Computational Science and Engineering, CSE 2011, the 11th International Symposium on Pervasive Systems, Algorithms, and Networks, I-SPAN 2011, and the 10th IEEE Int. Conf. on Ubiquitous Computing and Communications, IUCC 2011
Country/TerritoryChina
CityDalian, Liaoning
Period24/08/1126/08/11

Keywords

  • accuracy
  • architecture
  • Genetic Algorithm
  • GPU
  • multi-core
  • speedup

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Computer Science Applications

Cite this