基于HYB格式稀疏矩阵与向量乘在CPU+GPU异构系统中的实现与优化

稀疏矩阵与向量相乘SpMV是求解稀疏线性系统中的一个重要问题,但是由于非零元素的稀疏性,计算密度较低,造成计算效率不高。针对稀疏矩阵存在的一些不规则性,利用混合存储格式来进行SpMV计算,能够提高对稀疏矩阵的压缩效率,并扩大其适应范围。HYB是一种广泛使用的混合压缩格式,其性能较为稳定。而随着GPU并行计算得到普遍应用以及CPU日趋多核化,因此利用GPU和多核CPU构建异构并行计算系统得到了普遍的认可。针对稀疏矩阵的HYB存储格式中的ELL和COO存储特征,把两部分数据分别分割到CPU和GPU进行协同并行计算,既能充分利用CPU和GPU的计算资源,又能够发挥CPU和GPU的计算特性,从而提高了计算资源的利用效能。在分析CPU+GPU异构计算模式的特征的基础上,对混合格式的数据分割和共享方面进行优化,能够较好地发挥在异构计算环境的优势,提高计算性能。     

基于GPU加速的并行WMD算法

Word Mover's Distance(WMD)是一种度量文本相似度的方法,它将两个文本之间的差异定义为文本的词嵌入向量之间的最小距离.WMD利用词汇表,将文本表示为归一化的词袋向量.文本的单词在语料中所占的比例很小,因此用词袋模型生成的文本向量很稀疏.多个文本可以组成一个高维的稀疏矩阵,这样的稀疏矩阵会生成大量不必要的运算.通过一次性对多个目标文本计算单个源文本的WMD,可以使计算过程高度并行化.针对文本向量的稀疏性,文中提出了一种基于GPU的并行Sinkhorn-WMD算法,采取压缩格式存储目标文本的方式来提高内存利用率,根据稀疏结构减少中间过程的计算.利用预训练词嵌入向量计算单词距离矩阵,对WMD算法进行改进,在两个公开的新闻数据集上进行优化算法的验证.实验结果表明,在NVIDIA TITAN RTX上并行算法与CPU串行相比最高可以达到67.43倍的加速.     

基于GPU的稀疏矩阵Cholesky分解

稀疏矩阵Cholesky分解是求解大规模稀疏线性方程组的核心算法,也是求解过程中最耗时的部分.近年来,一系列并行算法通过图形处理器(GPU)获得了显著的加速比,然而,由于访存的不规则性以及任务间的大量数据依赖关系,稀疏矩阵Cholesky分解算法在GPU上的计算效率很低.文中实现了一种新的基于GPU的稀疏矩阵Cholesky分解算法.在数据组织方面,改进了稀疏矩阵超节点数据结构,通过超节点合并和分块控制计算粒度;在计算调度方面,将稀疏矩阵Cholesky分解过程映射为一系列的数据块任务,并设计了相应的任务生成与调度算法,在满足数据依赖性的前提下提高任务的并行性.实验结果表明,该算法能够显著提高稀疏矩阵Cholesky分解算法在GPU上的实现效率,在单个GPU上获得了相对4核CPU平台2.69~3.88倍的加速比.     

基于OpenCL的并行kNN算法设计与实现

kNN算法是机器学习和数据挖掘程序中经常使用的经典算法。随着数据量的增大,kNN算法的执行时间急剧上升。为了有效利用现代计算机的GPU等计算单元减少kNN算法的计算时间,提出了一种基于OpenCL的并行kNN算法,该算法对距离计算和排序两个瓶颈点进行并行化,在距离计算阶段使用细粒度并行化策略和优化的线程模型,排序阶段使用优化内存模型的双调排序。以UCI数据集letter为测试集,分别使用E8400和GTS450运行kNN算法进行测试,采用GPU加速的并行kNN算法的计算速度比CPU版提高了40.79倍。     

基于GPU与CPU协作的实时波束形成实现方法*

波束形成的实时性一直是声纳和雷达等领域信号处理过程中的重点和难点。本文采用基于CUDA(Compute Unified Device Architecture,统一计算设备架构)的GPU(Graphic Processing Unit,图形处理器)与CPU协作处理方法,实现了宽带波束形成的实时处理。本方法的处理速度相较于matlab和CPU平台可以提高一至两个数量级,相较于同等处理速度的多DSP平台则体现了开发周期短、费用低、工作量小和可靠性高等众多优势。     

基于OpenCL的连续数据无关访存密集型函数并行与优化研究

连续的数据无关是指计算目标矩阵连续的元素时使用的源矩阵元素之间没有关系且也为连续的,访存密集型是指函数的计算量较小,但是有大量的数据传输操作。在OpenCL框架下,以bitwise函数为例,研究和实现了连续数据无关访存密集型函数在GPU平台上的并行与优化。在考察向量化、线程组织方式和指令选择优化等多个优化角度在不同的GPU硬件平台上对性能的影响之后,实现了这个函数的跨平合性能移植。实验结果表明,在不考虑数据传输的前提下,优化后的函数与这个函数在OpenCV库中的CPU版本相比,在AMD HD 5850 GPU达到了平均40倍的性能加速比;在AMD HD 7970 GPU达到了平均90倍的性能加速比;在NVIDIA Tesla 02050 CPU上达到了平均60倍的性能加速比;同时,与这个函数在OpenCV库中的CUDA实现相比,在NVIDIA Tesla 02050平台上也达到了1.5倍的性能加速。     

GPU上稀疏矩阵与矢量乘积运算的一种改进

稀疏矩阵和矢量的乘积运算在工程实践及科学计算中经常用到,随着矩阵规模的增长,大量的计算限制了整个系统的性能,因此可以利用GPU的高运算能力加速SpMV。分析了现有GPU上实现的SpMV存在的问题,并设计了行分割优化和float4数据类型优化两种方案。实验表明,该方案可以使性能提升2—8倍。     

CPU与GPU的技术比较

CPU与GPU各有所长。CPU的资源多用于缓存,而GPU的资源多用于数据计算。将CPU技术就进行比较,希望创造具有高性能处理器与独立显卡的处理性能,从而提高了电脑的运行效率,提高更好的性价比,使其为我们带来更好的选择。     

GPU 上的矩阵乘法的设计与实现

矩阵乘法是科学计算中最基本的操作,高效实现矩阵乘法可以加速许多应用。本文使用NVIDIA的CUDA在GPU上实现了一个高效的矩阵乘法。测试结果表明,在Geforce GTX260上,本文提出的矩阵乘法的速度是理论峰值的97％,跟CUBLAS库中的矩阵乘法相当。     

面向GPU计算平台的归约算法的性能优化研究

归约算法在科学计算和图像处理等领域有着十分广泛的应用,是并行计算的基本算法之一,因此对归约算法进行加速具有重要意义。为了充分挖掘异构计算平台下GPU的计算能力以对归约算法进行加速,文中提出基于线程内归约、work-group内归约和work-group间归约3个层面的归约优化方法,并打破以往相关工作将优化重心集中在work-group内归约上的传统思维,通过论证指出线程内归约才是归约算法的瓶颈所在。实验结果表明,在不同的数据规模下,所提归约算法与经过精心优化的OpenCV库的CPU版本相比,在AMD W8000和NVIDIA Tesla K20M平台上分别达到了3.91~15.93和2.97~20.24的加速比; 相比于OpenCV库的CUDA版本与OpenCL版本,在NVIDIA Tesla K20M平台上分别达到了2.25~5.97和1.25~1.75的加速比;相比于OpenCL版本,在AMD W8000平台上达到了1.24~5.15的加速比。文中工作不仅实现了归约算法在GPU计算平台上的高性能,而且实现了在不同GPU计算平台间的性能可移植。     

基于国产软硬件的OpenCL计算平台研究

随着智能计算和大数据应用的发展,人们对GPU等加速部件的需求不断增长。基于国产基础软硬件平台运行显控应用做加速计算的需求,研究了OpenCL计算平台的移植和实现途径,就国产软硬件平台进行GPU计算做出了初步探索。研究的计算平台包括Mesa、ROCm、Pocl和Beignet,最后给出了如何将ROCm在国产平台上移植适配的思路和解决方案。     

移动智能终端的SIFT特征检测并行算法

特征的检测和匹配在计算机视觉应用中是一个重要的组成部分,如图像匹配、物体识别和视频跟踪等。SIFT算法以其尺度不变性和旋转不变性在图像配准领域得到了广泛应用。传统的SIFT算法效率低,因此提出一种在移动智能终端上实现的高效方法。在Android平台利用OpenCL框架实现了移动智能终端的SIFT算法,通过计算任务的重新分配,优化SIFT算法在移动GPU上的并行实现。实验结果表明,移动平台的SIFT算法充分利用了GPU并行计算能力,大大提高了SIFT算法的执行效率,实现了高效的特征检测。     

基于OpenCL的均值平移算法在多个众核平台的性能优化研究

OpenCL作为一种面向多种平台、通用目的的编程标准,已经对许多应用程序进行了加速。由于平台硬件和软件环境的差异,通用的优化方法不一定在所有平台都有很好的加速。通过对均值平移算法在GPU和APU平台的优化,探讨了不同平台各种优化方法的贡献力,一方面研究各个平台的计算特性,另一方面体会不同优化方法的优劣,在优劣的相互转化中寻求最优的解决方案。实验表明,算法并行优化前、后在AVIV 5850,Tesla 02050和APU A6365。上分别达到了9.68, 5.74和1.27倍加速,并行相比串行程序达到79.73,93.88和2.22倍加速,前两个平台OpcnCL版本相比,CUVA版本的OpenCV程序达到1.27和1.24倍加速。     

Characterizing the challenges and evaluating the efficacy of a CUDA-to-OpenCL translator

The proliferation of heterogeneous computing systems has led to increased interest in parallel architectures and their associated programming models. One of the most promising models for heterogeneous computing is the accelerator model, and one of the most cost-effective, high-performance accelerators currently available is the general-purpose, graphics processing unit (GPU).     

基于OpenCL的图像模糊化算法优化研究

现代GPU一般都提供特定硬件(如纹理部件、光栅化部件及各种片上缓存)以加速二维图像的处理和显示过程,相应的编程模型(CUDA、OpenCL)都定义了特定程序设计接口(CUDA的纹理内存,OpenCL的图像对象)以便图像应用能利用相关硬件支持。以典型图像模糊化处理算法在AMD平台GPU的优化为例,探讨了OpenCL的图像对象在图像算法优化上的适用范围,尤其是分析了其相对于更通用的基于全局内存加片上局部存储进行性能优化的方法的优劣。实验结果表明,图像对象只有在图像为四通道且计算过程中需要缓存的数据量较小时才能带来较好的性能改善,其余情况采用全局内存加局部存储都能获得较好性能。优化后的算法性能相对于精心实现的CPU版加速比为200～1000;相对于NVIDIA NPP库相应函数的性能加速比为1.3～5。     

MPFFT: An Auto-Tuning FFT Library for OpenCL GPUs

Fourier methods have revolutionized many fields of science and engineering,such as astronomy,medical imaging,seismology and spectroscopy,and the fast Fourier transform(FFT) is a computationally efficient method of generating a Fourier transform.The emerging class of high performance computing architectures,such as GPU,seeks to achieve much higher performance and efficiency by exposing a hierarchy of distinct memories to software.However,the complexity of GPU programming poses a significant challenge to developers.In this paper,we propose an automatic performance tuning framework for FFT on various OpenCL GPUs,and implement a high performance library named MPFFT based on this framework.For power-of-two length FFTs,our library substantially outperforms the clAmdFft library on AMD GPUs and achieves comparable performance as the CUFFT library on NVIDIA GPUs.Furthermore,our library also supports non-power-of-two size.For 3D non-power-of-two FFTs,our library delivers 1.5x to 28x faster than FFTW with 4 threads and 20.01x average speedup over CUFFT 4.0 on Tesla C2050.     

基于OpenCL的图像积分图算法优化研究

图像积分图算法在快速特征检测中有着广泛的应用,通过GPU对其进行性能加速有着重要的现实意义。然而由于GPU硬件架构的复杂性和不同硬件体系架构间的差异性,完成图像积分图算法在GPU上的优化,进而实现不同GPU平台间的性能移植是一件非常困难的工作。在分析不同CPU平台底层硬件架构的基础上,从片外访存带宽利用率、计算资源利用率和数据本地化等多个角度考察了不同优化方法在不同GPU硬件平台上对性能的影响。并在此基础上实现了基于OpenCL的图像积分图算法。实验结果表明,优化后的算法在AMD和NVIDIA CPU上分别取得了11.26和12.38倍的性能加速,优化后的GPU kernel比NVIDIA NPP库中的相应函数也分别取得了55.01%和65.17%的性能提升。验证了提出的优化方法的有效性和性能可移植性。