选择粗化函数优化并行稀疏矩阵向量乘法

讨论了如何分划稀疏矩阵的非零元素以减少并行矩阵向量乘法的通信代价。通过以粗化函数为工具,统一现有的数据分划方法;提出一种基于行列分划为初解的粗化函数选取方法,在理论上的证明其运行效率与分划质量不逊于一维数据分划方法;实验数据表明,该方法产生分划质量超过一维数据分划方法的结果,接近甚至超过二维细粒度方上法的结果。

TEB:GPU上矩阵分解重构的高效SpMV存储格式

稀疏矩阵向量乘法(SpMV)是科学与工程领域中一个至关重要的计算过程,CSR(compressed sparse row)格式是最常用的稀疏矩阵存储格式之一,在图形处理器(GPU)平台上实现并行SpMV的过程中,其只存储稀疏矩阵的非零元,避免零元素填充所带来的计算冗余,节约存储空间,但存在着负载不均衡的问题,浪费了计算资源。针对上述问题,对近年来效果良好的存储格式进行了研究,提出了一种逐行分解重组存储格式——TEB(threshold-exchangeorder block)格式。该格式采用启发式阈值选择算法确定合适分割阈值,并结合基于重排序的行归并算法,对稀疏矩阵进行重构分解,使得块与块之间非零元个数尽可能得相近,其次结合CUDA(computer unified device architecture)线程技术,提出了基于TEB存储格式的子块间并行SpMV算法,能够合理分配计算资源,解决负载不均衡问题,从而提高SpMV并行计算效率。为了验证TEB存储格式的有效性,在NVIDIA Tesla V100平台上进行实验,结果表明TEB相较于PBC(partition-block-CSR)、AMF-CSR(adaptive multi-row folding of CSR)、CSR-Scalar(compressed sparse row-scalar)和CSR5(compressed sparse row 5)存储格式,在SpMV的时间性能方面平均可提升3.23、5.83、2.33和2.21倍;在浮点计算性能方面,平均可提高3.36、5.95、2.29和2.13倍。

面向稀疏矩阵向量乘的DMA设计与验证

稀疏矩阵向量乘法(SpMV)是迭代法求解大型线性方程组的核心算法,被广泛应用在科研和工程中。高性能共轭梯度算法(HPCG)是评价高性能计算系统性能的测试程序之一,需要多次调用SpMV进行迭代计算。但是,SpMV计算过程中包含大量不规则访存操作,降低了系统计算性能。基于X-DSP项目,在DMA中设计一条面向SpMV的专用数据通道实现不规则访存的功能,提高HPCG算法运算速度。设计代码的验证与综合结果表明预期的功能实现正确,且满足项目对时序、面积和功耗的要求。

基于HYB格式SpMV在新一代申威架构上的实现与优化

稀疏矩阵与稠密向量乘SpMV在高性能计算领域有着广泛的应用。稀疏矩阵因其非零元素分布的稀疏性和不规则性,使得运算的并行化较稠密矩阵难度更大。因此,稀疏矩阵向量乘法的性能优化一直都是高性能计算领域中的研究重点。基于稀疏矩阵的HYB存储格式,面向国产新一代申威异构众核处理器SW26010P,设计了一种并行SpMV算法及其性能优化方案。并针对HYB存储格式的阈值选取难点,提出了一种多次迭代最大类间方差的方法,以确定HYB格式的阈值。实验结果表明,相比主核上的串行算法,并行SpMV算法可以获得23.36的平均加速比和34.85的最高加速比。

一种用于图形渲染的高性能SpMV专用加速器结构

图形渲染中涉及的几何变换、投影变换、视口变换等需要大量稀疏矩阵向量乘法(Sparse Matrix-Vector Multiplication,SpM V)运算,如何实现SpMV高性能计算成为了图形处理器设计中的关键性问题之一,然而,当前的SpMV运算存在并行度较差,资源占用较多等问题.为提升硬件运算的性能,本文基于矩阵列向量的线性组合,充分利用数据的并行性,设计了一种专用加速器结构.实验表明,在XC6VLX550T开发板上与其他两种结构相比,速度分别能够提高28%、37%,资源占用率分别减少约48%、18%,应用于图形渲染中的变换操作后,速度分别能够提高28%、30%,资源占用率分别最高减少约48%、60%.

一种针对GPU上的油藏数值模拟的高效SpMV

油藏数值模拟和很多其他科学计算问题一样需要求解大型稀疏线性代数方程组.在求解稀疏线性代数方程组的迭代法中,稀疏矩阵向量乘法(SpMV)是影响计算效率的核心函数之一.随着计算机硬件架构异构化,科学计算从单核、多核CPU计算架构逐渐发展到多核CPU+众核加速卡(GPU卡或MIC等)的计算架构.SpMV的实现效率与稀疏矩阵的存储格式及硬件架构关系密切.本文针对油藏模拟中常见的Jacobian矩阵的稀疏模式,利用GPU核心的合并访问和并发计算等特点,结合油藏模拟线性解法器的算法要求,设计了一种BHYB矩阵存储格式及其对应的线程组并行策略.数值实验测得基于该存储格式的SpMV相对串行BCSR格式的SpMV的加速比可达19倍,比cuSPARSE库中效率最高的HYB格式的SpMV快30%到80%.此外,本文所提出的BHYB存储格式对块状矩阵在GPU上的存储以及线程组并行策略对其它GPU并行程序中内核函数的设计和优化能起到一定的借鉴作用.