基于GPU的稀疏矩陣壓縮存儲格式研究
電子技術應用
陳閩昊，邊浩東
青海大學 計算機技術與應用學院
摘要： 稀疏矩陣向量乘法（Sparse Matrix-Vector Multiplication，SpMV）是矩陣數值計算領域重要的線性代數子程序。通過對SpMV算法的負載均衡以及訪存頻度這兩個關鍵性能瓶頸的研究，提出了一種VCSR（Vectorized Compressed Sparse Row）稀疏矩陣壓縮存儲格式。該格式根據各行非零元素分布的統計特性調整各個線程的數據負載來防止線程發散的問題，并且基于快速分段求和的策略以及使用矢量化的方法來提高SpMV流程的計算性能。通過使用佛羅里達大學的稀疏矩陣作為測試集，在GPU上進行性能測試，獲得了相較CSR5（Compressed Sparse Row 5）格式平均10%到30%，最高50%的性能提升。
中圖分類號：TP312 文獻標志碼：A DOI: 10.16157/j.issn.0258-7998.245825
中文引用格式： 陳閩昊，邊浩東. 基于GPU的稀疏矩陣壓縮存儲格式研究[J]. 電子技術應用，2024，50(11)：1-8.
英文引用格式： Chen Minhao，Bian Haodong. Sparse matrix compressed storage format based on GPU[J]. Application of Electronic Technique，2024，50(11)：1-8.
中文引用格式： 陳閩昊，邊浩東. 基于GPU的稀疏矩陣壓縮存儲格式研究[J]. 電子技術應用，2024，50(11)：1-8.
英文引用格式： Chen Minhao，Bian Haodong. Sparse matrix compressed storage format based on GPU[J]. Application of Electronic Technique，2024，50(11)：1-8.
Sparse matrix compressed storage format based on GPU
Chen Minhao，Bian Haodong
School of Computer Technology and Application， Qinghai University
Abstract： Sparse Matrix-Vector Multiplication (SpMV) is an important linear algebraic subroutine in Matrix numerical computation. Vectorized Compressed Sparse Row (VCSR) sparse matrix compression format is proposed by studying the load balancing and memory access frequency of SpMV algorithm. This format adjusts the data load of each thread according to the statistical characteristics of the distribution of each line of non-zero elements to prevent the problem of thread divergence, and improves the computational performance of SpMV flow based on the strategy of fast segmented summation and the vectorization method. By using the Sparse matrix of the University of Florida as the test set, the performance of the GPU is tested, and the average performance improvement is 10% to 30%, and the maximum performance is 50% compared to the CSR5 (Compressed Sparse Row 5) format.
Key words : SpMV；load balancing；storage format；segmented sum methods；floating-point calculation；vectorization；GPU
引言
在過去的很長一段時間中，SpMV都是科學計算和工程應用領域中大規模稀疏性系統問題求解的常用方法，也因此其實現和優化一直是高性能領域研究中的重點。SpMV計算簡化為一個大小為m×n的稀疏矩陣A與長度為n的密集向量x相乘，從而得到一個長度為m的向量y。
隨著稀疏矩陣規模的擴大，同時又因為其數據具有著分布稀疏無規則的問題，普通的順序計算和簡單的并行優化無法滿足現階段科學計算和工程應用領域的要求，所以人們嘗試使用更快速的并行優化算法以及提出更優質的壓縮存儲格式來加速大規模的SpMV計算。根據稀疏矩陣稀疏性、不規則性的特點，加速SpMV算法的難點主要集中在解決以下幾個問題上：（1）并行單元上負載不均衡導致的線程發散；（2）數據存儲不規則導致的頻繁訪存所產生的額外開銷；（3）低效矢量化產生的內存訪問沖突和數據依賴性。現階段許多的壓縮存儲格式也從這幾個方面入手加速大規模SpMV運算，例如BELLPACK、CVR、BCCOO、ACSR、CSR5[1-4]等。
本文也從這上述幾個方面入手，提出了一種新的格式名為VCSR，VCSR格式以CSR格式作為基礎，根據各行非零元素分布的統計特性，將數據以負載均衡的方式分發給各個線程。在這個過程中，將行作為數據分配的基礎單元，保證了線程與線程之間數據處理的相互獨立，不會產生數據依賴以及訪問沖突。最后，在每個并行單元中，使用快速分段求和的策略和矢量化的方式來加速SpMV內核程序的計算性能。
本文詳細內容請下載：
http://www.shi-ke.cn/resource/share/2000006202
作者信息：
陳閩昊，邊浩東
（青海大學 計算機技術與應用學院，青海 西寧 810016）
此內容為AET網站原創，未經授權禁止轉載。