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

本书使用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总结

前言欢迎来到高性能计算的世界！欢迎来到高性能数据科学的世界！
在本书中，我们将介绍面向数据科学（Data Science，DS）的高性能计算（High Performance Computing，HPC）。因此，本书主要分为两个部分：第一部分（前6章）涵盖HPC的基本原理；第二部分（后5章）介绍了数据科学的基本知识，并展示了如何编写面向基本串行算法的分布式程序，以应对大规模数据集。当前，许多大规模数据集都是公开的，这些数据集中蕴含了丰富的信息，但是这些信息需要通过精心设计才能被提取出来。
我们主要区分两种并行算法的设计方法：在单个共享内存多核机器上使用多线程并行化算法；在分布式内存集群系统上并行化算法。
一方面，当在共享内存架构（如智能手机、平板电脑，以及智能手表和其他物联网设备）上设计并行化算法时，所有的硬件计算单元（核）位于同一芯片上，我们可以使用多线程来轻松地对视频解码、渲染等任务进行并行化。这种并行是细粒度的（finegrained），但它受到芯片上物理核数的限制（2015年高端智能手机通常只有8个核）。另一方面，集群系统（即分布式内存架构）可以根据待处理的数据集规模来实时扩展资源。集群的构建具有很大的灵活性，例如可以选择异构的计算机节点，然后确定最适合这些节点的互连拓扑结构。这种并行是粗粒度的（coarsegrained），因为在集群中发生节点间通信之前，每个节点可以独立地进行大量的本地计算。
本书侧重于在分布式内存系统上利用标准消息传递接口（Message Passing Interface，MPI）来设计并行算法。MPI是管理集群节点之间通信和全局协同计算的实际标准。目前存在多种MPI标准的供应商实现，它们可以与C、C++、Fortran、Python等多种编程语言绑定。我们选择面向对象的语言C++来实现数据科学中的算法，并使用和C语言绑定的OpenMPI应用程序编程接口（Application Programming Interface，API）来编写并行程序。
本书中两部分内容的简要介绍如下。
第一部分：基于消息传递接口的高性能计算第1章首先简单介绍了HPC世界，然后讲解了Amdahl定律和Gustafson定律，这两个定律刻画了并行程序的理论最优加速比和扩展加速比。
第2章讲解了MPI的主要概念和编程接口：阻塞/非阻塞通信的概念、死锁和多种全局通信函数（例如broadcast、scatter、gather、alltoall、reduce、parallel prefix等）。
第3章着重介绍了互联网络拓扑的作用。我们首先区分物理拓扑和虚拟拓扑（或称为逻辑拓扑），并在设计并行算法的时候考虑不同网络拓扑对性能的影响。特别讲解了环形（包括优化的流水线广播）和超立方体形网络拓扑上的通信过程，后者依赖于节点的特定编号，称为格雷码。
第4章讲解了基于分布式内存的主要的并行排序算法。首先对著名的快速排序算法（Quicksort）进行了简单的并行化，然后介绍实际中广泛使用的HyperQuicksort和PSRS（Parallel Sorting by Regular Sampling）算法。
第5章研究了一些矩阵相乘和向量相乘的算法，并简要介绍了在环和环面（torus）的拓扑结构中计算矩阵乘积的各种技术。
第6章介绍了一个比较热门的并行编程范式，称为MapReduce（通常与开源系统Hadoop一起使用）。 MapReduce可以通过两个主要的用户定义的函数（map和reduce）来构建程序，然后部署到大量的网络互连的计算机上来完成计算任务。 然而，MapReduce也是一个完整的框架，包括一个主从架构。该主从架构能够处理各种硬件故障，或者当一些机器执行得太慢时，将这些机器上的并行计算任务（作业）重新发送到其他的机器上执行。该章还讲解了如何利用专门的名为MRMPI的软件库在MPI（MPI没有容错能力）中实现这些类型的MapReduce算法。
第二部分：面向数据科学的高性能计算这部分简要介绍了数据科学，并进一步讲解了如何使用MPI并行化数据科学中的算法。
首先介绍了两个最基本的数据聚类技术，分别是平面划分聚类（第7章）和层次树聚类（第8章）。聚类是探索性数据科学中一个非常重要的概念，用于发现数据集中的分类、同质数据中的分组。
第9章介绍了基于k最近邻规则（knearest neighbor）的有监督分类，并和k均值（kmeans）聚类算法进行关联。
第10章介绍了另一个计算科学中的新范式，允许人们在大型数据集（潜在的高维度）上解决优化问题。这种新范式就是寻找核心集（coreset），这些核心集就是原数据集的子集，而且和原数据集相比具有良好的近似性。这种技术最近变得非常流行，能够将大数据（big data）缩小到小数据（tiny data）！由于数据通常具有高维度特征，所以还简要介绍了一种有效的线性降维技术，其中讲解了JohnsonLindenstrauss定理，并给出一个简单的方法计算低失真嵌入，从而将数据从高维转化为低维，并确保在规定的近似因子内数据点之间的距离保持不变。有趣的是，嵌入的维度与原始外在维度无关，而是依赖于数据集大小的对数和近似因子。
第11章涵盖了一些图（graph）算法。图在社交网络分析和其他应用领域中是比较常见的。因此首先介绍一个顺序启发式方法和一个并行启发式方法来查找图的稠密子图，该子图近似于“最稠密”子图。 然后介绍了在计算机集群上利用分支限界法来进行图同构检测。图同构检测是一个备受关注的问题，因为它的理论复杂度还没有得到解决（尽管对于图的某些特定子类存在一些多项式算法）。
每章最后会对该章的一些要点进行总结。请读者浏览这些总结，以便进行第一遍快速阅读。在一些章节结束时会给出40多道练习题，这些练习标有各种难度，并允许读者对练习所涵盖内容的理解程度进行自测。以星号开头的部分可以先跳过，稍后再进行阅读。
本书的主要目的是帮助读者设计并行算法，然后利用C++和C语言绑定的MPI编写程序实现相应的并行算法。第二个目的是让读者对高性能计算和数据科学有更深刻的了解，并希望更好地促进两者之间的交叉。
本书是关于高性能计算和数据科学的入门教材，面向具有基本算法知识和编程能力的读者。因此，本书不包含（也没有提及）高性能计算和数据科学领域的高级概念。例如，任务调度问题和嵌套循环的自动并行化虽然在高性能计算中很重要，但是本书并没有涉及。类似地，本书也省略了数据科学领域中的回归技术和核心机器学习方法。
教辅资源本书的额外资源（包括超过35个用MPI/C++/R/Scilab/Gnuplot/Processing编写的程序、幻灯片、相关链接和其他精彩内容）可以通过网址https://wwwlixpolytechniquefr/nielsen/HPC4DS/获取。
程序的源代码可以在上述网址以下列方式获取：
祝阅读愉快！
Frank Nielsen2015年12月致谢非常感谢以下这些有才华的同事，他们给了我非常宝贵的反馈意见（姓名按随机顺序排列）并帮助我完善了本书：Claudiad Ambrosio, Ulysse Beaugnon, Annal Bonneton, JeanBaptiste Bordes, PatriceCalégari, Henri Casanova, Antoine DelignatLavaud, Amélie Héliou, Alice Héliou, Léo Liberti, Frédéric Magoulès, Gautier Marti, Sameh Mohamed, Franois Morain, Richard Nock, PierreLouis Poirion, Stéphane Redon, Thomas SibutPinote, Benjamin Smith, Antoine Soulé, Bogdan Tomchuk, Sonia Toubaline和 Frédéric Vivien。除了以上这些同事，我还与其他很多同事进行了讨论，当你们读到这句话时，希望你们能够知道，从这些宝贵的交谈中，我受益匪浅。我还要感谢所有巴黎综合理工大学INF442课程的学生，感谢他们富有成效的意见和反馈，并且感谢巴黎综合理工大学计算机科学学院（DIX）的支持。