在cuda上实现有效的稀疏矩阵乘法

《在cuda上实现有效的稀疏矩阵乘法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、在CUDA上实现有效的稀疏矩阵乘法摘要图像处理单元（GPU）的大规模并行性在许多高性能计算应用中提供了巨大的业绩。当稠密线性代数绘制到这样的平台上，利用这种可能性来进行稀疏矩阵的计算就呈现出额外的许多挑战。其在用迭代方法解决稀疏线性系统和特征值问题，以及稀疏矩阵向量乘法方面的地位在稀疏线性代数中具有独特的重要性。在本文中，我们讨论用于SPMV（稀疏矩阵向量乘法）的数据结构和算法，使SPMV在适合GPU的细粒度并行结构的CUDA技术平台上可以有效的执行。基于SPMV的有限存储特性，我们强调有效的内存带宽和紧凑的存储格式。我们认为广泛的稀疏矩阵来自那些结构严谨的规则矩阵和那些经

2、常在矩阵的每行带有不平衡的非零值分布的高度不规则矩阵。我们开发一些方法来探究许多常见的矩阵结构形式，同时也提供一些备选方案来适应更多更大的不规则矩阵。从结构上说，在一个GeForceGTX280GPU平台上，基于网格的矩阵，在单精度模式中我们可以获得每秒36亿次的性能，而在双精度模式中我们可以获得每秒16亿次的性能。对于没有结构的有限元素矩阵，我们通过分别进行超过每秒15亿次和10亿次的单双精度测试来观察它们的性能。这些结果比起之前用传统的多核处理器进行的关于SPMV的state-of-the-art研究方法要好的多。我们的双精度SPMV性能大体上是一个CellBEwith

3、8SPEs系统的2.5倍，是一个四核的INTELClovertown系统的10倍还多。1.介绍稀疏矩阵结构出现在许多计算学科中，因此评价一种方法能否有效地操作这些矩阵往往取决于他们在许多应用中的性能如何，稀疏矩阵乘法（SPMV）运算已经被证明在计算科学领域具有非常重要的意义。在许多用于科学工程应用中用来解决大规模线性系统和特征值问题的方法中，SPMV运算呈现出突出的价值。这些迭代方法剩下的部分可以典型地概括为稠密线性代数操作，而这些操作已经被BLAS和LAPACK尽可能有效地解决。最新的NVIDIAGPUS适应高吞吐量的多核处理能够提供非常高的计算吞吐量峰值，实现这种可能性

4、需要执行大量的细粒度并行性和结构化计算来实现执行通络和内存存取方式的足够规律性。最近，VolkovandDemmelandBarrachina已经证明了如何通过线性矩阵操作来获得吞吐量和带宽的峰值点。稠密矩阵操作是非常普遍的，因此也经常被限制于吞吐量浮点（floatingpointthroughput）。相比之下，稀疏矩阵操作在存取方式中更普遍，因此其速度一般限于纯粹的带宽。在本文中，我们研究用于GPU之类的多核处理器上的有效的SPMV内核的设计。我们用CUDA执行这些内核程序并在GeForceGTX280GPU上分析他们的性能。出现在不同问题中的稀疏矩阵呈现出广泛的规律性

5、。我们认为，从高度规则的对角线矩阵到高度不同行长度的无规则矩阵，数据交涉的实现技术都贯穿于其中。即使SPMV操作具有不规律性，我们可以证明他们可以被成功的映射为细粒度并行结构（fine-grantedparallerarchietecture）从而被GPU使用。对于非结构化矩阵，我们使用大约每秒10亿次的双精度和每秒15亿次的单精度来衡量他们的性能。此外，这些内核程序达到大约每秒90Gb带宽或者65%的峰值时，表明在限制带宽的计算中存在现对较高的有效性。1.稀疏矩阵格式这里有大量稀疏矩阵的代表格式，每一种都有不同的存储要求，计算特征，以及访问和进行矩阵操作的方法。在稀疏矩阵

6、矢量乘法（SPMV）中，我们并不关心修改矩阵元素，我们仅考虑静态的稀疏矩阵格式，而不是那些适合元素快速插入和删除的特征。各种稀疏矩阵实例之间最主要的差别在于他们的稀疏模式，或者说非零值的结构。虽然稀疏格式适合高度具体的各种矩阵类具有很大的计算吸引力，同样重要的是考虑一般存储策略针对任意稀疏模式的矩阵存储。在这一章节的接下来部分我们总结了一些稀疏矩阵的范例并且讨论了他们之间的相关权衡。第四部分将讨论采用CUDA技术对每一种稀疏格式执行SPMV操作。2.1对角线格式当非零值被限制在少量的矩阵对角线上时，对角线格式就是这样的一个非常恰当的范例，尽管并不是一个通用的格式，对角线存储

7、策略仍然可以有效地对矩阵（从实际应用的模型到规则的网格）进行编码，并且是一种普遍的离散化方法。图4说明了一个带有5条对角线的25*25的稀疏矩阵格式。图4：一个带有5条对角线的25*25的稀疏矩阵格式。该矩阵近似于5*5的拉普拉斯算子。对角线格式由两个矩阵组成；data矩阵，用来存储非零值，offset数组，用来存储每一条对角线到主对角线的偏移量。规定，主对角线偏移量相当于0，当i>0时表示在主对角线之上的第i条对角线，当i<0时表示在主对角线之下的第i条对角线。图5说明了一个带有3条对角线的对角线格式矩阵的范例。