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

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

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

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

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

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