一种稀疏矩阵向量乘访存优化的计算方法.pdf

(19)国家知识产权局(12)发明专利申请(10)申请公布号CN114491402A(43)申请公布日2022.05.13(21)申请号202210066814.X(22)申请日2022.01.20(71)申请人北京科技大学地址100083北京市海淀区学院路30号(72)发明人胡长军储根深何远杰丁哲昭董玲玉戴潮虎(74)专利代理机构北京市广友专利事务所有限责任公司11237专利代理师张仲波付忠林(51)Int.Cl.G06F17/16(2006.01)G06F9/50(2006.01)权利要求书1页说明书6页附图1页(54)发明名称一种稀疏矩阵向量乘访存优化的计算方法(57)摘要本发明公开了一种稀疏矩阵向量乘访存优化的计算方法，适用于DCU和GPU架构，该方法包括：将原始稀疏矩阵按照固定行数划分为若干块，每块由一个线程块单独完成计算，并为每个线程块在LDS开辟固定大小的空间；计算每一线程块需要计算的轮次数；在一个轮次的计算中，每个线程块中所有线程完成若干次非零元素计算并将结果写入LDS；每个线程块中一个或多个线程对LDS的乘法结果进行求和并将结果保存至寄存器；当完成所有轮次计算后，将寄存器中的结果进行进一步计算，并将结果写回显存。本发明基于原始CSR格式，无需预处理，且能充分利用访存合并特性，实现了较高的访存带宽利用。CN114491402ACN114491402A权利要求书1/1页1.一种稀疏矩阵向量乘访存优化的计算方法，适用于DCU和GPU架构，其特征在于，所述稀疏矩阵向量乘访存优化的计算方法包括：将原始稀疏矩阵按照固定行数划分为若干块，每块分别由一个线程块单独完成计算，并为每个线程块在LDS分别开辟固定大小的空间；计算每个线程块负责计算的非零元素数量，根据计算结果，结合预设的每个线程块每轮至多计算的非零元素个数，计算出每一线程块需要计算的轮次数；在一个轮次的计算中，每个线程块中所有线程完成若干次非零元素与相应向量中对应元素乘积的计算，并将乘法结果写入当前线程块所对应的LDS空间；将每个线程块中的所有线程以单个或多个线程为一组的形式进行划分，每一组线程分别对LDS的乘法结果进行求和，并将求和结果保存在寄存器中；当完成所有轮次的计算后，基于存储于寄存器中的求和结果，得到最终的计算结果，并将最终的计算结果写回显存。2.如权利要求1所述的稀疏矩阵向量乘访存优化的计算方法，其特征在于，所述原始稀疏矩阵使用CSR格式存储。3.如权利要求1所述的稀疏矩阵向量乘访存优化的计算方法，其特征在于，在将原始稀疏矩阵按照固定行数划分为若干块时，除最后一块之外，其余每块的行数相等且行数均为N，最后一块的行数小于或等于N。4.如权利要求1所述的稀疏矩阵向量乘访存优化的计算方法，其特征在于，每个线程块每轮至多计算的非零元素个数为R×M个；其中，M为每个线程块内含有线程的个数，R为正整数；在单个计算轮次中，每个线程块内每个线程完成当前线程块负责的稀疏矩阵块中最多R个非零元素与相应向量中对应元素乘积的计算。5.如权利要求1所述的稀疏矩阵向量乘访存优化的计算方法，其特征在于，在将每个线程块中的所有线程以单个或多个线程为一组的形式进行划分时，每组内的线程数量为2的非负整数次幂；并且，每个线程块的总组数大于或等于自身处理的矩阵行数。2CN114491402A说明书1/6页一种稀疏矩阵向量乘访存优化的计算方法技术领域[0001]本发明涉及高性能计算与算法技术领域，特别涉及一种适用于DCU和通用GPU架构的稀疏矩阵向量乘访存优化的计算方法。背景技术[0002]稀疏矩阵向量乘(SparseMatrix‑VectorMultiplication，SpMV)在科学计算、图形分析、信号处理等领域有着广泛的应用。其中参与计算的矩阵是稀疏的，即矩阵中大部分元素都为零。由于高效的压缩率，稀疏行压缩格式(CompressedSparseRowFormat，CSR)成为稀疏矩阵最常用的存储形式。在稀疏矩阵向量乘法中，其性能瓶颈是访存，如何提高访存性能成为关键。[0003]图形处理器(GPU，GraphicsProcessingUnit)可以提供强大的并行计算能力和巨大的数据吞吐量，在处理大规模数值计算问题方面表现优异，为高性能计算系统提供了坚实的计算平台。DCU(DeepComputingUnit，深度计算器)是GPU加速器的一种，其提供了高访存带宽。这使得在DCU加速器和GPU平台上实现高效的SpMV计算成为可能。[0004]现有的一些SpMV算法(如CSR‑Scalar、CSR‑Vector等方法)往往都面临访存不连续的问题，无法充分利用GPU的访存合并特性，因此访存带宽利用不高，总体性能损失较大。另外一些能高效利用访存带宽的方案(如CSR‑Stream算法、CSR‑Adapt