[發明專利]一種自適應稀疏矩陣向量乘策略選擇及優化方法

在審

• 申請號: 202210066813.5
• 申請日: 2022-01-20
• 公開（公告）號: CN114491401A
• 公開（公告）日: 2022-05-13
• 發明（設計）人: 胡長軍;盧旭;儲根深;何遠杰;董玲玉;邢龍岳
• 申請（專利權）人: 北京科技大學
• 主分類號: G06F17/16
• 分類號: G06F17/16
• 代理公司: 北京市廣友專利事務所有限責任公司 11237
• 代理人: 張仲波;付忠林

本發明公開了一種自適應稀疏矩陣向量乘策略選擇及優化方法，適用于GPU架構，該方法包括：對待處理矩陣按行進行分塊，統計各矩陣子塊的非零元素數，若各矩陣子塊的非零元素數差別倍數高于第一預設閾值，則采用自適應的CSR?Vector算法進行處理；統計待處理矩陣的行平均非零元素個數，若矩陣行平均非零元素個數低于第二預設閾值，則采用改進的CSR?Stream算法進行求解；統計待處理矩陣的非零元素個數，若其非零元素個數大于第三預設閾值，則采用hola算法進行求解；若以上條件均不滿足，則采用CSR?Vector算法進行求解。本發明實現了針對不同應用問題的自適應高效SpMV求解。

技術領域

本發明涉及高性能計算技術領域，特別涉及一種適用于GPU架構的自適應稀疏矩陣向量乘策略選擇及優化方法。

背景技術

SpMV(Sparse matrix–vector multiplication，稀疏矩陣向量乘)是形如y＝αAx+βy的矩陣向量乘法運算(其中，A是稀疏矩陣，x和y是稠密向量，α和β是標量)，它在科學計算、經濟建設、信號處理、文檔檢索等領域有著廣泛應用。通常，參與計算的矩陣是稀疏的，例如物理過程離散化產生的矩陣。近年來，SpMV被歸為七種被認為至少在未來十年對科學和工程非常重要的數值方法。

針對稀疏矩陣A不同的存儲格式，會有不同的SpMV算法，使用最為廣泛的稀疏矩陣存儲格式為CSR格式。目前，世界上基于異構多核計算系統對CSR存儲格式的SpMV算法進行了各種優化，并使其性能得到了顯著提升，如CSR-Vector算法、CSR-Stream算法、hola算法，三種算法的算法思想如下：

1)CSR-Vector算法：將wavefront劃分為多個包含相等線程數的線程向量(vector)，其中一個vector包含多個線程。最終由一個vector計算矩陣的一行與x向量相乘，vector內一個線程負責一行中部分數據的計算。一個vector計算完畢后，將各線程的結果規約到0號線程中，并由vector內的0號線程將結果寫回到內存上的y數組。CSR-Vector的缺點也很明顯，對于矩陣行非零元素較少的情況，進行從內存加載數據和數據寫回步驟時，vector之間訪存不連續，但對于矩陣行非零元素較多的情況時，這一劣勢可得到有效緩解。

2)CSR-Stream算法：按照矩陣行數進行劃分，每個block負責計算相同數量的行。CSR-Stream方法中，Block內每個線程從內存連續地訪問value數組、非零元素列索引Col_Index數組，并將其乘法結果保存在LDS中，最后若干線程從LDS中進行規約且每個線程規約一行。CSR-Stream方法各線程對存儲非零元素的Value數組、非零元素列索引Col_Index數組以及y向量訪存都是連續的，但是由于該方法需要預先在LDS為Value數組與x向量中元素的乘積分配存儲空間，因此CSR-Stream方法不適用于每行含有的非零元素個數太多的矩陣。

3)hola算法：按照非零元素數量進行任務劃分，使得每個block計算相同數量的非零元素。由于CSR的格式中，矩陣非零數值、列索引都是按行順序排列而成的，也是比較適合采用“按非零元素進行任務劃分”的，特別是對于行平均非零元素較大的矩陣，其y數組和行偏移索引Row_Index的load/store開銷占比較小，按照“非零元素數”來進行負載均衡，是十分有效的一種任務劃分策略。該方法的缺點是，其需要一個GPU端的預處理過程，這使得對于小規模的矩陣而言，其帶來的性能提升可能并不明顯，甚至會導致性能變差。

對于上述算法，雖然在特定矩陣條件下提高了計算性能，但對不同領域問題求解(如結構力學、計算流體力學、計算機圖形學等)優化的通用性較差。

發明內容

本發明提供了一種自適應稀疏矩陣向量乘策略選擇及優化方法，以解決現有的SpMV算法雖然在特定矩陣條件下提高了計算性能，但對不同領域問題求解優化的通用性較差的技術問題。

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