《電子技術應用》
您所在的位置：首頁 > 模擬設計 > 設計應用 > 基于GPU的稀疏矩陣壓縮存儲格式研究
基于GPU的稀疏矩陣壓縮存儲格式研究
電子技術應用
陳閩昊，邊浩東
青海大學 計算機技術與應用學院
摘要： 稀疏矩陣向量乘法（Sparse Matrix-Vector Multiplication，SpMV）是矩陣數(shù)值計算領域重要的線性代數(shù)子程序。通過對SpMV算法的負載均衡以及訪存頻度這兩個關鍵性能瓶頸的研究，提出了一種VCSR（Vectorized Compressed Sparse Row）稀疏矩陣壓縮存儲格式。該格式根據(jù)各行非零元素分布的統(tǒng)計特性調(diào)整各個線程的數(shù)據(jù)負載來防止線程發(fā)散的問題，并且基于快速分段求和的策略以及使用矢量化的方法來提高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.
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都是科學計算和工程應用領域中大規(guī)模稀疏性系統(tǒng)問題求解的常用方法，也因此其實現(xiàn)和優(yōu)化一直是高性能領域研究中的重點。SpMV計算簡化為一個大小為m×n的稀疏矩陣A與長度為n的密集向量x相乘，從而得到一個長度為m的向量y。

隨著稀疏矩陣規(guī)模的擴大，同時又因為其數(shù)據(jù)具有著分布稀疏無規(guī)則的問題，普通的順序計算和簡單的并行優(yōu)化無法滿足現(xiàn)階段科學計算和工程應用領域的要求，所以人們嘗試使用更快速的并行優(yōu)化算法以及提出更優(yōu)質(zhì)的壓縮存儲格式來加速大規(guī)模的SpMV計算。根據(jù)稀疏矩陣稀疏性、不規(guī)則性的特點，加速SpMV算法的難點主要集中在解決以下幾個問題上：（1）并行單元上負載不均衡導致的線程發(fā)散；（2）數(shù)據(jù)存儲不規(guī)則導致的頻繁訪存所產(chǎn)生的額外開銷；（3）低效矢量化產(chǎn)生的內(nèi)存訪問沖突和數(shù)據(jù)依賴性。現(xiàn)階段許多的壓縮存儲格式也從這幾個方面入手加速大規(guī)模SpMV運算，例如BELLPACK、CVR、BCCOO、ACSR、CSR5[1-4]等。

本文也從這上述幾個方面入手，提出了一種新的格式名為VCSR，VCSR格式以CSR格式作為基礎，根據(jù)各行非零元素分布的統(tǒng)計特性，將數(shù)據(jù)以負載均衡的方式分發(fā)給各個線程。在這個過程中，將行作為數(shù)據(jù)分配的基礎單元，保證了線程與線程之間數(shù)據(jù)處理的相互獨立，不會產(chǎn)生數(shù)據(jù)依賴以及訪問沖突。最后，在每個并行單元中，使用快速分段求和的策略和矢量化的方式來加速SpMV內(nèi)核程序的計算性能。


本文詳細內(nèi)容請下載：

http://theprogrammingfactory.com/resource/share/2000006202


作者信息：

陳閩昊，邊浩東

（青海大學 計算機技術與應用學院，青海 西寧 810016）


Magazine.Subscription.jpg

此內(nèi)容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權禁止轉(zhuǎn)載。