计算机应用   2016, Vol. 36 Issue (12): 3274-3279  DOI: 10.11772/j.issn.1001-9081.2016.12.3274
0

引用本文 

张硕, 何发智, 周毅, 鄢小虎. 基于自适应线程束的GPU并行粒子群优化算法[J]. 计算机应用, 2016, 36(12): 3274-3279.DOI: 10.11772/j.issn.1001-9081.2016.12.3274.
ZHANG Shuo, HE Fazhi, ZHOU Yi, YAN Xiaohu. GPU parallel particle swarm optimization algorithm based on adaptive warp[J]. JOURNAL OF COMPUTER APPLICATIONS, 2016, 36(12): 3274-3279. DOI: 10.11772/j.issn.1001-9081.2016.12.3274.

基金项目

国家自然科学基金资助项目(61472289);湖北省自然科学基金资助项目(2015CFB254)

通信作者

何发智(1968-),男,湖北武汉人,教授,博士,CCF会员,主要研究方向:计算机支持的协同工作、计算机图形学、图像处理、并行计算, fzhe@whu.edu.cn

作者简介

张硕(1992-),男,湖北仙桃人,硕士研究生,主要研究方向:计算机图形学、GPU并行计算;
周毅(1983-),男,湖北汉川人,高级工程师,博士研究生,主要研究方向:GPU通用计算、智能优化算法;
鄢小虎(1986-),男,湖北武汉人,高级工程师,博士研究生,CCF会员,主要研究方向为:软硬件协同设计、智能优化算法

文章历史

收稿日期:2016-06-03
修回日期:2016-07-06
基于自适应线程束的GPU并行粒子群优化算法
张硕, 何发智, 周毅, 鄢小虎    
武汉大学 计算机学院, 武汉 430072
摘要: 基于统一计算设备架构(CUDA)对图形处理器(GPU)下的并行粒子群优化(PSO)算法作改进研究。根据CUDA的硬件体系结构特点,可知Block是串行执行的,线程束(Warp)才是流多处理器(SM)调度和执行的基本单位。为了充分利用Block中线程的并行性,提出基于自适应线程束的GPU并行PSO算法:将粒子的维度和线程相对应;利用GPU的Warp级并行,根据维度的不同自适应地将每个粒子与一个或多个Warp相对应;自适应地将一个或多个粒子与每个Block相对应。与已有的粗粒度并行方法(将每个粒子和线程相对应)以及细粒度并行方法(将每个粒子和Block相对应)进行了对比分析,实验结果表明,所提出的并行方法相对前两种并行方法,CPU加速比最多提高了40。
关键词: 粒子群优化算法    并行计算    图形处理器    统一计算设备架构    自适应线程束    
GPU parallel particle swarm optimization algorithm based on adaptive warp
ZHANG Shuo, HE Fazhi, ZHOU Yi, YAN Xiaohu     
School of Computer, Wuhan University, Wuhan Hubei 430072, China
Abstract: The parallel Particle Swarm Optimization (PSO) algorithm was improved through Graphics Processor Unit (GPU) based on Compute Unified Device Architecture (CUDA). According to the structural characteristics of the CUDA hardware system, it can be concluded that block is executed serially and the basic scheduled and executive unit of Streaming Multiprocessor (SM) is warp. GPU parallel PSO algorithm based on adaptive warp was carried out in order to make full use of thread parallelism in the block. The dimensions of particles were corresponded to the threads of particles. Each particle was corresponded to one or more warps in accordance with its self-dimension adaptively by using the warp level parallelism of GPU. One or more particles were corresponded to each block. Comparison with the existing coarse-grained parallel approach (corresponding each particle to the thread) and fine-grained parallel approach (corresponding each particle to the block) was made, and the experimental results show that the proposed parallel approach achieves CPU speed-up ratio of 40 more than two kinds of approaches mentioned above.
Key words: Particle Swarm Optimization (PSO) algorithm    parallel computing    Graphic Processing Unit (GPU)    Compute Unified Device Architecture (CUDA)    adaptive warp    
0 引言

粒子群优化(Particle Swarm Optimization,PSO)算法[1]是一种演化计算技术,由于其概念简单、易于实现,同时又具备较强的全局搜索及收敛能力等特点,而得到了快速的发展和广泛的应用[2]。但由于实际问题的多元化和离散化,特别是NP(Non-deterministic Polynomial)类问题的复杂性和数据处理的高密性,使得其求解的速度相对较低[3]。基于PSO算法粒子之间互不干预的特点,并行化加速方案为该问题提供了有效的解决方法。

随着图形处理器(Graphic Processing Unit,GPU)技术的高速发展,其浮点计算能力已经可以达到CPU的10倍以上[4],这使得基于GPU的通用计算(General-Purpose computing on the GPU,GPGPU)技术成为高性能计算研究与应用的热点[5-6]。NVIDIA公司率先提出了统一计算设备架构(Compute Unified Device Architecture,CUDA),它提供了使用C语言和C++语言来开发GPU加速应用程序的综合开发环境[7],具有极强的可编程性,是目前最为流行的GPU编程语言之一。

Veronese等[8]首次使用CUDA实现的并行粒子群优化(Particle Swarm Optimization,PSO)算法,掀起了并行PSO算法研究的热潮,涌现出各种并行PSO算法版本。这其中,针对CUDA并行架构,对线程的分配方案主要有两种:1)一个线程对应一个粒子[8-10];2)一个线程对应一个维度,一个Block对应一个粒子[11]。第一种粗粒度并行方法,虽然已经取得了不错的加速比,但由于每个线程中粒子所对应的每个维度仍然是串行执行的,并行程度并不高。第二种细粒度并行方式在第一种的前提下作了改进,将每个粒子对应到每个Block,再将每个Block中的线程对应到每个粒子中的一个维度。这样无疑加大了并行程度,但值得注意的是,在CUDA 并行程序中,所有的Block是被串行地分配到每一个流多处理器上的[12]。在第二种方法的基础上还可以继续提高并行度,为此本文提出以下方法:一个线程对应一个维度,一个或多个Warp对应一个粒子,一个或多个粒子对应一个Block。这样可以进一步地提高其并行度。实验结果表明,相比前两种方法,本文提出的自适应线程束的并行方法相对前两种并行方法,CPU加速比最多提高了40。

1 标准粒子群优化算法

粒子群优化(PSO) 算法是一种通过模拟鸟群觅食过程中的迁徙和群集行为所发展起来的基于群体智能的演化计算技术[14]。在PSO算法中,鸟群中的每只鸟被抽象为一个粒子,N个粒子组成一个粒子群。每个粒子的位置Xid代表在D维的目标搜索空间中的一个潜在解,每个解都可以通过适应度函数Fitness(Xid)求得该粒子的适应度Fi,以判断该解的好坏程度。粒子以时间为单位进行连续迭代以模拟鸟类飞行过程,每个粒子有一个速度Vid决定它们每次迭代的方向和距离。粒子的速度通过跟踪两个“极值”来决定。 第一个极值是粒子自身所找到的最好适应度Fib对应的解,这个解叫作个体极值Pidb;另一个极值是整个粒子群到目前为止找到的最好适应度Fgb对应的解,这个解叫作全局极值Pdgb。当粒子群从时刻t飞行迭代到时刻t+1时,每个粒子将根据式(1)~(2)来更新自己的速度和位置:

$\begin{align} & {{V}_{id}}(t+1)=w{{V}_{id}}(t)+{{c}_{1}}{{r}_{1}}(P_{id}^{b}(t)-{{X}_{id}}(t)) \\ & +{{c}_{2}}{{r}_{2}}(P_{d}^{gb}(t)-{{X}_{id}}(t)) \\ \end{align}$ (1)
${{X}_{id}}(t+1)={{X}_{id}}(t)+{{V}_{id}}(t)$ (2)

其中:i=1,2,…,N;d=1,2,…,D;非负常数c1和c2成为加速因子,r1和r2是[0,1]区间中均匀分布的随机数。惯性权重系数w用来衡量前一时刻Vid(t)对后一时刻速度Vid(t+1)的影响程度。速度Vid∈[-Vmax,Vmax],其中Vmax限制粒子每个维度的最大速度不能超过Vmax。位置Xid∈[-Xdown,Xup],其中-Xdown限制粒子每个维度的向后最远位置不能低于-Xdown,Xup限制粒子每个维度的向前最远位置不能高于Xup

标准粒子群优化算法的流程如图 1所示。

图 1 标准粒子群优化算法的流程

本文使用的CPU-PSO算法版本,是标准PSO算法——Standard PSO version 2006[15]。其中惯性权重系数w,加速因子c1和c2的取值如式(3)~(4)所示:

$w=1/\left( 2*\ln \left( 2 \right) \right)$ (3)
${{c}_{1}}\text{=}{{c}_{2}}\text{=}0.5\text{ }+\text{ }ln\left( 2 \right)$ (4)
2 CUDA并行计算模型

CUDA并行计算模型是一种SIMD(单指令多数据)的并行化计算模型[16],其中GPU作为一个协处理器产生大量线程,可以帮助CPU完成高度并行化的大量简单计算工作。CUDA采用多层存储器的架构模型[3](见图 2),共有三个不同的层次:线程(Thread),线程块(Block)以及块网格(Grid)[16]。Thread运行在流处理器(Streaming Processor,SP)上,是其中最基本的执行单元,每个Thread拥有一个私有的寄存器,多个执行相同指令的Thread可以组成一个Block。Block运行在流多处理器(Streaming Multiprocessor,SM)上,一个Block内所有的Thread可以通过Block内的共享内存(Share Memory)进行数据通信和共享,并实现同步,多个完成相同功能的Block可以组成一个Grid。Grid运行在流处理器阵列(Streaming Processor Array,SPA)上,同一个Grid中的Block之间不需要通信,且Gird间的执行是串行的。即当程序加载时,Grid加载到GPU上之后,所有的Block被串行地分配到每一个流多处理器上[12]。因此,必须合理地分配每个Block中的线程数,以便更好地提高并行度[17]

图 2 CUDA并行计算模型

实际运行中,Block会被分割为更小的线程束Warp[3]。在一个SM上,每个Block中的线程按照其唯一的ID进行顺序分组,相邻的32个线程组成一个Warp。逻辑上所有的thread都是并行的,但是从硬件的角度来讲,并不是所有的thread能够在同一时刻执行,Warp才是SM调度和执行的基本单位。在CUDA编程模型之中并没有抽象出Warp的定义,Warp是由GPU的硬件结构决定的,但却对性能影响很大。同一Warp内的线程可以认为是“同时”执行的,不需要进行同步也能通过shared memory进行通信,可以进一步地节省调用__syncthreads( )函数对线程进行同步所消耗的时间。综上所述,增加每个Block中线程的使用量,并以Warp为单位考虑对Block中线程数分配的优化,可以获得更高性能。

3 基于CUDA的并行PSO算法 3.1 并行性对比 3.1.1 粗粒度并行方法

线程对应粒子的分配方案,其并行性主要体现在以下三个方面:

1) 每个粒子的速度和位置的更新是可并行的;

2) 每个粒子的适应度值的计算,下一代粒子自身所找到的最好适应度值及其对应的解的更新是可并行的;

3) 整个粒子群到目前为止找到的最好适应度值及其对应的解的更新是可并行的。

每次迭代过程,都必须按1)、2)、3)的顺序执行,因为下一步的执行需要用到上一步每个粒子计算得到的结果。因此,这里需要为每个步骤都设计一个单独的kernel核函数[18]。虽然多个核函数会带来核函数启动的时间消耗,但这里不能将这三个核函数合并为一个,因为在CUDA程序中虽然能通过调用__syncthreads( )使Block内的所有线程同步执行,但由于不同的Block之间是串行执行的,不同Block中的线程只能通过结束kernel来达到同步的效果[13]

由于步骤3)中只涉及到粒子数目的多少,和本文重点讨论的粒子维度并没有关系,所以本文使用CUBLAS的cublasI〈t〉amin( )函数(t为操作对象的数据类型)在GPU上求得整个粒子群到目前为止找到的最好适应度值及其对应的解。CUBLAS是NVIDIA公司免费提供的基于CUDA的BLAS(基本线性代数库)的GPU并行版本[16],其底层实现为并行规约(Reduction)算法[13]

根据以上对一个线程对应一个粒子方案的分析,可得到其算法飞行更新迭代流程如图 3所示。

图 3 粗粒度飞行更新迭代流程
3.1.2 细粒度并行方法

线程对应维度,Block对应粒子的分配方案,其并行性在粗粒度方法基础对步骤1)、2)有所改进:

1) 粒子速度和位置的每个维度的更新是可并行的。

2) 粒子每个维度的适应度值的计算,以及下一代粒子自身所找到的最好适应度值所对应的解每个维度的更新是可并行的。每个维度的适应度值计算完成后,需要通过并行规约(Reduction)算法[13]求取该粒子的适应度值。

根据以上对细粒度方法的分析,使用一个Block来包含一个粒子,将Block中的每个线程对应到该粒子的每一个维度,可以使得粒子的维度也并行化,达到Block级并行的效果。由此可得到其算法飞行更新迭代流程如图 4所示。

图 4 细粒度飞行更新迭代流程
3.1.3 自适应线程束并行方法

细粒度的方法虽然将粒子维度的更新也并行化了,达到了Block级的并行效果。但是通过第2章对CUDA计算模型的分析可知,增加每个Block中线程的使用量,并以Warp为单位考虑对Block中线程数分配的优化,可以获得更高性能。

本文提出的自适应线程束的并行方法,就是基于CUDA计算模型的特点,将每个粒子的维度划分为一个或多个Warp,然后使用Block来包含这些Warp,使得一个Block中对应一个或多个粒子,从而增加每个Block中线程的使用量,达到Warp级别并行的效果。

同时,粒子所对应Warp的个数WarpNum及Block所对应的粒子数ParticleNum都会根据粒子维度D的大小进行自适应的调整。具体的自适应过程遵循如式(5)~(7)所示:

$\text{WarpNum}=\text{DivUp(D, WarpSize)}$ (5)
$\text{ThreadNum}=\text{WarpNum*WarpSize}$ (6)
$\begin{align} & \text{ParticleNum}= \\ & \text{DivDown(BlockSize, ThreadNum)} \\ \end{align}$ (7)

其中:WarpSize表示CUDA架构中一个Warp的大小。通常一个Warp有32个线程,但实际上同时运行的只有16个线程,即HalfWarp,所以这里将WarpSize定义为16。DivUp函数的功能是将D除以WarpSize得到的商作向上取整,以得到粒子所对应Warp的个数WarpNum。ThreadNum用来表示每个粒子实际用到的线程总数。BlockSize表示CUDA架构中一个Block的大小。通常一个Block最多可包含1 024个线程,但考虑到当Block中线程数使用太高反而会导致拥堵使性能降低,这里将BlockSize定义为512。DivDown函数的功能是将BlockSize除以ThreadNum得到的商作向下取整,以得到Block所对应的粒子数ParticleNum。

根据以上对自适应线程束方法的分析,可以将粒子的维度自适应地整合为一个或多个Warp,同时使用一个Block来自适应地包含这些整合后的一个或多个粒子,以提高Block中线程的使用量,达到Warp级并行的效果。由此可得到其算法飞行更新迭代流程如图 5所示。

图 5 自适应线程束飞行更新迭代流程
3.2 自适应线程束并行方法设计

根据以上对自适应线程束方法并行性的分析,可以得到其GPU并行PSO算法设计步骤如下:

1) 在CPU端调用malloc( )函数,为粒子群分配CPU内存,并将该粒子群初始化;

2) 在CPU端调用cudamalloc( )函数,为粒子群分配GPU全局内存;

3) 在CPU端调用cudaMemcpy( )函数,将CPU端的粒子群信息传输到GPU端;

4) 在CPU端创建for循环完成更新迭代,在for循环中顺序调用kernel函数,执行GPU端的并行计算过程;

5) 在CPU端调用cudaMemcpy( )函数,将GPU端的粒子群信息回传到CPU端;

6) 在CPU端调用free( )函数和cudaFree( )函数,释放CPU端和GPU端分配的变量空间,防止内存泄漏。

需要注意的是,由于CUDA对二维数组的支持并不好,所以需要在步骤2)分配GPU全局内存时,将变量空间设计成展开了的二维数组所对应的一维数组的形式。同时在步骤3)与步骤5)在CPU与GPU之间传值时,需要有一个CPU端的一维数组作桥梁,以便CPU端的二维数组与GPU端的一维数组之间的传值。

这个CPU/GPU之间传值的过程是十分耗时的,但是整个并行PSO算法运行的过程中却只执行了一次这个来回传值过程。在计算加速比时,由于这个传值过程的干扰,使得加速比并不纯净,特别是在问题规模较小时,数据传输占比越尤为明显[19-20]。所以本文只计算步骤4)所消耗的时间,以避免传值对加速比的干扰,并将其称为“纯净加速比”。本文第4章提供的实验结果均采用“纯净加速比”作为参考,其中三种GPU并行方法共享相同的CPU/GPU传值的过程,只有核心的并行迭代过程(步骤4中的kernel函数)不同,以保证这三种方法在相同情况下消耗相同的CPU/GPU传值时间,消除其对“纯净加速比”的干扰。

根据3.1.3 节对自适应线程束并行方法的分析,可知步骤4)中for循环里面应当包含两个kernel核函数kernel1( )和kernel2( )以及一个CUBLAS库函数cublasI〈t〉amin( )函数。下面对核函数kernel1( )和kernel2( )作具体说明:

在调用核函数之前,首先需要确定CUDA的Block的大小BlockNum及Grid的大小GridNum,以体现自适应线程束方法的特点,具体如式(8)~(9)所示:

$\text{BlockNum}=\text{TreadNum*ParticleNum}$ (8)
$\text{GridNum}=\text{DivUp(N, ParticleNum)}$ (9)

kernel1( )核函数的主要功能是更新每个粒子每个维度的Vid及Xid,按照分配好的BlockNum和GridNum进行并行计算即可。需要注意的是,本文所提出的自适应线程束的方法使用的是“纯净加速比”,所以for循环中将不会出现CPU与GPU之间的传值,所有迭代更新过程全部在GPU端完成。更新Vid时需要用到随机数,在早期的GPU上需要先在CPU端生成随机数,再传输到GPU端,将大量的时间耗费在传值上[10],也有许多学者尝试过编写GPU端的随机函数,但使用起来并不方便[21-22]。本文直接使用CUDA提供的CURAND库中的curand_uniform( )函数在GPU中生成随机数[13, 16],避免在迭代过程中掺杂CPU与GPU之间传值所消耗的时间,以得到“纯净加速比”。

kernel2( )核函数的主要功能是,先按照分配好的BlockNum和GridNum并行计算每个粒子每个维度的适应度值,再根据每个维度的适应度值通过并行规约(Reduction) 算法[13],得到每个粒子的适应度值。最后根据得到的适应度值,更新Fib及其所对应的解Pidb。需要注意的是,由于每个Block中容纳有一个或多个粒子,相应地在使用并行规约时用到的共享内存也会变多,进一步提高了共享内存的使用量。同时在并行规约的过程中,应尽量减少Warp内的分支数目,以避免线程分支耗时[13]

4 实验结果与分析 4.1 基准函数及实验平台 4.1.1 基准函数

在实际实验中,优化算法通常由函数评估值来决定。本文采用Sphere、Rastringrin、Rosenbrok这3个基准函数对CPU-PSO算法、粗粒度GPU-PSO算法、细粒度GPU-PSO算法、自适应线程束GPU-PSO算法这四种不同的PSO算法进行了性能评测。这3个基准测试函数的表达式如(10)~(12)所示:

${{f}_{Sphere}}\left( x \right)=\sum\limits_{d=1}^{D}{x_{d}^{2}}{{x}_{d}}\in [-100,100]$ (10)
$\begin{align} & {{f}_{\text{Rastrigrin}}}\left( x \right)=\sum\limits_{d=1}^{D}{[x_{d}^{2}-10\cos (2\pi {{x}_{d}})\text{+}10]} \\ & ,{{x}_{d}}\in [-5.12,5.12] \\ \end{align}$ (11)
$\begin{align} & {{f}_{\text{Rosenbrock}}}\left( x \right)=\sum\limits_{d=1}^{D\text{-}1}{[100{{({{x}_{d+1}}-x_{d}^{2})}^{2}}+{{({{x}_{d}}-1)}^{2}}]} \\ & ,{{x}_{d}}\in [-10,10] \\ \end{align}$ (12)

在实验中,为了避免CPU-PSO算法执行时间过长,这里将这三个基准测试函数的维度D分别取值为24、20、16,并相应地调整算法飞行迭代次数。当然默认这些测试函数是特别复杂的优化问题,需要用到成百上千个粒子来求解。

4.1.2 实验平台

本文所使用的实验平台如表 1所示。CPU和GPU中小数均采用单精度浮点(float)表示[13]。在新版的GPU中,三角函数中的硬件函数__cosf( )的速度与软件库中的cosf( )函数的速度已经基本相当,相对的硬件函数反而会降低精度,所以本文使用软件库中的cosf( )函数。

表 1 计算平台
4.2 加速比

为了避免CPU与GPU之间的首次和末次传值耗时造成的干扰,本文使用“纯净加速比”用来评估算法的性能,即计算加速比时只计算飞行迭代所消耗的时间,具体定义如式(13)所示:

${{\text{S}}_{pure}}={{T}_{cpuFly}}/{{T}_{gpuFly}}$ (13)

其中:TcpuFly表示同等条件(粒子数、维度、迭代次数等均相同)下运行CPU-PSO算法中,飞行迭代所耗时间,单位为s;TcpuFly表示运行同等条件下GPU-PSO算法中,飞行迭代所耗时间,单位也是s;得到的Spure即是文中使用的“纯净加速比”。

4.3 结果分析

本文主要针对3个基准测试函数使用4种PSO算法作了测试和对比分析。实验结果均使用“纯净加速比”表示。同时,为保证实验结果的可靠性,本文将CPU端的CPU-PSO算法和三种GPU端的GUP-PSO算法各运行30次,取结果的平均值作为最终结果。

3个基准函数对应实验结果如表 2~4所示。表中,N代表粒子数;G代表迭代次数(×103);T代表运行时间(保留小数点后三位);S代表纯净加速比(保留小数点后三位);“CPU”代表CPU-PSO算法,“GPU1”代表粗粒度方法GPU-PSO算法,“GPU2”代表细粒度方法GPU-PSO算法,“GPU3”代表自适应线程束方法GPU-PSO算法。分析表 2~表 4中的数据,可以得到以下结论:

表 2 Sphere函数纯净加速比(维度24)
表 3 Rastringrin函数纯净加速比(维度20)
表 4 Rosenbrok函数纯净加速比(维度16)

1) 粗粒度并行方法与串行方法相比较,在一定程度上提高了加速比,但由于未对维度作并行处理,受维度影响较大:当维度低时,加速比高些;当维度变高时,加速比会变低。

2) 细粒度并行方法,将维度作了进一步的并行。与粗粒度的方法比较,当维度高时,由于并行度更高,所以加速比也更高,但当维度变低时,二者的差距会变小,甚至会因为存储资源消耗变大等问题导致加速比反而不如粗粒度方法。

3) 本文提出的自适应线程束的方法,并行程度相比细粒度的方法,从Block级提升到了Warp级,CPU加速比最多提高了40。当维度高时,由于其自适应的特性,并行效果会变得和粗粒度方法相当,故而加速比提高不明显。而当维度低时,由于每个Block中容纳的粒子数变多,所以加速比也更高,这就在一定程度上克服了细粒度方法维度低时加速比不高的问题。

4) CUDA并行计算模型决定了Block之间是串行执行的,当粒子数N较小时,与细粒度方法相比,对应的串行执行的Block数相差也很少,故而加速比提高不明显。而当粒子数变多时,对应的串行Block数差距也就更大,使得与细粒度方法相比,加速比提高得更加明显。

5 结语

本文对串行PSO算法以及三种不同CUDA架构方案下并行PSO算法的执行时间进行了对比分析。本文所提出的基于自适应线程束的GPU并行粒子群优化算法将CUDA并行级别提高到Warp级,加大了并行粒子群优化算法的并行度。通过对三个基准测试函数在这四种方法下执行所得到的“纯净加速比”的比较中可以看出,本文提出的方法,解决了细粒度方法中,当维度不高时加速比偏低,甚至是反而不如粗粒度方法的问题,CPU加速比最多提高了40,进一步提高了并行PSO算法的加速比。

参考文献
[1] KENNEDY J, EBERHART R. Particle swarm optimization[C]//Proceedings of the 1995 IEEE International Conference on Neural Networks. Piscataway, NJ:IEEE, 1995, 4:1942-1948.
[2] POLI R, KENNEDY J, BLACKWELL T. Particle swarm optimization[J]. Swarm Intelligence, 2007, 1 (1) : 33-57. doi: 10.1007/s11721-007-0002-0
[3] 张庆科, 杨波, 王琳, 等. 基于GPU的现代并行优化算法[J]. 计算机科学, 2012, 39 (4) : 304-310. ( ZHANG Q K, YANG B, WANG L, et al. Research on parallel modern optimization algorithms using GPU[J]. Computer Science, 2012, 39 (4) : 304-310. )
[4] 左颢睿, 张启衡, 徐勇, 等. 基于GPU的并行优化技术[J]. 计算机应用研究, 2009, 26 (11) : 4115-4118. ( ZUO H R, ZHANG Q H, XU Y, et al. Parallel optimize technology based on GPU[J]. Application Research of Computers, 2009, 26 (11) : 4115-4118. )
[5] 吴恩华, 柳有权. 基于图形处理器(GPU)的通用计算[J]. 计算机辅助设计与图形学学报, 2004, 16 (5) : 601-612. ( WU E H, LIU Y Q. General purpose computation on GPU[J]. Journal of Computer-Aided Design & Computer Graphics, 2004, 16 (5) : 601-612. )
[6] LUEBKE D, HUMPHREYS G. How GPUs work[J]. Computer, 2007, 40 (2) : 96-100. doi: 10.1109/MC.2007.59
[7] NVIDIA Corporation. CUDA Programming Guide 7. 0[EB/OL].[2016-06-01]. http://www.nvidia.com.
[8] VERONESE L D P, KROHLING R. Swarm's flight:accelerating the particles using C-CUDA[C]//CEC'09:Proceedings of the Eleventh Conference on IEEE Congress on Evolutionary Computation. Piscataway, NJ:IEEE, 2009:3264-3270.
[9] CALAZAN R M, NEDJAH N, DE MACEDO M L. Parallel GPU-based implementation of high dimension particle swarm optimizations[C]//Proceedings of the 2013 IEEE Fourth Latin American Symposium on Circuits and Systems. Piscataway, NJ:IEEE, 2013:1-4.
[10] ZHOU Y, TAN Y. GPU-based parallel particle swarm optimization[C]//CEC'09:Proceedings of the 2009 IEEE Congress on Evolutionary Computation. Piscataway, NJ:IEEE, 2009:1493-1500.
[11] MUSSI L, DAOLIO F, CAGNONI S. Evaluation of parallel particle swarm optimization algorithms within the CUDA architecture[J]. Information Sciences, 2011, 181 (20) : 4642-4657. doi: 10.1016/j.ins.2010.08.045
[12] 邹岩, 杨志义, 张凯龙. CUDA并行程序的内存访问优化技术研究[J]. 计算机测量与控制, 2009, 17 (12) : 2504-2506. ( ZOU Y, YANG Z Y, ZHANG K L. Study on optimization techniques for accesses of CUDA[J]. Computer Measurement & Control, 2009, 17 (12) : 2504-2506. )
[13] 陈风, 田雨波, 杨敏. 基于CUDA的并行粒子群优化算法研究及实现[J]. 计算机科学, 2014, 41 (9) : 263-268. ( CHEN F, TIAN Y B, YANG M. Research and design of parallel particle swarm optimization algorithm based on CUDA[J]. Computer Science, 2014, 41 (9) : 263-268. )
[14] 张德军, 何发智, 吴亦奇. 一种基于定向变异粒子群算法的异构CAD模型奇异特征互操作方法[J]. 中国科学:信息科学, 2015, 45 (5) : 634-649. ( ZHANG D J, HE F Z, WU Y Q. Singular feature interoperability of heterogeneous CAD model based on directed mutation particle swarm optimization[J]. SCIENCE CHINA Information Sciences, 2015, 45 (5) : 634-649. )
[15] Particle Swarm Central. Standard PSO version 2006[EB/OL].[2016-06-01]. http://www.particleswarm.info/Standard_PSO_2006.c.
[16] 蔡勇, 李光耀, 王琥. 基于CUDA的并行粒子群优化算法的设计与实现[J]. 计算机应用研究, 2013, 30 (8) : 2415-2418. ( CAI Y, LI G Y, WANG H. Research and implementation of parallel particle swarm optimization based on CUDA[J]. Application Research of Computers, 2013, 30 (8) : 2415-2418. )
[17] OWENS J D, HOUSTON M, LUEBKE D, et al. GPU computing[J]. Proceedings of the IEEE, 2008, 96 (5) : 879-899. doi: 10.1109/JPROC.2008.917757
[18] 赵明超, 陈智斌, 文有为. 基于GPU图像去噪总变分对偶模型的并行计算[J]. 计算机应用, 2016, 36 (5) : 1228-1231. ( ZHAO M C, CHEN Z B, WEN Y W. Parallel computation for image denoising via total variation dual model on GPU[J]. Journal of Computer Applications, 2016, 36 (5) : 1228-1231. )
[19] DOLPHIN Project Team. Metaheuristics on GPU[EB/OL].[2016-06-01]. http://www.sintef.no/globalassets/project/collab/presentations/the-van-metaheuristics-gpu-sintef.pdf.
[20] ROCKI K, SUDA R. Accelerating 2-opt and 3-opt local search using GPU in the travelling salesman problem[C]//Proceedings of the 201212th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing. Washington, DC:IEEE Computer Society, 2012:705-706.
[21] BASTOS-FILHO C J A, OLIVEIRA M A C, NASCIMENTO D N O, et al. Impact of the random number generator quality on particle swarm optimization algorithm running on graphic processor units[C]//Proceedings of the 201010th International Conference on High Performance Computing and Simulation. Piscataway, NJ:IEEE, 2010:85-90.
[22] SUSSMAN M, CRUTCHFIELD W, PAPAKIPOS M. Pseudorandom number generation on the GPU[C]//Proceedings of the 21st ACM SIGGRAPH/EUROGRAPHICS Symposium on Graphics Hardware. New York:ACM, 2006:87-94.