计算机科学与探索

作者：王宇华, 张宇琪, 何俊飞, 徐悦竹, 崔环宇

单位：哈尔滨工程大学 计算机科学与技术学院，哈尔滨 150000

关键词：稀疏矩阵向量乘法（SpMV）,重新排序,CSR格式,负载均衡,存储格式,图形处理器（GPU）

稀疏矩阵向量乘法（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倍。

来源：2024年第4期

《计算机科学与探索》期刊编辑部

查看计算机科学与探索杂志2024年第4期