Journal of Frontiers of Computer Science and Technology ›› 2021, Vol. 15 ›› Issue (10): 2015-2024.DOI: 10.3778/j.issn.1673-9418.2006059

• Theory and Algorithm • Previous Articles    

Parallel SaNSDE for Many-Core Sunway Processor

KANG Shang, QIAN Xuezhong, GAN Lin   

  1. 1. Engineering Research Center of Internet of Things Technology Applications, Ministry of Education, College of Artificial Intelligence and Computer Science, Jiangnan University, Wuxi, Jiangsu 214122, China
    2. National Supercomputing Center in Wuxi, Wuxi, Jiangsu 214131, China
    3. Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China
  • Online:2021-10-01 Published:2021-09-30

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

康上钱雪忠甘霖   

  1. 1. 江南大学 人工智能与计算机学院 物联网技术应用教育部工程研究中心,江苏 无锡 214122
    2. 国家超级计算无锡中心,江苏 无锡 214131
    3. 清华大学 计算机科学与技术系,北京 100084

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)。第一级为进程并行,实现了合作协同进化模型和池模型,将大规模问题划分为多个低维子问题并分布在不同进程上;第二级为线程并行,使用从核加速了适应度的计算过程。实验结果表明,采用合作协同进化模型和池模型的算法与传统的并行算法相比,经过多核扩展之后收敛效果提升更加明显。相较于串行版本算法,二级并行的SaNSDE算法在四个测试函数上分别获得了134.29、186.05、239.01和189.80的最大加速比。

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