《電子技術(shù)應(yīng)用》
您所在的位置：首頁(yè) > 模拟设计 > 设计应用 > 基于GPU的稀疏矩阵压缩存储格式研究
基于GPU的稀疏矩阵压缩存储格式研究
电子技术应用
陈闽昊，边浩东
青海大学 计算机技术与应用学院
摘要： 稀疏矩阵向量乘法（Sparse Matrix-Vector Multiplication，SpMV）是矩阵数值计算领域重要的线性代数子程序。通过对SpMV算法的负载均衡以及访存频度这两个关键性能瓶颈的研究，提出了一种VCSR（Vectorized Compressed Sparse Row）稀疏矩阵压缩存储格式。该格式根据各行非零元素分布的统计特性调整各个线程的数据负载来防止线程发散的问题，并且基于快速分段求和的策略以及使用矢量化的方法来提高SpMV流程的计算性能。通过使用佛罗里达大学的稀疏矩阵作为测试集，在GPU上进行性能测试，获得了相较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

引言

在過去的很長(zhǎng)一段時(shí)間中，SpMV都是科學(xué)計(jì)算和工程應(yīng)用領(lǐng)域中大規(guī)模稀疏性系統(tǒng)問題求解的常用方法，也因此其實(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ù)具有著分布稀疏無規(guī)則的問題，普通的順序計(jì)算和簡(jiǎn)單的并行優(yōu)化無法滿足現(xiàn)階段科學(xué)計(jì)算和工程應(yīng)用領(lǐng)域的要求，所以人們嘗試使用更快速的并行優(yōu)化算法以及提出更優(yōu)質(zhì)的壓縮存儲(chǔ)格式來加速大規(guī)模的SpMV計(jì)算。根據(jù)稀疏矩陣稀疏性、不規(guī)則性的特點(diǎn)，加速SpMV算法的難點(diǎn)主要集中在解決以下幾個(gè)問題上：（1）并行單元上負(fù)載不均衡導(dǎo)致的線程發(fā)散；（2）數(shù)據(jù)存儲(chǔ)不規(guī)則導(dǎo)致的頻繁訪存所產(chǎn)生的額外開銷；（3）低效矢量化產(chǎn)生的內(nèi)存訪問沖突和數(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è)過程中，將行作為數(shù)據(jù)分配的基礎(chǔ)單元，保證了線程與線程之間數(shù)據(jù)處理的相互獨(dú)立，不會(huì)產(chǎn)生數(shù)據(jù)依賴以及訪問沖突。最后，在每個(gè)并行單元中，使用快速分段求和的策略和矢量化的方式來加速SpMV內(nèi)核程序的計(jì)算性能。


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

http://m.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)載。

相關(guān)內(nèi)容