基于GPU的混合蛙跳算法改进

牛宝童 钱宇浛

摘  要： 【目的】 將混合蛙跳算法的求解过程转化为CUDA线程，提出并研究基于GPU的并行混合蛙跳算法，加快算法寻优过程，提高混合蛙跳算法的运算速度，以此促进群体智能优化算法的并行研究及应用。【方法】 本文采用了CPU+GPU异构形式进行计算，其中GPU负责对大规模的密集型数据进行设计分析以及计算，而对于CPU来讲，负责开展事务管理以及复杂逻辑运算等不适合数据并行的计算模块。【结果】 将混合蛙跳算法的求解过程转化为CUDA线程，实现基于GPU的并行混合蛙跳算法。在GPU上加速执行以提高算法运行速度，在保证与串行混合蛙跳算法相同优化性能的同时提高加速比。【结论】 （1）对于ISFLA算法它采用了并行调度的形式展开计算分析，对于虚拟机之间的负载起到了很好的平衡作用，减小了负载间的平衡度对于整体的工作时间来讲起到了很好的缩短作用。（2）ISFLA算法产生的初始种群有着更好的质量，这能够将一些表现不好的个体进行排除，加快了整体的收敛速度，减小了进行搜索迭代的时长。

关键词： 混合蛙跳算法;图形处理器;统一计算设备架构;群体智能优化算法

中图分类号： TP391.41    文献标识码： A    DOI：10.3969/j.issn.1003-6970.2020.07.031

本文著录格式：牛宝童，钱宇浛. 基于GPU的混合蛙跳算法改进[J]. 软件，2020，41（07）：152-158

Improved GPU-based Hybrid Frog Leaping Algorithm

NIU Bao-tong¹， QIAN Yu-han²

（1. College of Information Science and Technology， Gansu Agricultural University， Lanzhou 730070， Gansu， China;2. China Aerospace Science and Technology Corporation，Ninth Research Institute， Beijing 100094， China）

【Abstract】： [Objective] Transform the solution process of the hybrid frog leap algorithm into a CUDA thread， propose and study a parallel hybrid frog leap algorithm based on GPU， speed up the algorithm optimization process， increase the operation speed of the hybrid frog leap algorithm， and promote parallel research and application of swarm intelligent optimization. [Method] It adopts the CPU + GPU heterogeneous model. The CPU is responsible for performing complex logic processing and transaction management that are not suitable for data parallel computing. The GPU is mainly responsible for computing-intensive large-scale data parallel computing. [Results] The solution process of the hybrid frog leap algorithm is transformed into a CUDA thread， and a parallel hybrid frog leap algorithm based on GPU is realized. Accelerate the execution on the GPU to increase the speed of the algorithm， and improve the speedup while ensuring the same optimized performance as the serial hybrid frog leap algorithm. [Conclusion] （1） The ISFLA algorithm uses a parallel scheduling model to execute tasks， which effectively balances the load between virtual machines， reduces the load balance degree， and shortens the overall completion time of the workflow. （2） The quality of the initial population generated by ISFLA is better， which can effectively exclude some poorly performing individuals， thereby shortening the search iteration time and accelerating the convergence speed.

【Key words】： Hybrid frog jumping algorithm; graphics processor; unified computing device architecture; swarm intelligence optimization algorithm

0  引言

目前伴随着科学技术的快速发展，在进行科研以及日常活动中经常会碰到一些需要进行最优化求解的问题，对于最优化求解的问题如何获得一种既简单有高效的方式目前成为众多学者要开展研究的主要方向之一。目前来看，众多的学者已在众多的领域开展了混合蛙跳算法的应用，来获得更好的最优解，目前也已经取得了重要的成果。

混合蛙跳算法的靈感来自于对大自然中集体觅食的青蛙，针对这种觅食性行为开展了智能的仿生学算法，这种算法中存在以下优点即：思想容易理解、可变因子数目少、并行的搜索项目少等，这些优点使它成为了在求解最优化问题的关键，但是这种算法也存在它的弊端，比如：较慢的收敛速度以及过度依赖初始值等。

在GPU和CPU同时作用环境下展开的资源调配，进过众多的研究主要包含了下面两种方法：

当出现了资源设备存在较多的任务需求时，可以采用优先分配的原则来将这些资源进行分配，但是分配方案存在单一性，考虑的问题无法满足客户的要求。

如果出现资源设备空闲了大量的资源，我们可以将一些任务分配给这样的设备

综上所述，本文研究重点为设计出一种既能保障负载均衡又能保障计算速度的先进行的资源分配方案。

本文的通过分析研究，将混合蛙跳算法进行改进，同时在CPU+GPU的环境中展开新型算法的研究。由于原有的混合蛙跳算法在GPU运算时存在一系列的缺点，容易陷入到局部最优的环境中，同时在群组中交流较少，所以对其进行改进，改进厚的算法较少了工作流完成时间和提高搜索效率两方面工作。

1  研究背景及意义

人类发展至今，在开展一系列的生产活动中针对于要进行解决的问题，都会在众多的方案中进行比较分析以及判断，来得出一种最佳的解决方案，这一过程我们就可以将其看成为最优化问题^[1]。这也是一个古老的研究课题，对于最优化求解问题，就是指在进行满足一系列的条件要求下，来得出一套最优的问题解决方法或参数，将问题圆满的解决。

对于最优化问题的求解主要包含以下两种方法即构造型及经典型算法。构造型算法^[3]主要通过一定的原理来实现构造形式来解决具体的问题，效率比较高但是求解的质量难以保障，采用不同的规则原理也同样会对解的质量产生重要影响，对于该算法应用比较典型的实例为讷河算法以及约翰逊-贝尔曼法则。而经典算法则是依据数学计算展开比如：单纯形法以及牛顿法等^[2]，该算法在初始阶段会选择一个初始解，并按照一定的方式完成最优解的搜索，当出现满足要求的情况则停止搜索，但是该方法存在一定的局限性，比如对于全局的搜索速度过慢，同时难以达到最优解。对于存在高维度、非线性、不可微分等众多复杂的优化问题，上述两种方法对于具有这种特征的问题难以解决，为了能能更加完美的解决该问题，学者们经过研究提出了群体智能算法^[4]，该方法也称为邻域搜索算法。该方法起点一般选取若干临时解，在特定的规则下，对这些解的邻域展开搜索，并且通过迭代替换来提高求解的质量。该方法主要是并行计算，来在短时间内取得最优解，防止陷入局部最优情况。

混合蛙跳算法^[5]为近几年迅速兴起的一种新型算法，在群体智能算法这一领域中逐渐占有重要的地位，该算法由Kevin E.Lansey以及Muzaffar M.Eusuff两位学者提出^[6]，他们通过对青蛙觅食行为的深入研究，得到的仿生智能算法，这种算法有着信息共享以及交互的能力，同时结构框架也非常的简单，但是也存在一定的缺点，比如容易陷入局部优化等，该算法目前在应用以及理论研究中并不是很成熟，所以如何更好的改进这种算法的性能，已成为众多学者研究的重点。

因此，本篇论文将针对现有的混合蛙跳算法理论以及成果，以及算法本身存在的缺点^[7]，有针对性的开展相关研究，从高效和运算速度两方面来进行创新和改进，并将其与CPU+GPU相结合，实现异构形式，该论文将改进后的混合蛙跳算法投入到工作流完成时间和搜索效率试验中，取得了很好的效果。

2  混合蛙跳算法机理

SFLA是一种全新的启发式群体进化算法^[8]，具有高效的计算性能和优良的全局搜索能力。在模拟青蛙觅食过程时，假定在一片湿地生活着一群青蛙，首先，按照种群将青蛙分成多个子群，各子群中通过内部信息交流来优化内部个体;然后，为了实现全局的信息交换，再按照优劣顺序融合子群中的青蛙个体进行排序，之后再按照之前划分的规则划分青蛙种群。经过模拟可看出，混合蛙跳算法可以通过局部信息的交流和全局信息交换相结合的方式搜索寻优，便于一定程度上推迟局部极值点的出现。SFLA相关的概念见表1。

4  改进混合蛙跳算法的并行实现

4.1  CUDA动态并行技术

当前，该动态并行技术中是在host端调用全部的kernel，同时CPU负责控制GPU的具体运行状态以及工作内容。device端GPU kernel的创建以及调用，由CUDA Dynamic Parallelism进行控制。CUDA Dynamic Parallelism的使用降低了递归算法的调用难度以及增强了它的可理解性，同样它的启动配置是由device上运行中的thread来决定，这种方式可以极大地降低device与host之间的控制执行以及数据传递。本文利用CUDA动态并行技术，把迭代的过程都迁移到GPU上进行，减少CPU和GPU之间的数据传输和指令的延迟。

在算法中，由于递归比较消耗资源，所以如果可以的话最好是展开，但在本文中我们要实现递归，这部分主要就是再次证明DynamicParallelism的好处，有了它就可以实现像C那样写递归代码了。

kernel的调用增加了一个参数iDim，这是因为每次递归调用，child block的大小就减半，parent 的blockDim必须传递给child grid，从而使每个thread都能计算正确的global memory偏移地址。注意，所有空闲的thread都被移除了。相较于之前的实现，每次都会有一半的thread空闲下来而被移除，也就释放了一半的计算资源。以下为运行在Kepler K40上的结果：

1. $ nvcc -arch=sm_35 -rdc=true nestedReduce. cu -o nestedReduce -lcudadevrt

2. /nestedReduce starting reduction at device 0： Tesla K40c

3. array 1048576 grid 2048 block 512

4. cpu reduce elapsed 0.000689 sec cpu_sum： 1048576

5. gpu Neighbored elapsed 0.000532 sec gpu_ sum： 1048576<<>>

6. gpu nested elapsed 0.172036 sec gpu_sum： 1048576<<>>

对于一个给定的算法，我们可以有很多种实现方式，避免大量的nested调用可以提升很多性能。同步对算法的正确性至关重要，但也是一个消耗比较大的操作，block内部的同步操作倒是可以去掉。因为在device上运行nested程序需要额外的资源，nested调用是有限的。如图2所示，本文中的cuda代码中已经把处理过程都放到了sfla这个核函数里进行处理。

4.2  生成随机数

curand由两部分组成：host端的库和device端的头文件。host端的库就像其他的CPU库一样curand.h，随机数可以在设备端生成或者CPU端生成。在设备端生成的时候，对库的调用发生在host端，但是随机数的生成实际上发生在device端，随机数存储在global memory中，用户可以调用kernel直接使用这个随机数，也可以将此随机数拷贝回kernel。

device端的库头文件curand_kernel.h，这个头文件里面定义了设置随机数生成器的状态以及生成一系列随机数的设备函数，使得kernel可以调用函数生成随机数，而不需要从global memory处读写。

生成随机数除了可以使用不同的算法（由参数决定）以外，還能生成不同分布、不同浮点类型的随机数，这根据调用的生成随机数的API决定。

如图3所示，本文选用的API是curand_uniform，用于生成服从均匀分布的float。

4.3  转换一维线性储存结构

目前，取隐藏和减少latency的措施分为两种：

（1）首先内存的读取是要通过众多线程采用并行的方式不断进行，并行的概念可以理解为在读取thread内存过程中，每读到一个内存在等待计算其结果的时候，GPU可以立即读取下一个内存，同时切换到接下来的一个thread，其目的是将latency最大限度的进行隐藏。

（2）在内存中通过采用连续存储方式，最大限度地减少latency。

而通过分散访问可以有效提高单位时间内的访问次数，warp在进行不同地址数据之间的访问过程中，这些数据是离散的，其结果造成warp无法合并进行这些数据并进行访问，在一个flot由每一个thread进行访问的过程中，其总的访存指令需要被进行32次。如图4所示，在L1范式分散访问中，当访存请求的内存在0～383区间时，cache的有效率计算为128/384=33%。

针对L2范式，在同样的scatterd情况下，它的cache的有效率为128/192=67%，该结果具相比L1具有更高的优势。

如图6所示，本文通过将二维结构转换为一维线性储存结构，能提高内存访问的效率。

4.4  创建共享内存储存最优解

请求多次执行的现象会因为bank conflict的发生而发生，其根本原因是同一个bank中收到了多个地址的请求。当这种情况发生时，这种请求会被最大程度上分散到没有conflict的操作中。被分散到的传输操作个数是将有效带宽进行降低的一个因素，获得shared memory的经典方式在warp中主要有 三种：

（1）一次传输可以将一些或者全部的地址请求全部解决，这种模式主要是在Parallel access模式中，这种模式的含义就是如此，就是在得到没有conflict的shared memory的过程中，不同的地址都会存放在不同的bank里面，这是它的理想状态。

（2）当warp中的32个thread在访问bank过程中，没有重复现象发生，即每个thread对应了不同的位置，那就表示这是单独的访问，这种方式又被称为Serial access模式，这种情况是我们最不愿意看到的情况。

（3）另一种模式是Broadcast access模式，这种模式只执行一次传输，之后所有发出请求的thread都会收到传输的结果，这样必然会降低带宽的利用效率。

访问图示如下所示。

最优情况的是，不一样的bank值可以被分配到同一个的warp中的thread，用连续的threadIdx.x可以确定相同warp中的thread值，这里将以word的大小作为偏移量，将bank中的元素进行连续存储。所以shared Memory中的地址最好能够使用由具有连续性的thread来确定，而thread的连续性可以通过threadIdx.x的连续性来保证。最终我们可以得到tile[threadIdx.y][threadIdx.x]使能够表现出更加优异的成绩以及bank conflict的最少化。综上，如图8所示，可以通过创建共享内存储存最优解，来提高读取效率。

4.5  分配线程处理

在实际运行CUDA的过程中，我们将每个block分配到SM中计算，这里是以block为单位进行，同样warp作为block中thread的单位，将thread分组，然后对每组进行相关的计算，这里常取32个thread作为一个组，形成一个warp来共同执行，这也是当前CUDA中warp的大小是32的原因。同一个warp中的thread执行的指令是相同的，只是处理的数据不同。

通常情况下，我们以连续的方式进行分组，并且该过程是通过SM自动进行，最终完成warp的分组行为。一个block中的每个warp通常会被SM以一次一个的形式来执行，不过一个warp中的所有指令并不会被SM一次性全部执行完成。当前正在被执行的warp需要延迟的时候，比如global memory的存储就会耗费很长时间，此时通过调节其它warp来进行继续的工作，从而可以提高整体的工作效率。所以，当SM中有足够多的warp可以进行调用和调节时，此时的效率最高;这样不会发生全部warp都需要延时处理的情况发生，即耗费运算时间。

每个在CUDA中的SM的最小执行单位可以看作是warp，当我们的GPU有16组SM时，可以进行的实际thread数目能够达到32*16，但是因为thread的等待、延迟等需要被隐藏，并且该种隐藏方式正是由CUDA经warp的切换来实现的，最终可以实现平行化的数量最大化的目标。因此同一时间在一个SM中可以处理的thread数目可以通过名为active thread的指标来进行描述。另一个方面就是在block方面，多个thread block可以在同一时间由一个SM进行处理，若一个block中的所有thread被计算完成之后，算法会继续寻找另外没有完成处理的block进行处理。现在若存在64个block、16个SM，一个SM对应三个block，在算法的开始阶段，device会同时进行48个block的处理，当有SM处理完block之后会进行剩余block的处理，直至处理完全部的block。

所以本文在启动核函数时，需要为每个frog分配一个线程进行处理，如图9所示。

5  结果讨论

5.1  工作流完成时间试验

工作任务的调度对于负载平衡情况的影响可以从工作流完成时间的长短来进行判断，在虚拟机上的等待的队列越长那么体现为负载的平衡程度越高，进而说明完成全部工作流所需要的时间边长了。本文设计实验的参数设置为：迭代次数分别定为100，200，400和800，固定迭代次数不变，不同算法对于工作流的完成情况是由不同的任务数来进行对比体现，最终体现在时间的变化上，其结果如图10。

通过图10可以看出，完成工作流所用时间最少的调度方案是并行蛙跳实验ISFLA算法，本文用的是其改进算法。3种算法的运行时间差异比较小的原因主要是在任务数小于1000的情况下，因为此时受虚拟资源充沛的影响，没有发生超负载现象。超负载现象是随着任务数量的增加而增加的，通过图5可以明显看出，完成所有工作流的时间上，ISFLA算法得到的方案最低。主要是该算法将虚拟机之间的负载之间进行了有效的平衡，大大减少了全部工

5.2  搜索效率试验

ISFLA算法在应用过程中，其局部搜索所耗费的时间很大程度上取决于初始化中种群的质量，所以初始化阶段产生的个体对于该算法在后续的全局搜索中有很大的影响，将改进的混合蛙跳算法用于初始化是否优于随机方式产生的初始化群体时我们这次进行实验的主要目的，本实验采用的初始化数据群是由两种不同策略产生的，然后将其分别应用在ISFLA算法中，比较算法在局部搜索过程中耗费的时间以及任务数量的关系，结果如图11。

从上图中可以看出，迭代次数一定，在局部搜索过程中两种方法都会随着工作流任务数量的增加而增大，但是ISFLA算法中提出的时间贪心理念使得其在搜索过程中时间的增长更加平稳。纵向来看，搜索迭代时间在经过ISFLA算法初始化种群之后较原算法有很大的降低。主要是因为ISFLA算法初始化种群中的个体更加具有可计算性、稳定性、以及代表性，减少了差异化个体的产生几率，从而可以降低算法运行时间，也使得算法的收敛速度进一步提高。

参考文献

1. 肖晓伟， 肖迪， 林锦国等. 多目标优化问题的研究概述[J]. 计算机应用研究， 2011（03）： 11-14+33.

2. 李淑萍， 闫坤， 李环等. 利用单纯形法优化点到曲面的最近距离[J]. 图学学报， 2006， 27（1）： 116-118.

3. 刘金琨， 孙富春. 滑模变结构控制理论及其算法研究与进展[J]. 控制理论与应用， 2016， 24（03）： 407-418.

4. 李素， 袁志高， 王聪等. 群智能算法优化支持向量机参数综述[J]. 智能系统学报， 2018， 13（01）： 70-84.

5. 崔文華， 刘晓冰， 王伟等. 混合蛙跳算法研究综述[J]. 控制与决策， 2012（04）： 3-8+15.

6. EUSUFF M M， LANSEY K E. Optimization of Water Distribution Network Design Using the Shuffled Frog Leaping Algorithm[J]. Journal of Water Resources Planning & Management， 2003， 129（3）： 210-225.

7. 赵鹏军， 刘三阳. 求解复杂函数优化问题的混合蛙跳算法[J]. 计算机应用研究， 2009（07）： 41-43.

8. 罗雪晖， 杨烨， 李霞. 改进混合蛙跳算法求解旅行商问题[J]. 通信学报， 2009， 30（7）： 130-135.

9. 王丽萍， 孙平， 蒋志强等. 基于并行云变异蛙跳算法的梯级水库优化调度研究[J]. 系统工程理论与实践， 2015， 35（3）： 790-798.

10. 阳春华， 钱晓山， 桂卫华. 一种混沌差分进化和粒子群优化混合算法[J]. 计算机应用研究， 2011， 28（2）： 439-441.

11. 易文周， 田立伟. 一种基于混沌搜索和鲶鱼效应策略的粒子群算法[J]. 计算机应用与软件， 2013， 30（5）： 311-315.

12. 姜伟， 王宏力， 何星， 等. 并行免疫离散粒子群优化算法求解背包问题[J]. 系统仿真学报， 2014， 26（1）： 56-61.

13. 纪昌明， 刘方， 彭杨等. 基于鲶鱼效应粒子群算法的水库水沙调度模型研究[J]. 水力发电学报， 2013， 32（1）： 70-76.

14. 金荣洪， 袁智皓， 耿军平等. 基于改进粒子群算法的天线方向图综合技术[J]. 电波科学学报， 2006， 21（6）： 873-878.