面向申威众核处理器的并行SaNSDE算法

doi:10.3778/j.issn.1673-9418.2006059

摘要/Abstract

摘要：

演化算法作为解决大规模优化问题的重要方法，被广泛应用于机器学习、过程控制、工程优化、管理科学和社会科学等领域。然而在求解高维度、高计算密度问题时，程序性能很难得到保证。在高性能计算机上实现并行化是问题的一个热门解决方案。针对申威众核处理器的硬件特征，提出了采用二级并行策略的自适应邻域搜索的差分进化算法（SaNSDE）。第一级为进程并行，实现了合作协同进化模型和池模型，将大规模问题划分为多个低维子问题并分布在不同进程上；第二级为线程并行，使用从核加速了适应度的计算过程。实验结果表明，采用合作协同进化模型和池模型的算法与传统的并行算法相比，经过多核扩展之后收敛效果提升更加明显。相较于串行版本算法，二级并行的SaNSDE算法在四个测试函数上分别获得了134.29、186.05、239.01和189.80的最大加速比。

关键词: 高性能计算, 申威异构众核处理器, 演化算法, 合作协同进化模型（CC）, 池模型

Abstract:

Evolutionary algorithm is an important method for solving large-scale optimization problems, which is widely applied to machine learning, process control, engineering optimization, management science, and social sciences. However, when the traditional evolutionary algorithms are used to high-dimensional and computing-density task, the performance of corresponding applications is difficult to be satisfactory. Parallelization on supercomputer is a popular solution to solve this problem. This paper proposes a two-level parallel self-adaptive differential evolution algorithm with neighborhood search (SaNSDE) on the Sunway TaihuLight, which implements process-level and thread-level parallelism. In the process-level parallelism, the cooperative co-evolution model and pool model are implemented, which divide large-scale problems into multiple low-dimensional problems and distribute them in different processes. In the thread-level parallelism, fitness calculation is accelerated. Experimental results show that the algorithm using the cooperative co-evolution model and the pool model, compared with the traditional parallel algorithm, improves the convergence effect more obviously after multi-core expansion. Compared with the serial algorithm, the two-level parallel SaNSDE algorithm achieves the maximum speedup of 134.29, 186.05, 239.01 and 189.80 in the four benchmark functions, respectively.

Key words: high-performance computing, Sunway heterogeneous multi-core processor, evolutionary algorithm, cooperative co-evolution (CC), pool model

康上, 钱雪忠, 甘霖. 面向申威众核处理器的并行SaNSDE算法[J]. 计算机科学与探索, 2021, 15(10): 2015-2024.

KANG Shang, QIAN Xuezhong, GAN Lin. Parallel SaNSDE for Many-Core Sunway Processor[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(10): 2015-2024.

参考文献

[1] POTTER M A, JONG K A D. Cooperative coevolution: an architecture for evolving coadapted subcomponents[J]. Evolutionary Computation, 2000, 8(1): 1-29.
[2] MEI Y, OMIDVAR M N, LI X, et al. A competitive divide-and-conquer algorithm for unconstrained large-scale black-box optimization[J]. ACM Transactions on Mathematical Software, 2016, 42(2): 1-24.
[3] OMIDVAR M N, MEI Y, LI X D. Effective decomposition of large-scale separable continuous functions for cooperative co-evolutionary algorithms[C]//Proceedings of the 2014 IEEE Congress on Evolutionary Computation, Beijing, Jul 6-11, 2014. Piscataway: IEEE, 2014: 1305-1312.
[4] OMIDVAR M N, YANG M, MEI Y, et al. DG2: a faster and more accurate differential grouping for large-scale black-box optimization[J]. IEEE Transactions on Evolutionary Computation, 2017, 21(6): 929-942.
[5] OMIDVAR M N, LI X D, YAO X. Smart use of computational resources based on contribution for cooperative co-evolutionary algorithms[C]//Proceedings of the 13th Annual Genetic and Evolutionary Computation Conference, Dublin, Jul 12-16, 2011. New York: ACM, 2011: 1115-1122.
[6] KAZIMIPOUR B, OMIDVAR M N, LI X, et al. A sensitivity analysis of contribution-based cooperative co-evolutionary algorithms[C]//Proceedings of the 2015 IEEE Congress on Evolutionary Computation, Sendai, May 25-28, 2015. Piscataway: IEEE, 2015: 417-424.
[7] OMIDVAR M N, KAZIMIPOUR B, LI X D, et al. CBCC3—a contribution-based cooperative co-evolutionary algorithm with improved exploration/exploitation balance[C]//Proceedings of the 2016 IEEE Congress on Evolutionary Computation, Vancouver, Jul 24-29, 2016. Piscataway: IEEE, 2016: 3541-3548.
[8] ROBERGE V, TARBOUCHI M, LABONTé G. Fast genetic algorithm path planner for fixed-wing military UAV using GPU[J]. IEEE Transactions on Aerospace and Electronic Systems, 2018, 54(5): 2105-2117.
[9] FERRUCCI F, SALZA P, SARRO F. Using Hadoop Map-Reduce for parallel genetic algorithms: a comparison of the global, grid and island models[J]. Evolutionary Computation, 2018, 26(4): 535-567.
[10] CAO B, LI W, ZHAO J, et al. Spark-based parallel cooperative co-evolution particle swarm optimization algorithm[C]//Proceedings of the 2016 IEEE International Conference on Web Services, San Francisco, Jun 27-Jul 2, 2016. Washington: IEEE Computer Society, 2016: 570-577.
[11] ABDELHAFEZ A, ALBA E. Speed-up of synchronous and asynchronous distributed genetic algorithms: a first common approach on multiprocessors[C]//Proceedings of the 2017 IEEE Congress on Evolutionary Computation, Donostia, Jun 5-8, 2017. Piscataway: IEEE, 2017: 2677-2682.
[12] ZHAO R X, ZHENG K, LIU Y, et al. 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.
[13] SHEN H X, ZHENG K, LIU Y, et al. Parallel NSGA-II on Sunway many-core processor[J]. Computer Engineering and Applications, 2018, 54(17): 35-40.
沈焕学, 郑凯, 刘垚, 等. 申威众核处理器的并行NSGA-II算法[J]. 计算机工程与应用, 2018, 54(17): 35-40.
[14] Top500 committee. The 25th Top500 list on Nov 2018[EB/OL]. [2019-11-13]. https://www.top500.org/lists/2019/11/.
[15] XU Y T, FU H H, GAN L, et al. Performance optimization and analysis for different Stencil kernels on multi-core and many-core architectures[C]//Proceedings of the 2013 National Annual Conference on High Performance Computing, Guilin, Oct 28-31, 2013: 628-637.
徐阳彤, 付昊桓, 甘霖, 等. 多核与众核架构下对不同Stencil的性能优化和分析[C]//2013全国高性能计算学术年会, 桂林, 2013: 628-637.
[16] HONG W J, LI K L, QUAN Z, et al. PETSc??s heterogeneous parallel algorithm design and performance optimization on the Sunway TaihuLight system[J]. Chinese Journal of Computers, 2017, 40(9): 2057-2069.
洪文杰, 李肯立, 全哲, 等. 面向神威·太湖之光的PETSc可扩展异构并行算法及其性能优化[J]. 计算机学报, 2017, 40(9): 2057-2069.
[17] YANG Z Y, TANG K, YAO X. Self-adaptive differential evolution with neighborhood search[C]//Proceedings of the 2008 IEEE Congress on Evolutionary Computation, Hong Kong, China, Jun 1-6, 2008. Piscataway: IEEE, 2008: 1110-1116.
[18] ROY G, LEE H, WELCH J L, et al. A distributed pool architecture for genetic algorithms[C]//Proceedings of the 2009 IEEE Congress on Evolutionary Computation, Trondheim, May 18-21, 2009. Piscataway: IEEE, 2009: 1177-1184.
[19] JIA Y H, CHEN W N, GU T, et al. Distributed cooperative co-evolution with adaptive computing resource allocation for large scale optimization[J]. IEEE Transactions on Evolutionary Computation, 2018, 23(2): 188-202.
[20] LIU F F, YANG C, YUAN X H, et al. General SpMV implementation in many-core domestic Sunway 26010 processor [J]. Journal of Software, 2018, 29(12): 3921-3932.
刘芳芳, 杨超, 袁欣辉, 等. 面向国产申威26010众核处理器的SpMV实现与优化[J]. 软件学报, 2018, 29(12): 3921-3932.