發(fā)布時(shí)間：2019-07-29 10:13

【摘要】：稀疏矩陣向量乘法(sparse matrix vector multiplication,SpMV)是科學(xué)和工程領(lǐng)域中重要的核心子程序之一,也是稀疏基本線性代數(shù)子程序(basic linear algebra subprograms,BLAS)庫(kù)的重要函數(shù).目前很多SpMV的優(yōu)化工作在不同程度上獲得了性能提升,但大多數(shù)優(yōu)化工作針對(duì)特定存儲(chǔ)格式或一類具有特定特征的稀疏矩陣缺乏通用性.因此高性能的SpMV實(shí)現(xiàn)并沒(méi)有廣泛地應(yīng)用于實(shí)際應(yīng)用和數(shù)值解法器中.另外,稀疏矩陣具有眾多存儲(chǔ)格式,不同存儲(chǔ)格式的SpMV存在較大性能差異.根據(jù)以上現(xiàn)象,提出一個(gè)SpMV的自動(dòng)調(diào)優(yōu)器(SpMV auto-tuner,SMAT).對(duì)于一個(gè)給定的稀疏矩陣,SMAT結(jié)合矩陣特征選擇并返回其最優(yōu)的存儲(chǔ)格式.應(yīng)用程序通過(guò)調(diào)用SMAT來(lái)得到合適的存儲(chǔ)格式,從而獲得性能提升,同時(shí)隨著SMAT中存儲(chǔ)格式的擴(kuò)展,更多的SpMV優(yōu)化工作可以將性能優(yōu)勢(shì)在實(shí)際應(yīng)用中發(fā)揮作用.使用佛羅里達(dá)大學(xué)的2 366個(gè)稀疏矩陣作為測(cè)試集,在Intel上SMAT分別獲得9.11GFLOPS(單精度)和2.44GFLOPS(雙精度)的最高浮點(diǎn)性能,在AMD平臺(tái)上獲得了3.36GFLOPS(單精度)和1.52GFLOPS(雙精度)的最高浮點(diǎn)性能.相比Intel的核心數(shù)學(xué)函數(shù)庫(kù)(math kernel library,MKL)數(shù)學(xué)庫(kù),SMAT平均獲得1.4~1.5倍的性能提升.
【圖文】：

模桑粒劍危危?（Ｎｄｉａｇｓ×Ｍ）．（１）我們對(duì)這２個(gè)參數(shù)在子矩陣集ＤＩＡ＿ｍａｔｓ上測(cè)試其ＳｐＭＶ性能（如圖３、圖４所示）．１）對(duì)角線條數(shù)（Ｎｄｉａｇｓ）：ＤＩＡ－ＳｐＭＶ中寫(xiě)Ｙ的次數(shù)為Ｎｄｉａｇｓ，隨著對(duì)角線條數(shù)增多，對(duì)向量Ｙ的重復(fù)讀寫(xiě)次數(shù)增加，對(duì)ＳｐＭＶ性能造成影響．圖３給出了Ｎｄｉａｇｓ與ＤＩＡ－ＳｐＭＶ性能的關(guān)系．圖３中Ｆｉｇ．３ＴｈｅｉｎｆｌｕｅｎｃｅｏｆＮｄｉａｇｓｏｎＤＩＡ－ＳｐＭＶ．圖３Ｎｄｉａｇｓ對(duì)ＤＩＡ－ＳｐＭＶ性能的影響Ｆｉｇ．４ＴｈｅｉｎｆｌｕｅｎｃｅｏｆＥＲ＿ＤＩＡｏｎＤＩＡ－ＳｐＭＶ．圖４ＥＲ＿ＤＩＡ對(duì)ＤＩＡ格式ＳｐＭＶ性能的影響橫坐標(biāo)為Ｎｄｉａｇｓ的數(shù)目，分為９個(gè)取值區(qū)間；縱坐標(biāo)為矩陣所占比例．其中“ＧＯＯＤ”指ＤＩＡ為最優(yōu)格式的矩陣所占比例，可知所有的ＧＯＯＤ矩陣集合即表３中的“ｇｏｏｄ＿ＤＩＡ＿ｍａｔｓ”；而“ＢＡＤ”指ＤＩＡ未能獲得最好性能的矩陣比例．從圖３看出，當(dāng)對(duì)角線條數(shù)大于３００時(shí)，ＤＩＡ格式基本在絕大多數(shù)矩陣上不再獲得最高性能．結(jié)論１．當(dāng)稀疏矩陣的對(duì)角線條數(shù)較少時(shí)，ＳｐＭＶ使用ＤＩＡ格式具有性能優(yōu)勢(shì)．２）ＤＩＡ格式中非零元所占比例（ＥＲ＿ＤＩＡ）：即使一條對(duì)角線上只有一個(gè)非零元，ＤＩＡ格式也需要存儲(chǔ)整條對(duì)角線，，包含存儲(chǔ)額外的零元素．大量的補(bǔ)零操作降低了非零元所占比例，增加了ＳｐＭＶ的額外計(jì)算，從而影響其性能．ＥＲ＿ＤＩＡ與ＤＩＡ－ＳｐＭＶ的性能如

能（如圖３、圖４所示）．１）對(duì)角線條數(shù)（Ｎｄｉａｇｓ）：ＤＩＡ－ＳｐＭＶ中寫(xiě)Ｙ的次數(shù)為Ｎｄｉａｇｓ，隨著對(duì)角線條數(shù)增多，對(duì)向量Ｙ的重復(fù)讀寫(xiě)次數(shù)增加，對(duì)ＳｐＭＶ性能造成影響．圖３給出了Ｎｄｉａｇｓ與ＤＩＡ－ＳｐＭＶ性能的關(guān)系．圖３中Ｆｉｇ．３ＴｈｅｉｎｆｌｕｅｎｃｅｏｆＮｄｉａｇｓｏｎＤＩＡ－ＳｐＭＶ．圖３Ｎｄｉａｇｓ對(duì)ＤＩＡ－ＳｐＭＶ性能的影響Ｆｉｇ．４ＴｈｅｉｎｆｌｕｅｎｃｅｏｆＥＲ＿ＤＩＡｏｎＤＩＡ－ＳｐＭＶ．圖４ＥＲ＿ＤＩＡ對(duì)ＤＩＡ格式ＳｐＭＶ性能的影響橫坐標(biāo)為Ｎｄｉａｇｓ的數(shù)目，分為９個(gè)取值區(qū)間；縱坐標(biāo)為矩陣所占比例．其中“ＧＯＯＤ”指ＤＩＡ為最優(yōu)格式的矩陣所占比例，可知所有的ＧＯＯＤ矩陣集合即表３中的“ｇｏｏｄ＿ＤＩＡ＿ｍａｔｓ”；而“ＢＡＤ”指ＤＩＡ未能獲得最好性能的矩陣比例．從圖３看出，當(dāng)對(duì)角線條數(shù)大于３００時(shí)，ＤＩＡ格式基本在絕大多數(shù)矩陣上不再獲得最高性能．結(jié)論１．當(dāng)稀疏矩陣的對(duì)角線條數(shù)較少時(shí)，ＳｐＭＶ使用ＤＩＡ格式具有性能優(yōu)勢(shì)．２）ＤＩＡ格式中非零元所占比例（ＥＲ＿ＤＩＡ）：即使一條對(duì)角線上只有一個(gè)非零元，ＤＩＡ格式也需要存儲(chǔ)整條對(duì)角線，包含存儲(chǔ)額外的零元素．大量的補(bǔ)零操作降低了非零元所占比例，增加了ＳｐＭＶ的額外計(jì)算，從而影響其性能．ＥＲ＿ＤＩＡ與ＤＩＡ－ＳｐＭＶ的性能如圖４所示．可知，當(dāng)矩陣中非零元所占比例過(guò)�。ǎ迹玻埃ィ⿻r(shí)，ＤＩＡ格式的ＳｐＭＶ不會(huì)取得較好的性能．結(jié)論
【作者單位】： 計(jì)算機(jī)體系結(jié)構(gòu)國(guó)家重點(diǎn)實(shí)驗(yàn)室(中國(guó)科學(xué)院計(jì)算技術(shù)研究所);中國(guó)科學(xué)院大學(xué);
【基金】：國(guó)家自然科學(xué)基金項(xiàng)目(61272134,61033009,61003062,60925009) 國(guó)家“九七三”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃基金項(xiàng)目(2011CB302502,2012CB316502)
【分類號(hào)】：TP333;TP311.1

【參考文獻(xiàn)】

相關(guān)期刊論文 前1條

1 宋慶增;顧軍華;;稀疏矩陣向量乘的FPGA設(shè)計(jì)與實(shí)現(xiàn)[J];計(jì)算機(jī)工程;2011年23期

【共引文獻(xiàn)】

相關(guān)期刊論文 前1條

1 彭宇;仲雪潔;王少軍;;基于FPGA線性方程組的存儲(chǔ)優(yōu)化設(shè)計(jì)[J];計(jì)算機(jī)工程;2013年04期

相關(guān)博士學(xué)位論文 前2條

1 陳銳;CSAMT三維交錯(cuò)采樣有限差分?jǐn)?shù)值模擬并行算法研究[D];中國(guó)地質(zhì)大學(xué)(北京);2012年

2 張芡;大規(guī)模稀疏線性系統(tǒng)的稀疏近似逆預(yù)處理技術(shù)[D];清華大學(xué);2013年

【二級(jí)參考文獻(xiàn)】

相關(guān)期刊論文 前1條

1 張承暢;嚴(yán)單貴;楊力生;齊懷龍;楊宏;;基于XCF32P的多FPGA配置方案[J];計(jì)算機(jī)工程;2010年15期

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 王敏;;稀疏矩陣快速轉(zhuǎn)置算法的分析與優(yōu)化[J];計(jì)算機(jī)應(yīng)用與軟件;2010年08期

2 田翔;周凡;陳耀武;劉莉;陳耀;;基于FPGA的實(shí)時(shí)雙精度浮點(diǎn)矩陣乘法器設(shè)計(jì)[J];浙江大學(xué)學(xué)報(bào)(工學(xué)版);2008年09期

3 袁娥;張?jiān)迫?孫相征;;RAM(h)模型下SpMV存儲(chǔ)訪問(wèn)復(fù)雜度的分析[J];計(jì)算機(jī)工程與設(shè)計(jì);2009年03期

4 盧s

本文編號(hào)：2520436