[發明專利]一種稀疏矩陣向量乘訪存優化的計算方法

在審

• 申請號: 202210066814.X
• 申請日: 2022-01-20
• 公開（公告）號: CN114491402A
• 公開（公告）日: 2022-05-13
• 發明（設計）人: 胡長軍;儲根深;何遠杰;丁哲昭;董玲玉;戴潮虎
• 申請（專利權）人: 北京科技大學
• 主分類號: G06F17/16
• 分類號: G06F17/16;G06F9/50
• 代理公司: 北京市廣友專利事務所有限責任公司 11237
• 代理人: 張仲波;付忠林

本發明公開了一種稀疏矩陣向量乘訪存優化的計算方法，適用于DCU和GPU架構，該方法包括：將原始稀疏矩陣按照固定行數劃分為若干塊，每塊由一個線程塊單獨完成計算，并為每個線程塊在LDS開辟固定大小的空間；計算每一線程塊需要計算的輪次數；在一個輪次的計算中，每個線程塊中所有線程完成若干次非零元素計算并將結果寫入LDS；每個線程塊中一個或多個線程對LDS的乘法結果進行求和并將結果保存至寄存器；當完成所有輪次計算后，將寄存器中的結果進行進一步計算，并將結果寫回顯存。本發明基于原始CSR格式，無需預處理，且能充分利用訪存合并特性，實現了較高的訪存帶寬利用。

技術領域

本發明涉及高性能計算與算法技術領域，特別涉及一種適用于DCU和通用GPU架構的稀疏矩陣向量乘訪存優化的計算方法。

背景技術

稀疏矩陣向量乘(Sparse Matrix-Vector Multiplication，SpMV)在科學計算、圖形分析、信號處理等領域有著廣泛的應用。其中參與計算的矩陣是稀疏的，即矩陣中大部分元素都為零。由于高效的壓縮率，稀疏行壓縮格式(Compressed Sparse Row Format，CSR)成為稀疏矩陣最常用的存儲形式。在稀疏矩陣向量乘法中，其性能瓶頸是訪存，如何提高訪存性能成為關鍵。

圖形處理器(GPU，Graphics Processing Unit)可以提供強大的并行計算能力和巨大的數據吞吐量，在處理大規模數值計算問題方面表現優異，為高性能計算系統提供了堅實的計算平臺。DCU(Deep Computing Unit，深度計算器)是GPU加速器的一種，其提供了高訪存帶寬。這使得在DCU加速器和GPU平臺上實現高效的SpMV計算成為可能。

現有的一些SpMV算法(如CSR-Scalar、CSR-Vector等方法)往往都面臨訪存不連續的問題，無法充分利用GPU的訪存合并特性，因此訪存帶寬利用不高，總體性能損失較大。另外一些能高效利用訪存帶寬的方案(如CSR-Stream算法、CSR-Adaptive算法、HOLA算法和CSR5)，往往需要進行預處理或者將CSR格式轉換為其他格式，額外開銷較大。

發明內容

本發明提供了一種稀疏矩陣向量乘訪存優化的計算方法及裝置，以解決現有技術所存在的訪存帶寬利用不高，總體性能損失大及額外開銷大的技術問題。

為解決上述技術問題，本發明提供了如下技術方案：

一方面，本發明提供了一種稀疏矩陣向量乘訪存優化的計算方法，適用于DCU和通用GPU架構，所述稀疏矩陣向量乘訪存優化的計算方法包括：

將原始稀疏矩陣按照固定行數劃分為若干塊，每塊分別由一個線程塊單獨完成計算，并為每個線程塊在LDS(即共享內存)分別開辟固定大小的空間；

計算每個線程塊負責計算的非零元素數量，根據計算結果，結合預設的每個線程塊每輪至多計算的非零元素個數，計算出每一線程塊需要計算的輪次數；

在一個輪次的計算中，每個線程塊中所有線程完成若干次非零元素與相應向量中對應元素乘積的計算，并將乘法結果寫入當前線程塊所對應的LDS空間；

將每個線程塊中的所有線程以單個或多個線程為一組的形式進行劃分，每一組線程分別對LDS的乘法結果進行求和，并將求和結果保存在寄存器中；

當完成所有輪次的計算后，基于存儲于寄存器中的求和結果，得到最終的計算結果，并將最終的計算結果寫回顯存。

進一步地，所述原始稀疏矩陣使用CSR格式存儲。

進一步地，在將原始稀疏矩陣按照固定行數劃分為若干塊時，除最后一塊之外，其余每塊的行數相等且行數均為N，最后一塊的行數小于或等于N。

進一步地，每個線程塊每輪至多計算的非零元素個數為R×M個；其中，M為每個線程塊內含有線程的個數，R為正整數；