0 引言

随着科技进步，计算密集型任务需求与日俱增，但许多情况下单纯的串行计算已不能满足当前的要求，单个芯片的性能提高遇到了瓶颈^[1]：越来越高的集成度，导致高功耗^[2]和散热问题难以解决。采用多核或众核已成为提高处理能力的重要手段，相应的程序也需要从串行转向并行。但由于串行程序与并行程序存在巨大的差异，无法自动转换，许多用串行方式实现的应用移植到众核平台运行面临不小的挑战。

目前关于并行遗传算法的研究多数在多核平台实现^[3-5]，并采用消息传递接口(Message-Passing-Interface, MPI)编程模型，性能和加速比的提升受到主核数量的限制，当适应度函数的计算量复杂时性能和加速比的提升不明显。也有关于在通用并行计算架构^[6-9] (Compute Unified Device Architecture, CUDA)上基于图形处理器(Graphics Processing Unit, GPU)的粗粒度并行遗传算法的实现报道^[10]。为了与GPU架构兼容，在CUDA软件模型中使用简化的单向环移动，提高了迁移速度^[11]。但受GPU结构的限制，只适用单指令多数据流(Single Instruction Multiple Data, SIMD)类型的数据并行，内部各处理核之间不允许通信，使其应用范围受到很大局限。曾有学者试图利用现场可编程门阵列(Field-Programmable Gate Array, FPGA)来实现遗传算法的并行化，但很难实现。文献[12-13]指出，FPGA在硬件架构和优化时，灵活性较弱，算法中的许多部分不能很好地映射到硬件。而本文的实验平台采用国产超算“神威·太湖之光”。该机是世界上首台峰值运算性能超过十亿亿次量级的超级计算机，目前在TOP500中排行第一，也是中国首台全部采用国产处理器构建的超级计算机。该机采用我国自主研制的“申威26010”众核处理器，通过主核和从核间的并行协作，可以达到极高的并行计算能力。该处理器与GPU相比具有较强的通信和同步能力，与FPGA相比具有较好的灵活性，突出的特点是从核处理能力较强。文献[14]论证发现，“申威26010”上逾98%的理论性能均源自于从核。所以编程时将串行的、复杂的、需要内存容量大的工作放在拥有较多内存的主核上完成，而独立的、可以并行执行的、计算密集型的工作放在从核完成，更能体现出该众核架构的优势。

由于遗传算法的种群中每个个体之间的数据独立性强，具有天然的并行性，非常适合于在大规模并行机上实现。基于该平台，本文将典型的遗传算法进行了二级并行化设计，并结合两种编程模型，MPI和Athread (SW26010专用加速线程库)将其实现。目前已有的并行遗传算法一般是实现一级并行(MPI模式)，尚未看到有相关的研究基于申威“26010”众核处理器实现遗传算法的二级并行。本文的工作在这个领域是一种新的尝试。

1 混合式的二级并行模型的设计与实现 1.1 并行遗传算法模型介绍

目前遗传算法的并行模型可分为四种：主从式模型、粗粒度模型、细粒度模型和混合模型^[15]。

曾国荪等^[16]指出，主从式模型的优点是简单，且速度和效率优于串行遗传算法，但缺陷是经常会出现主从节点机负载不均衡、通信瓶颈和延迟问题。在主从式模型中，选择、交叉和变异操作由主节点机串行执行，而适应度评价由从节点机并行执行，所以这种模型适合适应度函数复杂的遗传算法，对于适应度函数较简单的情况，它将失去并行执行的优势。

粗粒度模型中每经过一定的进化代，各个子群体间将交换若干个个体，一方面用来引入更优良的个体，另一方面丰富种群的多样性，防止未成熟早收敛现象。对于粗粒度模型，确定迁移规模相当重要，迁移规模由迁移率、迁移周期两个参数控制，通常迁移率越大则迁移周期越长^[17]。郑志军等^[18]通过实验证明，大规模的迁移或迁移周期太短将导致通信开销增多；而迁移规模太小又容易形成局部最优解，影响解的质量；迁移周期太长则会导致优秀个体不能及时传播，反而降低收敛速度。

细粒度模型具有维持种群多样性从而抑制早熟现象及能实现高度并行化等优势^[19]。但由于每个个体需要单独占用一个节点，导致该模型通信开销大，并行机难以承受，并且研究人员难以找到适用于该模型的并行机。

混合模型^[20-21]是将上述三种模型混合形成的层次模型，一般有三种：粗粒度-细粒度、粗粒度-粗粒度、粗粒度-主从式。结合粗粒度模型适合迁移操作的特点和主从式模型适合计算密集型任务的优势，本文采用粗粒度-主从式模型，上层用粗粒度模型，下层用主从式模型。

1.2 混合式的二级并行模型的设计

以往并行遗传算法，实现的一般是一级并行(MPI模式)，存在通信延迟、负载不均衡、核的数量少、同步困难等问题，加速比较低，不能充分发挥出并行算法的优势。考虑到“申威26010”众核处理器的物理结构和“粗粒度-主从式”混合并行遗传算法逻辑结构相似，本文设计和实现了混合式的二级并行的遗传算法，可以充分利用申威众核架构实现遗传算法的高度并行。

如图 1^[14]所示，一个处理器节点拥有4个核组(Core Group, CG)，每一个核组由一个主核(Management Processing Element, MPE)和64个按照8×8的Mesh拓扑结构构成的从核(Computing Processing Element, CPE)组成，且核组间由片上内部网络互联，并支持低延迟的寄存器级数据通信。图 2中p1、p2、p3、p4分别代表4个子种群，每一个子种群就是一个岛，各岛之间按粗粒度模型并行进化，每一子种群又按分配的从核数量分成n组，除最后一组外，其他各组包含同等数量的个体，组数n不超过N (N为每个核组内的从核数，当前为64)。组内的个体按主从式模型并行进化，初始化、选择、交叉、变异在主核中运行，适应度计算在从核中进行。通过将遗传算法中的各子种群映射到核组的主核上，将子种群内的各组映射到该核组的从核上，核组间采用粗粒度模式并行，核组内采用主从式模式并行，实现了种群间和种群内的两级并行，提高了算法的收敛速度和求解质量。

如图 3所示，为本文采用的主从加速并行的并行模型。主从加速并行方法是“太湖之光”计算机系统支持的两级并行方法，从核根据实际应用课题的核心计算内容进行众核加速，而主核完成同步、通信、I/O和串行代码的计算。本文的核心计算内容为适应度函数计算。为完成适应度函数的众核计算，首先初始线程库和创建线程组，启动核组中的所有可用资源。然后将种群内个体信息通过Athread加载到对应从核上，此时主核处于等待状态，从核进行众核加速计算，计算完成后通过Athread将个体信息写回主核。最后主核在确认线程组所有从核都完成任务后，停止从核流水线，关闭从核组，完成本次众核加速计算任务。

1.3 混合式的二级并行模型的实现

就并行编程来说，本文结合了消息传递和共享内存两种编程模型，即MPI和Athread的混合编程。MPI一般用于主核间的通信。而节点内部的工作可通过“申威26010”加速线程库(Athread库)完成，它是针对主从加速编程模型所设计的程序加速库，其目的是为了用户能够方便、快捷地对核组内的线程进行控制和调度，从而更好地发挥核组内多运算核心的加速性能^[22-23]。该混合编程模型分为两层：上层为粗粒度模型中岛间的并行，即每一个岛对应一个进程；下层为岛内部的并行，采用主/从式模型，主核上的进程启动多个从核上的线程并行执行，每一个从核运行一个线程，从而实现了进程和线程的两级并行。

进程并行的实现：将遗传算法的求解任务分解为若干个相对独立的子任务，为每一个子任务分配一个主核，即一个进程。子任务间的通信，使用MPI模型实现。进程间可以同步执行，也可以异步执行。文献[24]表明，异步执行由于达到执行条件时不需要获取其他进程状态就可以执行，减少了等待时间，所以比同步速度更快。

线程并行的实现：将上一步分解完成的子任务继续分解为二级子任务，每一个二级子任务对应核组的一个从核，即一个线程。因为核组内的若干线程共享内存，所以节点内使用共享存储的Athread实现并行编程。

本文采用混合并行编程模型的目的是充分利用申威众核系统的硬件资源，保证负载均衡，降低通信代价，从而提高并行程序的性能。若采用单一的MPI并行编程，实际只利用了主核的性能，核组内的从核没有能够发挥作用，浪费了宝贵的计算资源。采用混合并行编程模型后，由于进程内包含若干线程，各线程通过利用从核资源，使进程执行时间缩短，进程间通信延迟也相应降低，高效实现了进程和线程的两级并行，算法的性能得到较大的提升。

2 混合并行遗传算法描述及实现 2.1 混合并行遗传算法描述及流程

混合并行遗传算法流程如图 4所示。

主要步骤如下。

1) 初始化操作。程序通过调用MPI_Comm_size ()函数获得总进程数，并设定第0号进程为主进程，其他进程为从进程。主进程调用MPI_Bcast ()将染色体上下限参数以广播的方式发送给其他进程。从进程收到参数后，独立并行地在相应主核内初始化种群。

2) 适应度计算操作。从进程在主核内串行执行交叉、变异等操作，而后通过对应线程完成适应度计算。首先从核调用Athread_get ()函数，从主核内获取种群内个体信息，然后在从核内并行执行个体适应度计算，最后从核调用Athread_put ()函数，将计算好的个体信息返回主核。

3) 迁移操作。当遗传算法中每代的个体适应度值计算完成后，通过轮盘赌策略选出将要迁移的若干个体(本文为3个)，进程通过调用MPI_Isend ()函数，将选中的若干个体迁移到其他进程，而后通过MPI_Recv ()函数接收来自其他进程的迁移个体，并随机替换本种群中适应值小的若干个体。

4) 归约操作。若当前进化代数达到最大进化数，则跳出循环，停止执行以上操作，进入最后的归约操作。进程调用MPI_Reduce ()函数，在各子种群中选出最优个体作为最后结果。

混合并行遗传算法模型可以从两个方面实现，一是并行编程模型实现，二是混合并行遗传算法实现。

2.2 混合并行遗传算法实现

本文采用“粗粒度-主从式”混合并行遗传算法模型。模型包括上下两层，上层由粗粒度并行遗传算法模型构成，该层将整个种群划分为若干子种群，每一个子种群称作一个岛，对应一个核组的主核。岛与岛之间独立并行的执行遗传操作，当经过固定的进化代数，种群之间通过某种迁移策略进行岛之间的个体迁移，以交换种群信息，使种群内优良个体得以保留，种群多样性得以保持。下层由主从式并行遗传算法模型构成，岛内的遗传操作包括迁移、变异、交叉、适应度计算等，除了适应度计算，其他操作都由在主核上运行的进程串行执行，而进程内启动的若干线程按主从式模型在从核上进行适应度计算。

3 算法测试与结果分析

本文的测试函数为标准测试函数^[25-26]:

Rastrigin函数为f (x)=x₁²+x₂²-cos(18x₁)-cos(18x₂), x∈[-10, 10]²，全局最小值为-2.0。

Hansen函数为$f(x) = \sum\limits_{i = 1}^5 {i\cos [(i - 1){x_1} + i]} \sum\limits_{i = 1}^5 {} j\cos [(j + 1){x_2} + j],x \in {[ - 10,10]^2}$，全局最小值为-176.523364。

Rosenbrock函数为f (x)=100(x₁²-x₂)²+(1-x₁)², x∈[-2.048, 2.048]²，全局最大值为3905.926。

通过求函数的最小值测试遗传算法的性能。由于测试函数计算量小，执行时间短，不能充分体现出超算中从核的高性能。文献[27]指出，可以在适应度函数的计算语句中加入一个挂起语句，可以根据问题的规模，设置将系统挂起的时间，模拟等时间的计算量，以分析遗传算法针对不同规模问题的求解性能。本文也采用在适应度函数内加入挂起语句来增加计算量以模拟大规模问题的求解。

本实验的运算平台为无锡超算中心的神威“太湖之光”超级计算机，其硬件配置如表 1^[28]所示。遗传算法具体参数如下：杂交概率为0.8，变异概率为0.15，迁移个体为3。

为验证所设计HBPGA算法的性能，同时也为了测试申威众核处理器中从核的性能，实验采用4个评价指标：执行时间、从核加速比、加速比和求解精度。Rastrigin函数的测试结果反映在图 5、图 6和表 3中，Hansen函数和Rosenbrock函数的测试结果反映在图 7和图 8中。

图 5的种群大小为198，使用主核数为6，每个主核配11个从核，横坐标是进化代数，纵坐标是执行时间。图中MPI代表仅使用MPI通信，hybrid表示同时使用了MPI和Athread，即本文的HBPGA算法。由图 5所示，HBPGA的执行时间和执行时间的增长速度远小于纯MPI，执行速率最多提高了12.7倍。

一般并行算法性能的提升使用加速比指标，但本文的算法使用了大量从核处理器，需要有新的衡量指标即从核加速比来衡量从核的性能。从核加速比定义如下：固定的并行问题w，获取仅使用主核运行的情况下的并行运行时间T_g以及获取主核和从核共同进行处理情况下的运行时间为T_c，得到从核加速比S=T_g/T_c。获取串行执行时间T_s，得到加速比H=T_s/T_c。

表 2的种群大小107520，最大执行代数20，每个主核配64个从核。已测得串行执行时间为13683.1856 s。通过变化主核数得到表3。由表3可知，HBPGA随着主核的增加，从核加速比不断增加，当主核数为16时(从核数为16×64)，加速比达到544.38，从核加速比为31.85。

为考察主核固定情况下从核增加对性能的影响，将主核数固定为10，逐步增加从核数，得到图 6。图 6中种群大小6000，最大执行代数20。图中显示，随着从核数的增加，HBPGA的从核加速比随之增加。当从核数达到60时，从核加速比达到最大值24.74。

为衡量本文提出的HBPGA算法对解的质量的影响，采用Rastrigin函数进行了测试。测试中，种群大小设为198，执行30次实验，都能收敛，平均收敛代数为11.9，优于串行算法的收敛代数(同等参数约为15)。实验还使用Hansen函数和Rosenbrock函数在同等进化代数下对算法的执行时间进行了测试(图 7和图 8)，结果表明，与一级并行的MPI模型的算法相比，HBPGA算法在申威众核处理器下明显具有更短的执行时间。

4 结语

本文通过分析申威众核的物理拓扑和并行遗传算法逻辑结构，并结合两者的特点，设计出基于申威众核的“粗粒度-主从式”混合并行遗传算法，并进行了性能的比较和分析。该算法模型在众核架构上具有一定的通用性，可以通过替换不同的适应度函数解决不同的问题，应用于不同场景。利用MPI和Athread两种并行编程工具，使所设计的算法在申威众核处理器上实现进程级和线程级的两级并行。最后，对混合并行遗传算法进行了实验，实验表明，不论与传统串行遗传算法还是单纯采用MPI的并行遗传算法比较，本文提出的基于申威众核处理器的混合并行遗传算法在求解速度和收敛代数方面都有明显提高。

本文针对申威众核处理器和并行遗传算法进行了研究，还有很多后续的工作有待开展，如，对申威众核架构更深层次的研究和分析，对本文提出的混合并行遗传算法进一步性能优化，以及将算法应用于车辆导航、物流配送等组合优化问题等。