基于申威众核处理器的混合并行遗传算法

摘要

传统遗传算法求解计算密集型任务时,适应度函数的执行时间增加相当快,致使当种群规模或者进化代数增大时,算法的收敛速度非常缓慢.基于此,设计了“粗粒度-主从式”混合式并行遗传算法(HBPGA),并在目前TOP500上排名第一的超级计算机神威“太湖之光”平台上实现.该算法模型采用两级并行架构,结合了MPI和Athread两种编程模型,与传统在单核或者一级并行构架的多核集群上实现的遗传算法相比,在申威众核处理器上实现了二级并行,并得到了更好的性能和更高的加速比.实验中,当从核数为16×64时,最大加速比达到544,从核加速比超过31.%When the traditional genetic algorithm is used to solve the computation-intensive task,the execution time of the fitness function increases rapidly,and the convergence rate of the algorithm is very low when the population size or generation increases.A "coarse-grained combined with master-slave" HyBrid Parallel Genetic Algorithm (HBPGA) was designed and implemented on Sunway "TaihuLight" supercomputer which is ranked first in the latest TOP500 list.Two-level parallel architecture was used and two different programming models,MPI and Athread were combined.Compared with the traditional genetic algorithm implemented on single-core or multi-core cluster with single-level parallel architecture,the algorithm using two-level parallel architecture was implemented on the Sunway many-core processors,better performance and higher speedup ratio were achieved.In the experiment,when using 16 × 64 CPEs (Computing Processing Elements),the maximum speedup can reach 544,and the CPE speedup ratio is more than 31.