编辑推荐
暂无
内容简介
本书使用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.3MonteCarlo随机积分算法估算π
2.9.4MonteCarlo随机积分算法估算分子体积
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基于MRMPI库在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.3kmeans ++:一种简单的概率保证的初始化方法
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章)介绍了数据科学的基本知识,并展示了如何编写面向基本串行算法的分布式程序,以应对大规模数据集。当前,许多大规模数据集都是公开的,这些数据集中蕴含了丰富的信息,但是这些信息需要通过精心设计才能被提取出来。
我们主要区分两种并行算法的设计方法:在单个共享内存多核机器上使用多线程并行化算法;在分布式内存集群系统上并行化算法。
一方面,当在共享内存架构(如智能手机、平板电脑,以及智能手表和其他物联网设备)上设计并行化算法时,所有的硬件计算单元(核)位于同一芯片上,我们可以使用多线程来轻松地对视频解码、渲染等任务进行并行化。这种并行是细粒度的(finegrained),但它受到芯片上物理核数的限制(2015年高端智能手机通常只有8个核)。另一方面,集群系统(即分布式内存架构)可以根据待处理的数据集规模来实时扩展资源。集群的构建具有很大的灵活性,例如可以选择异构的计算机节点,然后确定最适合这些节点的互连拓扑结构。这种并行是粗粒度的(coarsegrained),因为在集群中发生节点间通信之前,每个节点可以独立地进行大量的本地计算。
基于MPI的大数据高性能计算导论 pdf下载声明
本pdf资料下载仅供个人学习和研究使用,不能用于商业用途,请在下载后24小时内删除。如果喜欢,请购买正版