计算机应用 ›› 2017, Vol. 37 ›› Issue (9): 2518-2523.DOI: 10.11772/j.issn.1001-9081.2017.09.2518

• 先进计算 • 上一篇    下一篇

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

赵瑞祥1,2, 郑凯1,2, 刘垚1,2, 王肃1,2, 刘艳1,2, 沈焕学1,2, 周谦豪3   

  1. 1. 华东师范大学 计算机科学与软件工程学院, 上海 200062;
    2. 数学工程与先进计算国家重点实验室, 江苏 无锡 214215;
    3. 华东师范大学 经济与管理学部, 上海 200062
  • 收稿日期:2017-04-10 修回日期:2017-07-11 出版日期:2017-09-10 发布日期:2017-09-13
  • 通讯作者: 郑凯,kzheng@cs.ecnu.edu.cn
  • 作者简介:赵瑞祥(1990-),男,吉林扶余人,硕士研究生,主要研究方向:计算机网络、云计算;郑凯(1968-),男,浙江宁波人,副教授,博士,主要研究方向:计算机网络、云计算;刘垚(1981-),男,安徽灵璧人,高级工程师,硕士,主要研究方向:计算机网络、高性能计算;王肃(1980-),女,河南许昌人,讲师,博士,主要研究方向:智能优化、信息系统;刘艳(1976-),女,吉林通化人,助理研究员,博士,主要研究方向:智能优化、信息系统;沈焕学(1992-),男,安徽安庆人,硕士研究生,主要研究方向:计算机网络;周谦豪(1997-),男,上海人,主要研究方向:高性能计算。
  • 基金资助:
    数学工程与先进计算国家重点实验室开放基金资助项目(2016A05)。

Hybrid parallel genetic algorithm based on Sunway many-core processors

ZHAO Ruixiang1,2, ZHENG Kai1,2, LIU Yao1,2, WANG Su1,2, LIU Yan1,2, SHENG Huanxue1,2, ZHOU Qianhao3   

  1. 1. College of Computer Science and Software Engineering, East China Normal University, Shanghai 200062, China;
    2. State Key Laboratory of Mathematical Engineering and Advanced Computing, Wuxi Jiangsu 214215, China;
    3. Faculty of Economics and Management, East China Normal University, Shanghai 200062, China
  • Received:2017-04-10 Revised:2017-07-11 Online:2017-09-10 Published:2017-09-13
  • Supported by:
    This work is partially supported by the Open Fund Project of the State Key Laboratory of Mathematical Engineering and Advanced Computing (2016A05).

摘要: 传统遗传算法求解计算密集型任务时,适应度函数的执行时间增加相当快,致使当种群规模或者进化代数增大时,算法的收敛速度非常缓慢。基于此,设计了"粗粒度-主从式"混合式并行遗传算法(HBPGA),并在目前TOP500上排名第一的超级计算机神威"太湖之光"平台上实现。该算法模型采用两级并行架构,结合了MPI和Athread两种编程模型,与传统在单核或者一级并行构架的多核集群上实现的遗传算法相比,在申威众核处理器上实现了二级并行,并得到了更好的性能和更高的加速比。实验中,当从核数为16×64时,最大加速比达到544,从核加速比超过31。

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

Abstract: 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.

Key words: hybrid parallel genetic algorithm, Sunway "TaihuLight", many-core, MPI, Athread

中图分类号: