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 language | English |
|---|---|
| Title of host publication | Proc. - 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 |
| Pages | 321-334 |
| Number of pages | 14 |
| DOIs | |
| Publication status | Published - 23 Nov 2011 |
| Externally published | Yes |
| Event | 14th 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 2011 → 26 Aug 2011 |
Conference
| Conference | 14th 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/Territory | China |
| City | Dalian, Liaoning |
| Period | 24/08/11 → 26/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