《電子技術(shù)應(yīng)用》
您所在的位置：首頁(yè) > 模擬設(shè)計(jì) > 設(shè)計(jì)應(yīng)用 > 基于GPU的稀疏矩陣壓縮存儲(chǔ)格式研究
基于GPU的稀疏矩陣壓縮存儲(chǔ)格式研究
電子技術(shù)應(yīng)用
陳閩昊，邊浩東
青海大學(xué) 計(jì)算機(jī)技術(shù)與應(yīng)用學(xué)院
摘要： 稀疏矩陣向量乘法（Sparse Matrix-Vector Multiplication，SpMV）是矩陣數(shù)值計(jì)算領(lǐng)域重要的線性代數(shù)子程序。通過(guò)對(duì)SpMV算法的負(fù)載均衡以及訪存頻度這兩個(gè)關(guān)鍵性能瓶頸的研究，提出了一種VCSR（Vectorized Compressed Sparse Row）稀疏矩陣壓縮存儲(chǔ)格式。該格式根據(jù)各行非零元素分布的統(tǒng)計(jì)特性調(diào)整各個(gè)線程的數(shù)據(jù)負(fù)載來(lái)防止線程發(fā)散的問(wèn)題，并且基于快速分段求和的策略以及使用矢量化的方法來(lái)提高SpMV流程的計(jì)算性能。通過(guò)使用佛羅里達(dá)大學(xué)的稀疏矩陣作為測(cè)試集，在GPU上進(jìn)行性能測(cè)試，獲得了相較CSR5（Compressed Sparse Row 5）格式平均10%到30%，最高50%的性能提升。
中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)志碼：A DOI: 10.16157/j.issn.0258-7998.245825
中文引用格式： 陳閩昊，邊浩東. 基于GPU的稀疏矩陣壓縮存儲(chǔ)格式研究[J]. 電子技術(shù)應(yīng)用，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

引言

在過(guò)去的很長(zhǎng)一段時(shí)間中，SpMV都是科學(xué)計(jì)算和工程應(yīng)用領(lǐng)域中大規(guī)模稀疏性系統(tǒng)問(wèn)題求解的常用方法，也因此其實(shí)現(xiàn)和優(yōu)化一直是高性能領(lǐng)域研究中的重點(diǎn)。SpMV計(jì)算簡(jiǎn)化為一個(gè)大小為m×n的稀疏矩陣A與長(zhǎng)度為n的密集向量x相乘，從而得到一個(gè)長(zhǎng)度為m的向量y。

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

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


本文詳細(xì)內(nèi)容請(qǐng)下載：

http://ihrv.cn/resource/share/2000006202


作者信息：

陳閩昊，邊浩東

（青海大學(xué) 計(jì)算機(jī)技術(shù)與應(yīng)用學(xué)院，青海 西寧 810016）


Magazine.Subscription.jpg

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