稀疏矩阵计算优化

图书标准信息

• 作者 计卫星 著
• 出版社 北京理工大学出版社
• 出版时间 2022-04
• 版次 1
• ISBN 9787568298049
• 定价 79.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 220页

【内容简介】

本书详细阐述了稀疏矩阵相关计算的应用背景，并对目前已知的主要压缩编码格式进行了详细介绍。在此基础上，分别对稀疏矩阵向量乘（SpMV）、稀疏矩阵稀疏矩阵乘（SpGEMM）的算法设计和实现技术进行了详细阐述；给出了面向异构计算平台的稀疏矩阵划分方法及SpMV负载均衡算法，能够适用于CPU+GPU以及多GPU构成的异构计算系统；介绍了一种基于数学形态学的稀疏矩阵划分方法，该方法基于稀疏矩阵缩略图和形态学方法，提取稀疏矩阵中稠密子矩阵，包括矩形稠密区域，三角形稠密区域，以及稠密对角线，并根据非零元分布为不同的子矩阵选择较优的压缩编码格式；本书还介绍了基于机器学习的SpMV性能预测方法，以及多精度优化相关内容。最后对常用的开源库程序以及相关的工具包进行了简要介绍。

 

本书可供从事相关科学计算和工程计算的研究人员、工程师，以及从事大规模稀疏线性方程组求解和稀疏矩阵计算优化的高校教师和研究生阅读。

 

【作者简介】

计卫星，北京理工大学计算学院副教授，计算机学会体系结构专业委员会、科普工作委员会委员。2008年毕业于北京理工大学计算机学院获工学博士学位，同年进入北京理工大学计算学院工作。2012年至2013年赴美国罗切斯特大学计算机系访问1年。目前主要研究方向包括代码分析与优化、并行与高性能计算等，主持和参与国家自然科学基金项目多项，在国内外著名期刊和国际会议（TACO、PLDI、RTSS和DATE等）上发表论文多篇，获省部级教学成果奖各1项，出版教材3部。

【目录】

第1章   稀疏矩阵概述 1

 

1.1 矩阵与稀疏矩阵 1

 

1.2 应用领域 1

 

1.2.1 线性系统 2

 

1.2.2 图计算 7

 

1.2.3 线性规划 8

 

1.2.4 PageRank算法 9

 

1.3 稀疏矩阵相关计算 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

 

本章参考文献 18

 

第2章  稀疏矩阵压缩编码方法 23

 

2.1 常见压缩编码概述 23

 

2.2 常见基本压缩格式 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

 

本章参考文献 33

 

第3章  SpMV研究现状综述 36

 

3.1 问题定义 36

 

3.2 最佳格式选择 37

 

3.2.1 基于目标平台特性的格式选择 37

 

3.2.2 基于强化学习的格式选择 37

 

3.2.3 基于决策树的格式选择 38

 

3.2.4 基于SVM的格式选择 38

 

3.2.5 基于深度学习的格式选择 39

 

3.3 面向体系结构的优化 40

 

3.3.1 面向多核/众核处理器的优化 40

 

3.3.2 面向GPU的优化 42

 

3.3.3 基于FPGA的优化 42

 

3.3.4 面向异构计算平台的优化 43

 

3.4 自动调优技术 43

 

3.5 矩阵划分 44

 

3.5.1 一维划分 44

 

3.5.2 二维划分 45

 

本章参考文献 45

 

第4章  SpGEMM研究现状综述 51

 

4.1 SpGEMM介绍 51

 

4.2 常见应用 52

 

4.2.1 代数多网格求解器 52

 

4.2.2 三角形计数 53

 

4.2.3 多源宽度优先搜索 55

 

4.3 主要研究方法 56

 

4.3.1 结果矩阵的大小预测 56

 

4.3.2 矩阵划分和负载均衡 59

 

4.3.3 中间结果累加 62

 

4.4 面向体系结构的优化 64

 

4.4.1 多核平台 64

 

4.4.2 现场可编程门阵列 67

 

4.4.3 异构计算平台 67

 

4.4.4 分布式平台 67

 

4.5 实验评估 68

 

4.5.1 系统设置 69

 

4.5.2 测试基准 70

 

4.5.3 评估结果 71

 

4.6 挑战与未来工作 76

 

本章参考文献 77

 

第5章  面向异构平台的SpMV优化算法 86

 

5.1 CPU-GPU异构平台编程 86

 

5.2 基于机器学习的SpMV性能预测 88

 

5.2.1 基于回归分析的性能预测 89

 

5.2.2 模型训练与测试 89

 

5.2.3 性能分析 91

 

5.3 面向异构平台的划分与协同优化算法 91

 

5.3.1 稀疏矩阵数据布局分析 91

 

5.3.2 特定模式稀疏矩阵的SpMV划分 92

 

5.3.3 SpMV计算协同任务优化 93

 

5.3.4 实验评估 96

 

5.3.5 小结 99

 

5.4 多GPU异构平台的SpMV优化 100

 

5.4.1 面向CPU ? GPU异构平台的稀疏矩阵划分 101

 

5.4.2 实验评估 106

 

5.4.3 小结 114

 

本章参考文献 115

 

第6章  基于数学形态学的SpMV划分优化方法 119

 

6.1 矩阵划分 119

 

6.2 基本工作流程 121

 

6.3 形状识别 123

 

6.4 矩阵二维划分 132

 

6.5 算法实现与GPU优化 135

 

6.5.1 形状识别算法实现 135

 

6.5.2 GPU优化 136

 

6.6 实验评估 138

 

6.6.1 SpMV性能分析 139

 

6.6.2 形态学参数选择 142

 

6.6.3 数据失真 143

 

6.6.4 额外开销分析 144

 

本章参考文献 145

 

第7章  面向GPU的SpMV编码选择算法 146

 

7.1 引言 146

 

7.2 在GPU上进行稀疏格式选择的重要性 148

 

7.2.1 SpMV内核在GPU上的性能 148

 

7.2.2 SpMV内核在GPU上的能效 150

 

7.3 BestSF：一种稀疏元格式 151

 

7.3.1 离线训练 152

 

7.3.2 在线决策 153

 

7.4 稀疏特征选择 153

 

7.5 Pairwise Model学习 155

 

7.5.1 学习算法 155

 

7.5.2 特征选择 156

 

7.5.3 训练与测试 156

 

7.6 评估 157

 

7.7 总结 164

 

本章参考文献 164

 

第8章  SpMV性能预测分析 168

 

8.1 引言 168

 

8.2 面向硬件体系结构的性能预测方法 169

 

8.3 基于传统机器学习的性能预测方法 170

 

8.4 基于深度学习的性能预测方法 180

 

8.5 多性能指标下SpMV性能分析 182

 

本章参考文献 183

 

第9章  面向精度的稀疏矩阵计算优化 186

 

9.1 数据表示与精度 186

 

9.1.1 常见浮点数据表示 186

 

9.1.2 处理器与精度 188

 

9.1.3 精度可调算法设计的主要挑战 191

 

9.2 混合精度算法设计 192

 

9.2.1 数据驱动的混合精度算法 192

 

9.2.2 混合精度的迭代算法 192

 

9.2.3 混合精度的预条件迭代算法 193

 

9.2.4 计算格式与存储格式解耦 195

 

本章参考文献 197

 

第10章  开源库和工具 199

 

10.1 测试集 199

 

10.1.1 SuiteSparse Matrix Collection 199

 

10.1.2 SparseBench 201

 

10.2 相关库 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 各类库对比 204

 

本章参考文献 204

 

彩插 206