Hybrid parallel genetic algorithm based on Sunway many-core processors

doi:10.11772/j.issn.1001-9081.2017.09.2518

Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (9): 2518-2523.DOI: 10.11772/j.issn.1001-9081.2017.09.2518

Previous Articles Next Articles

Hybrid parallel genetic algorithm based on Sunway many-core processors

ZHAO Ruixiang^1,2, ZHENG Kai^1,2, LIU Yao^1,2, WANG Su^1,2, LIU Yan^1,2, SHENG Huanxue^1,2, ZHOU Qianhao³

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-13 Published:2017-09-10
Supported by:
This work is partially supported by the Open Fund Project of the State Key Laboratory of Mathematical Engineering and Advanced Computing (2016A05).

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

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

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

通讯作者: 郑凯,kzheng@cs.ecnu.edu.cn
作者简介:赵瑞祥(1990-),男,吉林扶余人,硕士研究生,主要研究方向:计算机网络、云计算;郑凯(1968-),男,浙江宁波人,副教授,博士,主要研究方向:计算机网络、云计算;刘垚(1981-),男,安徽灵璧人,高级工程师,硕士,主要研究方向:计算机网络、高性能计算;王肃(1980-),女,河南许昌人,讲师,博士,主要研究方向:智能优化、信息系统;刘艳(1976-),女,吉林通化人,助理研究员,博士,主要研究方向:智能优化、信息系统;沈焕学(1992-),男,安徽安庆人,硕士研究生,主要研究方向:计算机网络;周谦豪(1997-),男,上海人,主要研究方向:高性能计算。
基金资助:
数学工程与先进计算国家重点实验室开放基金资助项目（2016A05）。

Abstract

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

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

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

CLC Number:

ZHAO Ruixiang, ZHENG Kai, LIU Yao, WANG Su, LIU Yan, SHENG Huanxue, ZHOU Qianhao. Hybrid parallel genetic algorithm based on Sunway many-core processors[J]. Journal of Computer Applications, 2017, 37(9): 2518-2523.

赵瑞祥, 郑凯, 刘垚, 王肃, 刘艳, 沈焕学, 周谦豪. 基于申威众核处理器的混合并行遗传算法[J]. 计算机应用, 2017, 37(9): 2518-2523.

References

[1] ESMAEILZADEH H, BLEM E, AMANT R S, et al. Dark silicon and the end of multicore scaling[C]//Proceeding of the 38th Annual International Symposium on Computer Architecture. New York:ACM, 2011:365-376.
[2] 郑方,张昆,邬贵明,等.面向高性能计算的众核处理器结构级高能效技术[J].计算机学报,2014,37(10):2176-2186.(ZHENG F, ZHANG K, WU G M, et al. Architecture techniques of many-core processor for energy-efficient in high performance computing[J]. Chinese Journal of Computers, 2014, 37(10):2176-2186.)
[3] ZHENG L, LU Y, GUO M, et al. Architecture-based design and optimization of genetic algorithms on multi-and many-core systems[J]. Future Generation Computer Systems, 2014, 38(3):75-91.
[4] UMBARKAR A J, JOSHI M S, HONG W C. Multithreaded Parallel Dual Population Genetic Algorithm (MPDPGA) for unconstrained function optimizations on multi-core system[J]. Applied Mathematics and Computation, 2014, 243:936-949.
[5] 丁孟为.遗传算法在多核系统上的性能分析和优化[D].上海:上海交通大学,2012.(DING M W. Performance analysis and optimization of genetic algorithms on multi-core systems[D]. Shanghai:Shanghai Jiao Tong University, 2012.)
[6] NVIDIA Corporation. NVIDIA's next generation CUDA compute architecture:FERMI[EB/OL].[2016-09-15]. http://www.nvidia.com/content/PDF/fermi_white_papers/NVIDIA_Fermi_Compute_Architecture_Whitepaper.pdf.
[7] LIU X, SMELYANSKIY M, CHOW E, et al. Efficient sparse matrix-vector multiplication on x86-based many-core processors[C]//Proceedings of the 27th International ACM Conference on International Conference on Supercomputing. New York:ACM, 2013:273-282.
[8] SAINI S, JIN H, JESPERSEN D, et al. An early performance evaluation of many integrated core architecture based SGI rackable computing system[C]//Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis. New York:ACM, 2013:Article No. 94.
[9] 巨涛,朱正东,董小社.异构众核系统及其编程模型与性能优化技术研究综述[J].电子学报,2015,43(1):111-119.(JU T, ZHU Z D, DONG X S. The feature, programming model and performance optimization strategy of heterogeneous many-core system:a review[J]. Acta Electronica Sinica, 2015, 43(1):111-119.)
[10] POSPICHAL P, JAROS J, SCHWARZ J. Parallel genetic algorithm on the CUDA architecture[C]//Proceedings of the 2010 European Conference on the Applications of Evolutionary Computation, LNCS 6024. Berlin:Springer, 2010:442-451.
[11] XUE Y, QIAN Z, WEI G, et al. An efficient Network-on-Chip (NoC) based multicore platform for hierarchical parallel genetic algorithms[C]//Proceedings of the 8th IEEE/ACM International Symposium on Networks-On-Chip. Piscataway, NJ:IEEE, 2014:17-24.
[12] GUO L, THOMAS D B, GUO C, et al. Automated framework for FPGA-based parallel genetic algorithms[C]//Proceedings of the 201424th International Conference on Field Programmable Logic and Applications. Piscataway, NJ:IEEE, 2014:1-7.
[13] GUO L, GUO C, THOMAS D B, et al. Pipelined genetic propagation[C]//Proceedings of the 2015 IEEE 23rd Annual International Symposium on Field-Programmable Custom Computing Machines. Washington, DC:IEEE Computer Society, 2015:103-110.
[14] 王一超,林新华,蔡林金,等.太湖之光上基于神威OpenACC的GTC-P移植与优化研究[EB/OL].[2017-05-01]. http://max.book118.com/html/2017/0623/117447540.shtm. (WANG Y C, LIN X H, CAI L J, et al. Porting and optimizing GTC-P on TaihuLight supercomputer with Sunway OpenACC[EB/OL].[2017-05-01]. http://max.book118.com/html/2017/0623/117447540.shtm.)
[15] 郭彤城,慕春棣.并行遗传算法的新进展[J].系统工程理论与实践,2002,22(2):15-23.(GUO T C, MU C D. The parallel drifts of genetic algorithms[J]. Systems Engineering-Theory & Practice, 2002, 22(2):15-23.)
[16] 曾国荪,丁春玲.并行遗传算法分析[J].计算机工程,2001,27(9):53-55.(ZENG G S, DING C L. An analysis on parallel genetic algorithm[J]. Computer Engineering, 2001, 27(9):53-55.)
[17] 李想,魏加华,傅旭东.粗粒度并行遗传算法在水库调度问题中的应用[J].水力发电学报,2012,31(4):28-33.(LI X, WEI J H, FU X D. Application of coarse-grained genetic algorithm to reservoir operation[J]. Journal of Hydroelectric Engineering, 2012, 31(4):28-33.)
[18] 郑志军,郑守淇.粗粒度并行遗传算法性能分析[J].小型微型计算机系统,2006,27(6):1002-1006.(ZHENG Z J, ZHENG S Q. Performance analysis of coarse-grained parallel genetic algorithms[J]. Journal of Chinese Computer Systems, 2006, 27(6):1002-1006.)
[19] BACH F R, JORDAN M I. Learning spectral clustering[J]. Advances in Neural Information Processing Systems, 2004, 16(2):2006.
[20] XUE S, GUO S, BAI D. The analysis and research of parallel genetic algorithm[C]//Proceedings of the 20084th International Conference on Wireless Communications, Networking and Mobile Computing. Piscataway, NJ:IEEE, 2008:1-4.
[21] CHENG C H, FU A W, ZHANG Y. Entropy-based subspace clustering for mining numerical data[C]//Proceedings of the 5th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York:ACM, 1999:84-93.
[22] 国家超级计算无锡中心."神威·太湖之光"系统快速使用指南[EB/OL].[2016-09-15]. http://www.nsccwx.cn/ceshi.php?id=13. (National Supercomputing Center in Wuxi. Guide of "Sunway TaihuLight"[EB/OL].[2016-09-15]. http://www.nsccwx.cn/ceshi.php?id=13.)
[23] 国家超级计算无锡中心."神威·太湖之光"编译系统用户手册[EB/OL].[2016-09-15].http://www.nsccwx.cn/ceshi.php?id=12.(National Supercomputing Center in Wuxi. User's manual of "Sunway Taihu-Light" computer compilation system[EB/OL].[2016-09-15]. http://www.nsccwx.cn/ceshi.php?id=12.)
[24] ZHENG L, LU Y, GUO M, et al. Architecture-based design and optimization of genetic algorithms on multi-and many-core systems[J]. Future Generation Computer Systems, 2014, 38(3):75-91.
[25] 胡玉兰,潘福成,梁英,等.基于种群规模可变的粗粒度并行遗传算法[J].小型微型计算机系统,2003,24(3):534-536.(HU Y L, PAN F C, LIANG Y, et al. Parallel genetic algorithm based on population size mutable coarse-grained[J]. Journal of Chinese Computer Systems, 2003, 24(3):534-536.)
[26] TSOULOS I G, TZALLAS A, TSALIKAKIS D. PDoublePop:an implementation of parallel genetic algorithm for function optimization[J]. Computer Physics Communications, 2016, 209:183-189.
[27] 凌实,刘晓平.基于MPI的主从式并行遗传算法研究与实现[EB/OL].[2016-12-11]. http://xueshu.baidu.com/s?wd=paperuri%3A%2890fc2666352b25fdeaecbd242355ca7c%29&filter=sc_long_sign&tn=SE_xueshusource_2kduw22v&sc_vurl=http%3A%2F%2Fwww.doc88.com%2Fp-0406863398613.html&ie=utf-8&sc_us=5462928728543012625.(LIN S, LIU X P. The study and implementation of master-slave parallel genetic algorithm based on MPI[EB/OL].[2016-12-11]. http://xueshu.baidu.com/s?wd=paperuri%3A%2890fc2666352b25fdeaecbd242355ca7c%29&filter=sc_long_sign&tn=SE_xueshusource_2kduw22v&sc_vurl=http%3A%2F%2Fwww.doc88.com%2Fp-0406863398613.html&ie=utf-8&sc_us=5462928728543012625.)
[28] FU H H, LIAO J F, YANG J Z, et al. The Sunway TaihuLight supercomputer:system and applications[J]. Science China Information Sciences, 2016, 59(7):072001.

Hybrid parallel genetic algorithm based on Sunway many-core processors

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	Mu LI, Yu LUO, Xizheng KE. Human vital signs detection algorithm based on frequency modulated continuous wave radar [J]. Journal of Computer Applications, 2024, 44(6): 1978-1986.
[2]	Hu CHEN, Pengling ZHOU. Programming model for domestic high-performance many-core processor [J]. Journal of Computer Applications, 2023, 43(11): 3517-3526.
[3]	Xiaoyi YANG, Rongcai ZHAO, Hongsheng WANG, Lin HAN, Kunkun XU. Compilation optimizations for inconsistent control flow on deep computer unit [J]. Journal of Computer Applications, 2023, 43(10): 3170-3177.
[4]	Chong CHEN, Zhu YAN, Jixuan ZHAO, Wei HE, Huaqing LIANG. Prediction of NOx emission from fluid catalytic cracking unit based on ensemble empirical mode decomposition and long short-term memory network [J]. Journal of Computer Applications, 2022, 42(3): 791-796.
[5]	KONG Lingxu, WU Haifeng, ZENG Yu, LU Xiaoling. Diagnosis of mild cognitive impairment using deep learning and brain functional connectivities with different frequency dimensions [J]. Journal of Computer Applications, 2021, 41(2): 590-597.
[6]	WANG Guilin, LI Bin. Improved imperialist competitive algorithm inspired by historical facts of Spring and Autumn Period [J]. Journal of Computer Applications, 2021, 41(2): 470-478.
[7]	MENG Xinyu, WANG Ruihan, ZHANG Xiping, WANG Mingjie, QIU Gang, WANG Zhengxia. Ultra-short-term wind power prediction based on empirical mode decomposition and multi-branch neural network [J]. Journal of Computer Applications, 2021, 41(1): 237-242.
[8]	ZHANG Xiaohan, FENG Aimin. Short-term traffic flow prediction based on empirical mode decomposition and long short-term memory neural network [J]. Journal of Computer Applications, 2021, 41(1): 225-230.
[9]	Xiangshuai SONG, Fuzhang YANG, Jiang XIE, Wu ZHANG. Optimization and parallelization of Graphlet Degree Vector method [J]. Journal of Computer Applications, 2020, 40(2): 398-403.
[10]	DING Jianli, LI Yang, WANG Jialiang. Short text automatic summarization method based on dual encoder [J]. Journal of Computer Applications, 2019, 39(12): 3476-3481.
[11]	SUN Jiamin, ZHU Jiafu, YANG Fuzhang, XIE Jiang. Parallel algorithm of Markov clustering for large-scale biological networks [J]. Journal of Computer Applications, 2019, 39(1): 66-71.
[12]	YANG Fuzhang, ZHU Jiafu, SUN Jiamin, XIE Jiang. Parallel algorithm of biological complex network motifs discovery [J]. Journal of Computer Applications, 2019, 39(1): 72-77.
[13]	MO Zan, ZHAO Bing, HUANG Yanying. Network public opinion prediction by empirical mode decomposition-autoregression based on extreme gradient boosting model [J]. Journal of Computer Applications, 2018, 38(3): 615-619.
[14]	WANG Peng, ZHOU Yan. MPI big data processing for high performance applications [J]. Journal of Computer Applications, 2018, 38(12): 3496-3499.
[15]	LI Yingying, GAO Wei, GAO Yuchen, ZHAI Shengwei, LI Pengyuan. Method for exploiting function level vectorization on simple instruction multiple data extensions [J]. Journal of Computer Applications, 2017, 37(8): 2200-2208.