顧 越,趙銀亮
(西安交通大學(xué)計(jì)算機(jī)學(xué)院,陜西 西安 710049)
隨著云計(jì)算與物聯(lián)網(wǎng)浪潮的興起,人們對(duì)可定制、低功耗和高性價(jià)比CPU的需求日漸增加。最初由加州大學(xué)伯克利分校研究人員開發(fā)的開源指令集架構(gòu)RISC-V,憑借其可伸縮、可擴(kuò)展和模塊化的特性[1 - 3],在相關(guān)領(lǐng)域的影響力逐漸擴(kuò)大。該指令集由整數(shù)基本指令和多個(gè)拓展指令集組成[4],拓展指令集中包括了用于向量處理的V指令集——RV32V。RV32V目前仍在GitHub上開發(fā)[5],最新穩(wěn)定版本為v0.9。與傳統(tǒng)SIMD向量架構(gòu)不同的地方在于,RISC-V向量指令集具有向量寄存器可配置的特性,解決了向量計(jì)算中向量長(zhǎng)度不可知的問題[6,7]。
向量計(jì)算中的稀疏矩陣與向量乘法SpMV(Sparse Matrix-Vector multiplication),常用于科學(xué)計(jì)算和工程應(yīng)用問題中的大規(guī)模稀疏線性系統(tǒng)求解[8],其實(shí)現(xiàn)與優(yōu)化一直是高性能計(jì)算領(lǐng)域的研究重點(diǎn)。因稀疏矩陣具有非零元素占比少的特性,研究人員常采用壓縮存儲(chǔ)格式來(lái)提高存儲(chǔ)效率,又因非零元素分布和硬件設(shè)備的多樣性,其存儲(chǔ)格式也具有多樣性[9]。如COO(COOrdinate list format)[10]格式以行坐標(biāo)、列坐標(biāo)和值組成的三元組對(duì)稀疏矩陣中非零元素進(jìn)行存儲(chǔ),簡(jiǎn)單直觀靈活,但不利于計(jì)算和向量化。另一種常用的存儲(chǔ)格式CSR(Compress Sparse Row format)格式,將所有非零元素的值和列索引按行順序存儲(chǔ)在2個(gè)單獨(dú)的數(shù)組中,第3個(gè)數(shù)組保留指向這些數(shù)組中每一行的起始位置的指針。它的主要優(yōu)點(diǎn)是對(duì)任何類型的矩陣元素分布都有很好的壓縮比,其主要缺點(diǎn)為數(shù)據(jù)局部性差,存在寫沖突、負(fù)載不均衡等問題[11]。ELLPACK(format used by ELLPACK system)格式可在GPU和矢量體系結(jié)構(gòu)中高效運(yùn)算,但需要付出額外的存儲(chǔ)代價(jià)[12]。它以m*k的矩陣存儲(chǔ)數(shù)據(jù),其中k的大小取決于每行非零元素個(gè)數(shù)中的最大值。面對(duì)不規(guī)則矩陣時(shí),其存儲(chǔ)和計(jì)算效率都會(huì)退化。HYB(HYBrid format)格式[13]結(jié)合了ELLPACK格式和COO格式,對(duì)每行中超過(guò)閾值的非零元素使用COO格式存儲(chǔ),以減少ELLPACK格式中零元素的填充,兼顧計(jì)算效率的同時(shí)節(jié)約了存儲(chǔ)空間。
SELLPACK(Sliced ELLPACK format)[14]格式是基于ELLPACK格式的改進(jìn)。通過(guò)將矩陣行向量按照其非零元素?cái)?shù)量排序,以固定行數(shù)對(duì)矩陣分片,對(duì)得到的矩陣塊分別使用ELLPACK格式存儲(chǔ),提高了存儲(chǔ)不規(guī)則矩陣的效率和吞吐量。更進(jìn)一步地,SELL-C-σ(Sliced ELLPACK format with parameterC,σ)格式[15]通過(guò)限制排序窗口避免了重新排列整個(gè)矩陣的高昂代價(jià),同時(shí)充分利用了矩陣相鄰行與被乘向量x相乘時(shí),對(duì)向量x訪問的局部性。針對(duì)Intel 公司設(shè)計(jì)的異構(gòu)眾核處理器Xeon Phi,Liu等人[16]提出了ESB(ELLPACK Sparse Block)格式,該格式引入了位數(shù)組編碼和列分塊技術(shù),以降低帶寬需求,進(jìn)一步提高了向量訪問的局部性。而Liu 等人[17]提出的CSR5存儲(chǔ)格式,易于從傳統(tǒng)的CSR格式轉(zhuǎn)換得到,對(duì)輸入稀疏矩陣的非零元素分布不敏感。通過(guò)采用一種改進(jìn)的分段求和算法實(shí)現(xiàn)了基于CSR5的SpMV算法,在跨平臺(tái)測(cè)試中得到了較高的吞吐量。
RISC-V向量指令集作為向量指令家族中的新晉成員,方興未艾。相關(guān)研究尚處于起步階段,基于RISC-V向量指令實(shí)現(xiàn)和優(yōu)化SpMV算法的工作還未有報(bào)道,開展此項(xiàng)工作具有重要意義。
本文基于RISC-V向量指令集RV32V,利用其向量寄存器可配置及尋址特性,實(shí)現(xiàn)了基于CSR、ELLPACK和HYB壓縮格式的SpMV算法,比較了在稀疏矩陣非零元素不同分布情況下各個(gè)算法的計(jì)算與存儲(chǔ)效率的變化。同時(shí),針對(duì)極度稀疏矩陣每行非零元素?cái)?shù)量波動(dòng)較大的情況,通過(guò)壓縮非零元素密度低的行向量的存儲(chǔ)、調(diào)整HYB分割閾值等手段,改進(jìn)了HYB存儲(chǔ)格式并實(shí)現(xiàn)了對(duì)應(yīng)的SpMV算法,顯著改善了計(jì)算效率和存儲(chǔ)效率。
CSR格式是一種比較標(biāo)準(zhǔn)的稀疏矩陣存儲(chǔ)格式,使用3類數(shù)據(jù)來(lái)表示:數(shù)值val、列號(hào)col和行偏移row。其中,數(shù)值val為非零元素的值,列號(hào)col為非零元素的列號(hào),行偏移row表示某行的第1個(gè)非零元素在數(shù)值val中的起始偏移位置。對(duì)于如式(1)所示的矩陣A,采用CSR格式存儲(chǔ)的結(jié)果如式(2)所示:
(1)
(2)
CSR格式的主要優(yōu)點(diǎn)是對(duì)規(guī)則與不規(guī)則稀疏矩陣的存儲(chǔ)都具有穩(wěn)定良好的壓縮比,主要缺點(diǎn)是基于此實(shí)現(xiàn)的SpMV算法存在數(shù)據(jù)訪問局部性差、寫沖突和負(fù)載不均衡等問題。
ELLPACK格式是一種易于向量化的稀疏矩陣存儲(chǔ)格式,使用2個(gè)和原始矩陣行數(shù)相同的矩陣來(lái)表示:第1個(gè)矩陣val存的是數(shù)值,第2個(gè)矩陣col存的是列號(hào),行號(hào)用自身所在的行來(lái)表示。對(duì)于行中存在的零元素,可以在val矩陣中填充零元素、在col矩陣中填充11來(lái)表示。對(duì)于如式(1)所示的矩陣A,采用ELLPACK格式存儲(chǔ)的結(jié)果如式(3)所示:
(3)
當(dāng)矩陣中某行的非零元素個(gè)數(shù)很多時(shí),ELLPACK格式的存儲(chǔ)效率將急劇下降。
HYB格式對(duì)ELLPACK格式的缺點(diǎn)進(jìn)行改進(jìn),采用COO格式與ELLPACK格式混合的方式對(duì)稀疏矩陣壓縮存儲(chǔ)。對(duì)每行元素個(gè)數(shù)小于閾值的部分采用ELLPACK格式,超過(guò)閾值的部分采用COO格式。其中,ELLPACK格式如上所述,需要數(shù)值矩陣val和列號(hào)矩陣col存儲(chǔ),而COO格式使用coo_r、coo_c和coo_v分別存儲(chǔ)元素的行號(hào)、列號(hào)和值。對(duì)于如式(4)所示的矩陣B,采用HYB格式存儲(chǔ)的結(jié)果如式(5)所示:
(4)
coo_r=(0),
coo_c=(2),
coo_v=(9)
(5)
矩陣B中第1行第3列的元素值為9,行號(hào)為0,列號(hào)為2,分別存儲(chǔ)于coo_v、coo_r和coo_c中。因此,當(dāng)每行非零元素?cái)?shù)量相差較大時(shí),采用HYB格式可節(jié)約存儲(chǔ)空間,提高存儲(chǔ)效率。
SpMV可用式(6)描述:
y=A*x
(6)
其中,A為m*n維的稀疏矩陣,x為n* 1維的乘數(shù)向量,y為m* 1維的結(jié)果向量。
為了更好地描述稀疏矩陣,假設(shè)矩陣中每行元素?cái)?shù)量呈正態(tài)分布,正態(tài)分布標(biāo)準(zhǔn)差為σ,均值為μ。
為了表征稀疏矩陣中非零元素的分布特征,使用空行率、稠密度和波動(dòng)度3個(gè)指標(biāo),其定義如式(7)~式(9)所示:
空行率=矩陣全零行數(shù)/矩陣總行數(shù)
(7)
稠密度=非零元素?cái)?shù)/矩陣元素總數(shù)
(8)
波動(dòng)度=標(biāo)準(zhǔn)差σ/均值μ
(9)
為了表征基于某特定壓縮存儲(chǔ)格式的SpMV算法性能,使用壓縮率和加速比2個(gè)指標(biāo),其定義如式(10)和式(11)所示:
壓縮率=壓縮后數(shù)據(jù)大小/原始矩陣大小
(10)
加速比=基于該壓縮格式的SpMV執(zhí)行時(shí)間/非壓縮的SpMV執(zhí)行時(shí)間
(11)
壓縮率與壓縮效率成反比,壓縮率越小,說(shuō)明該壓縮存儲(chǔ)格式的壓縮效率越高。
其中,非壓縮的SpMV偽代碼如下所示:
for(inti= 0;i for(intj=0;j y[i]+=A[i*m+j] *x[j]; } } 加速比與計(jì)算效率成正比,加速比越大,說(shuō)明所執(zhí)行的算法計(jì)算效率越高。 RISC-V指令集采用模塊化的方式組織,使用一個(gè)英文字母表示一個(gè)模塊。其中向量指令部分使用“V”表示,32位的RISC-V向量模塊簡(jiǎn)記為RV32V。對(duì)于32位的RISC-V向量架構(gòu),在執(zhí)行向量乘操作的for循環(huán)時(shí),可以用設(shè)置向量寄存器組的操作作為循環(huán)判斷條件,每次循環(huán)后將當(dāng)前剩余向量長(zhǎng)度減去設(shè)置結(jié)果,發(fā)揮向量寄存器可配置的特性,避免了傳統(tǒng)SIMD指令面對(duì)計(jì)算向量長(zhǎng)度非架構(gòu)所支持的向量數(shù)的整數(shù)倍時(shí),需要對(duì)剩余尾向量進(jìn)行額外的循環(huán)操作的缺點(diǎn)。例如,對(duì)于傳統(tǒng)的擁有固定128位向量寄存器的處理器而言,在處理包含41個(gè)32位整型元素的向量時(shí),每次循環(huán)能夠處理的元素個(gè)數(shù)為4。10次循環(huán)之后,需要額外循環(huán)處理剩余的1個(gè)元素。而在RV32V體系結(jié)構(gòu)中,向量寄存器長(zhǎng)度可通過(guò)類似vsetvl_e32m8的接口靈活配置,開始待處理向量較長(zhǎng)時(shí),使用大的向量寄存器位數(shù),最后向量長(zhǎng)度不足時(shí),將向量寄存器長(zhǎng)度設(shè)置為合適值,充分簡(jiǎn)化了代碼編寫,提高了程序效率。 在實(shí)現(xiàn)矩陣運(yùn)算時(shí),常用的向量操作包括間隔向量尋址、索引向量尋址、向量乘加和向量標(biāo)量乘等,如圖1所示。 Figure 1 Vector operations of RV32V圖1 RV32V向量操作示意圖 基于RV32V,充分利用RISC-V向量寄存器可配置和尋址的特點(diǎn),本文分別實(shí)現(xiàn)CSR、ELLPACK和HYB存儲(chǔ)格式的SpMV算法。向量化SpMV算法實(shí)現(xiàn)總體可分為索引計(jì)算、乘數(shù)加載、向量相乘、結(jié)果回寫和指針偏移這幾個(gè)步驟,下面結(jié)合偽代碼分別描述各壓縮格式的RISC-V向量化SpMV實(shí)現(xiàn)。 基于CSR格式的RISC-V向量化SpMV偽代碼如下所示: 輸入行偏移指針row_p;row_p數(shù)組長(zhǎng)度m;坐標(biāo)指針col_idx;值指針val;向量指針x。 輸出結(jié)果向量指針y。 1:vfloat32m8_tvec_a,vec_b,vec_c; 2:vuint32m8_tindex; 3:float *a=val,*b=x,*c=y; 4:whilevl=vsetvl_e32m8(col)do 5:vec_a=*(vfloat32m8_t *)a; 6:index=*(vuint32m8_t *)col_idx; 7:index=vfmul_vf_f32m8(index,4); 8:vec_b=vlxe_v_f32m8(b,index); 9:vec_c=*(vfloat32m8_t *)c; 10:vec_c=vfmadd_vv_f32m8(vec_a,vec_b,vec_c) 11: *(vfloat32m8_t *) c=vec_c; 12:c+=vl;a+=vl;b+=vl; 13:col_idx+=vl;col-=vl; 14:endwhile 15:returny. 首先對(duì)列號(hào)col_idx數(shù)組進(jìn)行順序?qū)ぶ罚?jì)算出索引,如第6、7行所示;然后根據(jù)計(jì)算出的索引,在乘數(shù)向量x中進(jìn)行索引尋址,加載第1個(gè)向量乘數(shù),并對(duì)數(shù)值val數(shù)組順序?qū)ぶ?,加載第2個(gè)向量乘數(shù),如第8、9行所示;最后2個(gè)向量乘數(shù)中各元素依次相乘,結(jié)果回寫暫存,如第10、11行所示。進(jìn)行指針偏移準(zhǔn)備下一輪計(jì)算,如第12、13行所示。依次循環(huán)往復(fù)直到計(jì)算完成。 基于ELLPACK格式的RISC-V向量化SpMV偽代碼如下所示: 輸入坐標(biāo)指針col_idx;值指針val;值矩陣長(zhǎng)度m;值矩陣寬度col;向量指針x。 輸出結(jié)果向量指針y。 1:vfloat32m8_tvec_a,vec_b,vec_c; 2:vuint32m8_tindex; 3:float *a=val,*b=x,*c=y; 4:fori=0 tocoldo 5:num=m;a=val+i*col; 6:b=x;c=y+i*col; 7:col_idx=col_idx+i*col; 8:whilevl=vsetvl_e32m8(num)do 9:vec_a=*(vfloat32m8_t *)a; 10:index=vlse_v_f32m8(col_idx,col*4); 11:index=vfmul_vf_f32m8(index,4); 12:vec_b=vlxe_v_f32m8(b,index); 13:vec_c=*(vfloat32m8_t *)c; 14:vec_c=vfmadd_vv_f32m8(vec_a,vec_b,vec_c); 15: *(vfloat32m8_t *)c=vec_c; 16:c+=vl;a+=vl;b+=vl; 17:col_idx+=vl;num-=vl; 18:endwhile 19:endfor 20:returny. 向量化計(jì)算過(guò)程中,首先對(duì)列號(hào)col數(shù)組間隔尋址,間隔為每行字節(jié)數(shù),按列順序獲取向量,如第10行。對(duì)得到的向量值做向量標(biāo)量乘法,轉(zhuǎn)化為字節(jié)數(shù),計(jì)算出索引,如第11行;然后根據(jù)計(jì)算出的索引,在乘數(shù)向量x中進(jìn)行索引尋址,加載第1個(gè)向量乘數(shù),如第12行;接著對(duì)數(shù)值val數(shù)組順序?qū)ぶ?,加載第2個(gè)向量乘數(shù),如第13行;最后向量元素依次相乘,如第14行,結(jié)果回寫暫存,如第15行。指針偏移準(zhǔn)備下一輪計(jì)算,如第16、17行,依次循環(huán)往復(fù)直到計(jì)算完成。 對(duì)基于HYB格式的向量化SpMV可以分為ELLPACK和COO 2部分,其中ELLPACK部分與上述基于ELLPACK格式的RISC-V向量化過(guò)程相同,COO部分的向量化過(guò)程與CSR格式的類似。 基于HYB格式的RISC-V向量化SpMV偽代碼(COO部分)如下所示: 輸入行坐標(biāo)指針col_r;列坐標(biāo)指針coo_c;值指針val;長(zhǎng)度num;向量指針x。 輸出結(jié)果向量指針y。 1:whilevl=vsetvl_e32m8(num)do 2:vec_a=*(vfloat32m8_t *)a; 3:index=*(vuint32m8_t *)coo_c; 4:index=vfmul_vf_f32m8(index,4); 5:vec_b=vlxe_v_f32m8(b,index); 6:vec_c=*(vfloat32m8_t *)c; 7:vec_c=vfmadd_vv_f32m8(vec_a,vec_b,vec_c); 8: *(vfloat32m8_t *) c=vec_c; 9:c+=vl;a+=vl;b+=vl; 10:col_index+=vl;num-=vl; 11:endwhile 12:returny. 首先對(duì)列號(hào)col數(shù)組順序?qū)ぶ罚绲?行,得到的向量值做向量標(biāo)量乘法,如第4行,計(jì)算出索引;然后在乘數(shù)向量x中進(jìn)行索引尋址,加載第1個(gè)向量乘數(shù),如第5行;接著對(duì)數(shù)值val數(shù)組順序?qū)ぶ?,加載第2個(gè)向量乘數(shù),如第6行;最后向量元素依次相乘,如第7行,結(jié)果回寫暫存,如第8行。指針偏移準(zhǔn)備下一輪計(jì)算,如第9、10行。依次循環(huán)往復(fù)直到計(jì)算完成。 HYB格式使用ELLPACK格式和COO格式混合的方式,以更緊湊的方式存儲(chǔ)擁有非零元素密度大的行的稀疏矩陣,提升了存儲(chǔ)效率。圖2給出了矩陣C的HYB格式存儲(chǔ)結(jié)果。將第1行和第2行的元素5存儲(chǔ)為COO格式,使所需的存儲(chǔ)空間從60(6*5*2)個(gè)整型大小降低到54(6*4*2+6)個(gè)整型大小。 Figure 2 Storage diagram based on HYB format圖2 基于HYB格式的存儲(chǔ)示意圖 但是,行之間非零元素相差很大的情況不僅表現(xiàn)在擁有非零元素密度大的行,同時(shí)也體現(xiàn)在擁有非零元素密度小的行?;谶@一點(diǎn),本文提出改進(jìn)的HYB格式IHYB(Improved HYB format)。IHYB格式對(duì)非零元素密度低于IHYB分割閾值的行也使用COO格式存儲(chǔ)。此時(shí)ELLPACK格式所存儲(chǔ)元素的行號(hào)不能用自身所在的行來(lái)表示,于是引入bitarray數(shù)組記錄ELLPACK格式中每行元素在原始矩陣中的行號(hào)。對(duì)于HYB格式,在假設(shè)完全填充的ELLPACK格式計(jì)算速度比COO格式快3倍的情況下,通過(guò)經(jīng)驗(yàn)法則選擇數(shù)值K作為ELLPACK和COO之間的分割值,使得矩陣中具有K個(gè)以上非零元素?cái)?shù)的行數(shù)不少于M/3,其中M是矩陣總行數(shù)[13]。而對(duì)于IHYB格式,參照類似規(guī)則,閾值的確定使用迭代算法1。 算法1確定IHYB分割閾值的算法 輸入:稀疏矩陣每行非零元素?cái)?shù)。 輸出:IHYB分割閾值。 Step1對(duì)稀疏矩陣每行元素?cái)?shù)中的非零值從小到大排序,找到2/3分位點(diǎn)作為HYB閾值。 Step2將HYB閾值/4作為IHYB分割閾值。 Step3去除非零元素?cái)?shù)低于IHYB分割閾值的行,按照Step 1更新HYB閾值。 Step4將更新后的HYB閾值/4作為最終的IHYB分割閾值。 如HYB使用的經(jīng)驗(yàn)參數(shù),IHYB閾值中使用的參數(shù)2/3,1/4等,也是通過(guò)經(jīng)驗(yàn)法則確定。閾值的兩步迭代求解操作開銷包括對(duì)稀疏矩陣的2次遍歷(統(tǒng)計(jì)每行非零元素?cái)?shù)時(shí))和每行非零元素?cái)?shù)大小的排序。矩陣遍歷可以在壓縮存儲(chǔ)格式的轉(zhuǎn)換過(guò)程中完成,并不增加額外開銷。假設(shè)稀疏矩陣有m行k列,排序的復(fù)雜度為m*logm,一般而言不會(huì)超過(guò)矩陣元素?cái)?shù)m*k,可以忽略。因此,通常來(lái)說(shuō),閾值求解過(guò)程的開銷并不會(huì)影響算法性能。 圖3給出了圖2中矩陣C的IHYB格式存儲(chǔ)結(jié)果。第6行的元素1也存儲(chǔ)為COO格式,同時(shí)bitarray數(shù)組指示了矩陣value中每行元素的行號(hào),使所需的存儲(chǔ)空間從HYB的54(6*4*2+6)個(gè)整型大小進(jìn)一步降低到45(4*4*2+4+9)個(gè)整型大小。 Figure 3 Storage diagram based on IHYB format圖3 基于IHYB格式的存儲(chǔ)示意圖 本文實(shí)驗(yàn)使用Spike模擬器[18]環(huán)境,其中DCache設(shè)置大小為32 KB,ICache大小為32 KB,L2 Cache大小為128 KB,CPU主頻1 GHz,內(nèi)存使用4 GB。限定矩陣規(guī)模為4 KB,矩陣每行非零元素個(gè)數(shù)滿足正態(tài)分布,以空行率、稠密度和波動(dòng)度控制稀疏矩陣非零元素分布特性,以壓縮率和加速比衡量算法的空間效率和時(shí)間效率。 固定空行率為0.3,波動(dòng)度為0,改變稠密度觀察稀疏矩陣稠密度對(duì)SpMV算法性能的影響。隨著稠密度增加,非零元素?cái)?shù)量也增加,各算法所需存儲(chǔ)空間增加,計(jì)算時(shí)間增多,因此,加速比減小,壓縮率升高。整體上由加速比衡量的計(jì)算效率由高到低為CSR、IHYB、HYB和ELLPACK,如圖4所示。由壓縮率衡量的存儲(chǔ)效率由高到低為IHYB、CSR、HYB和ELLPACK,如圖5所示。由圖4可知,當(dāng)稠密度超過(guò)0.08時(shí),CSR的計(jì)算效率降低,IHYB的加速比反超CSR。原因在于CSR的段累加求和部分難以被向量化,當(dāng)非零元素?cái)?shù)量較多時(shí),計(jì)算效率受到影響開始下降。得益于較高的壓縮效率和較好的向量化程度,IHYB的加速比表現(xiàn)優(yōu)異。而ELLPACK中存儲(chǔ)了大量零元素,導(dǎo)致整體計(jì)算效率較低。 Figure 4 Effect of density on speedup圖4 稠密度對(duì)加速比的影響 Figure 5 Effect of density on compressibility圖5 稠密度對(duì)壓縮率的影響 固定空行率為0.3,稠密度為0.08,改變波動(dòng)度觀察稀疏矩陣波動(dòng)度對(duì)SpMV算法性能的影響。圖6和圖7別顯示了波動(dòng)度對(duì)加速比和壓縮率的影響。隨著波動(dòng)度增大,IHYB、HYB和ELLPACK的壓縮率不同程度增大,加速比不同程度減小,而CSR的壓縮率和加速比基本保持穩(wěn)定。由圖6可知,隨著波動(dòng)度增大,ELLPACK的加速比迅速降低。原因在于波動(dòng)度的增大導(dǎo)致ELLPACK格式壓縮率迅速升高,存儲(chǔ)效率降低,這點(diǎn)由圖7也可以看出。存儲(chǔ)的無(wú)效零元素大量增加,進(jìn)一步導(dǎo)致ELLPACK格式的計(jì)算效率下降,加速比走低。與ELLPACK格式不同的是,其他3種格式壓縮率較為穩(wěn)定。由圖7可知,CSR的壓縮率最為穩(wěn)定,基本不受波動(dòng)度影響,HYB和IHYB的壓縮率隨著波動(dòng)度增大緩慢增加,并且IHYB在壓縮效果上好于HYB格式。波動(dòng)度低于0.2時(shí),IHYB的存儲(chǔ)效率表現(xiàn)甚至好于CSR。由圖6可知,很大程度得益于此,在波動(dòng)度低于0.2時(shí),IHYB的計(jì)算效率也高于CSR。 Figure 6 Effect of volatility on speedup圖6 波動(dòng)度對(duì)加速比的影響 Figure 7 Effect of volatility on compressibility圖7 波動(dòng)度對(duì)壓縮率的影響 圖8和圖9分別進(jìn)行了HYB格式和基于HYB格式改進(jìn)的IHYB在不同波動(dòng)度下,加速比和壓縮率的對(duì)比。平均而言,相比HYB格式,IHYB格式在加速比上提升了13%,壓縮率上降低了6%。壓縮率的降低趨勢(shì)和加速比的提升趨勢(shì)一致,從而體現(xiàn)了壓縮效率的提高導(dǎo)致計(jì)算效率隨之提高的規(guī)律。 Figure 8 Comparison of speedup between HYB and IHYB圖8 HYB和IHYB的加速比對(duì)比 Figure 9 Comparison of compressibility between HYB and IHYB圖9 HYB和IHYB的壓縮率對(duì)比 SpMV算法在科學(xué)計(jì)算中占有重要地位,實(shí)現(xiàn)并優(yōu)化基于RISC-V向量指令的SpMV算法也具有重要價(jià)值。本文首次利用RISC-V向量寄存器可配置性和向量尋址模式,結(jié)合CSR、ELLPACK和HYB存儲(chǔ)格式的特點(diǎn),實(shí)現(xiàn)了對(duì)應(yīng)的SpMV算法。在仿真環(huán)境下比較了各SpMV算法面對(duì)不同非零元素分布的稀疏矩陣,表現(xiàn)出的計(jì)算效率和存儲(chǔ)效率差異。同時(shí),針對(duì)HYB格式,提出了更為緊湊、穩(wěn)定的改進(jìn)格式IHYB。實(shí)驗(yàn)顯示,在非零元素分布變化時(shí),基于IHYB格式實(shí)現(xiàn)的SpMV表現(xiàn)出更為優(yōu)異的存儲(chǔ)效率和計(jì)算效率。但是,目前實(shí)現(xiàn)的算法都是基于單個(gè)RISC-V核心的。面對(duì)更為復(fù)雜的RISC-V多核處理器或異構(gòu)計(jì)算環(huán)境,如何充分發(fā)掘算法中的并行性,提高并行度,將是一個(gè)更為復(fù)雜深刻的挑戰(zhàn)和命題。3.2 RISC-V向量指令集RV32V
3.3 基于RV32V與傳統(tǒng)壓縮格式的SpMV實(shí)現(xiàn)
3.4 基于 HYB格式的改進(jìn)
4 算法測(cè)試與分析
4.1 稠密度的影響
4.2 波動(dòng)度的影響
5 結(jié)束語(yǔ)