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

Hybrid parallel genetic algorithm based on Sunway many-core processors

作　　者：赵瑞祥[1,2] 郑凯[1,2] 刘垚[1,2] 王肃[1,2] 刘艳[1,2] 沈焕学 周谦豪 

机构地区：[1]华东师范大学计算机科学与软件工程学院,上海200062 [2]数学工程与先进计算国家重点实验室,江苏无锡214215 [3]华东师范大学经济与管理学部,上海200062

出　　处：《计算机应用》2017年第9期2518-2523,共6页journal of Computer Applications

基　　金：数学工程与先进计算国家重点实验室开放基金资助项目(2016A05)~~

摘　　要：传统遗传算法求解计算密集型任务时,适应度函数的执行时间增加相当快,致使当种群规模或者进化代数增大时,算法的收敛速度非常缓慢。基于此,设计了"粗粒度-主从式"混合式并行遗传算法(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 1664 CPEs （Computing Processing Elements）, the maximum speedup can reach 544, and the CPE speedup ratio is more than 31.

关 键 词：混合并行遗传算法 神威"太湖之光" 众核 MPI Athread 

分 类 号：TP332[自动化与计算机技术—计算机系统结构]