《電子技術(shù)應(yīng)用》
您所在的位置：首頁(yè) > 模擬設(shè)計(jì) > 設(shè)計(jì)應(yīng)用 > 稀疏矩陣在C66x上的應(yīng)用及優(yōu)化
稀疏矩陣在C66x上的應(yīng)用及優(yōu)化
電子技術(shù)應(yīng)用
黃旭東，洪澤，陳振嬌
中國(guó)電子科技集團(tuán)公司第五十八研究所
摘要： 隨著大數(shù)據(jù)的爆炸式發(fā)展，稀疏矩陣已經(jīng)成為機(jī)器學(xué)習(xí)和邊緣計(jì)算的重要一環(huán)。在機(jī)器學(xué)習(xí)領(lǐng)域，數(shù)據(jù)集的稀疏矩陣化既可以保存信息又可以節(jié)省內(nèi)存，已成為不可避免的趨勢(shì)。SpMV（稀疏矩陣向量乘）作為稀疏矩陣計(jì)算中的核心，其迭代求解過(guò)程的空間復(fù)雜度和時(shí)間復(fù)雜度具有重要研究意義。分析稀疏矩陣C00、CSR、ELLPACK和DIA壓縮格式，改變稀疏矩陣的稀疏度和非零元素的分布，得出COO讀取數(shù)據(jù)、CSR進(jìn)行計(jì)算的SpMV通用性更強(qiáng)。利用C66x的VLIW指令構(gòu)架，采用軟件流水的方式對(duì)SpMV_CSR算法進(jìn)行指令并行優(yōu)化，利用SIMD單指令多數(shù)據(jù)指令集對(duì)SpMV_CSR算法完成數(shù)據(jù)并行優(yōu)化。實(shí)驗(yàn)結(jié)果表明，優(yōu)化后的SpMV_CSR算法相較于優(yōu)化前的加速比平均達(dá)到5倍以上。
關(guān)鍵詞： 稀疏矩陣 SpMV CSR C66x 軟件流水
中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)志碼：Ａ DOI: 10.16157/j.issn.0258-7998.244858
中文引用格式： 黃旭東，洪澤，陳振嬌. 稀疏矩陣在C66x上的應(yīng)用及優(yōu)化[J]. 電子技術(shù)應(yīng)用，2024，50(11)：23-27.
英文引用格式： Huang Xudong，Hong Ze，Chen Zhenjiao. Application and optimization of sparse matrix vector multiplication on C66x[J]. Application of Electronic Technique，2024，50(11)：23-27.
Application and optimization of sparse matrix vector multiplication on C66x
Huang Xudong，Hong Ze，Chen Zhenjiao
China Electronics Technology Group Corporation No.58 Research Institute
Abstract： With the explosive development of big data, sparse matrix has become an important part of machine learning and edge computing. In the field of machine learning, sparse matrix of data sets can not only save information but also save memory, which has become an inevitable trend. Sparse matrix vector multiplication (SpMV) is the core of sparse matrix computation. The space complexity and time complexity of its iterative solution process have important research significance. Analyze the compression format of sparse matrix C00, CSR, ELLPACK and DIA, change the sparsity of sparse matrix and the distribution of non-zero elements, and conclude that the SpMV read by COO and calculated by CSR is more universal. Utilizing the VLIW instruction architecture of C66x, using software pipelining to manage SpMV_CSR algorithm for instruction parallel optimization, utilizing SIMD single instruction multiple data instruction set for SpMV_CSR algorithm completes data parallel optimization. The experimental results indicate that the optimized SpMV_CSR algorithm has an average acceleration ratio of over 5 times compared to before optimization.
Key words : sparse matrix；SpMV；CSR；C66x；software pipelining；SIMD

引言

在機(jī)器學(xué)習(xí)和邊緣計(jì)算中，由于樣本數(shù)量巨大，大部分?jǐn)?shù)據(jù)集都是轉(zhuǎn)換成稀疏矩陣進(jìn)行數(shù)據(jù)處理。問(wèn)題求解通常轉(zhuǎn)換成解線性代數(shù)方程組AX=B，其中A大部分是稀疏矩陣，因此SpMV 在求解過(guò)程中被重復(fù)調(diào)用，SpMV 的計(jì)算效率直接影響了整體求解效率[1]。李億淵實(shí)現(xiàn)了SpMV 在申威SW26010處理器上的性能優(yōu)化[2-3]；吳志勇在FPGA上使用并行計(jì)算的方式對(duì)稀疏矩陣求解進(jìn)行加速[4]；談?wù)啄暝诋悩?gòu)計(jì)算平臺(tái)上完成了SpMV劃分優(yōu)化算法[5]；上述文獻(xiàn)方法SpMV 多集中于FPGA、CPU和GPU上的實(shí)現(xiàn)和優(yōu)化，而在高性能DSP C66x內(nèi)核上的研究還未見報(bào)道，因此開展此項(xiàng)工作具有重要意義。

稀疏矩陣具有自身特殊性，矩陣中大部分元素都是0，且0元素分布具有不規(guī)則性。大規(guī)模矩陣計(jì)算大部分都是稀疏矩陣計(jì)算，且稀疏度都在90%甚至99%以上，因此高效的稀疏矩陣壓縮格式更利于減少稀疏矩陣計(jì)算的空間復(fù)雜度[6]。如COO壓縮格式利用行號(hào)、列和數(shù)值三元組來(lái)表示，壓縮方式簡(jiǎn)單但不利于減少空間復(fù)雜度[7]。ELLPACK壓縮格式用兩個(gè)和原始矩陣相同行數(shù)的矩陣來(lái)存儲(chǔ)數(shù)據(jù)，DIA對(duì)角線壓縮法，按對(duì)角線方式存儲(chǔ)，列代表對(duì)角線，行代表行[8]。這兩種壓縮格式利于實(shí)現(xiàn)稀疏矩陣的應(yīng)用迭代法（如共軛梯度法），但是抵抗稀疏矩陣的隨機(jī)性較弱。CSR采用整體編碼格式，利用數(shù)值、列號(hào)以及行偏移來(lái)表示數(shù)據(jù)，比起DIA和ELLPACK格式，通用性更高且靈活。

C66x內(nèi)核采用VLIW構(gòu)架，集成了單精度和雙精度的浮點(diǎn)運(yùn)算單元，可以實(shí)現(xiàn)定點(diǎn)和浮點(diǎn)的操作。C66x 內(nèi)核可同時(shí)運(yùn)行多達(dá)八項(xiàng)浮點(diǎn)乘法運(yùn)算，加之高達(dá)1.25 GHz的時(shí)鐘頻率，單核浮點(diǎn)峰值可以達(dá)到20 GFLOPS[9]。目前C66x已經(jīng)廣泛應(yīng)用到電力控制，機(jī)器視覺，機(jī)器人等領(lǐng)域。

本文分析COO、ELLPACK、DIA和CSR壓縮格式的優(yōu)缺點(diǎn)，利用C66x的軟件流水和SIMD實(shí)現(xiàn)SpMV_CSR 算法的性能優(yōu)化。通過(guò)改變稀疏矩陣的規(guī)模和稠密度計(jì)算優(yōu)化后與優(yōu)化前的加速比，比較C66x內(nèi)核SpMV_CSR 優(yōu)化效果[10]。


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

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


作者信息：

黃旭東，洪澤，陳振嬌

（中國(guó)電子科技集團(tuán)公司第五十八研究所，江蘇 無(wú)錫214035）


Magazine.Subscription.jpg

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