求解大型（稀疏）線性代數(shù)方程組（Ax=b）是科學(xué)計(jì)算的基礎(chǔ)共性問題,其主要計(jì)算量是（稀疏）矩陣向量乘積（SpMV）,因此,高效計(jì)算矩陣向量乘積是提升科學(xué)計(jì)算的核心重要環(huán)節(jié)。近年來隨著圖形處理器（GPU）的快速發(fā)展,其多處理器和獨(dú)特的物理架構(gòu)適合計(jì)算密集型和高度并行的計(jì)算。GPU上SpMV的性能主要受稀疏矩陣存儲格式的影響。本文利用GPU對稀疏矩陣向量乘積進(jìn)行加速,并研究最優(yōu)存儲格式的預(yù)測。首先,基于JAD格式的排序思想,我們對ELLR格式進(jìn)行了優(yōu)化和改進(jìn),提出了PELLR格式。通過排序減少了SpMV的迭代次數(shù)和冗余計(jì)算,且與ELLR格式相比,PELLR格式的性能提升了 1.5倍。與其它格式對比,如CSR、BiELL等,70%測試矩陣中PELLR格式是性能占優(yōu)的。此外,我們推導(dǎo)了公式用于計(jì)算迭代次數(shù)和矩陣行非零元素個數(shù)的擾亂程度。其次,我們提出了一種方法來預(yù)估GPU上SpMV的計(jì)算時間,通過預(yù)測的時間來判斷哪種存儲格式對SpMV在計(jì)算上是最優(yōu)的。該方法采取了分而治之的思想,把總時間分為三部分:數(shù)據(jù)傳輸Tc、SpMV計(jì)算Ts和結(jié)果重排Tp,每個部分的估計(jì)分別使用了GPU的構(gòu)架參數(shù)和稀疏矩陣... 

【文章來源】：東北師范大學(xué)吉林省 211工程院校 教育部直屬院校

【文章頁數(shù)】：65 頁

【學(xué)位級別】：碩士

【文章目錄】：
中文摘要
英文摘要
第一章 緒論
    1.1 研究背景
    1.2 相關(guān)研究工作
    1.3 論文安排
第二章 預(yù)備知識
    2.1 GPU硬件架構(gòu)
    2.2 CUDA編程模型
第三章 GPU上稀疏矩陣向量乘積及其優(yōu)化
    3.1 一般稀疏矩陣存儲格式
        3.1.1 坐標(biāo)格式（Coordinate,COO）
        3.1.2 壓縮稀疏行格式（Compressed Sparse Row,CSR）
        3.1.3 對角線格式（Diagonal,DIA）
        3.1.4 ELL格式（Ellpack,ELL）
    3.2 優(yōu)化的稀疏矩陣存儲格式
        3.2.1 ELLR和ELLR-T格式
        3.2.2 齒對角線格式（Jagged Diagonals,JAD）
        3.2.3 SELL-C-σ格式
        3.2.4 BiELL和BiJAD格式（Bisection ELL/JAD, BiELL/BiJAD）
        3.2.5 混合存儲格式（Hybrid Format,HYB）
    3.3 新的PELLR格式:基于行置換的ELLR格式
    3.4 數(shù)值實(shí)驗(yàn)
    3.5 本章小節(jié)
第四章 最優(yōu)存儲格式的預(yù)測方法
    4.1 測試矩陣
    4.2 稀疏矩陣向量乘的次數(shù)比較
    4.3 SpMV運(yùn)算時間的預(yù)測
        4.3.1 Tc的預(yù)測
        4.3.2 Tp的預(yù)測
        4.3.3 ELL格式Ts的預(yù)測
    4.4 本章小節(jié)
參考文獻(xiàn)
在學(xué)期間公開發(fā)表論文及著作情況
展望
致謝


【參考文獻(xiàn)】：
期刊論文
[1]基于HYB格式稀疏矩陣與向量乘在CPU+GPU異構(gòu)系統(tǒng)中的實(shí)現(xiàn)與優(yōu)化[J]. 陽王東,李肯立.  計(jì)算機(jī)工程與科學(xué). 2016(02)

博士論文
[1]基于GPU的矩陣乘法優(yōu)化研究[D]. 殷建.山東大學(xué) 2015

碩士論文
[1]異構(gòu)并行機(jī)上快速求解線性方程組[D]. 鄭驄.中國工程物理研究院 2014
[2]基于CUDA的大規(guī)模線性稀疏方程組求解器的設(shè)計(jì)[D]. 吳長江.電子科技大學(xué) 2013



本文編號：2997501