基于GPU的并行优化算法研究

曹亚群

摘  要：该文介绍了GPU概念及发展、并行计算的概念以及与串行计算相比而具有的优势，指出智能优化算法具有天然的并行性和分布性，在基础理论和工程应用中具有很高的研究价值，该文对智能优化算法中的模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法及蚁群算法的原理和实际应用进行了深入研究，提出了基于GPU的并行优化算法。

关键词：GPU  并行计算  算法

中图分类号：TP301    文献标识码：A 文章编号：1672-3791（2019）07（c）-0007-02

Abstract： This paper introduces the concept and development of GPU， the concept of parallel computation and the advantage of the serial calculation， and points out that the intelligent optimization algorithm has the natural parallelism and the distribution， and has very high research value in the basic theory and engineering application. In this paper， the principle and practical application of the simulated annealing algorithm， the genetic algorithm， the tabu search algorithm， the artificial neural network algorithm and the ant colony algorithm in the intelligent optimization algorithm are deeply studied， and a parallel optimization algorithm based on the GPU is proposed.

Key Words： GPU; Parallel Computing; Algorithms

GPU并行计算是利用图形处理器，充分利用GPU内部结构，提高运算效率，目前，人们己经提出了很多GPU并行计算的模型，大家对GPU的并行计算都有非常大的兴趣，该文对GPU并行优化算法进行了研究。

1  CPU简介

GPU是Graphic Processing Unit的英文缩写，中文意思为图形处理器。GPU计算就是利用图形处理器进行科学和工程计算，最早GPU出现是为了提高3D图形处理速度，之后，GPU引入了编程和通用计算，目的是求解数学扩散方程和矩阵乘法。GPU在并行计算上的优势非常明显，矩阵运算、生命科学等方面的应用，有大量重复的数据运算，所以都需要GPU强大的计算功能。但是GPU并行運算的条件是它要解决的问题能够分解并行执行。所以，GPU要发展得更好必须有两个方面能力：（1）分支能力。GPU只有具有更强的分支能力，复杂的计算程序才能进行。（2）更大的共用存储器和缓存空间。共享存储器是共享数据、挂起线程，缓存空间越大，线程跳转就越快，分支能力就越大。

GPU发展到如今，已经突破了很多技术壁垒，由当初图形处理而诞生的硬件发展成大规模并行计算。智能终端对图像显示的要求逐渐提高，GPU的性能也会随之更加优化。

2  并行计算

所谓并行计算[1]是指在单位时间内，充分利用多个处理器单元，同时执行多条数据及指令的计算，用传统的串行计算处理大规模数据需要很长时间，于是，人们研究是否有途径能同时处理不同的数据，并行计算就随之出现了，在时间上，并行是指流水线技术，在空间上，并行是指多个处理器同时进行计算。因为并行计算是用多个处理器共同完成一个计算任务，能最大程度地缩短完成任务的时间，所以与串行算法相比较，并行算法能有效解决大规模运算问题。如图1所示，所谓并行计算就是把要解决的问题划分成一系列子任务，然后由多个不同功能的处理核完成各自的计算任务，这些处理核在计算数据时应彼此配合，以求达到获得最大计算性能[2]。

3  智能优化算法

智能优化算法[3]是仿照自然界智能优化原理而设计产生的算法，智能优化算法具有天然的并行性和分布性，此特性十分适合在并行计算设备上实现并行算法。智能优化算法在理论研究上和工程应用上都具有很高的价值，在图像处理、信号处理、任务分配、生产调度、模式识别、机械设计和自动控制等众多领域得到了成功应用。其主要包括模拟退火算法、遗传算法、禁忌搜索算法和人工神经网络等。

（1）模拟退火算法。

模拟退火算法是依照固态物质的退火原理而产生的，主要应用于解决组合优化问题。当被加热的固态物质的温度到某定值时，其里面微粒的布朗运动逐渐加剧，直至到达一定的运动强度时，固态就变成了液态，此时再退火，固态物质内的朗运动会慢慢变弱，最终稳定下来。

用模拟退火算法不会出现局部最优解，在模拟退火算法中设定某个理想概率P，若新解的目标函数的数值更优，就取P=1，也就是选择更加优化的解。否则，让理想概率P取当下解的目标函数、新解的目标函数及参数T的函数。可以看出，在求解最优解时该算法既考虑最优的解，同时还考虑目标函数不理想的解。算法中的参数T在运行该算法时会逐渐减小，直到小于某个数值时该算法结束。

（2）遗传算法。

遗传算法是来自于大自然中适者生存、优胜劣汰的遗传变异的生物进化而设计产生一种算法。该算法是开始于一个种群，该种群代表要优化问题的可能解集，包含标有基因编码的一定数目的个体，把基因编码为染色体，所有个体都具有染色体的特点，算法过程中引入一些随机参数高效搜索解空间。遗传算法首先编码生成初代种群，然后检查否满足收敛准则，若不满足，则继续，若满足，则结束算法，接着评价检测适应性及选出最优个体，最后交叉配种和基因突变产生新的种群。遗传算法过程类似于自然进化过程，产生的后代种群比前代种群有更好的适应性，算法结束后，把末代种群内最优个体解码，就是问题的最优解[4]。