基于MPI的大数据高性能计算导论2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载

基于MPI的大数据高性能计算导论PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第一部分 基于消息传递接口的高性能计算2

第1章 走进高性能计算2

1.1 什么是高性能计算2

1.2 为什么我们需要HPC3

1.3 大数据：四个特性（数据量、多样性、生成速度、价值）4

1.4 并行编程范式：MPI和MapReduce4

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：使用OpenMPI31

2.5.1 用MPI C＋＋编写“Hello World”程序32

2.5.2 用C绑定进行MPI编程33

2.5.3 通过C＋＋Boost使用MPI34

2.6 通过OpenMP使用MPI34

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 基于网格的排序：ShearSort89

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=Ax101

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和reduce120

6.3 数据类型和MapReduce机制121

6.4 MapReduce在C＋＋中的完整示例122

6.5 启动MapReduce作业和MapReduce架构概述123

6.6 基于MR-MPI库在MPI中使用MapReduce125

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