王 鑫,彭 健

(江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院,江蘇 無錫 214122)

1 引言

稀疏矩陣向量乘法SpMV(Sparse Matrix-Vector multiplication)是科學(xué)計算與工程應(yīng)用中一個廣泛使用的計算核心,在機(jī)器學(xué)習(xí)[1]、圖像分析[2]等領(lǐng)域中有著廣泛應(yīng)用。SpMV涉及最多的應(yīng)用就是大規(guī)模稀疏線性系統(tǒng)的迭代求解,求解過程中包含大量循環(huán)或者迭代的SpMV操作,這會帶來巨大的時間開銷,從而影響整個系統(tǒng)的求解效率。因此,對SpMV算法的加速與優(yōu)化是至關(guān)重要的。

稀疏矩陣向量乘法是用于計算y=A×x等式的方法,其中,等式右側(cè)的矩陣A表示稀疏矩陣,x表示參與計算的稠密向量,左側(cè)的y則代表經(jīng)過計算后得到的結(jié)果向量。稀疏矩陣中非零元素的分布情況復(fù)雜且很不規(guī)則,處理器計算架構(gòu)又處于不斷升級的狀態(tài),所以,SpMV并行算法的設(shè)計與優(yōu)化實現(xiàn)是現(xiàn)在算法研究的熱點之一。目前,擁有強大并行計算能力的處理器得到了普遍使用,例如GPU(Graphics Processing Unit)[3]、Intel公司提供的眾核處理器Intel Xeon Phi[4]等,利用這些處理器的并行計算架構(gòu)能迅速提升SpMV的計算性能,研究成果不在少數(shù)。隨著國產(chǎn)眾核處理器的不斷發(fā)展,研究在其上實現(xiàn)高效的SpMV算法具有現(xiàn)實意義,因此,本文選擇國產(chǎn)新一代申威異構(gòu)眾核處理器SW26010P作為計算平臺,研究SpMV算法的并行化設(shè)計。

提高SpMV計算性能不僅跟處理器架構(gòu)有關(guān),還取決于如何選取一個合適的稀疏矩陣存儲格式。稀疏矩陣中非零元素占比低且分布不規(guī)則的特性,使得稀疏矩陣的存儲格式具有多樣性。最常見的稀疏矩陣存儲格式有COO(COOrdinate)格式、ELL(ELLPACK)格式、CSR(Compressed Sparse Row)格式和HYB(HYBrid)格式等。其中,COO格式采用三元組的形式對稀疏矩陣中非零元素進(jìn)行存儲,三元組由行索引、列索引和數(shù)值構(gòu)成,該存儲格式是最為簡單的一種存儲格式,比較直觀靈活,但不利于計算和并行化;CSR格式采用數(shù)值、列號、行偏移3類數(shù)據(jù)的編碼方式,數(shù)值和列號按照行順序存儲非零元素的值和列索引,行偏移存儲每一行的第一個元素在數(shù)值中的起始偏移位置,它是一種較為普遍使用的存儲格式;ELL格式采用m×k的矩陣存儲數(shù)據(jù),其中k為稀疏矩陣中每行非零元素個數(shù)中的最大值,該格式與稠密矩陣較為相似,只是在矩陣的列數(shù)上進(jìn)行了壓縮,適合并行化計算;HYB格式則結(jié)合了ELL和COO 2種格式的優(yōu)點,對每行中超出給定閾值的非零元素使用COO格式存儲,以解決ELL格式由于每行之間非零元素個數(shù)差異過大導(dǎo)致過多的零值填充。

本文對SpMV算法的并行化設(shè)計是基于HYB存儲格式。HYB格式中閾值的選取是一個難點,常常采用經(jīng)驗法來確定閾值。針對這個問題,本文提出了一種新的閾值劃分方法,并借助新一代申威異構(gòu)眾核處理器強大的計算能力和高度的并行架構(gòu),設(shè)計出一種并行SpMV算法。

2 背景

2.1 申威眾核處理器SW26010P

SW26010P處理器是我國自主研發(fā)的新一代神威超級計算機(jī)上所使用的處理器[5],圖1展示了其硬件架構(gòu)。

Figure 1 Architecture of SW26010P CPU

每個SW26010P異構(gòu)眾核處理器集成了6個核心組CG(Core Group),每個CG包括1個主核MPE(Management Processing Element)與1個由64個從核組成的從核陣列CPE(Computing Processing Element),總共390個核心。眾核處理器每個核心組本地內(nèi)存容量為16 GB,單個核組的內(nèi)存帶寬為51.2 GB/s,總內(nèi)存帶寬為307.2 GB/s。

每個主核包含1個L1指令緩存和1個L1數(shù)據(jù)緩存,以及1個數(shù)據(jù)和指令共用的L2緩存,這3類緩存都是由硬件控制的。每個從核包含一塊容量為256 KB的本地數(shù)據(jù)存儲空間LDM(Local Data Memory),其完全由軟件管理,其容量有限,訪存速度快,屬于處理器的珍惜資源。每個從核支持直接存儲器訪問DMA(Direct Memory Access),通過DMA操作可以實現(xiàn)LDM與主存之間粗粒度數(shù)據(jù)的快速訪問,以提高從核訪問主存的效率。處理器的另一個特性是從核支持遠(yuǎn)程內(nèi)存訪問RMA(Remote Memory Access),RMA取代了上一代處理器SW26010的寄存器通信技術(shù)[6],從核通過RMA操作實現(xiàn)本地LDM與其他從核LDM之間的高效數(shù)據(jù)傳輸,可以緩解LDM容量有限的問題。

2.2 相關(guān)工作

SpMV的并行實現(xiàn)和優(yōu)化,一直是科學(xué)計算領(lǐng)域中的一個研究熱點。尤其當(dāng)一款新的處理器問世時,基于該處理器的稀疏矩陣向量乘法的實現(xiàn)與優(yōu)化工作就會持續(xù)不斷。Cardellini等人[7]基于多種稀疏矩陣存儲格式和負(fù)載均衡策略研究了適合異構(gòu)CPU+GPU計算平臺的SpMV實現(xiàn)與優(yōu)化。Sun等人[8]在GPU平臺上提出了一種基于索引壓縮的SpMV優(yōu)化方法,該方法可以顯著減少索引的訪問次數(shù),提高訪存性能。Zhang等人[9]針對多核結(jié)構(gòu)上SpMV的內(nèi)存帶寬高和負(fù)載不均衡的問題提出了解決方法。Elafrou等人[10]針對GPGPUs提出了一種SpMV瓶頸感知的自動調(diào)節(jié)器——BASMAT(Bottleneck-Aware Sparse matrix-vector Multiplication Auto-Tuner),可以根據(jù)輸入稀疏矩陣的結(jié)構(gòu)特點自動優(yōu)化SpMV內(nèi)核,以解決GPGPUs上內(nèi)存帶寬、內(nèi)存延遲和線程不平衡的問題。Zhang等人[11]利用Intel?Xeon?Phi眾核架構(gòu)上的向量單元,提出了一種切片ELLPACK稀疏矩陣存儲格式并設(shè)計了相應(yīng)的SpMV并行算法。Liu等人[12]提出了一種新的存儲格式ESB(ELLPACK Sparse Block),該格式有助于改善Intel?Xeon?Phi處理器上SpMV向量化性能,并且能減少帶寬需求。除了常用CPU、GPU平臺外,還有許多是針對上一代申威處理器SW26010的研究。Sun等人[13]在SW26010處理器上針對CSR存儲格式設(shè)計了SWCSR-SpMV算法,并利用申威眾核架構(gòu)特殊的局存通信技術(shù)優(yōu)化了SpMV的訪存性能。

合適的稀疏矩陣存儲格式也是優(yōu)化SpMV的一個關(guān)鍵之處。Liu等人[14]提出了一種新的存儲格式CSR5(Compressed Sparse Row 5),該格式對輸入稀疏矩陣的結(jié)構(gòu)特性不敏感,易于從傳統(tǒng)的CSR格式轉(zhuǎn)換得到,并能夠在多個平臺上實現(xiàn),通用性較強。Zhang等人[9]在COO格式的基礎(chǔ)上設(shè)計了一種新的稀疏矩陣存儲格式BCCOO(Blocked Compressed COO),用以緩解SpMV帶寬的限制,再通過對矩陣垂直切片將BCCOO格式改進(jìn)為BCCOO+格式,以獲得更好的數(shù)據(jù)局部性;為了解決SpMV負(fù)載不均衡的問題,還提出一種高效的基于矩陣的SpMV分段/掃描算法。Bian等人[15]提出了一種適用于SIMD(Single Instruction Multiple Data)的稀疏矩陣存儲格式CSR2,該格式操作易于實現(xiàn),轉(zhuǎn)換開銷小。另外,針對不同特性的稀疏矩陣,采用混合壓縮存儲格式更能適應(yīng)不規(guī)則的稀疏特征。比如,Liang等人[16]提出的HCC(HydroCAD prefab Chamber data file)格式,采用了CSR+COO混合格式;陽王東等人[17]針對準(zhǔn)對角矩陣的不規(guī)則性,采用DIA+CSR混合格式來提升SpMV性能;陽王東等人[18]基于混合COO和ELL格式的HYB格式,利用數(shù)據(jù)劃分策略實現(xiàn)SpMV在CPU+GPU上的異構(gòu)計算。

3 稀疏矩陣存儲格式

3.1 COO存儲格式

COO格式采用三元組的編碼方式來存儲稀疏矩陣中的非零元素。三元組指的是rowindices、colindices和values3個數(shù)組,其中rowindices記錄非零元素所在的行索引,colindices記錄非零元素所在的列索引,values記錄非零元素的值。對于圖2a所示的稀疏矩陣A,其COO格式如圖2b所示。

Figure 2 Example of the COO format

COO格式的存儲方式可以有效地存儲任何結(jié)構(gòu)的稀疏矩陣,簡單直觀,但是數(shù)據(jù)訪問缺乏像稠密矩陣行列訪問的規(guī)則性,不適合在并行架構(gòu)處理器上進(jìn)行并行運算。

3.2 ELL存儲格式

ELL格式采用2個與原始矩陣行數(shù)相同的矩陣來存儲數(shù)據(jù),列數(shù)為包含非零元素最多行的非零元素數(shù)。其中,values矩陣存儲非零元素的值,colindices矩陣存儲非零元素的列索引,對于values矩陣中的零元素可以由零值填充,colindices矩陣可以由-1填充。對于如圖2a所示的稀疏矩陣A,其ELL格式如圖3所示。

Figure 3 Example of the ELL format

ELL格式與稠密矩陣的存儲方式相似,相比COO格式更適合在并行架構(gòu)處理器上運算,但當(dāng)矩陣中每行非零元素個數(shù)差異較大時,就會導(dǎo)致ELL格式的存儲效率和計算效率驟降。

3.3 HYB存儲格式

HYB格式是采用ELL格式和COO格式混合的存儲格式,根據(jù)閾值將稀疏矩陣劃分為ELL格式和COO格式2個部分存儲,對于每行元素個數(shù)小于閾值的部分采用ELL格式存儲,大于閾值的部分采用COO格式存儲。對于圖2a所示的稀疏矩陣A,其HYB格式如圖4所示。

Figure 4 Example of the HYB format

對于HYB格式,其ELL格式存儲部分由數(shù)值矩陣values和列索引矩陣colindices存儲,COO格式存儲部分由coo_row、coo_col和coo_val數(shù)組分別存儲超出閾值部分非零元素的行索引、列索引和值。HYB格式彌補了ELL格式由于非零元素數(shù)量差異過大導(dǎo)致的存儲空間過于冗余的缺陷,但是閾值的選取是一個難點。

4 SpMV算法并行設(shè)計

4.1 SpMV并行設(shè)計整體框架概述

基于HYB存儲格式的SpMV算法實現(xiàn)主要涉及2個方面的內(nèi)容:其一是HYB格式閾值的確定方法;其二是基于HYB格式的SpMV在SW26010P處理器上的設(shè)計。圖5展示了其整體的框架結(jié)構(gòu)。

Figure 5 Overall framework of the SpMV design

針對HYB格式閾值選取的難點,本文提出了一種多次迭代最大類間方差法的方法來確定HYB格式的閾值。

閾值確定后,HYB格式由ELL格式和COO格式2個部分構(gòu)成。針對并行架構(gòu)友好的ELL格式采用從核陣列進(jìn)行并行處理,COO格式則采用主核進(jìn)行串行處理,2個部分的結(jié)果進(jìn)行累加即為最終的計算結(jié)果。

4.2 HYB格式的閾值劃分算法

對于HYB格式,通常是基于經(jīng)驗法選取閾值作為ELL和COO之間的分割值,這導(dǎo)致ELL和COO部分非零元素所占比例存在很大的不確定性,容易影響SpMV計算的性能。為了解決HYB格式所存在的問題,本節(jié)提出了一種新的閾值劃分算法。

本文提出的閾值劃分算法基于最大類間方差法(Otsu)[19]。Otsu是由日本學(xué)者大津展之(Nobuyuki Otsu)在1979年提出的,它是一種處理圖像二值化的非參數(shù)、自適應(yīng)閾值分割方法,也稱大津算法。假設(shè)稀疏矩陣A包含M行、N列以及NNZ個非零元數(shù)量,x為輸入向量,y為輸出向量,T為HYB格式的閾值。假設(shè)t={1,2,…,N}為閾值選取范圍,nnz_left是以t為分割線矩陣左邊的非零元素個數(shù),nnz_right是以t為分割線矩陣右邊的非零元素個數(shù),nnz_left_all是以t為分割線矩陣左邊的所有元素個數(shù),nnz_right_all是以t為分割線矩陣右邊的所有元素個數(shù),假設(shè)以t為分割線矩陣左邊非零元素占左邊總元素的比例稱為左區(qū)均值,其定義如式(1)所示:

(1)

以t為分割線矩陣右邊非零元素占右邊總元素的比例稱為右區(qū)均值,其定義如式(2)所示:

(2)

以t為分割線矩陣左邊元素占矩陣總元素的比例ω0的定義如式(3)所示:

(3)

以t為分割線矩陣右邊元素占矩陣總元素的比例的定義如式(4)所示:

(4)

則整個矩陣的均值如式(5)所示:

u=ω0u0+ω1u1

(5)

根據(jù)最大類間方差法建立的目標(biāo)函數(shù)如式(6)所示:

g=ω0(u0-u)2+ω1(u1-u)2

(6)

其中,g就是當(dāng)分割閾值為t時矩陣左右兩邊的類間方差表達(dá)式。遍歷整個閾值選取范圍t,使得t為某個值時類間方差最大,則這個值就是HYB格式的分割閾值T。

計算閾值之前,需要對稀疏矩陣A進(jìn)行預(yù)處理。先將稀疏矩陣A按照ELL方式存儲,但不壓縮稀疏矩陣的列,重新排布后的稀疏矩陣記為A′,包含M行、N列。根據(jù)經(jīng)驗,采用一次基于最大類間方差法確定的閾值,COO部分占的比例依然比較大,所以,針對HYB格式最終的閾值選取方法采用的是多次迭代最大類間方差法。一般認(rèn)為當(dāng)COO部分的非零元素個數(shù)比例低于P時(P定義為COO部分非零元素個數(shù)占總非零元素個數(shù)的比例)就停止迭代,此時,將多次迭代過程中確定的閾值累加后即為最終的閾值。

多次迭代最大類間方差法的偽代碼如下所示:

輸入：ELL存儲格式稀疏矩陣A′;稀疏矩陣的行數(shù)M與列數(shù)N;非零元素數(shù)量NNZ。

輸出：HYB分割閾值T。

1:floatu0,u1,ω0,ω1;

2:floatg[N];

3:intTtmp=0;

4:initiatet[N];

5:do

6:intNtmp=N-Ttmp;

7:fori=0 toNtmpdo

8: calculateu0,u1,ω0,ω1;

9: calculateg[i];

11:intindex=0;

12:fori=0 toNtmpdo

13:ifg[index]

14:index=i;

15:endif

16:endfor

17:Ttmp=index+1;

18:T+=Ttmp;

19: calculatep;

兩權(quán)分離度與企業(yè)技術(shù)創(chuàng)新實證研究——兼論產(chǎn)權(quán)性質(zhì)與業(yè)績偏離的調(diào)節(jié)效應(yīng)..................................................................................................................................劉 玉 盛宇華（60）

20:ifp

21:break;

22:endif

23:while(1)

24:returnT;

第1～4行:定義一些臨時變量。比如g[N]表示遍歷整個閾值選取范圍t得到的類間方差數(shù)組,Ttmp表示每次迭代的臨時閾值。

第6行:Ntmp表示每次迭代過程中稀疏矩陣的列數(shù)。

第8～9行:遍歷計算類間方差,結(jié)果存放在g[N]數(shù)組中。

第11～17行:根據(jù)數(shù)組g[N]得到最大類間方差所對應(yīng)的臨時閾值Ttmp。

第18行:將臨時閾值Ttmp累加到閾值T中。

第19～24行:計算COO部分的非零元素數(shù)占總非零元素數(shù)的比例,結(jié)果存放在p中。若小于設(shè)定的比例P,則停止迭代,并返回最終的閾值。

4.3 HYB格式的SpMV并行設(shè)計

HYB格式是由ELL格式和COO格式構(gòu)成的,其中,ELL格式適合并行處理,COO格式數(shù)據(jù)分布比較松散,不宜并行處理。因此,針對HYB格式中的ELL部分,采用SW26010P處理器中的從核陣列進(jìn)行并行SpMV運算,COO部分則在主核上進(jìn)行串行運算。

定義Np為SW26010P處理器上核組的個數(shù),Nc為每個核組上從核的個數(shù)。定義矩陣At為經(jīng)過閾值劃分后ELL部分的數(shù)值矩陣?；贖YB格式的SpMV并行設(shè)計分為以下幾個部分:

(1)對于單個核組的從核陣列,將矩陣At按行劃分為Nc個塊矩陣(block),每塊含有M/Nc行。每塊矩陣的數(shù)值和索引部分和輸入向量x都分配到一個從核上。

(2)由于每個從核256 KB的私有存儲限制,每個塊矩陣又被進(jìn)一步劃分為多個含有τ行的子塊(subblock)。子塊矩陣的數(shù)值和索引部分、輸入向量x以及計算含有τ行的結(jié)果向量所占的存儲空間不應(yīng)超過256 KB。圖6展示了一個基于HYB格式在SW26010P處理器上的SpMV算法并行設(shè)計的例子。如圖6所示,A是一個8×8稀疏矩陣,包含26個非零元素,即M=8,N=8,NNZ=26。假設(shè)核組的個數(shù)Np設(shè)置為1,從核的個數(shù)Nc設(shè)置為2,每個子塊的行τ設(shè)置為2,T=3為HYB的劃分閾值。

Figure 6 Example of parallel SpMV design

首先,每個從核需要加載輸入向量x、子塊矩陣的數(shù)值和索引部分到LDM空間上;其次,從核進(jìn)行子塊矩陣與輸入向量x的SpMV計算;最后,將部分計算結(jié)果向量寫回到主存中。

如圖6所示,每個從核的子塊矩陣計算后的結(jié)果向量記為ycpe,包含τ個元素,將每個從核計算的結(jié)果合并成整個向量,記為ycg,ycg就是HYB格式中ELL部分并行計算的結(jié)果。從核陣列完成ELL部分的并行計算后,主核完成COO部分的串行運算,并與ycg進(jìn)行累加后返回最終的計算結(jié)果。

5 SpMV并行設(shè)計優(yōu)化技術(shù)

5.1 雙緩沖優(yōu)化

對于HYB格式中的并行計算部分,從核先通過DMA的方式加載計算數(shù)據(jù)到從核LDM上,加載完成后才開始進(jìn)行SpMV計算,計算完成后再把計算后的數(shù)據(jù)寫回到主存中,上述過程其實是一個串行執(zhí)行的過程,在一定程度上會影響SpMV性能,所以,本文采用了雙緩沖機(jī)制進(jìn)行優(yōu)化。

如圖7所示,雙緩沖機(jī)制本質(zhì)上是一種并行流水技術(shù),它能使計算開銷和通信開銷相互隱藏,從而取得良好的加速效果。具體來說,就是在從核的LDM空間上申請2倍于通信數(shù)據(jù)大小的存儲空間,以便存放2份同樣大小且互為對方緩沖的數(shù)據(jù)。對于每個從核,塊矩陣劃分成幾個子塊,一個塊矩陣的SpMV運算就需要幾個輪次子塊的加載、計算和寫回。在串行執(zhí)行階段,后一個子塊的加載、計算和寫回需要前一個子塊加載、計算和寫回完成后才能進(jìn)行,采用雙緩沖優(yōu)化后,除了第1個子塊的加載和最后1個子塊的寫回外,其余子塊的計算和通信存在重疊過程,從而節(jié)省一定的時間開銷,提高了SpMV的性能。

Figure 7 Sketch map of double buffers mechanism

5.2 DMA傳輸帶寬優(yōu)化

根據(jù)SW26010P處理器架構(gòu),DMA處理部件會把DMA請求拆分成128 B的多次請求來訪問主存數(shù)據(jù)。非128 B對界的地址,DMA會拆出更多的請求。因此,當(dāng)主存中的數(shù)據(jù)地址與128 B對齊,且傳輸?shù)臄?shù)據(jù)量是128 B的倍數(shù)時,DMA的傳輸性能就會得到提高。

SW26010P處理器上一個整數(shù)占用的內(nèi)存大小是4 B,一個單精度浮點數(shù)占用的內(nèi)存大小也是4 B。對于并行SpMV設(shè)計,每個從核需要加載一個子塊(subblock)的ELL 2個矩陣,矩陣大小為τ行、T列。由于T無法改變,且為了保證ELL 2個矩陣中的元素個數(shù)為128/4的倍數(shù),所以,將τ設(shè)置為128/4的倍數(shù),以保證數(shù)據(jù)對齊內(nèi)存訪問,進(jìn)一步提高SpMV的性能。

6 實驗與結(jié)果分析

6.1 實驗環(huán)境

本文實驗使用的測試平臺是SW26010P處理器的單個核組,其訪存帶寬為51.2 GB/s,擁有1個主核和8×8的從核陣列。測試選擇的稀疏矩陣樣例都來自于UF Sparse Matrix Collection[20],即佛羅里達(dá)大學(xué)的稀疏矩陣集合。表1展示了測試用的10個稀疏矩陣樣例。

Table 1 Test examples of sparse matrices

在本文實驗中,通常將P設(shè)置為0.5%,但是為了獲得更好的性能,P值可以進(jìn)一步調(diào)整。為了驗證本文設(shè)計的SpMV算法的加速效果,使用加速比(Speedup)和加速效率作為評價標(biāo)準(zhǔn),同時采用GFlops作為性能測試單位。其中,加速比定義為算法的并行執(zhí)行時間與串行執(zhí)行時間的比值,加速效率定義為加速比與從核個數(shù)的比值,GFlops定義為2倍的稀疏矩陣非零元素的個數(shù)與算法的并行執(zhí)行時間的比值。GFlops數(shù)值越大,表明算法性能越好。

6.2 實驗結(jié)果分析

圖8展示了基于HYB格式的并行SpMV設(shè)計在單個核組(CG)上實現(xiàn)的加速比和加速效率,使用了64個從核(CPE)。加速比是通過計算基于HYB格式在單個CG上的并行SpMV計算時間與在一個主核上的串行計算時間的比值獲取的,加速效率則是加速比與從核個數(shù)的比值。

Figure 8 Speedup and efficiency of the parallel SpMV design on single CG

如圖8所示,本文所設(shè)計的并行SpMV算法在單個CG上可以獲得平均23.36的加速比,平均的加速效率為36.50%,其中,在稀疏矩陣nd6k上獲得最高加速比34.85,加速效率為54.45%;在稀疏矩陣ex6上獲得最低加速比10.03,加速效率為15.67%。結(jié)合圖8的加速比、加速效率和表1中測試矩陣的規(guī)模,可以看出,在稀疏矩陣規(guī)模比較大的情況下,本文設(shè)計的并行SpMV算法加速效果優(yōu)于規(guī)模比較小的情況。除此之外,算法的平均加速效率偏低,這主要受制于ELL部分?jǐn)?shù)據(jù)在主從核之間的通信開銷。

圖9展示了主核上串行SpMV算法、使用64個從核的并行SpMV算法以及采用雙緩沖優(yōu)化和DMA傳輸帶寬優(yōu)化技術(shù)后的并行算法的性能對比。串行SpMV算法的性能由標(biāo)簽“MPE”表示,使用64個從核的并行SpMV算法的性能由標(biāo)簽“MPE+CPE”表示,采用雙緩沖優(yōu)化后的性能由標(biāo)簽“MPE+CPE with DB”表示,采用DMA傳輸帶寬優(yōu)化后的性能由標(biāo)簽“MPE+CPE with TB”表示。采用DMA傳輸帶寬優(yōu)化技術(shù)后,設(shè)計的并行SpMV算法性能平均提升了5.93%,最高提升了13.26%,最低提升了1.55%。采用雙緩沖優(yōu)化技術(shù)后,設(shè)計的并行SpMV算法性能平均提升了16.30%,最高提升了44.44%,最低提升了2.48%。ex6和ex40稀疏矩陣性能提升比較小,這是因為數(shù)據(jù)規(guī)模比較小時,分到每個從核的數(shù)據(jù)運算速度快,而數(shù)據(jù)加載與寫回動作的發(fā)起需要耗費時間,從而無法有效地進(jìn)行計算訪存重疊,因此,采用雙緩沖優(yōu)化的效果不顯著。

圖10展示了設(shè)計的并行算法在從核上的并行可擴(kuò)展性,并給出了并行算法在不同從核數(shù)量下的性能對比。設(shè)置的從核數(shù)量Nc分別為1,4,16和64。當(dāng)從核個數(shù)為64時,本文設(shè)計的算法在稀疏矩陣nd6k上最高可獲得6.31 GFlops的性能。隨著從核個數(shù)的增加,基于HYB格式的異構(gòu)并行SpMV算法的性能也在逐步提升,這是因為從核數(shù)量越多,同一時間內(nèi)處理的矩陣數(shù)據(jù)就越多,所消耗的時間就越少,并行性能越好。然而,隨著從核個數(shù)的增加,性能雖在不斷提高,但是增長比例卻在逐漸下降,這主要是主核與從核之間的通信開銷以及從核之間爭奪計算資源導(dǎo)致的額外開銷造成的。

Figure 10 Performance of the parallel SpMV design with different CPEs

7 結(jié)束語

稀疏矩陣向量乘法在高性能計算領(lǐng)域中占有重要地位,是數(shù)據(jù)分析、深度學(xué)習(xí)等應(yīng)用領(lǐng)域中非常重要的核心算法之一。本文根據(jù)新一代申威處理器SW26010P的計算架構(gòu)和內(nèi)存模式,提出了一種基于HYB格式的異構(gòu)并行設(shè)計方案,并對HYB格式的并行計算部分采用了通信與計算相互隱藏的優(yōu)化技術(shù),同時,針對HYB格式閾值選取難的問題,提出了一種多次迭代的自適應(yīng)閾值確定方法。測試結(jié)果表明,在單個核組下,本文提出的異構(gòu)并行SpMV算法最高可以獲得6.31 GFlops的性能,采用DMA傳輸帶寬優(yōu)化技術(shù)后,最高可獲得13.26%的性能提升,采用雙緩沖優(yōu)化技術(shù)后,最高可獲得44.44%的性能提升。但是,目前實現(xiàn)的算法都是基于單個核組的,面向SW26010P處理器的多核組結(jié)構(gòu)的并行SpMV設(shè)計還有待研究,并且針對其他稀疏矩陣存儲格式在SW26010P處理器上的實現(xiàn)和優(yōu)化也是一個值得探究的問題。