大规模稀疏矩阵的主特征向量计算优化方法

矩阵主特征向量(principal eigenvectors computing,PEC)的求解是科学与工程计算中的一个重要问题。随着图形处理单元通用计算(general-purpose computing on graphics pro cessing unit,GPGPU)的兴起,利用GPU来优化大规模稀疏矩阵的图形处理单元求解得到了广泛关注。分别从应用特征和GPU体系结构特征两方面分析了PEC运算的性能瓶颈,提出了一种面向GPU的稀疏矩阵存储格式——GPU-ELL和一个针对GPU的线程优化映射策略,并设计了相应的PEC优化执行算法。在ATI HD Radeon5850上的实验结果表明,相对于传统CPU,该方案获得了最多200倍左右的加速,相对于已有GPU上的实现,也获得了2倍的加速。     

图形处理器通用计算的实现与验证

讨论了显示卡用于通用科学计算的问题,并以大型矩阵的基本运算问题详细比较了CPU和GPU计算之间的差别。在基本的矩阵运算中,运用适当的矩阵分块,GPU的计算速度比CPU快50倍左右。而且,显示卡低廉的价格为更多科研工作者实现大规模运算提供了可能。     

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

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

大规模三角线性方程的高效求解

大规模三角线性方程求解是科学与工程应用中重要的计算核心,受限于处理器的缓存容量和结构设计,其在CPU和GPU等平台上的计算效率不高。大规模三角线性方程的分块求解中,矩阵乘是主要运算,其计算效率对提升三角线性方程求解的计算效率至关重要。以矩阵乘计算效率较高的矩阵乘协处理器为计算平台,针对其结构特点提出了矩阵乘协处理器上大规模三角线性方程分块求解的实现方法和性能分析模型。实验结果表明,矩阵乘协处理器上大规模三角线性方程求解的计算效率最高可达85.9%,其实际性能和资源利用率分别为同等工艺下GPU的2.42倍和10.72倍。     

基于图形处理器的边缘检测算法

边缘检测是一种高度并行的算法,计算量较大,传统的CPU处理难以满足实时要求。针对图像边缘检测问题的计算密集性,在分析常用边缘检测算法的基础上,利用CUDA(Compute Unified Device Architecture,计算统一设备架构)软硬件体系架构,提出了图像边缘检测的GPU(Graphics Processing Unit,图形处理器)实现方案。首先介绍GPU高强度并行运算的体系结构基础,并将Roberts和Sobel这两个具有代表性的图像边缘检测算法移植到GPU,然后利用当前同等价格的CPU和GPU进行对比实验,利用多幅不同分辨率图像作为测试数据,对比CPU和GPU方案的计算效率。实验结果表明,与相同算法的CPU实现相比,其GPU实现获得了相同的处理效果,并将计算效率最高提升到了17倍以上,以此证明GPU在数字图像处理的实际应用中大有潜力。     

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

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

基于GPU的稀疏矩阵Cholesky分解

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

基于图形处理器的层次聚类算法效率研究

鉴于Larsen等人利用图形处理器（GPU）的多纹理技术做矩阵运算操作,以实现GPU在矩阵相乘方面的通用计算,提出一种利用GPU和CPU的协同处理模式,应用在基于层次聚类的动态近邻选择模型的聚类算法（DNNS）中,将算法中比较耗时的邻接度矩阵计算步骤交由GPU完成,而算法其余步骤由CPU执行,从而使算法的聚类效率得到显著提高。在配有Pentium IV 3.4 G CPU和NVIDIA GeForce 7800GT显卡的硬件环境下经过实验测试,证明这种协同处理模式下的运算速度比完全采用CPU计算速度要快25%左右。这种改进的层次聚类算法适合在数据流环境下对大量数据进行实时高效聚类操作。     

GPU上循环矩阵的快速求逆算法

循环矩阵是一种特殊类型的Toeplitz矩阵,在很多专业领域尤其是图像和数字信号处理中有广泛的应用。计算其逆矩阵的快速算法由三个步骤组成:(1)使用离散傅立叶变换将矩阵的第一行元素转换到频率空间;(2)计算转换后的频谱中每个幅度的倒数;(3)在调整过的频谱上施加傅立叶反变换,获得逆矩阵的第一行元素,从而构建原始循环矩阵的逆矩阵。此算法的特点是每个数据元素的计算过程完全相同,同时独立于其它元素的计算,因而非常适合在GPU上运行。本文在GPU上实现了上述循环矩阵求逆的快速算法,将其转换为一个正方形的图形绘制。实验结果表明,该算法在GPU上的运行速度比在CPU上提高了大约10倍。     

基于GPU的多层次并行QR分解算法研究

QR分解作为一个基本计算模块,广泛应用在图像处理、信号处理、通信工程等众多领域.传统的并行QR分解算法只能挖掘计算过程中的数据级并行.在分析快速Givens Rotation分解特征的基础上,提出了一种多层次并行算法,能够同时挖掘计算过程中的任务级并行和数据级并行,非常适合于以图形处理器(GPU)为代表的大规模并行处理器.同时,采用GPU的并行QR分解算法可以作为基本运算模块被GPU平台上的众多应用程序直接调用.实验结果显示,与CPU平台上使用OpenMP实现的算法相比,基于GPU的多层次并行算法能够获得5倍以上的性能提升,而调用QR分解模块的奇异值分解(SVD)应用可以获得3倍以上的性能提升.     

Parallel multi-objective Ant Programming for classification using GPUs

Classification using Ant Programming is a challenging data mining task which demands a great deal of computational resources when handling data sets of high dimensionality. This paper presents a new parallelization approach of an existing multi-objective Ant Programming model for classification, using GPUs and the NVIDIA CUDA programming model. The computational costs of the different steps of the algorithm are evaluated and it is discussed how best to parallelize them. The features of both the CPU parallel and GPU versions of the algorithm are presented. An experimental study is carried out to evaluate the performance and efficiency of the interpreter of the rules, and reports the execution times and speedups regarding variable population size, complexity of the rules mined and dimensionality of the data sets. Experiments measure the original single-threaded and the new multi-threaded CPU and GPU times with different number of GPU devices. The results are reported in terms of the number of Giga GP operations per second of the interpreter (up to 10 billion GPops/s) and the speedup achieved (up to 834× vs CPU, 212× vs 4-threaded CPU). The proposed GPU model is demonstrated to scale efficiently to larger datasets and to multiple GPU devices, which allows the expansion of its applicability to significantly more complicated data sets, previously unmanageable by the original algorithm in reasonable time.     

PMVS算法的CPU多线程和GPU两级粒度并行策略

PMVS(Patch-based Multi-View Stereo)三维重建算法被广泛应用于无人机航拍影像的三维场景重建中。针对PMVS三维重建算法计算量大、时间复杂度高的问题,提出了PMVS算法的CPU多线程和GPU两级粒度并行策略(Multithread and GPU Parallel Schema,MGPS),方法具体包括:基于GPU的PMVS算法特征提取和片面扩散的并行设计;多影像的GPU和CPU任务分配机制,以使得部分任务分配给CPU采用多线程并行,部分任务分配给GPU并行时,程序总运行时间最短。实验采用搭载24核CPU和NVIDIA Tesla K20 GPU的高性能服务器作为测试平台,针对分辨率为4081×2993的16幅无人机影像进行三维重建。实验结果表明,相比串行的PMVS算法,基于MGPS的PMVS算法取得4倍左右的加速比,其中特征提取最高加速13倍,计算误差在10%以内,该方法实现了更高效的PMVS三维重建。基于MGPS的PMVS算法还可用于文物保护、医学图像处理、虚拟现实等领域。     

CPU与GPU上几种矩阵乘法的比较与分析

描述了矩阵乘法在CPU上的三种实现方法和在GPU上基于CUDA架构的四种实现方法,分析了高性能方法的原由,发现它们的共同特点都是合理地组织数据并加以利用,这样能有效地减少存取开销,极大地提高算法的速度。其中CPU上的最优实现方法比普通算法快了200多倍,GPU上的最优实现方法又比CPU上的最优实现方法快了约6倍。     

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

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

GPU-OSDDA: a bit-vector GPU-based deadlock detection algorithm for single-unit resource systems

This article presents a GPU-based single-unit deadlock detection methodology and its algorithm, GPU-OSDDA. Our GPU-based design utilizes parallel hardware of GPU to perform computations and thus is able to overcome the major limitation of prior hardware-based approaches by having the capability of handling thousands of processes and resources, whilst achieving real-world run-times. By utilizing a bit-vector technique for storing algorithm matrices and designing novel, efficient algorithmic methods, we not only reduce memory usage dramatically but also achieve two orders of magnitude speedup over CPU equivalents. Additionally, GPU-OSDDA acts as an interactive service to the CPU, because all of the aforementioned computations and matrix management techniques take place on the GPU, requiring minimal interaction with the CPU. GPU-OSDDA is implemented on three GPU cards: Tesla C2050, Tesla K20c, and Titan X. Our design shows overall speedups of 6-595X over CPU equivalents.     

融合遗传和蚁群算法并行求解最短公共超串

依据各级缓存容量,将CPU主存中种群个体和蚂蚁个体数据划分存储到一级、二级和三级缓存中,以减少并行计算过程中数据在各级存储之间的传输开销,在CPU与GPU之间采取异步传送和不完全传送数据、GPU多个内核函数异步执行多个流的方法,设置GPU block线程数量为16的倍数、GPU共享存储器划分大小为32倍的bank,使用GPU常量存储器存储交叉概率、变异概率等需频繁访问的只读参数,将输入串矩阵和重叠部分长度矩阵只读大数据结构绑定到GPU纹理存储器,设计实现了一种多核CPU和GPU协同求解最短公共超串问题的计算、存储和通信高效的并行算法。求解多种规模的最短公共超串问题的实验结果表明,多核CPU与GPU协同并行算法比串行算法快70倍以上。     

采用GPU的ZIP密码恢复算法

常用的zip密码恢复软件使用通用处理器进行密码恢复,每秒尝试密码次数少,往往需要很长时间才能找到正确密码。为了提高密码破解效率,提出了GPU平台上的快速ZIP密码恢复算法,针对GPU的特点,重点优化了寄存器使用以及存储器访问,对AES和HMAC算法进行了并行优化,充分发挥了GPU大规模并行运算的优势,并利用ZIP文档格式中的密码校验位提前筛选密码,大部分错误密码都不需要进行后续运算。实验结果表明,恢复AES-128加密的ZIP文档,基于GPU的算法实现了11.09倍的加速比。