[發(fā)明專利]一種基于CSR格式的高性能稀疏矩陣向量乘法計算方法

在審

• 申請?zhí)枺?/td>: 202110636177.0
• 申請日: 2021-06-08
• 公開（公告）號: CN113377534A
• 公開（公告）日: 2021-09-10
• 發(fā)明（設(shè)計）人: 王超;張加浩;左岳;王寅初;周亦非
• 申請（專利權(quán)）人: 東南大學(xué)
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F9/52
• 代理公司: 南京瑞弘專利商標(biāo)事務(wù)所(普通合伙) 32249
• 代理人: 孫峰

本發(fā)明公開了一種基于CSR格式的高性能稀疏矩陣向量乘法計算方法，該方法首先根據(jù)現(xiàn)有的方法進(jìn)行空間局部性優(yōu)化，循環(huán)效率優(yōu)化與訪存效率優(yōu)化；根據(jù)現(xiàn)有硬件資源的配置與仿真情況，自適應(yīng)的開辟合理數(shù)目的線程，優(yōu)化加鎖解鎖方式使線程池更高效；針對cache missing問題與硬件條件完成適應(yīng)性的親和性設(shè)置。本發(fā)明基于傳統(tǒng)的CSR格式的稀疏矩陣向量乘法，充分考慮硬件資源對計算性能的限制，以及算法對計算效率與訪存效率的影響；在改進(jìn)原有算法基礎(chǔ)上，模型可以資源配置與任務(wù)數(shù)目，自適應(yīng)的通過基于矩陣索引的線程池與親和性設(shè)置完成仿真加速。

技術(shù)領(lǐng)域

本發(fā)明涉及稀疏矩陣向量乘法計算的技術(shù)領(lǐng)域，特別是涉及一種基于CSR格式的高性能稀疏矩陣向量乘法計算方法。

背景技術(shù)

目前工藝的不斷進(jìn)步，結(jié)點(diǎn)的尺寸在不斷縮小，導(dǎo)致集成電路的密集程度不斷增加。尤其針對大型的存儲電路(動態(tài)隨機(jī)存取存儲器,靜態(tài)隨機(jī)存取存儲器,快閃存儲器等)，矩陣向量運(yùn)算會在整個仿真中占據(jù)很大規(guī)模的時間，仿真所運(yùn)算的矩陣與向量與電路規(guī)模成正比，矩陣的規(guī)模甚至?xí)_(dá)到千萬維以上。但是電路中不同的結(jié)點(diǎn)之間并不是全連接關(guān)系，用簡單的二維數(shù)組去表示會有大量的0值，存儲空間有著極大的消耗。而采用CSR格式的壓縮矩陣去存儲并計算這些稀疏矩陣向量乘法，雖然可以減少大量的零元素的乘法，但是依舊會存在以下問題。

要計算的矩陣中，每行非零值數(shù)目不確定，非零值位置未知，甚至要仿真的行都是要變化的，因此在不考慮并發(fā)的條件下，如何在CSR格式下調(diào)度數(shù)據(jù)并選取合理的計算方式，保證各非零值找到的同時并完成加速。

通過CSR格式壓縮稀疏矩陣，順序訪問壓縮矩陣元素即可完成對矩陣所有元素的訪問，同時，通過對應(yīng)的橫坐標(biāo)值，可以訪問與該矩陣元素進(jìn)行乘法運(yùn)算的向量元素。

利用多線程是實(shí)現(xiàn)加速的一個重要途徑，但是選取獨(dú)立的計算單元保證線程之間不沖突，與如何處理多個矩陣之間運(yùn)算順序保證各個矩陣都完成仿真都是要考慮的問題，在保證這兩個條件下，如何做到更快的仿真依舊是重點(diǎn)與難點(diǎn)。

矩陣數(shù)據(jù)以CSR格式在內(nèi)存中進(jìn)行存儲，可以保證每次緩存訪問都可以從內(nèi)存中拿到相當(dāng)比例的非零元素。在CPU對緩存中的數(shù)據(jù)訪問時，在L1,L2,L3cache每次向上傳遞時，也都可以保證緩存命中。但是向量由內(nèi)存向緩存在向CPU傳遞時，依舊會存在cachemissing現(xiàn)象。簡單的利用多線程會使線程在不同core上反復(fù)調(diào)度，每個CPU core都要求對數(shù)據(jù)的重新搬運(yùn)，會造成更嚴(yán)重的cache missing，甚至是DRAM從磁盤中調(diào)用所需數(shù)據(jù)，數(shù)據(jù)搬運(yùn)所消耗的時間變得越來越重要，已不再是簡單的計算密集型仿真任務(wù)，更是訪存類型的問題。

發(fā)明內(nèi)容

有鑒于此，本發(fā)明的目的在于提供一種基于CSR格式的高性能稀疏矩陣向量乘法計算方法，針對現(xiàn)有技術(shù)存在的仿真速度慢，讀取內(nèi)存中CSR格式的數(shù)據(jù)時造成不規(guī)則訪問導(dǎo)致cache missing，帶寬利用率低，多線程加速不理想以及帶來的cache missing等問題。本發(fā)明為針對超大規(guī)模集成電路仿真中CSR格式的稀疏矩陣向量乘法，提供一種能優(yōu)化計算結(jié)構(gòu)與多線程調(diào)度方式，能夠充分利用硬件CPU并行資源，自適應(yīng)完成親和性設(shè)置來實(shí)現(xiàn)SPMV(稀疏矩陣向量乘法)優(yōu)化的方法。

為解決上述技術(shù)問題，本發(fā)明采用的技術(shù)方案為：

一種基于CSR格式的高性能稀疏矩陣向量乘法計算方法，包括如下步驟：

步驟S1、采用最簡高效循環(huán)結(jié)構(gòu)，進(jìn)行空間局部性優(yōu)化，循環(huán)效率優(yōu)化與訪存效率優(yōu)化；

步驟S2、引入局部變量減少冗余訪存和冗余計算；

步驟S3、在利用多線程加快仿真結(jié)果方面，借鑒線程池的基本思想并對線程池進(jìn)行改進(jìn)；

步驟S4、采用適應(yīng)性的親和性設(shè)置。

進(jìn)一步的，所述采用最簡高效循環(huán)結(jié)構(gòu)具體包括：