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

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

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

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

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

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

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

【二級參考文獻(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í)時雙精度浮點(diǎn)矩陣乘法器設(shè)計(jì)[J];浙江大學(xué)學(xué)報(bào)(工學(xué)版);2008年09期

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

4 盧s

本文編號：2520436