本书使用MPI标准介绍了数据科学中的高性能计算，可帮助本科生了解分布式存储模型中的并行编程的知识，本书分为两部分，第一部分基于MPI标准介绍高性能计算，第二部分介绍计算机集群中的高性能数据分析。

1

欢迎来到高性能计算的世界！欢迎来到高性能数据科学的世界！
在本书中，我们将介绍面向数据科学（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 Nielsen
2015年12月

计算机\高性能计算

本书是关于高性能计算和数据科学的入门教材，面向有基本算法知识和编程能力的读者，书中选择C++语言来实现数据科学中的算法，并使用和C语言绑定的OpenMPI应用程序编程接口来编写并行程序，使用MPI标准介绍数据科学中的高性能计算，帮助读者了解分布式存储模型中的并行编程知识。

本书分为两部分，第一部分（第1~6章）基于MPI介绍高性能计算，第二部分（第7~11章）介绍计算机集群中的高性能数据分析。本书教辅资源丰富，书中相关的伪代码可在对应网站下载，章末附有各种难度的练习和参考文献，可供读者进行自测和深入学习。

通过阅读本书，你将学到：
阻塞与非阻塞的点对点通信、死锁、全局通信函数（广播、散播等）和协同计算（归约）的基本概念。
互联网络的拓扑结构（环、环面和超立方体）以及相应的全局通信程序。
如何设计并实现基于分布式内存的并行排序，了解并行线性代数知识（如矩阵相乘）。
使用MPI框架计算适用于处理大数据的MapReduce模型。
数据聚类技术（平面划分聚类、层次聚类）。
基于k-NN的有监督分类及其与k均值聚类算法的比较。
核心集以及相关降维技术。
图算法（最稠密子图、图同构检测）。

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

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

数据科学（Data Science,DS）的目的是研究数据本身，研究数据的各种类型、状态、属性及变化形式和变化规律。随着当前数据量的指数级增长，数据科学的战略意义已经不在于掌握“大数据”（big data）信息本身，而在于对这些含有意义的数据进行快速、准确、高效地分析处理。
高性能计算（High Performance Computing，HPC）是辅助“大数据”快速分析与处理的利器之一。通过高性能网络互连的很多处理器或者某一集群中的大量计算机，对“大数据”进行并行聚类、分类以及降维等操作，从而能够更加快速地获取数据中蕴含的规律和有价值的信息。
本书的主要目的是将数据科学与高性能计算两大研究分支交叉融合起来，让高性能计算更好地为数据科学服务，让数据科学对高性能计算发展提出新的需求。因此，本书分为两个部分：第一部分，介绍了高性能计算的基本概念及基于标准消息传递接口（Message Passing Interface，MPI）的并行编程方法；第二部分，给出了高性能计算在数据科学中的应用，尤其重点阐述了如何利用MPI来并行化数据科学中的算法。
本书由哈尔滨工业大学计算机科学与技术学院张伟哲教授对全书统稿和校对，其中第1章、第4章、第5章、第11章和附录由哈尔滨工业大学鲁刚钊翻译，第2章由哈尔滨工业大学王德胜翻译，第3章由哈尔滨工业大学孙博文翻译，第6～10章由哈尔滨工业大学郝萌翻译。同时，我们的工作还得到哈尔滨工业大学梁智颖、任雪健的帮助，在此一并表示感谢。
还要特别感谢机械工业出版社的编辑唐晓琳、王春华在本书的编辑、出版方面所付出的辛勤劳动。
我们希望本书的出版对相关科技人员和读者所有帮助，同时也期望广大专家和读者提出宝贵意见。

译者序
前言
致谢
第一部分基于消息传递接口的高性能计算
第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总结
712练习
参考文献
第8章层次聚类
81凝聚式与分裂式层次聚类及其树状图表示
82定义一个好的连接距离的几种策略
821一个用于凝聚式层次聚类的通用算法
822为元素选择合适的基本距离函数
83Ward合并准则和质心
84从树状图中获取平面划分
85超度量距离和进化树
86注释和参考
87总结
88练习
参考文献
第9章有监督学习: kNN规则分类的理论和实践
91有监督学习
92最近邻分类：NN规则
921最近邻查询中欧几里得距离计算的优化方法
922最近邻（NN）规则和Voronoi图
923利用kNN规则通过表决来增强NN规则
93分类器性能评估
931误判错误率
932混淆矩阵与真/假及阳性/阴性
94准确率、召回率和F值
95统计机器学习和贝叶斯最小误差界
951非参数概率密度估计
952误差概率和贝叶斯误差
953kNN规则的误差概率
96在计算机集群上实现最近邻查询
97注释和参考
98总结
99练习
参考文献
第10章基于核心集的高维快速近似优化和快速降维
101大规模数据集的近似优化
1011高维度的必要性示例
1012高维度上的一些距离现象
1013核心集：从大数据集到小数据集
102核心集的定义
103最小闭包球的核心集
104一个用来近似最小闭包球的简单迭代启发式方法
1041收敛性证明
1042小闭包球和用于SVM的边缘线性分离器
105k均值的核心集
106基于随机投影矩阵的快速降维
1061维数灾难
1062高维度任务的两个示例
1063线性降维
1064JohnsonLindenstrauss定理
1065随机投影矩阵
107注释和参考
108总结
109练习
参考文献
第11章图并行算法
111在大图中寻找（最）稠密子图
1111问题描述
1112最稠密子图的复杂度和一个简单的贪心启发式算法
1113最稠密子图的并行启发式算法
112判断（子）图同构
1121枚举算法的一般原则
1122Ullman算法：检测子图同构性
1123枚举算法并行化
113注释和参考
114总结
115练习
参考文献
附录A 笔试
附录B SLURM:集群上的资源管理器和任务调度器