并行编程原理与程序设计

**篇 并行计算基础 这一篇主要介绍并行计算的软硬件基础，包括并行计算机硬件基础(第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能力、吞吐量、分时共享能力和稳