123,123

內(nèi)容簡(jiǎn)介

　　本書(shū)詳細(xì)闡述了稀疏矩陣相關(guān)計(jì)算的應(yīng)用背景，并對(duì)目前已知的主要壓縮編碼格行了簡(jiǎn)要介紹。在此基礎(chǔ)上，分別對(duì)稀疏矩陣向量乘（SpMV）、稀疏矩陣、稀疏矩陣乘（SpGEMM）的算法設(shè)計(jì)和實(shí)現(xiàn)技行了詳細(xì)闡述。介紹了面向異構(gòu)計(jì)臺(tái)的稀疏矩陣劃分方法及SpMV負(fù)載均衡算法，能夠充分利用CPU GPU以及多GPU構(gòu)成的異構(gòu)計(jì)算系統(tǒng)的資源。介紹了一種基于數(shù)學(xué)形態(tài)學(xué)的稀疏矩陣劃分方法，該方法基于稀疏矩陣縮略圖和形態(tài)學(xué)方法，提取稀疏矩陣中稠密子矩陣?yán)ň匦螀^(qū)域、三角形區(qū)域，以及對(duì)角線，并根據(jù)非零元分布為不同的子矩陣選擇較優(yōu)的壓縮編碼格式。本書(shū)還介紹了基于機(jī)器學(xué)SpMV性能預(yù)測(cè)方法，以及多精度優(yōu)化相關(guān)內(nèi)容。后對(duì)常用的開(kāi)源庫(kù)程序以及相關(guān)的工行了簡(jiǎn)要介紹。本書(shū)建議的讀者為從事相關(guān)科學(xué)計(jì)算和工程計(jì)算的研究人員、工程師，以及從事大規(guī)模稀疏線性方程組求解和稀疏矩陣計(jì)算優(yōu)化的高校教師和研究生。

作者簡(jiǎn)介

　　計(jì)衛(wèi)星，北京理工大學(xué)計(jì)算學(xué)院副教授，計(jì)算機(jī)學(xué)會(huì)體系結(jié)構(gòu)專(zhuān)業(yè)委員會(huì)、科普工作委員會(huì)委員。2008年畢業(yè)于北京理工大學(xué)計(jì)算機(jī)學(xué)院獲工學(xué)博士學(xué)位，同年進(jìn)入北京理工大學(xué)計(jì)算學(xué)院工作。2012年至2013年赴美國(guó)羅切斯特大學(xué)計(jì)算機(jī)系訪問(wèn)1年。目前主要研究方向包括代碼分析與優(yōu)化、并行與高性能計(jì)算等，主持和參與國(guó)家自然科學(xué)基金項(xiàng)目多項(xiàng)，在國(guó)內(nèi)外著名期刊和國(guó)際會(huì)議（TACO、PLDI、RTSS和DATE等）上發(fā)表論文多篇，獲省部級(jí)教學(xué)成果獎(jiǎng)各1項(xiàng)，出版教材3部。

圖書(shū)目錄

第1章稀疏矩陣概述 1
1.1　矩陣與稀疏矩陣 1
1.2　應(yīng)用領(lǐng)域 1
1.2.1　線性系統(tǒng) 2
1.2.2　圖計(jì)算 7
1.2.3　線性規(guī)劃 8
1.2.4　PageRank算法 9
1.3　稀疏矩陣相關(guān)計(jì)算 12
1.3.1　BLAS 12
1.3.2　Sparse BLAS 14
1.3.3　SpMV 16
1.3.4　SpGEMM 16
1.3.5　SpMM 17
本章參考文獻(xiàn) 18
第2章稀疏矩陣壓縮編碼方法 23
2.1　常見(jiàn)壓縮編碼概述 23
2.2　常見(jiàn)基本壓縮格式 24
2.2.1　COO 24
2.2.2　CSR 24
2.2.3　ELL 25
2.2.4　DIA 26
2.3　切片和分塊壓縮格式 26
2.3.1　BCSR 26
2.3.2　BCCOO/BCCOO 27
2.3.3　CSR5 28
2.3.4　CSR2 30
2.3.5　SELL 30
2.3.6　CDS 31
2.4　混合格式 31
2.4.1　HYB 31
2.4.2　MMSparse 32
2.4.3　其他 33
本章參考文獻(xiàn) 33
第3章 SpMV研究現(xiàn)狀綜述 36
3.1　問(wèn)題定義 36
3.2　格式選擇 37
3.2.1　基于目標(biāo)平臺(tái)特性的格式選擇 37
3.2.2　基于強(qiáng)化學(xué)習(xí)的格式選擇 37
3.2.3　基于決策樹(shù)的格式選擇 38
3.2.4　基于SVM的格式選擇 38
3.2.5　基于深度學(xué)習(xí)的格式選擇 39
3.3　面向體系結(jié)構(gòu)的優(yōu)化 40
3.3.1　面向多核/眾核處理器的優(yōu)化 40
3.3.2　面向GPU的優(yōu)化 42
3.3.3　基于FPGA的優(yōu)化 42
3.3.4　面向異構(gòu)計(jì)算平臺(tái)的優(yōu)化 43
3.4　自動(dòng)調(diào)優(yōu)技術(shù) 43
3.5　矩陣劃分 44
3.5.1　一維劃分 44
3.5.2　二維劃分 45
本章參考文獻(xiàn) 45
第4章 SpGEMM研究現(xiàn)狀綜述 51
4.1　SpGEMM介紹 51
4.2　常見(jiàn)應(yīng)用 52
4.2.1　代數(shù)多網(wǎng)格求解器 52
4.2.2　三角形計(jì)數(shù) 53
4.2.3　多源寬度優(yōu)先搜索 55
4.3　主要研究方法 56
4.3.1　結(jié)果矩陣的大小預(yù)測(cè) 56
4.3.2　矩陣劃分和負(fù)載均衡 59
4.3.3　中間結(jié)果累加 62
4.4　面向體系結(jié)構(gòu)的優(yōu)化 64
4.4.1　多核平臺(tái) 64
4.4.2　現(xiàn)場(chǎng)可編程門(mén)陣列 67
4.4.3　異構(gòu)計(jì)算平臺(tái) 67
4.4.4　分布式平臺(tái) 67
4.5　實(shí)驗(yàn)評(píng)估 68
4.5.1　系統(tǒng)設(shè)置 69
4.5.2　測(cè)試基準(zhǔn) 70
4.5.3　評(píng)估結(jié)果 71
4.6　挑戰(zhàn)與未來(lái)工作 76
本章參考文獻(xiàn) 77
第5章面向異構(gòu)平臺(tái)的SpMV優(yōu)化算法 86
5.1　CPU-GPU異構(gòu)平臺(tái)編程 86
5.2　基于機(jī)器學(xué)習(xí)的SpMV性能預(yù)測(cè) 88
5.2.1　基于回歸分析的性能預(yù)測(cè) 89
5.2.2　模型訓(xùn)練與測(cè)試 89
5.2.3　性能分析 91
5.3　面向異構(gòu)平臺(tái)的劃分與協(xié)同優(yōu)化算法 91
5.3.1　稀疏矩陣數(shù)據(jù)布局分析 91
5.3.2　特定模式稀疏矩陣的SpMV劃分 92
5.3.3　SpMV計(jì)算協(xié)同任務(wù)優(yōu)化 93
5.3.4　實(shí)驗(yàn)評(píng)估 96
5.3.5　小結(jié) 99
5.4　多GPU異構(gòu)平臺(tái)的SpMV優(yōu)化 100
5.4.1　面向CPU - GPU異構(gòu)平臺(tái)的稀疏矩陣劃分 101
5.4.2　實(shí)驗(yàn)評(píng)估 106
5.4.3　小結(jié) 114
本章參考文獻(xiàn) 115
第6章基于數(shù)學(xué)形態(tài)學(xué)的SpMV劃分優(yōu)化方法 119
6.1　矩陣劃分 119
6.2　基本工作流程 121
6.3　形狀識(shí)別 123
6.4　矩陣二維劃分 132
6.5　算法實(shí)現(xiàn)與GPU優(yōu)化 135
6.5.1　形狀識(shí)別算法實(shí)現(xiàn) 135
6.5.2　GPU優(yōu)化 136
6.6　實(shí)驗(yàn)評(píng)估 138
6.6.1　SpMV性能分析 139
6.6.2　形態(tài)學(xué)參數(shù)選擇 142
6.6.3　數(shù)據(jù)失真 143
6.6.4　額外開(kāi)銷(xiāo)分析 144
本章參考文獻(xiàn) 145
第7章面向GPU的SpMV編碼選擇算法 146
7.1　引言 146
7.2　在GPU上進(jìn)行稀疏格式選擇的重要性 148
7.2.1　SpMV內(nèi)核在GPU上的性能 148
7.2.2　SpMV內(nèi)核在GPU上的能效 150
7.3　BestSF：一種稀疏元格式 151
7.3.1　離線訓(xùn)練 152
7.3.2　在線決策 153
7.4　稀疏特征選擇 153
7.5　Pairwise Model學(xué)習(xí) 155
7.5.1　學(xué)習(xí)算法 155
7.5.2　特征選擇 156
7.5.3　訓(xùn)練與測(cè)試 156
7.6　評(píng)估 157
7.7　總結(jié) 164
本章參考文獻(xiàn) 164
第8章 SpMV性能預(yù)測(cè)分析 168
8.1　引言 168
8.2　面向硬件體系結(jié)構(gòu)的性能預(yù)測(cè)方法 169
8.3　基于傳統(tǒng)機(jī)器學(xué)習(xí)的性能預(yù)測(cè)方法 170
8.4　基于深度學(xué)習(xí)的性能預(yù)測(cè)方法 180
8.5　多性能指標(biāo)下SpMV性能分析 182
本章參考文獻(xiàn) 183
第9章面向精度的稀疏矩陣計(jì)算優(yōu)化 186
9.1　數(shù)據(jù)表示與精度 186
9.1.1　常見(jiàn)浮點(diǎn)數(shù)據(jù)表示 186
9.1.2　處理器與精度 188
9.1.3　精度可調(diào)算法設(shè)計(jì)的主要挑戰(zhàn) 191
9.2　混合精度算法設(shè)計(jì) 192
9.2.1　數(shù)據(jù)驅(qū)動(dòng)的混合精度算法 192
9.2.2　混合精度的迭代算法 192
9.2.3　混合精度的預(yù)條件迭代算法 193
9.2.4　計(jì)算格式與存儲(chǔ)格式解耦 195
本章參考文獻(xiàn) 197
220章開(kāi)源庫(kù)和工具 199
10.1　測(cè)試集 199
10.1.1　SuiteSparse Matrix Collection 199
10.1.2　SparseBench 201
10.2　相關(guān)庫(kù) 201
10.2.1　cuSPARSE 201
10.2.2　CSPARSE 202
10.2.3　CUSP 202
10.2.4　bhSPARSE 203
10.2.5　KokkosKernels 203
10.2.6　SpBLAS 203
10.2.7　Scilab 204
10.2.8　各類(lèi)庫(kù)對(duì)比 204
本章參考文獻(xiàn) 204
彩插 206