稀疏矩陣向量乘及自動(dòng)調(diào)優(yōu).pdf

1、在數(shù)值分析領(lǐng)域中，稀疏矩陣是陣內(nèi)元素大部分為零的矩陣。大規(guī)模稀疏矩陣廣泛出現(xiàn)在科學(xué)計(jì)算以及工程領(lǐng)域中，用于大規(guī)模線性求解系統(tǒng)和求解矩陣特征值等問題。稀疏矩陣在很多科學(xué)問題的物理過程離散求解中都有著重要的作用，如在有限元分析中利用稀疏矩陣來表示元素之間的相互作用，在圖論中利用稀疏矩陣來描述圖并通過稀疏矩陣的運(yùn)算來實(shí)現(xiàn)圖的變換，流體力學(xué)偏微分方程的求解等等。目前，針對(duì)稀疏矩陣的研究已經(jīng)滲入到很多領(lǐng)域，在結(jié)構(gòu)分析、網(wǎng)絡(luò)理論、電力分配系統(tǒng)、化學(xué)

2、工程、攝影測(cè)繪學(xué)以及管理科學(xué)等方面研究中，都出現(xiàn)了上千階直至幾百萬階的稀疏矩陣。因此對(duì)于稀疏矩陣向量乘(SpMV)及其調(diào)優(yōu)技術(shù)的研究有助于提升解決相關(guān)領(lǐng)域問題的運(yùn)算效率，有著巨大的研究?jī)r(jià)值與意義。
　　本文在大量閱讀國(guó)內(nèi)外相關(guān)研究文獻(xiàn)的基礎(chǔ)上，研究并實(shí)現(xiàn)了稀疏矩陣向量乘運(yùn)算的相關(guān)優(yōu)化技術(shù)與方法，給出了一種基于主成分分析法的優(yōu)化技術(shù)自動(dòng)調(diào)優(yōu)算法，進(jìn)而提出并開發(fā)了一種整合現(xiàn)有優(yōu)化技術(shù)的數(shù)學(xué)庫(kù)COSC。在以上工作的基礎(chǔ)上，本文創(chuàng)新性地提

3、出一種基于四叉樹的稀疏矩陣存儲(chǔ)方式，利用遞歸進(jìn)行分解重排，保證在該存儲(chǔ)格式下的稀疏矩陣向量乘運(yùn)算擁有較高的Cache命中率，從而提升運(yùn)算的整體性能。進(jìn)一步的，本文給出了基于四叉樹的稀疏矩陣向量乘優(yōu)化技術(shù)的性能分析與優(yōu)化原則。本文的主要工作總結(jié)如下：
　　(1)查閱并研究國(guó)內(nèi)外現(xiàn)有優(yōu)化技術(shù)，從面向計(jì)算體系結(jié)構(gòu)的優(yōu)化方面入手，論述、總結(jié)并歸納了在該方向上的四類基本策略及現(xiàn)有優(yōu)化技術(shù)的優(yōu)勢(shì)與不足，從而為本文的研究提供了基本的研究方向。<

4、br>　　(2)闡述和介紹了基于CSR格式的稀疏矩陣向量乘優(yōu)化與自動(dòng)調(diào)優(yōu)。該部分通過編碼實(shí)現(xiàn)與優(yōu)化，給出了一種基于訓(xùn)練集與主成分分析法的自動(dòng)調(diào)優(yōu)策略SCS，并基于此提出一種可整合優(yōu)化策略的數(shù)學(xué)庫(kù)COSC。實(shí)驗(yàn)表明SCS的有效性，結(jié)合COSC，可以為以稀疏矩陣向量乘運(yùn)算為計(jì)算熱點(diǎn)的相關(guān)問題在解決效率上帶來顯著的改進(jìn)。
　　(3)提出一種基于四叉樹的稀疏矩陣存儲(chǔ)方式。該存儲(chǔ)方式通過遞歸進(jìn)行分解重排，保證了進(jìn)行稀疏矩陣向量乘運(yùn)算時(shí)的高C

5、ache命中率，從而帶來性能上的提升?；谠摯鎯?chǔ)方式，本文亦提出了其上相關(guān)的優(yōu)化技術(shù)，進(jìn)而分析了各優(yōu)化技術(shù)的性能影響。實(shí)驗(yàn)證明基于四叉樹存儲(chǔ)結(jié)構(gòu)的稀疏矩陣在矩陣乘法中具有較高的性能，其結(jié)構(gòu)利于計(jì)算并行化并具較高的數(shù)據(jù)局部性。在深騰7000高性能計(jì)算集群上的實(shí)驗(yàn)表明基于四叉樹存儲(chǔ)結(jié)構(gòu)的矩陣向量乘較MKL的實(shí)現(xiàn)能獲得平均63%的性能提升。
　　(4)對(duì)本文的上述方面研究作了總結(jié)性的概括，給出了本課題今后的研究方向，展望并提出下一步工作