基于MPI的大数据高性能计算导论_[法] 弗兰克·尼尔森(Frank Nielsen)_9787111602149

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

前言欢迎来到高性能计算的世界！欢迎来到高性能数据科学的世界！
在本书中，我们将介绍面向数据科学（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）的支持。

你还可能感兴趣

我要评论