《并行编程原理与程序设计》主要介绍目前最常用的几种并行程序设计思路与方法，主要内容包括并行计算基础、OpenMP并行程序设计简介、MPI并行程序设计、CUDA并行程序设计及求解声波方程的并行程序五个部分。其中OpenMP对应共享内存的CPU并行编程，MPI对应消息传递的CPU并行编程，CUDA对应GPU编程。因此，通过对《并行编程原理与程序设计》的学习，可以掌握目前最常用的几种并行编程方法。

本书包含了CPU并行编程和GPU并行编程，填补国内空白，具有很好的实用价值

第一篇 并行计算基础
　　这一篇主要介绍并行计算的软硬件基础，包括并行计算机硬件基础(第1章)和并行程序设计基础(第2章)两部分，为后续并行编程方法的学习提供必需的储备知识。
　　第1章为硬件基础部分。首先介绍了并行计算的概念，分析了并行计算和计算科学之间的关系及当代科学与工程问题的计算需求，正是这些需求推动了并行算法与并行计算机软硬件的发展；然后介绍并行计算机的发展历史、分类、体系结构与存储结构模型，并对目前常见的共享存储多处理机系统、分布存储多处理机系统和集群系统进行了简要介绍；最后介绍了并行计算机的一些基本性能指标。
　　第2章为软件基础部分。首先给出了并行算法、进程、线程及加速比和效率等并行计算领域的基本概念，简要介绍了并行程序的三种开发策略和并行算法的描述方法；然后通过一个计算?的样本程序介绍了数据并行模型、消息传递模型和共享变量模型的主要特点和实现思路，并对PCAM并行程序设计思路进行了较为详细的介绍；最后对HPF、PVM、OpenMP、MPI及CUDA等目前最常用的并行程序设计工具进行了介绍。
　　第1章 并行计算机硬件基础
　　1.1 并行计算
　　1.1.1 并行计算的概念
　　并行计算是相对于串行计算来说的，是一种可以同时执行多个指令的计算方法，也可以同时使用多种计算资源解决计算问题，其目的一般有：①通过利用多个CPU或GPU等资源提供更高的计算效率；②通过利用多个处理器的内存或显存等资源扩大问题求解规模，提供更强的计算能力。并行计算可分为时间上的并行和空间上的并行，时间上的并行指流水线技术，空间上的并行指用多个处理器并发的执行计算。并行计算和高性能计算、超级计算是同义词，因为任何高性能计算和超级计算总离不开并行技术。
　　并行计算的基本思想是用多个处理器来协同求解同一问题，将被求解的问题分解成若干部分，各部分均由一个独立的处理机来计算。并行计算系统既可以是专门设计的、含有多个处理器的超级计算机，也可以是以某种方式互连的若干台独立计算机构成的集群。
　　1.1.2 并行计算与计算科学
　　随着计算机和计算方法的飞速发展，几乎所有的学科都走向定量化和精确化，产生了诸如计算物理、计算化学、计算生物学、计算地球物理学、计算气象学和计算材料科学等的计算科学，逐渐形成了一门计算性的学科分支—计算科学与工程。目前，计算科学已经和理论科学、实验科学并列成为第三门科学，它们彼此相辅相成地推动科学发展与社会进步。许多情况下，由于理论模型复杂甚至理论尚未建立，或者实验费用昂贵甚至实验无法进行，此时计算就成为求解问题的唯一或主要手段。计算科学极大地增强了人们从事科学研究的能力，加速科技向生产力的转化过程，深刻地改变着人类认识世界和改造世界的方法和途径。计算科学的理论和方法作为新的研究手段和新的设计与制造技术的理论基础，正推动着当代科技向纵深发展。
　　计算科学涉及的大型科学工程计算问题往往需要数学家、工程师和计算机科学家进行跨学科和跨行业协同研究，一方面，它需要运用许多基础数学理论，另一方面又需要熟悉某一特定应用领域的背景知识，并且还需要充分掌握和运用先进的计算设备。所以今后的科学与工程计算工作者应尽可能兼备数学、物理、工程科学和计算机科学等多方面的知识，并善于应用超级计算机进行大规模数值试验与分析。
　　1.1.3 当代科学与工程问题的计算需求
　　人类对计算机性能的要求是无止境的，在诸如物理现象模拟、工程设计和自动化、能源勘探、医学、军事及基础理论研究等领域中都对计算提出了极高要求。例如，在气象预报时，要提高全球气象预报的准确性，在经度、纬度和大气层方向上至少要取200 × 100 × 20 = 40万个网格点。中期天气预报有的模式需要635万个点，内存需要几十千兆字节，总运算量达25万亿次，并要求在不到2小时内完成48小时的天气预报。当计算能力不足时，只好降低结果的分辨率，简化计算方案，从而影响了预报的准确度。又如，在进行油田“油藏模拟”时，假定一个油田有上万口井，每口井模拟时至少要取8 × 8 × 50个点，则总的变量个数可高达千万量级，现有的串行计算机很难高效地完成这类问题中的计算工作。此外，在三维地震勘探数值模拟或偏移成像时，往往需要取2000 × 2000 × 2000个网格点的变量进行运算，其计算量更大，串行计算机根本无法胜任，必须借助规模庞大的集群来完成计算工作。其他应用领域包括数字核试验、航空航天飞行器的设计、原子物理过程微观世界的模拟、材料科学计算、环境资源以及生物计算等。这些重大的计算问题，往往涉及不规则复杂结构、不均匀复合材料、非线性的动力学系统等复杂数学物理问题。要对这些复杂的非线性数学物理方程进行大规模和高精度的计算，在一般的计算机上用传统的计算方法往往无能为力。
　　目前科学界和工业界对高速并行计算的需求是广泛的，归纳起来主要有三种类型的应用需求：①计算密集应用，如大型科学工程计算与数值模拟等；②数据密集型应用，如数字图书馆、数据仓库、数据挖掘和计算可视化等；③网络密集型应用，如协同工作、遥控和远程医疗诊断等。
　　这些重大的应用需求推动了当代计算技术的迅速发展。我们也可以从评测计算机性能的单位量词证实业界对计算能力需求的不断提高：20世纪70年代到80年代，常用Mflops(每秒百万次浮点运算)作为评测计算机性能的指标；20世纪80年代中期又增用 Gflops(每秒10亿次浮点运算)作为评测计算机性能的指标；近年来由于大规模并行机的问世，Gflops亦嫌太小，又出现了采用Tflops(每秒万亿次浮点运算)作为评测计算机性能的指标；现在Pflops(每秒千万亿次浮点运算)的计算机的预研工作正在进行。这种计算机速度单位量词的演变，从M(Mega=106)到G(Giga=109)到T(Tera=1012)一直到P(Peta=1015)，反映了计算机本身速度的惊人的改变，而其背后的驱动力就是那些挑战性的应用需求。
　　1.2 并行计算机硬件简介
　　1.2.1 并行计算机的发展历史
　　并行计算机从20世纪70年代开始快速发展，到20世纪80年代出现了蓬勃发展和百家争鸣的局面，20世纪90年代体系结构框架趋于统一，21世纪初期，集群技术成为一个新的快速发展热点。目前，并行计算机技术日趋成熟，下面以时间为线索简要介绍并行计算机的发展历史。
　　20世纪70年代诞生了世界上第一台并行计算机ILLIAC IV(伊利阿克IV计算机)，它包含32个处理单元，具有可扩展性，其计算速度相当于当时性能最高的CDC 7600计算机速度的2～6倍，但在编程模式上与传统的大型机相差很大。之后诞生的并行机还有ICLDAP、Good-year MPP，以及向量机CRAY-1、STAR-100等，它们都属于SIMD(single instruction multiple data，单指令多数据)类型，其中CRAY-1获得了很好的向量计算效果。这些并行机的出现引起了人们的极大兴趣，吸引了大量的专家学者从事并行计算机的研制和并行程序的设计，为20世纪80年代并行机的发展奠定了基础。
　　20世纪80年代早期，以MIMD(multiple instruction multiple data，多指令多数据)并行机的研制为主，首先诞生的是Dendlcor HEP，含16台处理机，共享存储，能同时支持细粒度和粗粒度并行，并且被应用到实际计算中，使许多人学会了并行计算。之后诞生了共享存储向量多处理机CRAY X-MP/22(2个向量机节点)、IBM3090(6个向量机节点)，取得了很好的并行计算性能。同时，以超立方体结构连接的分布式存储MIMD结构原型机开始出现。
　　20世纪80年代中期，共享存储多处理机系统得到了稳定发展。两个成功的机器为Sequent(20个节点)、Encore(16～32个节点)，它们提供稳定的UNIX操作系统，实现用户间的分时共享，对当时VAX系列串行机构成了严重威胁。同时，还诞生了8个节点的向量多处理机Alliant，Alliant提供了非常好的自动向量并行编译技术；诞生了4个节点的向量处理机CRAY-2。这些向量多处理机系统在实际应用中均取得了巨大的成功。与此同时，人们对共享存储多处理机系统的内存访问瓶颈问题有了较清楚的认识，纷纷寻求解决办法以保证它们的可扩展性。此期间还诞生了可扩展的分布存储MIMD MPPn CUBE，这台机器含1024个节点，CPU和存储单元均分布包含在节点内，所有节点通过超立方体网络相互连接，支持消息传递并行编程环境，并真正投入实际使用。由于该机在流体力学领域中的几个实际应用获得了超过1000的加速比，引起了计算机界的轰动，改变了人们对 Amdahl定律的认识，排除了当时笼罩并行计算技术的阴影。
　　在当时的分布式存储体系结构中，处理机间的消息传递与消息长度、处理机间的距离有较大的关系。因此互联网络最优拓扑连接和数据包路由选择算法的研究引起了人们的注意，目的在于减少处理机远端访问的花费。
　　20世纪80年代后期，真正具有强大计算能力的并行机开始出现。例如，Meiko系统，它由400个T800 Transputer通过二维Mesh(网孔)相互连接构成，适合中等粒度并行。此间出现的主要并行计算机包括：①三台SIMD并行机：CM2，Maspar和DAP，其中CM2对 Linpack测试获得了5.2 GFLOPS的性能；②超立方体连接的分布存储MIMD并行机 nCUBE2与 InteliPSc/860，分别可扩展到8192个节点和128个节点，峰值性能达27 GFLOPS和7 GFLOPS；③由硬件支持共享存储机制的BBN TO2000，用Buttery多级互联网连接处理机和存储模块，可扩展到500台处理机，本地cache、内存和远端内存访问的延迟时间之比为1∶3∶7；共享存储向量多处理机系统CRAY Y-MP，能获得很好的实际运算性能。
　　进入20世纪90年代，得益于微电子技术的发展，基于RISC指令系统的微处理芯片的性能几乎以每18个月增长1倍、内存容量几乎每年增长1倍的速度发展，而网络通信技术也得到了快速增长，它们都对并行计算机的发展产生了重要影响。
　　为了满足美国HPCC(High Performance Computing and Communications，高性能计算与通信)计划中提出的高性能计算要求，考虑到共享存储并行机的内存访问瓶颈问题，人们纷纷把眼光瞄准到分布式存储MPP(massively parallel processing)系统，使得MPP的硬件和软件系统得到了长足发展。由于微处理芯片性能和网络技术的发展，MPP并行机大量采用商用微处理芯片作为单节点，通过高性能互联网连接而成。由于普遍采用虫孔路由选择算法，因此消息传递的耗时不再与它所经过的节点个数相关，即处理机间的消息传递花费不再与距离相关，或者相关程度可以忽略不计。分布式存储并行程序设计以消息传递为主。
　　这一时期，MIMD类型占据主导地位，SIMD并行机和向量机逐渐退出舞台，但以单个向量机为节点构成的MIMD并行机仍然在实际应用中发挥着重要作用。
　　20世纪90年代中期，微处理器的性能已经非常强大，能够提供每秒几亿到十几亿次的浮点运算速度。同时，互联网络点对点的通信能达到每秒超过500MB的带宽。高性能微处理器和网络通信技术为并行计算硬件环境带来了新的面貌，呈现出以下发展趋势。
　　(1)以高性能微处理芯片和互联网络通信技术为基础，共享存储对称多处理机(symmetric multiprocessor， SMP)系统得到了迅速发展。它们大多以高性能服务器的面目出现，能提供每秒几百亿次的浮点运算能力、几十个GB的内存和超过10GB的访存带宽，具有丰富的系统软件和应用软件，很强的容错能力、I/O能力、吞吐量、分时共享能力和稳

目录
前言
第一篇 并行计算基础
第1章 并行计算机硬件基础 3
1.1 并行计算 3
1.1.1 并行计算的概念 3
1.1.2 并行计算与计算科学 3
1.1.3 当代科学与工程问题的计算需求 4
1.2 并行计算机硬件简介 4
1.2.1 并行计算机的发展历史 4
1.2.2 并行计算机的分类 8
1.2.3 并行计算机的体系结构 9
1.3 当代并行计算机系统简介 14
1.3.1 共享存储多处理机系统 15
1.3.2 分布存储多处理机系统 15
1.3.3 集群系统 17
1.4 并行计算机的一些基本性能指标 24
1.4.1 CPU和存储器的某些性能指标 24
1.4.2 通信开销 25
1.4.3 机器的成本、价格与性价比 26
第2章 并行程序设计基础 28
2.1 并行算法的基础知识 28
2.1.1 并行算法领域的一些基本概念 28
2.1.2 并行程序开发策略与并行算法的描述方法 30
2.1.3 并行算法中的同步与通信 31
2.2 并行程序设计模型 32
2.2.1 计算π的样本程序 32
2.2.2 数据并行模型 33
2.2.3 消息传递模型 34
2.2.4 共享变量模型 36
2.3 并行程序设计方法 38
2.3.1 PCAM并行程序设计思路 38
2.3.2 并行编程语言 41
第二篇 OpenMP并行程序设计简介
第3章 OpenMP介绍 55
3.1 什么是OpenMP 55
3.2 共享内存式并行计算 55
3.3 OpenMP的发展历程 56
3.4 Windows平台下OpenMP环境搭建 56
第4章 OpenMP指令结构 59
4.1 编译指导语句的一般形式 59
4.2 主要指令 60
4.3 主要子句 61
4.4 常用库函数 62
第5章 OpenMP常用指令的用法 63
5.1 数据管理 63
5.1.1 Private子句 63
5.1.2 Firstprivate/Lastprivate子句 64
5.1.3 Shared子句 65
5.1.4 Default子句 66
5.1.5 Threadprivate子句 67
5.1.6 Copyin、copyprivate子句 68
5.1.7 Reduction子句 69
5.2 并行控制 70
5.2.1 Parallel指令 70
5.2.2 For指令 75
5.2.3 Schedule子句 76
5.2.4 Sections指令 80
5.2.5 Single指令 82
5.3 同步管理 82
5.3.1 Critical指令 83
5.3.2 Atomic指令 84
5.3.3 Barrier指令 85
5.3.4 Ordered指令 86
5.3.5 Master指令 86
5.3.6 Flush指令 87
5.4 常用库函数 87
5.4.1 运行时库函数 87
5.4.2 锁管理 88
5.4.3 环境变量 90
第6章 OpenMP实例 91
6.1 循环实例 91
6.2 并行程序的优化 93
6.2.1 临界区实现 93
6.2.2 原子操作实现 95
6.2.3 归约实现 95
6.3 快速排序并行算法 96
第三篇 MPI并行程序设计
第7章 MPI编程基础 103
7.1 MPI简介 103
7.1.1 MPI的含义 103
7.1.2 MPI的目标 103
7.1.3 MPI的产生 103
7.1.4 MPI的语言绑定 104
7.1.5 目前MPI的主要实现 104
7.2 一个简单的MPI程序 105
7.2.1 MPI实现的“Hello World!” 105
7.2.2 MPI程序的框架结构 109
7.2.3 MPI程序的一些惯例 109
7.3 6个基本函数组成的MPI子集 109
7.3.1 子集介绍 109
7.3.2 MPI预定义的数据类型 114
7.3.3 MPI数据类型匹配 115
7.3.4 MPI消息 117
7.4 简单的MPI程序示例 118
7.4.1 求二维数据中各元素绝对值的最大值 119
7.4.2 用MPI实现计时功能 121
7.4.3 获取机器名字与MPI版本号 123
7.4.4 是否初始化及错误退出 124
7.4.5 环形消息传递 125
7.4.6 所有进程相互问候 126
7.4.7 任意源和任意标识的使用 128
7.4.8 编写安全的MPI程序 129
第8章 MPI的安装与并行编程环境的设置 132
8.1 Linux环境下的MPICH2安装与设置 132
8.2 Windows环境下MPICH2的安装与设置 133
8.2.1 安装 133
8.2.2 编译运行C+MPI程序 134
8.2.3 编译运行Fortran+MPI程序 138
第9章 对等模式与主从模式的MPI程序设计 141
9.1 对等模式MPI程序设计 141
9.1.1 问题描述——雅可比迭代 141
9.1.2 用MPI程序实现雅可比迭代 142
9.1.3 采用捆绑发送接收实现雅可比迭代 146
9.1.4 引入虚拟进程后雅可比迭代的实现 151
9.2 主从模式MPI程序设计 155
9.2.1 矩阵向量乘 155
9.2.2 主进程打印各从进程的消息 159
第10章 MPI的四种通信模式 162
10.1 标准通信模式 162
10.2 缓存通信模式 163
10.3 同步通信模式 165
10.4 就绪通信模式 167
第11章 MPI的非阻塞通信 170
11.1 非阻塞通信简介 170
11.1.1 阻塞通信 170
11.1.2 非阻塞通信 171
11.2 非阻塞标准发送与接收 173
11.3 非阻塞通信与其他三种通信模式的结合 174
11.4 非阻塞通信的完成与检测 175
11.4.1 单个非阻塞通信的完成与检测 175
11.4.2 多个非阻塞通信的完成与检测 176
11.5 非阻塞通信对象 178
11.5.1 非阻塞通信的取消 179
11.5.2 非阻塞通信对象的释放 180
11.5.3 消息到达的检查 181
11.5.4 用非阻塞通信来实现雅可比迭代 182
11.6 重复非阻塞通信 185
第12章 MPI的组通信调用 190
12.1 组通信概述 190
12.2 组通信的通信功能 191
12.2.1 广播 191
12.2.2 收集 192
12.2.3 散发 196
12.2.4 组收集 199
12.2.5 全互换 201
12.3 组通信的同步功能 204
12.4 组通信的计算功能 205
12.4.1 归约 205
12.4.2 MPI的内置归约算符 206
12.4.3 程序举例 207
12.4.4 组归约 209
12.4.5 归约并散发 211
12.4.6 扫描 212
12.4.7 不同类型归约操作的对比 213
12.4.8 MINLOC和MAXLOC 215
12.4.9 用户自定义的归约操作 216
第13章 MPI的派生数据类型 220
13.1 类型图 220
13.2 新数据类型的定义 221
13.2.1 MPI提供的数据类型生成器 221
13.2.2 新类型递交和释放 226
13.2.3 地址函数 227
13.2.4 与数据类型有关的调用 228
13.2.5 下界类型和上界类型 231
13.3 例题 232
13.4 打包与解包 236
第14章 MPI的进程组和通信域 239
14.1 简介 239
14.2 进程组和通信域的管理 239
14.2.1 MPI的进程组管理接口 240
14.2.2 通信域的管理 245
14.3 组间通信域 250
第15章 MPI扩展 255
15.1 MPI的动态进程管理 255
15.1.1 组间通信域 255
15.1.2 动态进程的创建 257
15.1.3 独立进程间的通信 260
15.1.4 基于socket的通信 263
15.2 MPI的远程存储访问 263
15.2.1 窗口创建与窗口操作 264
15.2.2 窗口同步管理 267
15.3 并行I/O 275
15.3.1 并行文件管理的基本操作 276
15.3.2 显式指定偏移量的并行文件读写 279
15.3.3 多视口的并行文件并行读写 283
15.3.4 共享文件指针读写 291
第16章 MPI函数调用原型与简单解释 297
16.1 MPI-1与C语言的接口 297
16.2 MPI-1与Fortran语言的接口 305
16.3 MPI-2与C语言的接口 314
16.4 MPI-2与Fortran语言的接口 324
第四篇 CUDA并行程序设计
第17章 GPU简介 339
17.1 NVIDIA GPU发展简介 339
17.2 GPU硬件架构 340
17.2.1 图形显卡概览 340
17.2.2 PCI-E总线 341
17.2.3 显存 342
17.2.4 GPU芯片 343
17.3 基于GPU的程序开发 344
17.3.1 传统GPU开发 344
17.3.2 CUDA开发 344
第18章 CUDA安装与编译 346
18.1 CUDA函数库与CUDA C++语言 346
18.1.1 CUDA API和函数库 346
18.1.2 CUDA C++语言 347
18.1.3 CUDA C++拓展限定符语法 348
18.2 CUDA的安装与配置 351
18.2.1 开发环境 351
18.2.2 安装平台 354
18.2.3 CUDA安装与配置 355
18.3 CUDA编译与驱动 357
18.3.1 Emu调试 357
18.3.2 编译相关 358
18.3.3 错误处理 359
18.3.4 计算模式 359
第19章 CUDA编程基础 360
19.1 主机与设备 360
19.2 核函数的定义与调用 362
19.3 设备中的空间管理与数据传输 363
19.4 线程结构 365
19.5 硬件映射 370
19.5.1 计算单元 370
19.5.2 Warp 372
19.5.3 执行模型 372
19.6 存储器类型 373
19.6.1 寄存器 374
19.6.2 局部存储器 375
19.6.3 共享存储器 3