基于滑动门中心点计算的K均值聚类并行算法研究

随着GPU硬件设备的普及和GPGPU技术的快速发展,越来越多的研究人员投入到GPGPU的研究当中。当前,GPU具有很强大的并行计算能力、浮点运算能力、计算单元集成能力等特点,显示出了GPU在并行计算领域的巨大潜力。CUDA是由NVIDIA公司提出的一种利用GPU进行并行计算的架构,CUDA使得GPU具有友好的可编程性,为研究人员能够在GPU上实现各种领域的科学计算提供了方便的途径。K均值聚类算法由于其概念简单,易于实现等优点成为并行计算研究的一个热门方向。对于K均值并行算法的研究,有基于8核CPU并配备FPGA加速板的方法,但对于一个需要启动数千个线程的复杂模型,基于传统CPU并行计算方法难以实现;也有使用CUDA并行计算平台对K均值聚类算法进行处理,但处理算法时通常忽略对CUDA平台上K均值聚类算法自身的优化。基于以上缺陷,介绍K均值聚类算法的同时对算法在CUDA平台上进行了相应优化,特别针对更新中心点的耗时问题,提出了一种基于滑动门中心点计算的K均值聚类并行计算。实验结果表明,当聚类数较多时,相对于传统的更新中心点算法,基于滑动门中心点并行算法的效率更高。     

CUDA相邻归约与其避免线程分化算法的研究

在边缘计算环境下,上层应用调度图形处理器（Graphic Processing Unit,GPU）的统一计算架构（Compute Unified Device Architecture,CUDA）进行计算时,可能会遇到CUDA线程分化问题,导致运算耗时较长或线程空置化。本研究介绍了CUDA底层开发的基础原理和概念,并解释了CUDA运算的执行流程。通过分析GPU架构原理,提出了相邻归约算法和相邻归约的避免线程分化算法的实现方式和应用方法。     

RSA算法的CUDA高效实现技术

CUDA（Compute Unified Device Architecture）作为一种支持GPU通用计算的新型计算架构,在大规模数据并行计算方面得到了广泛的应用。RSA算法是一种计算密集型的公钥密码算法,给出了基于CUDA的RSA算法并行化高效实现技术,其关键为引入大量独立并发的Montgomery模乘线程,并给出了具体的线程组织、数据存储结构以及基于共享内存的性能优化实现技术。根据RSA算法CUDA实现方法,在某款GPU上测试了RSA算法的运算性能和吞吐率。实验结果表明,与RSA算法的通用CPU实现方式相比,CUDA实现能够实现超过40倍的性能加速。     

基于CUDA架构的FFT并行计算研究

FFT（快速傅里叶变换）是基于提高DFT（离散傅里叶变换）计算的高效算法,它在众多科学和工程领域都得到了广泛的应用。自FFT算法出现以后,从早期的以降低复杂度到近年以来的大规模并行FFT计算,各种优化算法得到广泛的研究。在并行运算领域中,随着可编程的、并行化GPU的不断推广,特别是通用并行统一计算架构CUDA的出现,极大增强了GPU的计算能力,在编程和优化等方面都有显著地提升。鉴于此,本文在分析FFT算法实现的基础上,研究了一种适合GPU运算的FFT并行计算方法,并通过CUDA架构实现了FFT算法在GPU上的运算。该方法的引入在理论不计算数据传输的情况下,使一维FFT运算时间的复杂度由O（N logN2）可以降到O（N/rlogN2）。通过验证,本文提出的CUDA的并行FFT方法得到较好的加速效果,在精度计算上也符合实际的要求,从而证明了该方法的正确性和有效性。     

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

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

特征点检测DoG并行算法

特征点检测被广泛应用于目标识别、跟踪及三维重建等领域。针对三维重建算法中特征点检测算法运算量大、耗时多的特点,对高斯差分（Difference-of-Gaussian,DoG）算法进行改进,提出特征点检测DoG并行算法。基于OpenMP的多核CPU、CUDA及OpenCL架构的GPU并行环境,设计实现DoG特征点检测并行算法。对hallFeng图像集在不同实验平台进行对比实验,实验结果表明,基于OpenMP的多核CPU的并行算法表现出良好的多核可扩展性,基于CUDA及OpenCL架构的GPU并行算法可获得较高加速比,最高加速比可达96.79,具有显著的加速效果,且具有良好的数据和平台可扩展性。     

基于统一计算设备架构技术的并行图像处理研究

对统一计算设备架构CUDA技术进行研究,分析了CUDAGPU的显著特性,总结了CUDA的通用并行程序模式,详细介绍了用CUDA实现直方图均衡化的过程,接着简要介绍了CUDA在其它图像处理算法中的应用;最后对比CPU和GPU计算256级直方图均衡化的时间,实验结果表明随着图像像素的增大,CUDA可以把计算速度提高40多倍,在其它的图像算法中,甚至可以上百倍地提高速度.     

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

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

基于CUDA技术的卷积神经网络识别算法

针对具有高浮点运算能力的流处理器设备GPU对神经网络的适用性问题,提出卷积神经网络的并行化识别算法,采用计算统一设备架构(CUDA)技术,并定义其上的并行化数据结构,描述计算任务到CUDA的映射机制。实验结果证明,在GTX200硬件架构的GPU上实现的并行识别算法的平均浮点运算能力峰值较CPU上串行算法提高了近60倍,更适用于神经网络的相关应用。     

GPU编程原理及其在网络安全领域的应用算法分析

近年来,GPU在通用计算方面对传统的CPU应用发起了强有力的冲击,被广泛运用于各种高性能计算中,特别是网络安全领域.为了解决传统硬件加速存在的缺陷问题,首先介绍GPU的基本硬件架构及其并行计算原理,其次说明基于CUDA的GPU编程与通用CPU编程之间算法实现的性能差异,最后详细分析了几种典型的网络安全算法,并设计了相应的GPU并行加速试验进行性能测试.实验结果表明,在算法设计合理的前提下,GPU可以提升应用算法上百倍的计算性能.     

CUDA‐quicksort: an improved GPU‐based implementation of quicksort

Sorting is a very important task in computer science and becomes a critical operation for programs making heavy use of sorting algorithms. General‐purpose computing has been successfully used on Graphics Processing Units (GPUs) to parallelize some sorting algorithms. Two GPU‐based implementations of the quicksort were presented in literature: the GPU‐quicksort, a compute‐unified device architecture (CUDA) iterative implementation, and the CUDA dynamic parallel (CDP) quicksort, a recursive implementation provided by NVIDIA Corporation. We propose CUDA‐quicksort an iterative GPU‐based implementation of the sorting algorithm. CUDA‐quicksort has been designed starting from GPU‐quicksort. Unlike GPU‐quicksort, it uses atomic primitives to perform inter‐block communications while ensuring an optimized access to the GPU memory. Experiments performed on six sorting benchmark distributions show that CUDA‐quicksort is up to four times faster than GPU‐quicksort and up to three times faster than CDP‐quicksort. An in‐depth analysis of the performance between CUDA‐quicksort and GPU‐quicksort shows that the main improvement is related to the optimized GPU memory access rather than to the use of atomic primitives. Moreover, in order to assess the advantages of using the CUDA dynamic parallelism, we implemented a recursive version of the CUDA‐quicksort. Experimental results show that CUDA‐quicksort is faster than the CDP‐quicksort provided by NVIDIA, with better performance achieved using the iterative implementation. Copyright © 2015 John Wiley & Sons, Ltd.     

基于CUDA的塔台模拟机冲突检测算法

塔台模拟机冲突检测算法是一种耗时大的并行算法。针对其导致塔台模拟系统核心服务器CPU负担过重的缺点,在常用冲突检测算法的基础上,提出一种基于统一设备构架（CUDA）的塔台模拟机冲突检测实现方案。首先介绍GPU并行运算的体系结构基础,并将基于卡尔曼滤波的目标物体跟踪技术的分层冲突检测算法移植到GPU。然后利用相同价格的CPU和GPU对比运算效果。实验结果表明：与相同算法的CPU实现方案相比,GPU实现方案将计算效率提高10～50倍。使用此方案,极大地减轻了核心服务器的负担,使塔台模拟机的性能得到质的提高。     

多核CPU和GPU加速分子动力学模拟

在多核中央处理器(CPU)—图形处理器(GPU)异构并行体系结构上,采用OpenMP和计算统一设备架构(CUDA)编程实现了基于AMBER力场的蛋白质分子动力学模拟程序。通过合理地将程序划分为CPU单线程、CPU多线程和GPU多线程执行部分,高效地利用了计算机的处理能力。性能测试结果表明,相对于优化后的CPU串行计算,多核CPU-GPU异构并行计算模型有强大的性能优势,特别是将占整个程序执行时间90%的作用力的计算移植到GPU上执行,获得了最高可达12倍的计算加速比。     

Parallel data mining techniques on Graphics Processing Unit with Compute Unified Device Architecture (CUDA)

Recent development in Graphics Processing Units (GPUs) has enabled inexpensive high performance computing for general-purpose applications. Compute Unified Device Architecture (CUDA) programming model provides the programmers adequate C language like APIs to better exploit the parallel power of the GPU. Data mining is widely used and has significant applications in various domains. However, current data mining toolkits cannot meet the requirement of applications with large-scale databases in terms of speed. In this paper, we propose three techniques to speedup fundamental problems in data mining algorithms on the CUDA platform: scalable thread scheduling scheme for irregular pattern, parallel distributed top-k scheme, and parallel high dimension reduction scheme. They play a key role in our CUDA-based implementation of three representative data mining algorithms, CU-Apriori, CU-KNN, and CU-K-means. These parallel implementations outperform the other state-of-the-art implementations significantly on a HP xw8600 workstation with a Tesla C1060 GPU and a Core-quad Intel Xeon CPU. Our results have shown that GPU + CUDA parallel architecture is feasible and promising for data mining applications.     

基于GPU的位并行多模式串匹配研究

图形处理器(GPU)具有较强的单一运算能力及高度并行的体系结构。根据上述特点,选择基于位并行技术的多模式串匹配算法M-BNDM,将其移植到GPU上加以实现和优化。通过对需要处理的数据进行预处理,将串匹配的过程简化为更适合CUDA计算数据的位操作。对基于CUDA架构的并行串匹配算法的性能影响因子进行分析。实验结果表明,与同等CPU算法相比,该算法能够获得约十几倍的加速比。     

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

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

基于CUDA的位并行近似串匹配算法

为满足文本检索、计算生物学等领域海量数据匹配对高性能计算的要求,提出一种基于计算统一设备架构(CUDA)的位并行近似串匹配算法。结合图形处理器(GPU)的高并行计算结构及存储带宽特性,通过优化数据存储方式,实现并行化动态规划矩阵算法(BPM)的加速,并对加速性能进行对比测试。实验结果表明,BPM算法通过GPU加速能获得20倍左右的加速比。     

基于CUDA的泥石流模拟计算研究

针对泥石流仿真过程中海量数据计算问题,采用CUDA技术即结合CPU与GPU的优点研究了一种协同计算方法以提高数据计算效率和仿真性能。同时,搭建了基于GPU的泥石流仿真计算平台,对优化的CUDA并行计算方法进行验证。实验结果表明,该方法对海量数据的计算具有快速准确、低成本、低功耗的特点,能为灾害预测提供及时准确的决策支持,满足了高密集型计算的需求。     

并行时空处理模型下的快速N-body算法

图形处理器(graphic processing unit,GPU)的最新发展已经能够以低廉的成本提供高性能的通用计算。基于GPU的CUDA(compute unified device architecture)和OpenCL(open computing language)编程模型为程序员提供了充足的类似于C语言的应用程序接口(application programming interface,API),便于程序员发挥GPU的并行计算能力。采用图形硬件进行加速计算,通过一种新的GPU处理模型——并行时间空间模型,对现有GPU上的N-body实现进行了分析,从而提出了一种新的GPU上快速仿真N-body问题的算法,并在AMD的HD Radeon 5850上进行了实现。实验结果表明,相对于CPU上的实现,获得了400倍左右的加速;相对于已有GPU上的实现,也获得了2至5倍的加速。