第一部分 基于消息传递接口的高性能计算 2
第1章 走进高性能计算 2
1.1 什么是高性能计算 2
1.2 为什么我们需要HPC 3
1.3 大数据：四个特性（数据量、多样性、生成速度、价值） 4
1.4 并行编程范式：MPI和MapReduce 4
1.5 粒度：细粒度并行与粗粒度并行 5
1.6 超级计算架构：内存和网络 5
1.7 加速比 8
1.7.1 扩展性和等效率分析 9
1.7.2 Amdahl定律：描述数据规模固定时渐近加速比的变化趋势 9
1.7.3 Gustafson定律：可扩展的加速比，随着资源的增加不断扩大数据量 11
1.7.4 在串行计算机上模拟并行机 12
1.7.5 大数据和并行输入/输出 13
1.8 关于分布式系统的八个常见误区 13
1.9 注释和参考 15
1.10 总结 15
1.11 练习 16
参考文献 17
第2章 MPI简介：消息传递接口 18
2.1 基于MPI的并行程序设计：基于消息通信 18
2.2 并行编程模型、线程和进程 19
2.3 进程之间的全局通信 20
2.3.1 四个基本的MPI原语：广播、收集、归约和全交换 20
2.3.2 阻塞与非阻塞和同步与异步通信 22
2.3.3 阻塞通信产生的死锁 24
2.3.4 并发性：局部计算可以与通信重叠执行 27
2.3.5 单向与双向通信 27
2.3.6 MPI中的全局计算：归约和并行前缀（扫描） 27
2.3.7 采用通信器定义通信组 29
2.4 同步屏障：进程的交汇点 30
2.4.1 MPI中的一个同步示例：测量运行时间 30
2.4.2 整体同步并行计算模型 31
2.5 开始使用MPI：使用OpenMPI 31
2.5.1 用MPI C＋＋编写“Hello World”程序 32
2.5.2 用C绑定进行MPI编程 33
2.5.3 通过C＋＋Boost使用MPI 34
2.6 通过OpenMP使用MPI 34
2.7 MPI中的主要原语 36
2.7.1 广播、散播、收集、归约和全归约的MPI语法 36
2.7.2 其余混杂的MPI原语 38
2.8 环形拓扑上利用MPI进行的通信 38
2.9 MPI程序示例及其加速比分析 39
2.9.1 MPI中的矩阵向量积 40
2.9.2 MPI归约操作示例：计算数组的阶乘和最小值 41
2.9.3 Monte-Carlo随机积分算法估算π 42
2.9.4 Monte-Carlo随机积分算法估算分子体积 44
2.10 注释和参考 48
2.11 总结 49
2.12 练习 49
参考文献 50
第3章 互联网络的拓扑结构 51
3.1 两个重要概念：静态与动态网络，以及逻辑与物理网络 51
3.2 互联网络：图建模 51
3.3 一些描述拓扑结构的属性 52
3.3.1 度和直径 53
3.3.2 连通性和对分 53
3.3.3 一个好的网络拓扑结构的标准 53
3.4 常见的拓扑结构：简单的静态网络 54
3.4.1 完全图：团 54
3.4.2 星形图 55
3.4.3 环和带弦环 55
3.4.4 网（网格）与环面簇（环面的集合） 55
3.4.5 三维立方体与循环连接立方体 56
3.4.6 树与胖树 57
3.5 超立方体拓扑结构以及使用格雷码进行节点标识 57
3.5.1 超立方体的递归构造 57
3.5.2 使用格雷码对超立方体节点编号 58
3.5.3 使用C＋十生成格雷码 59
3.5.4 格雷码和二进制码的相互转换 61
3.5.5 图的笛卡儿乘积 61
3.6 一些拓扑结构上的通信算法 63
3.6.1 有向环上的通信原语 64
3.6.2 超立方体上的广播：树状通信 68
3.7 将（逻辑）拓扑结构嵌入到其他（物理）拓扑结构中 72
3.8 复杂规则拓扑结构 73
3.9 芯片上的互联网络 74
3.10 注释和参考 76
3.11 总结 77
参考文献 77
第4章 并行排序 78
4.1 串行排序快速回顾 78
4.1.1 主要的串行排序算法 78
4.1.2 排序的复杂性：下界 80
4.2 通过合并列表实现并行排序 80
4.3 利用秩实现并行排序 81
4.4 并行快速排序 82
4.5 超快速排序 86
4.6 正则采样并行排序 87
4.7 基于网格的排序：ShearSort 89
4.8 使用比较网络排序：奇偶排序 89
4.9 使用比较网络合并有序列表 92
4.10 双调归并排序 93
4.11 注释和参考 95
4.12 总结 95
4.13 练习 95
参考文献 96
第5章 并行线性代数 97
5.1 分布式线性代数 97
5.1.1 数据科学中的线性代数 97
5.1.2 经典线性代数 99
5.1.3 矩阵-向量乘法：y=Ax 101
5.1.4 并行数据模式 101
5.2 有向环拓扑上的矩阵-向量乘积 102
5.3 网格上的矩阵乘法：外积算法 108
5.4 二维环面拓扑上的矩阵乘积 108
5.4.1 Cannon算法 110
5.4.2 Fox算法：广播-相乘-循环移位矩阵乘积 111
5.4.3 Snyder算法：在对角线上进行本地乘积累加 115
5.4.4 Cannon、Fox和Snyder算法的比较 116
5.5 注释和参考 116
5.6 总结 116
5.7 练习 117
参考文献 117
第6章 MapReduce范式 118
6.1 快速处理大数据的挑战 118
6.2 MapReduce的基本原理 119
6.2.1 map和reduce过程 119
6.2.2 历史视角：函数式编程语言中的map和reduce 120
6.3 数据类型和MapReduce机制 121
6.4 MapReduce在C＋＋中的完整示例 122
6.5 启动MapReduce作业和MapReduce架构概述 123
6.6 基于MR-MPI库在MPI中使用MapReduce 125
6.7 注释和参考 127
6.8 总结 127
参考文献 128
第二部分 面向数据科学的高性能计算 130
第7章 基于k均值的划分聚类 130
7.1 探索性数据分析与聚类 130
7.1.1 硬聚类：划分数据集 131
7.1.2 成本函数和模型聚类 131
7.2 k均值目标函数 132
7.2.1 重写k均值成本函数以对聚类效果进行双重解释：聚类簇内数据或分离簇间数据 136
7.2.2 k均值优化问题的复杂性和可计算性 137
7.3 Lloyd批量k均值局部启发式方法 138
7.4 基于全局启发式的k均值初始化方法 140
7.4.1 基于随机种子的初始化方法 140
7.4.2 全局k均值：最佳贪心初始化 141
7.4.3 k-means＋十：一种简单的概率保证的初始化方法 141
7.5 k均值向量量化中的应用 142
7.5.1 向量量化 142
7.5.2 Lloyd的局部最小值和稳定Voronoi划分 143
7.6 k均值的物理解释：惯性分解 143
7.7 k均值中k的选择：模型选择 144
7.7.1 基于肘部法则的模型选择 144
7.7.2 模型选择：用k解释方差减少 145
7.8 集群上的并行k均值聚类 145
7.9 评估聚类划分 147
7.9.1 兰德指数 148
7.9.2 归一化互信息 148
7.10 注释和参考 148
7.11 总结 150
7.12 练习 151
参考文献 153
第8章 层次聚类 155
8.1 凝聚式与分裂式层次聚类及其树状图表示 155
8.2 定义一个好的连接距离的几种策略 158
8.2.1 一个用于凝聚式层次聚类的通用算法 158
8.2.2 为元素选择合适的基本距离函数 159
8.3 Ward合并准则和质心 161
8.4 从树状图中获取平面划分 162
8.5 超度量距离和进化树 163
8.6 注释和参考 164
8.7 总结 165
8.8 练习 166
参考文献 167
第9章 有监督学习：k-NN规则分类的理论和实践 169
9.1 有监督学习 169
9.2 最近邻分类：NN规则 169
9.2.1 最近邻查询中欧几里得距离计算的优化方法 170
9.2.2 最近邻（NN）规则和Voronoi图 171
9.2.3 利用k-NN规则通过表决来增强NN规则 172
9.3 分类器性能评估 173
9.3.1 误判错误率 173
9.3.2 混淆矩阵与真/假及阳性/阴性 173
9.4 准确率、召回率和F值 174
9.5 统计机器学习和贝叶斯最小误差界 174
9.5.1 非参数概率密度估计 175
9.5.2 误差概率和贝叶斯误差 176
9.5.3 k-NN规则的误差概率 178
9.6 在计算机集群上实现最近邻查询 178
9.7 注释和参考 178
9.8 总结 180
9.9 练习 181
参考文献 182
第10章 基于核心集的高维快速近似优化和快速降维 183
10.1 大规模数据集的近似优化 183
10.1.1 高维度的必要性示例 183
10.1.2 高维度上的一些距离现象 184
10.1.3 核心集：从大数据集到小数据集 184
10.2 核心集的定义 184
10.3 最小闭包球的核心集 185
10.4 一个用来近似最小闭包球的简单迭代启发式方法 186
10.4.1 收敛性证明 187
10.4.2 小闭包球和用于SVM的边缘线性分离器 189
10.5 k均值的核心集 189
10.6 基于随机投影矩阵的快速降维 189
10.6.1 维数灾难 189
10.6.2 高维度任务的两个示例 190
10.6.3 线性降维 191
10.6.4 Johnson-Lindenstrauss定理 191
10.6.5 随机投影矩阵 191
10.7 注释和参考 192
10.8 总结 193
10.9 练习 193
参考文献 193
第11章 图并行算法 194
11.1 在大图中寻找（最）稠密子图 194
11.1.1 问题描述 194
11.1.2 最稠密子图的复杂度和一个简单的贪心启发式算法 195
11.1.3 最稠密子图的并行启发式算法 198
11.2 判断（子）图同构 200
11.2.1 枚举算法的一般原则 201
11.2.2 Ullman算法：检测子图同构性 202
11.2.3 枚举算法并行化 203
11.3 注释和参考 204
11.4 总结 204
11.5 练习 205
参考文献 205
附录A 笔试 206
附录B SLURM：集群上的资源管理器和任务调度器 216