Paper Info
Title
A Heterogeneous Parallel Genetic Algorithm Based on SW26010 Processors
Abstract
The genetic algorithm is a kind of evolutionary algorithms, which is widely used to solve optimization problems. It still faces the challenge of computing efficiency when dealing with large-scale optimization problems, which motivates the research on parallel genetic algorithm (PGA) to accelerate it. Sunway TaihuLight system is the first supercomputer with a peak performance of over 125 PFlops, which is powered by SW26010 heterogeneous many-core processors. Among the common PGA models, the hierarchical model fits the SW26010 best due to its heterogeneity. In this paper, we propose a heterogeneous parallel genetic algorithm (swGA) on Sunway TaihuLight system, which implements process-level and thread-level parallelism. In the process-level parallelism, we propose an island model based on a migration pool, which preserves the elitists and provides the globally stochastic individuals to be immigrated for islands. In addition, an interleaving emigration scheme and a dynamic immigration scheme are proposed to reduce the communication overhead of migration. In the thread-level parallelism, we propose the island/master-slave, island/cellular, and island/island models based on the unique mechanisms of SW26010. We optimize these models by using some optimization methods such as direct memory access, register-level communication, double buffering, vectorization. The experimental results show that the island model of swGA has a better search ability compared with a directed migration based island model and a serial GA. Based on the island model, the three hierarchical models all have satisfied search ability and acceleration effect. Among them, the island/island model has the best search ability, and the island/cellular model has the best acceleration effect, which achieves a speedup up to 3603.13× on 64 CGs.
Year
DOI
Venue
2019
10.1109/HPCC/SmartCity/DSS.2019.00023
2019 IEEE 21st International Conference on High Performance Computing and Communications; IEEE 17th International Conference on Smart City; IEEE 5th International Conference on Data Science and Systems (HPCC/SmartCity/DSS)
Keywords
Field
DocType
heterogenous parallel,genetic algorithm,many core processor,migration pool
Evolutionary algorithm,Supercomputer,Computer science,SW26010,Vectorization (mathematics),Hierarchical database model,Optimization problem,Genetic algorithm,Speedup,Distributed computing
Conference
ISBN
Citations 
PageRank 
978-1-7281-2059-1
0
0.34
References 
Authors
12
6
Name
Order
Citations
PageRank
Yao Liu100.34
Qidan Liao200.34
Jun Sun3106079.09
Mengtao Hu400.34
Li Liu518112.42
Lin Zheng600.34