基于CUDA的并行粒子群优化算法的设计与实现

针对处理大量数据和求解大规模复杂问题时粒子群优化(PSO)算法计算时间过长的问题, 进行了在显卡(GPU)上实现细粒度并行粒子群算法的研究。通过对传统PSO算法的分析, 结合目前被广泛使用的基于GPU的并行计算技术, 设计实现了一种并行PSO方法。本方法的执行基于统一计算架构（CUDA）, 使用大量的GPU线程并行处理各个粒子的搜索过程来加速整个粒子群的收敛速度。程序充分使用CUDA自带的各种数学计算库, 从而保证了程序的稳定性和易写性。通过对多个基准优化测试函数的求解证明, 相对于基于CPU的串行计算方法, 在求解收敛性一致的前提下, 基于CUDA架构的并行PSO求解方法可以取得高达90倍的计算加速比。     

基于GPU的现代并行优化算法

针对现代优化算法在处理相对复杂问题中所面临的求解时间复杂度较高的问题,引入基于GPU的并行处理解决方法。首先从宏观角度阐释了基于计算统一设备架构CUDA的并行编程模型,然后在GPU环境下给出了基于CUDA架构的5种典型现代优化算法(模拟退火算法、禁忌搜索算法、遗传算法、粒子群算法以及人工神经网络)的并行实现过程。通过对比分析在不同环境下测试的实验案例统计结果,指出基于GPU的单指令多线程并行优化策略的优势及其未来发展趋势。     

图形处理器维度层并行粒子群优化算法

笔者提出基于GPU维度层面并行的局部PSO算法,换言之,基于GPU的局部粒子群优化算法求解高维优化函数,即在求解目标函数时对每一个维度进行并行处理。将粒子与线程块对应,线程块中的线程与目标函数的维度对应。实验表明,此算法在优化高维度目标函数中优势明显,概念简单,易编程实现,能有效果解决串行粒子群优化算法性能急剧下降的问题。     

基于CUDA的热传导GPU并行算法研究

在热传导算法中,使用传统的CPU串行算法或MPI并行算法处理大批量粒子时,存在执行效率低、处理时间长的问题。而图形处理单元(GPU)具有大数据量并行运算的优势,为此,在统一计算设备架构(CUDA)并行编程环境下,采用CPU和GPU协同合作的模式,提出并实现一个基于CUDA的热传导GPU并行算法。根据GPU硬件配置设定Block和Grid的大小,将粒子划分为若干个block,粒子输入到GPU显卡中并行计算,每一个线程执行一个粒子计算,并将结果传回CPU主存,由CPU计算出每个粒子的平均热流。实验结果表明,与CPU串行算法在时间效率方面进行对比,该算法在粒子数到达16 000时,加速比提高近900倍,并且加速比随着粒子数的增加而加速提高。     

基于自适应线程束的GPU并行粒子群优化算法

基于统一计算设备架构（CUDA）对图形处理器（GPU）下的并行粒子群优化（PSO）算法作改进研究。根据CUDA的硬件体系结构特点,可知Block是串行执行的,线程束（Warp）才是流多处理器（SM）调度和执行的基本单位。为了充分利用Block中线程的并行性,提出基于自适应线程束的GPU并行PSO算法：将粒子的维度和线程相对应;利用GPU的Warp级并行,根据维度的不同自适应地将每个粒子与一个或多个Warp相对应;自适应地将一个或多个粒子与每个Block相对应。与已有的粗粒度并行方法（将每个粒子和线程相对应）以及细粒度并行方法（将每个粒子和Block相对应）进行了对比分析,实验结果表明,所提出的并行方法相对前两种并行方法,CPU加速比最多提高了40。     

基于CUDA的快速图像压缩

为了进一步提高JPEG编码效率,对JPEG压缩算法进行研究,分析得出JPEG核心步骤可以并行化处理.因此,实现平台宜采用以并行计算为优势的GPU,而不是以串行计算为主的CPU.NVIDIA新推出的CUDA(计算统一设备架构)为此实现提供了软硬件环境.CUDA是基于GPU进行通用计算的开发平台,非常适合大规模的并行数据计算.在GPU流处理器架构下用CUDA技术实现编码并行化,并针对流处理器架构特点进行内存读写等方面的优化,提高了JPEG编码的速度.实验结果表明了CUDA技术在并行处理方面的优越性,JPEG编码效率得到了极大提高.     

基于GPU的H.264并行解码算法

针对并行处理H.264标准视频流解码问题,提出基于CPU/GPU的协同运算算法。以统一设备计算架构(CUDA)语言作为GPU编程模型,实现DCT逆变换与帧内预测在GPU中的加速运算。在保持较高计算精度的前提下,结合CUDA混合编程,提高系统的计算性能。利用NIVIDIA提供的CUDA语言,在解码过程中使DCT逆变换和帧内预测在GPU上并行实现,将并行算法与CPU单机实现进行比较,并用不同数量的视频流验证并行解码算法的加速效果。实验结果表明,该算法可大幅提高视频流的编解码效率,比CPU单机的平均计算加速比提高10倍。     

面向三维重建的无人机影像并行处理技术

为提升三维重建任务的执行速度,解决行业现实应用对时效性的需求,提出一种无人机影像并行处理与特征提取算法,基于CPU与GPU两种计算架构在三维重建的两个阶段并行加速处理。一是基于CPU的并行处理策略,针对多核处理器采用OpenMP多线程机制,对无人机影像进行并行加载,为后续处理提供高效数据源;二是基于GPU的并行处理策略,通过改进SIFTGPU算法在GPU上以并行方式对图像进行特征提取,为快速重建提供特征输入。真实数据的实验结果表明,与现有算法相比,在图像处理速度上提升了2倍,特征点数量提升了4倍的同时,提取速度提升了11倍。     

基于CUDA的多尺度Retinex图像增强算法实现

多尺度Retinex图像增强是一种基于色彩恒定理论的图像增强算法,算法增强效果好,但随着图像分辨率的提高计算时间显著增加。分析并利用计算统一设备架构(CUDA)图形处理器(GPU)的并行处理特性,提出了一种基于CUDA的多尺度Retinex图像增强并行算法,将多尺度高斯滤波、对数空间差分和动态范围压缩等计算非常耗时的模块采用并行方式放在GPU中进行计算。实验结果表明所提算法能显著提高计算速度,随着图像分辨率的增加,最大加速比超过100倍。     

GPU加速的差分进化粒子滤波算法

为了解决实时系统中粒子滤波的计算复杂性问题,本文提出了一种零bank冲突并行规约的差分进化粒子滤波方法。该方法首先分析了并行差分进化粒子滤波算法在GPU中的内存访问模式,根据粒子滤波器的均方根误差与内存访问bank(存储体)冲突度成正比的关系,提出了一种去除bank冲突的有填充寻址的差分进化粒子滤波算法,降低了计算复杂度。将该算法在NVIDIA GTX960 GPU中实现,与串行差分进化粒子滤波算法进行比较。实验表明,随着粒子数增加,计算量以指数增加,采用GPU加速的跟踪算法的执行时间明显减少,有效提高了跟踪精度、降低了计算时间。     

基于CUDA的邻近粒子搜索算法研究

在粒子方法中,运用邻近粒子搜索算法可以快速获取每个粒子的邻近粒子信息。由于粒子方法模拟一个体系的行为所采用的粒子数据是十分庞大的,对计算机的运算速度提出了挑战。研究了GPU的计算能力和CUDA开发环境,利用GPU的并行多线程处理技术,提出了一种并行邻近粒子搜索算法。实验结果表明,基于CUDA的并行邻近粒子搜索算法,加快了邻近粒子搜索过程,显著地减少了计算时间,成功实现了硬件加速,可获取290以上的加速比,对大规模粒子系统呈现出高效的处理能力。     

一种基于GPU的粒子系统

粒子系统在当今不定形物体仿真中已经得到广泛的应用,但是普通的粒子系统在实时仿真中,粒子总数最多只能达到10000个左右,其中瓶颈在于粒子数据从主处理器到图形硬件的传输和CPU的并行处理能力。文章研究并实现了一种完全基于图形硬件(GPU)的粒子系统,利用GPU的多通道并行处理功能,提高处理速度,可以很大程度地增加粒子系统实时仿真应用中的粒子数量,从而可以提高虚拟环境的逼真程度。实验证明基于GPU的粒子系统的实时性能远远高于普通粒子系统。     

一种基于GPU的粒子系统火焰模拟

针对传统火焰模拟耗时、模拟真实性不理想这一问题,提出了一种借助GPU(图形处理器)高通用计算能力进行并行模拟的粒子系统火焰模拟方法.该方法采用基于方位角和仰角的粒子散射器、基于层流火焰轮廓计算公式的火焰外形计算及通过拉格朗日插值方法平滑火焰骨架线等手段提高了素流火焰的模拟真实度.在提高性能方面,该方法使用全局存储空间存储粒子信息,避免了因使用纹理存储而产生的反复绑定的开销,同时结合GPU强大的通用计算能力,通过采用CUDA(计算统一设备架构)编写的并行算法,实现了基于GPU的拉格朗日插值并行求解及并行计算、更新粒子属性,并就如何确定块内线程数量作了论述.实验结果表明,该方法满足了火焰模拟的真实性和实时性要求,且较传统方法有很大的提高.     

可满足性求解器算法基于GPU的加速研究

可满足性求解(SAT)问题被广泛应用于软件验证、理论证明、微处理器验证、模块验证等领域,工业应用实例问题求解变量规模已达到百万数量级,传统的基于CPU的串行和并行SAT求解方法已无法满足如此规模的问题求解。不同于以往的并行SAT研究,利用GPU并行处理的特点和SAT算法的特点,将SAT算法中最耗时的BCP(Boolean Constraint Propagation)过程并行化,设计实现了基于GPU的BCP过程GP_BCP(GPU Paralleled BCP),从而将BCP过程的性能提高了5.4～10.3倍。     

基于GPU的遥感图像融合并行算法研究

基于通用GPU并行计算技术,结合遥感图像数据融合处理特点,利用NVIDIA公司的CUDA编程框架,在其GPU平台上对BROVEY变换和YIQ变换融合算法进行了并行研究与实现.实验结果表明,随着遥感图像融合算法的计算复杂度、融合处理的问题规模逐渐增加,GPU并行处理的加速性能优势也逐渐增大,GPU通用计算技术在遥感信息处理领域具有广阔的应用前景.     

GPU通用计算平台上的SPH流体模拟

针对流体模拟需要大量计算资源从而很难达到实时模拟的问题,提出一种完全在GPU上实现的基于平滑粒子流体动力学的流体模拟方法.首先通过在GPU上构造基于哈希函数的空间均匀网格来实现任意大小场景的快速邻近粒子查找,并在GPU上并行求解SPH流体方程来实现流体模拟;渲染流体时,通过在顶点着色器中进行纹理采样,利用粒子坐标缓存数据直接更新流体粒子系统的顶点缓存,从而避免了CPU—GPU之间的数据传输,充分利用了GPU的并行性.实验对比表明,与纯CPU实现以及CPU和GPU混合实现的模拟结果相比,采用该方法能显著地减少单个时间片的计算时间,大幅度提高流体模拟和渲染的整体性能.     

AVS标准中整数DCT变换的CUDA并行算法

随着图形处理器(GPU)的处理能力的不断增强,图形处理器越来越多的运用在计算密集型的数据处理中.AVS标准视频压缩算法中一些步骤存在典型的并行特性,高清、超清视频压缩的串行算法执行时间开销较大,难以满足实时编码的需要,因此利用GPU的并行处理能力和CUDA的编程框架对AVS标准中的整数DCT变换算法进行了并行实现.经过实验测试,并行算法与串行算法相比具有较高的加速比.     

基于GPU的高性能并行计算技术

为研究基于GPU的高性能并行计算技术,利用集成448个处理核心的NVIDIA GPU GTX470实现了脉冲压缩雷达的基本数据处理算法,包括脉冲压缩算法与相参积累算法;同时根据GPU的并行处理架构,将脉冲压缩、相参积累算法完成了并行优化设计,有效地将算法并行映射到GPU GTX470的448个处理核心中,完成了脉冲压缩雷达基本处理算法的GPU并行处理实现;最后验证了并行计算的结果,并针对处理结果效果与实时性进行了评估。     

基于GPU的CUDA应用开发环境构架

随着GPU(graphics processing unit,图像处理单元)的快速发展,其强大的计算能力使得GPU由最初仅用于加速图形计算,越来越多地应用到非图形领域的计算。在CPU-GPU体系中,CPU负责进行复杂的逻辑运算和事务管理等不适合并行处理的数据计算,GPU负责进行计算密集度高、逻辑分支简单的适合并行处理的大规模数据计算。CPU-GPU体系的不断完善,使得利用GPU来加速大规模科学计算成为了一种必然趋势。着眼GPU的应用开发,介绍在windows环境下CUDA+VS2008开发平台的构架,并对该构架下GPU与CPU的科学计算性能进行比对。     

一种基于GPU的移动对象并行处理框架

PGrid是一个基于格网索引的移动对象并行处理框架。通过分析PGrid框架不利于在GPU上并行的因素,提出基于GPU的无锁并行处理G-LFPP(GPU Based Lock Free Parallel Processing)框架。采用基于操作分解/聚类的无锁更新策略,消除更新过程中并发控制对更新性能的影响;为了实现细粒度并行查询,提出基于候选集映射表和查询确认表的快速查询索引。实验表明,该方法更新和查询策略有利于大规模线程并发处理更新和查询。当移动对象的数量达到千万级时,更新速率和查询速率仍然可以超过每秒1100万次和110万次。与PGrid相比,并发处理更新和查询的速度提高了6.61倍。