A fast Hough Transform algorithm for straight lines detection in an image using GPU parallel computing with CUDA-C

The Hough Transform (HT) is a digital image processing method for the detection of shapes which has multiple uses today. A disadvantage of this method is its sequential computational complexity, particularly when a single processor is used. An optimized algorithm of HT for straight lines detection in an image is presented in this article. Optimization is realized by using a decomposition of the input image recently proposed via central processing unit (CPU), and the technique known as segment decomposition. Optimized algorithms improve execution times significantly. In this paper, the optimization is implemented in parallel using graphics processing unit (GPU) programming, allowing a reduction of total run time and achieving a performance more than 20 times better than the sequential method and up to 10 times better than the implementation recently proposed. Additionally, we introduce the concept of Performance Ratio, to emphasize the outperforming of the GPU over the CPUs.     

利用并行GPU对分层分布式狄利克雷分布算法加速

分层分布式狄利克雷分布(HD-LDA)算法是一个对潜在狄利克雷分布(LDA)进行改进的基于概率增长模型的文本分类算法,与只能在单机上运行的LDA算法相比,可以运行在分布式框架下,进行分布式并行处理。Mahout在Hadoop框架下实现了HD-LDA算法,但是因为单节点算法的计算量大,仍然存在对大数据分类运行时间太长的问题。而大规模文本集合分散到多个节点上迭代推导,单个节点上文档集合的推导仍是顺序进行的,所以处理大规模文本集合时仍然需要很长时间才能完成全部文本的分类。为此,提出将Hadoop与图形处理器(GPU)相结合,将单节点文本集合的推导过程转移到GPU上运行,实现单节点多个文档并行推导,利用多台并行的GPU对HD-LDA算法进行加速。应用结果表明,使用该方法能使分布式框架下的HD-LDA算法对大规模文本集合处理达到7倍的加速比。     

LU分解和Laplace算法在GPU上的实现

随着图形处理器(GPU)性能的大幅度提升以及可编程性的发展,已经有许多算法成功地移植到GPU上.LU分解和Laplace算法是科学计算的核心,但计算量往往很大,由此提出了一种在GPU上加速计算的方法.使用Nvidia公司的统一计算设备架构(CUDA)编程模型实现这两个算法,通过对CPU与GPU进行任务划分,同时利用GP...     

基于CUDA的拉普拉斯边缘检测算法

拉普拉斯边缘检测算法常用于去除CCD天文图像中的宇宙射线噪声,但其串行算法计算复杂度较高。为此,分析拉普拉斯边缘检测算法的并行性,在统一计算设备架构(CUDA)并行编程环境下,提出一种基于CUDA的拉普拉斯边缘检测图形处理单元(GPU)并行算法。分割天文图像得到多幅子图,根据GPU的硬件配置设定Block和Grid的大小,将子图依次传输到显卡进行并行计算,传回主存后拼接得到完整的图像输出。实验结果表明,图像尺寸越大,该并行算法与串行算法相比具有的速度优势越大,可获得10倍以上的加速比。     

基于CUDA的尺度不变特征变换快速算法

针对尺度不变特征变换(SIFT)算法耗时多限制其应用范围的缺点,提出一种基于统一计算设备架构(CUDA)的尺度不变特征变换快速算法,分析其并行特性,在图像处理单元(GPU)的线程和内存模型方面对算法进行优化。实验证明,相对于CPU,算法速度提升了30~50倍,对640×480图像的处理速度达到每秒24帧,满足实时应用的需求。     

基于DEM图像增强的航海雷达回波模拟

针对传统的航海雷达回波模拟利用扫描扇形与电子海图求交,得到的回波多边形数量巨大,大场景的回波模拟无法实时处理、真实感差等问题,提出了利用DEM图像增强的回波模拟方法。该算法建立了一种CPU结合GPU的异构系统,首先在CPU中通过聚合、连通步骤减少多边形数量实时生成回波,然后在GPU中叠加港口DEM高程信息对回波实现图像增强,纬度上分段处理消除纬度渐长率的影响。该算法实现了回波图像从扫描像素点到扇形带状回波的转化,仿真过程符合真实的雷达回波形成原理。在较大仿真场景下,回波图像增强经过GPU处理后并行效率提高,相对CPU的加速比可至240倍。     

基于GPU的压缩感知重构算法的设计与实现

针对大尺度压缩感知重构算法实时性应用的需要,探讨了基于图形处理器(GPU)的正交匹配追踪算法(OMP)的加速方法及实现。为降低中央处理器与GPU之间传输的高延迟,将整个OMP算法的迭代过程转移到GPU上并行执行。其中,在GPU端根据全局存储器的访问特点,改进CUDA程序使存储访问满足合并访问条件,降低访问延迟。同时,根据流多处理器(SM)的资源条件,增加SM中共享存储器的分配,通过改进线程访问算法来降低bank conflict,提高访存速度。在NVIDIA Tesla K20Xm GPU和Intel(R) E5-2650 CPU上进行了测试,结果表明,算法中耗时长的投影模块、更新权值模块分别可获得32和46倍的加速比,算法整体可获得34倍的加速比。     

GPU加速的二维地震波场模拟研究

采用交错网格有限差分方法模拟二维地震弹性/粘弹性波场要花费大量的计算时间,为此利用GPU并行处理特点和绘制管道,将计算区域划分为内部区域和PML边界处理区域,整个计算过程由顶点编程和片段编程处理,采用FBO技术实现差分迭代结果的纹理转换。实验结果表明,与CPU实现相比,GPU方法提高了模拟效率,并且随着网格规模的增加,其效率不断提升,可以实现大规模的高效模拟。     

基于CUDA的SKINNY加密算法并行实现与分析

针对SKINNY加密算法在中央处理器（CPU）下实现效率偏低的问题,提出一种基于图形处理器（GPU）的快速实现方法。首先,结合SKINNY算法的结构特征提出优化方案,将5个分步操作优化整合为1个整体运算;然后,分析该算法的电子密码本（ECB）模式和计数器（CTR）模式的特性,并给出并行粒度、内存分配等并行设计方案。实验结果表明,与传统的CPU实现方法下的SKINNY算法相比,基于计算统一设备架构（CUDA）实现的SKINNY算法的效率和吞吐量得到很大提升。具体来说,当处理的数据达到16 MB及以上时,在所提实现方法下,SKINNY算法的ECB模式的加速效率提升峰值为99.85%,加速比峰值为671,CTR模式的加速效率提升峰值为99.87%,加速比峰值为765;而与已有AES-256（ECB）和SKINNY_ECB并行算法比较,新提出的SKINNY-256（ECB）并行算法的吞吐量分别是它们的吞吐量的1.29倍和2.55倍。     

基于图形处理器的可变形部件模型算法的并行化

目前目标识别领域,在人体检测中精确度最高的算法就是可变形部件模型(DPM)算法,针对DPM算法计算量大的缺点,提出了一种基于图形处理器(GPU)的并行化解决方法.采用GPU编程模型OpenCL,对DPM算法的整个算法的实现细节采用了并行化的思想进行重新设计实现,优化算法实现的内存模型和线程分配.通过对OpenCV库和采用GPU重新实现的程序进行对比,在保证了检测效果的前提下,使得算法的执行效率有了近8倍的提高.     

基于图形处理器加速的医学图像配准技术进展

针对目前医学图像配准技术无法满足临床实时性需求问题,对基于图形处理器(GPU)加速的医学图像配准技术进行综述探讨。首先对GPU通用计算进行概述,再以医学图像配准基本框架为主线,对近年来基于GPU加速的医学图像配准技术在国内外发展现状进行深入研究,并针对正电子发射型计算机断层显像(PET)和电子计算机断层扫描(CT)数据的非线性配准问题,分别基于中央处理器(CPU)和GPU平台进行配准实验,通过实验结果的对比,体现GPU加速配准技术的优越性。基于GPU加速的自由形变(FFD)和归一化互信息(NMI)结合的非线性配准方法配准后互信息值略低于CPU平台的配准结果,但其配准速度是CPU平台的12倍。基于GPU加速的配准算法在保持配准精度的基础上,配准速度都得到了很大的提升。     

GPU加速的二值图连通域标记并行算法

结合NVIDIA公司统一计算设备架构(CUDA)下的图形处理器(GPU)并行结构和硬件特点,提出了一种新的二值图像连通域标记并行算法,高速有效地标识出了二值图的连通域位置及大小,大幅缩减了标记时间耗费。该算法通过搜索邻域内最小标号值的像素点对连通域进行标记,各像素点处理顺序不分先后并且不相互依赖,因此可以并行执行。算法效率不受连通域形状及数量的影响,具有很好的鲁棒性。实验结果表明,该并行算法充分发挥了GPU并行处理能力,在处理高分辨率与多连通域图像时效率为一般CPU标记算法的300倍,比OpenCV的优化函数(CPU)效率高近17倍。     

面向多核CPU和GPU平台的数据库星形连接优化

针对联机分析处理（OLAP）中事实表与多个维表之间的星形连接执行代价较高的问题,提出了一种在先进的多核中央处理器（CPU）和图形处理器（GPU）上的星形连接优化方法。首先,对于多核CPU和GPU平台的星形连接中的物化代价问题,提出了基于向量索引的CPU和GPU平台上的向量化星形连接算法;然后,通过面向CPU cache和GPU shared memory大小的向量划分来提出基于向量粒度的星形连接操作,从而优化星形连接中向量索引的物化代价;最后,提出了基于压缩向量的星形连接算法,将定长向量索引压缩为变长的二元向量索引,从而在低选择率时提高cache内向量索引的存储访问效率。实验结果表明,在CPU平台上向量化星形连接算法相对于常规的行式或列式连接性能提升了40%以上,在GPU平台上向量化星形连接算法相对于常规星形连接算法性能提升超过了15%;与当前主流的内存数据库和GPU数据库相比,优化的星形连接算法性能相对于最优内存数据库Hyper性能提升了130%,相对于最优的GPU数据库OmniSci性能提升了80%。可见基于向量索引的向量化星形连接优化技术有效地提高了多表连接性能,与传统优化技术相比,基于向量索引的向量化处理提高了较小cache上的数据存储访问效率,压缩向量进一步提升了向量索引在cache内的访问效率。     

基于GPU图像去噪总变分对偶模型的并行计算

研究基于总变分(TV)的图像去噪问题,针对中央处理器(CPU)计算速度较慢的问题,提出了在图像处理器(GPU)上并行计算的方法。考虑总变分最小问题的对偶模型,建立原始变量与对偶变量的关系,采用梯度投影算法求解对偶变量。数值实验分别在GPU与CPU上进行。实验结果表明,总变分去噪模型对偶算法在GPU设备上执行的效率高于在CPU上执行的效率,并且随着图像尺寸的增大,GPU并行计算的优势更加突出。     

雅可比迭代法在图形处理器上实现的研究

雅可比迭代法是求解大型线性方程组的基本方法。利用GPU（Graphics Processing Unit,图形处理器）的并行处理能力,将雅可比迭代求解线性方程组过程中运算量较大的部分移植到GPU上执行,以提高运算速度。并分析了影响运算速度的两个因素：CPU-GPU数据交换和共享变量的访问;实验结果表明采用单个thread访问共享变量判断迭代是否收敛时,线性方程组的阶数为500,速度可以提高45倍以上。     

异构计算平台上列存储系统的并行连接优化策略

GPU以及集成式的CPU-GPU架构凭借其强大的并行处理能力和可编程流水线方式,已经成为数据库领域的研究热点。为充分利用异构平台的并行计算能力,提升列存储系统的查询性能,在研究异构平台结构特性的基础上,首先提出了GPU多线程平台上进行连接的数据划分策略--ICMD（Improved CMD）,利用GPU流处理器并行处理各个子空间上的连接,然后利用任务评估分配模型实现查询负载的动态分配,使得查询操作能在多核CPU、GPU上高效并行执行。同时利用片上全局同步机制、局部内存重用技术优化ICMD连接算法。最后采用SSB基准测试集测试,结果表明：Intel? HD Graphics 4600平台上并行连接查询相比于CPU版本获得了35%的性能提升,较GPU查询引擎的Ocelot性能上提升了18%。     

基于OpenCL的直方图生成算法优化方法研究

随着GPU计算能力及可编程性的不断增强,采用GPU作为通用加速器对应用程序进行性能加速已经成为提升程序性能的主要模式。直方图生成算法是计算机视觉的常用算法,在图像处理、模式识别、图像搜索等领域都有着广泛的应用。随着图像处理规模的扩大和实时性要求的提高,通过GPU提升直方图生成算法性能的需求也越来越强。在GPU计算平台关键优化方法和技术的基础上,完成了直方图生成算法在GPU计算平台上的实现及优化。实验结果表明,通过使用直方图备份、访存优化、数据本地化及规约优化等优化方法,直方图生成算法在AMD HD7850 GPU计算平台上的性能相对于优化前的版本达到了1.8~13.3倍的提升;相对于CPU版本,在不同数据规模下也达到了7.2~210.8倍的性能提升。     

基于GPU的多点触控图像处理技术

现有的图像校正技术仅对触点坐标进行校正,存在损失大量操控面信息,限制复杂交互方式的缺点。为此,利用图形处理器(GPU)的可编程性和图形图像计算方面的优势,由GPU完成图像校正和处理过程,以此提高图像处理速度。为使系统支持更复杂的操控与交互,改进图像校正和处理流程,实现图像的整体校正,在保留操控面全部信息的同时减少CPU占用资源。理论分析与实验结果验证了该方法的有效性。     

Massively parallel Wang–Landau sampling on multiple GPUs

Wang–Landau sampling is implemented on the Graphics Processing Unit (GPU) with the Compute Unified Device Architecture (CUDA). Performances on three different GPU cards, including the new generation Fermi architecture card, are compared with that on a Central Processing Unit (CPU). The parameters for massively parallel Wang–Landau sampling are tuned in order to achieve fast convergence. For simulations of the water cluster systems, we obtain an average of over 50 times speedup for a given workload.     

基于图形处理器的形态学重建系统

形态学重建是医学图像处理中非常基础和重要的操作。它根据掩膜图像的特征对标记图像反复进行膨胀操作，直到标记图像中的像素值不再变化为止。对于传统基于中央处理器（CPU）的形态学重建系统计算效率不高的问题，提出了使用图形处理器（GPU）来加速形态学重建。首先，设计了适合GPU处理的数据结构：并行堆集群；然后，基于并行堆集群，设计和实现了一套基于GPU的形态学重建系统。实验结果表明，相比传统基于CPU的形态学重建系统，基于GPU的形态学重建系统可以获取超过20倍的加速比。基于GPU的形态学重建系统展示了如何把基于复杂数据结构的软件系统高效地移植到GPU上。