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

康 上，钱雪忠，甘 霖

1.江南大学 人工智能与计算机学院 物联网技术应用教育部工程研究中心，江苏 无锡 214122

2.国家超级计算无锡中心，江苏 无锡 214131

3.清华大学 计算机科学与技术系，北京 100084

演化算法作为经典的启发式算法，有着易理解、自适应和搜索能力强等优点，从离散的单目标问题到连续的多目标问题，其适用于解决各种复杂的黑盒优化问题。演化算法在解决低维问题上有着优异的表现，然而随着问题决策变量增加，算法的搜索能力会急剧下降。针对这个问题，现在最为常用的解决方案是将合作协同进化模型（cooperative co-evolution，CC）[1]与演化算法相结合，CC 模型的基本思想是将规模较大的问题分解为多个小规模问题。大量实验证明这样的组合取得了很好的效果[2-4]。后来为了提高最优解的质量，Omidvar 等人又提出了基于贡献的合作协同进化模型[5]及其改进[6-7]。然而遗憾的是，上述研究仍然是处于串行思路下展开的，当面对复杂度高的大规模问题时，算法性能仍然得不到保证。

由于演化算法具有天然的并行性，许多大规模优化问题的解决思路逐步向并行化靠拢。与此同时，高性能计算机的发展与普及为算法的并行化提供了强有力的硬件支撑。目前已经有很多演化算法在多核处理器架构上实现并行化的探索。

Roberge 等人在CUDA（compute unified device architecture）上面实现并行遗传算法解决无人机路径规划问题[8]。Ferrucci 等人在MapReduce 平台上分别实现了基于主从模型、细胞模型和岛屿模型的并行遗传算法，并比较了三个模型的性能表现[9]。Cao等人在Spark上实现了并行协同粒子群算法[10]。Abdelhafez等人使用MPI（message passing interface）在多核处理器上实现了基于岛屿模型的分布式遗传算法[11]。总结以上研究，目前并行遗传算法大多采用岛屿模型来实现，根据种群分布的原则来划分任务。然而对于岛屿模型来说，迁移机制会影响算法的性能和寻优能力：迁移频率和迁移规模过大会增大通信开销，过小又会降低种群多样性最终影响解的质量，这无疑增大了岛屿模型的设计难度。另一方面，上述研究也未能对适应度计算过程做出优化。适应度作为判断个体优劣程度的评价指标，需要在优化过程中对种群中所有个体进行评估，判断产生的新个体能否进入下一代。问题越复杂，适应度计算量就会越大，例如在资源优化调度、深度学习模型超参数的寻优等问题中，单个个体的适应度评估就要花费很长的时间，在这种情况下程序性能很难得到保证。此外，受硬件平台的限制，大多数的并行化研究只采用一级并行的策略，未充分挖掘演化算法的并行化潜力。

本文所使用的“神威·太湖之光”实验平台，是世界上首台峰值运算性能超过十亿亿次量级的超级计算机，机器全部采用申威26010 国产处理器，申威独特的主从核式物理架构为实现二级并行策略提供了可能。基于申威众核处理器平台实现并行演化算法的研究已经有了一些初步的进展，赵瑞祥等人提出了“粗粒度-主从式”混合并行遗传算法[12]。沈焕学等人实现了并行非支配排序遗传算法以解决多目标优化问题[13]。以上研究仅局限于低维问题，没有对大规模问题的优化做进一步的讨论。

基于以上问题，本文面向申威异构众核处理器平台，以采用二级并行策略的自适应邻域搜索的差分进化算法（self-adaptive differential evolution algorithm with neighborhood search,SaNSDE）为问题求解过程的优化算法，研究在超级计算机神威·太湖之光上解决大规模优化问题的并行化策略。本文主要工作如下：

（1）针对申威众核处理器特殊的架构设计了进程并行+线程并行的二级并行模型。进程级并行使用消息传递接口实现了基于维度分布原则的CC 模型和基于种群分布原则的池模型；线程级并行使用64 个从核加速了个体适应度的计算过程。

（2）实现了并行合作协同自适应邻域搜索的差分进化算法（parallel-cooperative co-evolution self-adaptive differential evolution with neighborhood search,PCCSaNSDE）。研究了算法在解决高维问题上的表现和大规模并行后的性能。

（3）为了进一步探索SaNSDE 算法使用混合模型后进行大规模扩展的性能表现，在CC 模型的基础上引入池模型。实现了混合模型下的并行自适应邻域搜索的差分进化算法（parallel-hybrid self-adaptive differential evolution with neighborhood search,P-HSaNSDE）。

1 相关背景知识

1.1 “神威·太湖之光”和申威26010处理器

“神威·太湖之光”是中国第一台全部采用国产处理器的超级计算机，2016—2017 年曾四次荣登TOP500 超级计算机榜首，在2019 年11 月最新一期全球超级计算机TOP500 中位列第三[14]。

“神威·太湖之光”计算机系统搭载的是申威26010（sunway26010，SW26010）异构众核处理器。SW26010 基本构架如图1 所示，一个处理器包含4 个核组（core group，CG）共260 个核心，它们都是64 位的RISC 内核。每个核组包括1 个控制核心（management processing element，MPE）和以8×8 阵列方式排列的64 个计算核心（computing processing element，CPE），即一个主核和64 个从核。在执行运算任务时，MPE 与CPE 的分工是不同的，MPE 主要负责任务的管理和调度；CPE 主要负责执行重复密集的计算。每个SW26010 处理器有32 GB 的内存，单个核组内存为8 GB。每个从核包含64 KB 的片上局部数据空间（local directive memory，LDM），LDM 作为用户控制快速缓冲。从核访问主存有两种方式：gld/gst（global load/store）直接离散访问和DMA（direct memory access）方式批量访问，从核之间使用寄存器进行通信。SW26010 特殊的设计方式可以提高整体性能，但是独特的架构也增大了编程难度，数据的分割会严重影响访存、通信和计算能力[15-16]。因此如何对程序的任务和数据进行划分，充分发挥从核之间的协作能力和计算效率，是提升性能的关键。

1.2 SaNSDE 算法

差分进化（differential evolution，DE）算法于1997年由Storn 和Price 在遗传算法思想的基础上提出，模拟遗传算法中的杂交、变异、复制来设计算子，用于求解多维空间中全局最优解。由于差分进化算法具有结构简单、易于实现、收敛速度快等优点，被广泛应用于人工神经网络、数据挖掘和模式识别等各个领域。DE 有三个主要步骤：（1）变异。使用差分策略实现个体变异，最常见的方法是将两个不同的个体向量缩放后与待变异个体向量合成。（2）交叉。交换个体间某些向量的信息产生新的个体。（3）选择。采用优胜劣汰的原则选择进入下一代的个体。

SaNSDE 算法[17]为DE 算法的改进，相比于DE 算法有两个改进：（1）变异率F由高斯分布和柯西分布随机生成，这样可以产生较大的搜索步长避免结果陷入局部最优解。（2）引入两种变异策略，在优化过程中根据问题的不同选择合适的策略，并且可以在优化过程中自适应交叉率CR 的值。

Fig.1 Structure diagram of SW26010 multi-core processor图1 申威26010众核处理器结构图

1.3 合作协同进化模型

CC 模型是一个维度分布模型，一个完整的CC模型应该包括两个流程：问题分解和问题优化。对于一个复杂的高维问题，CC 先将其划分为多个维度较小的子问题，划分的原则是将具有相关性的决策变量分为一组，互不相关的决策变量放在不同的组。然后演化算法分别对这些子问题求解，最后将子问题的最优解进行整合就得到了全局最优解。

如图2（a）所示，对于一个D维问题D={x1,x2,…,xD}，CC 将其划分为M个子问题，按顺序进行优化。CC 框架的每个子组在优化过程中是相互独立的，只需要在优化结束后同步最优解和种群信息，具备天然的并行性，每个子组可以分布在不同的进程上同时进行优化。分布式CC（distribute cooperative coevolution，dCC）与串行CC 在问题分解阶段是相同的，区别在于问题优化阶段，如图2（b）所示。

Fig.2 Structure of CC图2 CC 框架的结构

1.4 CCSaNSDE 算法

CCSaNSDE 算法将SaNSDE 作为CC 模型问题求解阶段的优化器，算法具体的执行步骤如下：

（1）初始化种群，对每个个体进行适应度评估，找到当前最优个体和最优解gbest。

（2）将高维度复杂问题分解为多个低维子问题。

（3）按一定顺序对每个子问题进行优化，优化完成后更新种群信息。

（4）子问题全都执行完优化操作后重新计算个体适应度，找到当前最优个体和最优解gbest。记在j代中，第i个子种群Si最优个体为。通常，子种群中个体适合度是通过与其他子种群中最优秀的个体相结合来计算的，全局最优值计算方法为:

（5）判断是否达到最大迭代次数。若否，转至步骤（3）；若是，输出gbest。

1.5 池模型

池模型[18]是种群分布模型，池模型将所有个体放入一个共享的数据结构中，处理器可以并发地访问池中的所有个体。但是每个个体同一时刻只允许有一个处理器对其进行写操作。如图3 所示，此处将池设计为一个数组，其中N代表个体数量，数组被划分为M份，即将种群划分为M个子种群。多个处理器可以共同处理一个子种群。每个处理器只与池进行交互，彼此之间相互独立不进行通信。

Fig.3 Structure of pool model图3 池模型结构

2 SaNSDE 并行算法的设计与实现

申威众核处理器独特的主从核式架构为实现算法的高度并行化提供了理想的平台，然而传统的并行演化算法难以充分发挥申威的优势。因此本章针对其物理架构设计了算法的二级并行模型。第一级为进程级并行，即主核间并行；第二级为线程级并行，即从核间并行。主核间并行使用MPI 进行通信，用来进行任务划分。本文实现了维度分布模型CC和种群分布模型池，从问题维度和种群数量两方面来分解大规模问题，并且对模型进行了调整使之适用于多核扩展。从核间并行使用申威处理器特有的Athread 线程库来发挥从核的加速性能，将个体信息分配到64 个从核上，实现个体适应度计算的并行。

2.1 进程级并行

2.1.1 P-CCSaNSDE 算法的设计与实现

由于dCC 并不具备计算资源分配的功能，很难去适应核心数量的变化，为了使CCSaNSDE 算法更加易于进行多核扩展，本文在使用CC 模型的基础上引入了主从模型。与传统主从式模型所不同的是从节点不只是执行适应度计算，也会执行优化过程。更确切地说，主节点作为一个管理者主要负责任务分发和管理，优化操作由从节点完成。具体实现步骤如图4 所示，设置0 号进程为主节点，其余进程为从节点。主节点存有种群信息以及分组结果，优化开始时，主节点将子组依次分配到从节点上，从节点得到子组后使用SaNSDE 算法进行优化，优化完成后将优化结果反馈至主节点。整个优化过程中，从节点之间不进行通信，仅与主节点进行数据交换。各个子组之间的优化同时进行并且相互独立，这也体现出了P-CCSaNSDE 算法的并行性。

Fig.4 Flow diagram of algorithm图4 算法流程图

当所有子组优化完成后，需要同步种群信息，对于dCC 而言更新种群就意味着要与主节点进行通信交换数据，频繁通信会花费大量的时间，影响程序性能。为了减少这种损失，本文设置阈值MaxGen，即每个子组需要在相应子节点上优化MaxGen次才与主节点通信更新种群。

在分组数量固定的情况下进行扩展性实验时，核心数与分组数量不一定相等，考虑到负载均衡的原则，本文对模型结构做出适当调整，当核心数小于分组数量时，子组会被均等分配到每个核心上；当核心数等于分组数量时，子组与核心一一对应；当核心数大于分组数量时，多个核心将处理同一个子组，由主节点选择其中最优解。

2.1.2 P-HSaNSDE 算法的设计与实现

为了避免单一模型造成粒度过粗或者过细的问题，本文在CC 框架的基础上又引入了池模型。探索使用混合模型下进行大规模扩展的性能。整个程序分为两层：在第一层dCC 模型将高维问题划分为低维子组，属于维度分布模型；第二层为池模型，将每个子组进一步分解为子种群，属于种群分布模型。对于一个D维问题首先使用分组策略划分为M个子组{S1,S2,…,SM}。在这里将每一个子组Si看作一个种群，每个种群与分配到的处理器共同组成一个池模型，若种群S1分配到两个进程P1和P2，则将S1分为两个子种群,每个进程分配到一个子种群。第二个种群S2分配到三个进程，则将其划分为三部分与三个进程一一对应。考虑到当单个进程内个体数量过小时，会降低种群多样性，影响算法的搜索能力，本文引入了Jia 等人在文中提到的种群平衡性策略[19]。种群数量与处理器的数量相关联，当处理器增加时，种群数也会增加；当处理器减少时，种群数也会相应减少。种群数量|Si|和进程数|Pi|的关系如下:

这样可以保证每个处理器都有相同数量的个体，不会由于进程数增加造成个体数量降低。引入池模型的算法进行大规模扩展时，会先根据种群一致性原则扩充种群，当优化结束后，采用精英主义的原则，保留子种群中较优的个体。

2.2 线程级并行

以上模型分别从维度和种群方面划分任务并均等分配到不同处理器上，减少了单个处理器的计算压力。考虑到每个处理器在执行优化操作时需要进行适应度评估，比较优化前后的效果决定种群是否进入下一代。复杂的大规模问题往往会在适应度计算时花费大量的时间，对这部分进行优化也是提升程序性能的关键。针对此问题，本文使用申威众核处理器特有的Athread 线程库，将种群内个体的适应度评估交给从核阵列进行加速。

从核访存方式有两种：一是通过寄存器直接访存；二是寄存器LDM 访存。由于申威26010 处理器主从核之间没有共享缓存，寄存器直接访存时间开销巨大[20]，本文采用DMA 方式将数据拷贝至LDM 之后再进行访存，通过这种方法提高访存速度。

主核伪代码如算法1 所示。由于Athread 是共享内存编程模型，主从核都要定义共享变量，函数开始时要先初始化线程库，然后启动线程组进行计算并等待计算完成，最后当程序结束后要将线程回收。

算法1主核伪代码

从核伪代码如算法2 所示。首先发起DMA 将主存中的数据发送至从核的LDM，计算完成后发起DMA 将结果发送回主核。

算法2从核伪代码

3 实验与分析

3.1 适应度函数及实验参数

为了测试P-CCSaNSDE 和P-HSaNSDE 两个算法在申威众核处理器上大规模扩展的效果，本文以优化结果和加速比两个指标评价算法的性能。适应度函数采用以下4 个标准测试函数，为了模拟大规模问题，将n设置为1 024。

4 个标准测试函数的理论最小值为0，优化结果越接近0，说明算法的优化效果更好。种群中个体数量NP 为64，迭代的终止条件为单进程上适应度评估次数达到2×106次，设置MaxGen为50，即每个进程优化50 次后再进行通信交换数据。实验结果都是独立运行25 次后取平均值。

3.2 收敛结果

本节以采用岛屿模型的P-SaNSDE 算法为基准进行结果对比。算法在测试函数F1、F2、F3 和F4 上的收敛结果如表1 所示。随着核心数量增加，两个并行算法的优化结果都有较为明显的提升。相对于PSaNSDE 算法，采用CC 模型的P-CCSaNSDE 算法收敛结果变化的趋势更显著，最优解的质量更高，在F1函数上效果差异最大。需要特别指出的是，当处理核心数小于分组数量时，解的质量并没有很明显的提升，但是当处理核心数大于分组数量时，优化效果有了大幅度的提升。这说明当多个核心处理一个子组时，优化过程中会增加产生优质解的可能性，从而提高最终解的质量，这也是大规模并行的优势所在。通过观察实验数据，P-SaNSDE 算法，从1 核扩展到1 024 核之后，优化结果虽有提升，但是并没有很大的突破。这说明CC 模型相较于需要考虑迁移策略的岛屿模型，更易于进行大规模扩展。

Table 1 Fitness of P-SaNSDE and P-CCSaNSDE on benchmark functions表1 P-SaNSDE 和P-CCSaNSDE 算法在测试函数上的适应度

图5 为采用dCC+Pool 混合模型的P-HSaNSDE算法在4 个测试函数上优化结果随核数增加的变化情况。随着核心数量增加，与P-CCSaNSDE 算法相比，P-HSaNSDE 在F2 和F3 函数的收敛效果有了进一步的提升，在F1 和F4 函数上则略有下降。这说明针对特定问题，使用合适的混合模型可以提高最优解的质量。

Fig.5 Fitness of 4 benchmark functions图5 4 个测试函数的适应度

3.3 加速比

CC 模型与混合模型虽然实现方法不同，但是大规模扩展后单个核心内所处理的种群大小是相同的，因此性能是相同的。本节仅以P-CCSaNSDE 算法为例，讨论算法二级并行后的性能表现。如图6 所示，随着核心数量增加，算法的性能有很大的提升：当核数为1 时，算法是串行执行的，唯一的进程需要处理所有的子组，此时程序的运行时间最长；随后核心数量每增加一倍，单核心处理的子组数量就减少50%，运行时间也随之减少50%。当核数增加至32 时，每个进程只处理一个子组，此时程序运行时间最低，达到最大加速比，在4个标准测试函数上分别为134.29、186.05、239.01 和189.80。

在随后的大规模扩展的实验中，核数从32 提升到1 024，算法性能逐渐下降，这是由于核数增加会导致进程间通信耗时增大，最终影响性能。然而从表2可知，当核数最高扩展到1 024 时，算法仍然有很高的加速比，运行时间远远低于串行版本。经过大规模扩展后的算法，不仅在优化结果方面有较大优势，而且也有极高的性能表现。

Table 2 Speedup表2 加速比

3.4 相关工作对比

从优化结果来看，使用CC 模型和混合模型的算法在4 个测试函数上的最优解质量都要远远高于PSaNSDE，并且随着扩展规模增大，这种差异就愈加明显。两个算法在4 个测试函数上的收敛结果各有优劣。P-CCSaNSDE 在F1 和F4 函数上收敛效果较好，而P-HSaNSDE 在F2 和F3 函数上收敛效果更优。

从算法运行时间上来看，采用二级并行后的算法有着十分优异的性能表现，即使进行大规模扩展后算法运行时间仍然远远低于串行版本。与传统仅使用一级并行的算法相比，使用Athread 加速适应度计算后，算法获得了更好的加速效果。

Fig.6 Speedup of 4 benchmark functions图6 4 个测试函数的加速比

4 结束语

本文以“神威·太湖之光”为实验平台，通过研究和分析申威异构众核处理器特殊的架构，对演化算法求解大规模优化问题从进程级和线程级两方面进行了高度并行化实现。在模型选择上，分别使用了CC 模型和CC+Pool 的混合模型，并对其进行了大规模的扩展。为了充分发挥SW26010 处理器的性能，使用从核对适应度计算部分进行了加速。实验表明，在高维测试函数上，多核扩展后的P-CCSaNSDE和P-HSaNSDE 算法表现出了很强的搜索能力，相较于P-SaNSDE 算法，收敛结果有很明显的提升，并且二级并行后的算法具有很高的加速比，在4 个测试函数上最高达到了239.01。