基于MPI的大数据高性能计算导论

　　本书使用MPI标准介绍了数据科学中的高性能计算，帮助读者了解分布式存储模型中的并行编程的知识。全书分为两部分，*部分（第1~6章）基于消息传递接口介绍高性能计算，内容包括：阻塞与非阻塞的点对点通信、死锁、全局通信函数（广播、散播等）、协同计算（归约）的基本概念；互联网络的拓扑结构（环、环面和超立方体）以及相应的全局通信程序；基于分布式内存的并行排序及其实现，涵盖相关并行线性代数知识；MapReduce模型。第二部分（第7~11章）介绍计算机集群中的高性能数据分析，内容包括：数据聚类技术（平面划分聚类、层次聚类）；基于k-NN的有监督分类；核心集以及相关降维技术；图算法（稠密子图、图同构检测）。每章章末附有各种难度的练习和参考文献，可供读者进行自测和深入学习。本书适合作为“高性能计算”相关课程的本科生教材。

　　弗兰克•尼尔森（Frank Nielsen） 巴黎综合理工学院教授，负责教授研究生计算机视觉和图形学方面的课程以及本科生的算法和Java课程。他是Sony计算机科学实验室研究员。

目录
译者序
前言
致谢
部分基于消息传递接口的高性能计算
第1章走进高性能计算
1.1什么是高性能计算
1.2为什么我们需要HPC
1.3大数据：四个特性（数据量、多样性、生成速度、价值）
1.4并行编程范式：MPI和MapReduce
1.5粒度：细粒度并行与粗粒度并行
1.6超级计算架构：内存和网络
1.7加速比
1.7.1扩展性和等效率分析
1.7.2Amdahl定律：描述数据规模固定时渐近加速比的变化趋势
1.7.3Gustafson定律：可扩展的加速比，随着资源的增加不断扩大数据量
1.7.4在串行计算机上模拟并行机
1.7.5大数据和并行输入/输出
1.8关于分布式系统的八个常见误区
1.9注释和参考
1.10总结
1.11练习
参考文献
第2章MPI简介：消息传递接口
2.1基于MPI的并行程序设计：基于消息通信
2.2并行编程模型、线程和进程
2.3进程之间的全局通信
2.3.1四个基本的MPI原语：广播、收集、归约和全交换
2.3.2阻塞与非阻塞和同步与异步通信
2.3.3阻塞通信产生的死锁
2.3.4并发性：局部计算可以与通信重叠执行
2.3.5单向与双向通信
2.3.6MPI中的全局计算：归约和并行前缀（扫描）
2.3.7采用通信器定义通信组
2.4同步屏障：进程的交汇点
2.4.1MPI中的一个同步示例：测量运行时间
2.4.2整体同步并行计算模型
2.5开始使用MPI：使用OpenMPI
2.5.1用MPI C++编写“Hello World”程序
2.5.2用C绑定进行MPI编程
2.5.3通过C++ Boost使用MPI
2.6通过OpenMP使用MPI
2.7MPI中的主要原语
2.7.1广播、散播、收集、归约和全归约的MPI语法
2.7.2其余混杂的MPI原语
2.8环形拓扑上利用MPI进行的通信
2.9MPI程序示例及其加速比分析
2.9.1MPI中的矩阵向量积
2.9.2MPI归约操作示例：计算数组的阶乘和小值
2.9.3MonteCarlo随机积分算法估算π
2.9.4MonteCarlo随机积分算法估算分子体积
2.10注释和参考
2.11总结
2.12练习
参考文献
第3章互联网络的拓扑结构
3.1两个重要概念：静态与动态网络，以及逻辑与物理网络
3.2互联网络：图建模
3.3一些描述拓扑结构的属性
3.3.1度和直径
3.3.2连通性和对分
3.3.3一个好的网络拓扑结构的标准
3.4常见的拓扑结构：简单的静态网络
3.4.1完全图：团
3.4.2星形图
3.4.3环和带弦环
3.4.4网（网格）与环面簇（环面的集合）
3.4.5三维立方体与循环连接立方体
3.4.6树与胖树
3.5超立方体拓扑结构以及使用格雷码进行节点标识
3.5.1超立方体的递归构造
3.5.2使用格雷码对超立方体节点编号
3.5.3使用C++生成格雷码
3.5.4格雷码和二进制码的相互转换
3.5.5图的笛卡儿乘积
3.6一些拓扑结构上的通信算法
3.6.1有向环上的通信原语
3.6.2超立方体上的广播：树状通信
3.7将（逻辑）拓扑结构嵌入到其他（物理）拓扑结构中
3.8复杂规则拓扑结构
3.9芯片上的互联网络
3.10注释和参考
3.11总结
参考文献
第4章并行排序
4.1串行排序快速回顾
4.1.1主要的串行排序算法
4.1.2排序的复杂性：下界
4.2通过合并列表实现并行排序
4.3利用秩实现并行排序
4.4并行快速排序
4.5超快速排序
4.6正则采样并行排序
4.7基于网格的排序：ShearSort
4.8使用比较网络排序：奇偶排序
4.9使用比较网络合并有序列表
4.10双调归并排序
4.11注释和参考
4.12总结
4.13练习
参考文献
第5章并行线性代数
5.1分布式线性代数
5.1.1数据科学中的线性代数
5.1.2经典线性代数
5.1.3矩阵向量乘法：y=Ax
5.1.4并行数据模式
5.2有向环拓扑上的矩阵向量乘积
5.3网格上的矩阵乘法：外积算法
5.4二维环面拓扑上的矩阵乘积
5.4.1Cannon算法
5.4.2Fox算法：广播相乘循环移位矩阵乘积
5.4.3Snyder算法：在对角线上进行本地乘积累加
5.4.4Cannon、Fox和Snyder算法的比较
5.5注释和参考
5.6总结
5.7练习
参考文献
第6章MapReduce范式
6.1快速处理大数据的挑战
6.2MapReduce的基本原理
6.2.1map和reduce过程
6.2.2历史视角：函数式编程语言中的map和reduce
6.3数据类型和MapReduce机制
6.4MapReduce在C ++中的完整示例
6.5启动MapReduce作业和MapReduce架构概述
6.6基于MRMPI库在MPI中使用MapReduce
6.7注释和参考
6.8总结
参考文献
第二部分面向数据科学的高性能计算
第7章基于k均值的划分聚类
7.1探索性数据分析与聚类
7.1.1硬聚类：划分数据集
7.1.2成本函数和模型聚类
7.2k均值目标函数
7.2.1重写k均值成本函数以对聚类效果进行双重解释：聚类簇内数据或分离簇间数据
7.2.2k均值优化问题的复杂性和可计算性
7.3Lloyd批量k均值局部启发式方法
7.4基于全局启发式的k均值初始化方法
7.4.1基于随机种子的初始化方法
7.4.2全局k均值：贪心初始化
7.4.3kmeans ++：一种简单的概率保证的初始化方法
7.5k均值向量量化中的应用
7.5.1向量量化
7.5.2Lloyd的局部小值和稳定Voronoi划分
7.6k均值的物理解释：惯性分解
7.7k均值中k的选择：模型选择
7.7.1基于肘部法则的模型选择
7.7.2模型选择：用k解释方差减少
7.8集群上的并行k均值聚类
7.9评估聚类划分
7.9.1兰德指数
7.9.2归一化互信息
7.10注释和参考
7.11总结