并行计算与实现技术

《并行计算与实现技术》系统地介绍了并行计算的基础知识和相关算法，并分别介绍了目前主流的并行编程语言MPI、OpenMP以及CUDA的相关语法、编程以及优化技巧等知识，是并行计算程序开发人员快速入门的一本较全面的教材和参考书。
《并行计算与实现技术》共6章。第1章介绍并行计算的基础知识，阐明了并行计算的起源、发展和现状以及相关的基本概念；第2章介绍部分基础的并行算法，包括区域分解、功能分解、流水线等六种方法，并帮助读者掌握并行算法设计的基本原则；第3章针对矩阵乘法、线性方程组求解、经典迭代算法的并行化、特征值求解这四类典型的数学问题，深入介绍了对应的经典的并行计算算法；第4章和第5章分别介绍了目前使用最广泛的消息传递编程语言MPI和共享存储并行编程语言OpenMP的相关知识和编程技巧；最后一章介绍了GPU并行加速实现技术，并重点介绍了GPU上使用最广泛的CUDA语言的相关语法、硬件架构、优化技巧以及与MPI/OpenMP的混合编程方法。

第1章 并行计算基础
1.1 什么是并行计算
1.2 为什么需要并行计算
1.3 并行计算机的发展
1.4 并行算法复杂性分析
1.5 并行计算的基本概念

第2章 基础并行算法
2.1 并行算法设计基本原则
2.2 区域分解方法
2.3 功能分解方法
2.4 流水线技术
2.5 分而治之方法
2.6 同步并行算法
2.7 异步并行算法

第3章 经典算法的并行计算
3.1 矩阵乘并行计算方法
3.1.1 矩阵卷帘存储方式
3.1.2 并行矩阵乘法
3.2 线性方程组并行求解方法
3.2.1 分布式系统的并行LU分解算法
3.2.2 三角方程组的并行解法
3.3 经典迭代算法的并行化
3.3.1 Jacobi迭代法
3.3.2 Gauss-Seidel迭代法
3.4 特征值问题并行计算方法
3.4.1 对称三对角矩阵特征值问题
3.4.2 Householder变换
3.4.3 化对称矩阵为三对角矩阵

第4章 消息传递编程接口MPI
4.1 并行环境函数
4.2 MPI进程控制函数
4.2.1 MPI进程组操作函数
4.2.2 MPI通信子操作
4.3 点到点通信函数
4.3.1 阻塞式通信函数
4.3.2 非阻塞式通信函数
4.3.3 特殊的点到点通信函数
4.3.4 MPI的通信模式
4.4 自定义数据类型
4.4.1 用户定义的数据类型
4.4.2 MPI的数据打包与拆包
4.5 聚合通信函数
4.5.1 障碍同步
4.5.2 单点与多点通信函数
4.5.3 多点与多点通信函数
4.6 全局归约操作函数

第5章 共享存储并行编程OpenMP
5.1 OpenMP发展历程
5.2 OpenMP执行模型和存储模型
5.3 OpenMP指导语句
5.3.1 parallel结构
5.3.2 工作共享结构
5.3.3 数据共享属性子句
5.3.4 其他子句
5.3.5 Tasking结构
5.3.6 结构嵌套规则
5.4 OpenMP运行时函数库
5.4.1 运行时函数定义
5.4.2 执行环境函数
5.4.3 锁函数
5.4.4 时间函数
5.5 OpenMP环境变量
5.6 OpenMP在MIC架构上的优化技术
5.6.1 offload模式下将Host环境传播至MIC（target）计算节点
5.6.2 offload模式提供了多种关键字来实现多功能的需求
5.6.3 查看编译器对程序中OpenMP区域的优化处理
5.6.4 OpenMP在Offload及Native模式下的不同缺省值
5.6.5 设置OpenMP的栈空间大小
5.6.6 分配部分计算资源给运行的程序

第6章 GPU并行加速实现技术
6.1 GPU以及GPGPU发展简介
6.2 CUDA并行编程模型
6.2.1 线程结构
6.2.2 线程调度
6.3 CUDA软件体系
6.3.1 CUDA函数定义以及变量类型限定符
6.3.2 CUDA算数指令与数学函数
6.3.3 CUDA内置函数
6.3.4 CUDA软件体系结构
6.3.5 CUDA程序的编译
6.4 CUDA存储器模型
6.4.1 寄存器
6.4.2 全局存储器
6.4.3 本地存储器
6.4.4 共享存储器
6.4.5 常量存储器
6.4.6 纹理存储器
6.5 CUDA程序的优化
6.5.1 处理器利用率优化
6.5.2 指令吞吐量优化
6.5.3 存储器访问优化
6.5.4 矩阵乘法程序优化示例
6.5.5 矩阵转置程序优化示例
6.6 MPI/CUDA混合编程
6.6.1 MPI/CUDA混合编程模型
6.6.2 GPU集群上的数据传输模型
6.6.3 MPI/CUDA混合编程以及编译运行示例
6.6.4 MPI/OpenMP/CUDA混合编程
6.6.5 异构平台数学库MAGMA简介
参考文献
索引
《信息与计算科学丛书》已出版书目

《并行计算与实现技术》：
第一章 并行计算基础
近期随着计算机的快速发展，并行计算技术已经得到广泛发展，日常办公用计算机已经是由多核处理器组成的并行计算机，因此，并行计算机对于今天的每个人来说，已经并不陌生。如何有效地让这些计算机发挥其性能，使得物尽其用，就需要了解这些计算机的特点，设计适合并行计算机执行的算法和相应的程序。本章将重点介绍为什么需要并行计算、并行计算机的发展历程、并行算法复杂性分析以及并行计算的基本概念。目的是让读者对并行计算有一个基本认识，掌握一定的理论基础。
1.1 什么是并行计算
并行计算（parallelcomputing）是相对于串行计算提出来的，其基本思想是通过多个处理器共同解决同一个计算问题，即每一个处理器单独承担整个计算任务中的一部分内容。因此计算任务的分解就是并行计算中首要考虑的关键问题，目前常见的分解方法可大体分为时间和空间上的并行，一般情况下计算问题在时间上具有相互关联的特点，所以关于时间并行方法往往采用流水线（详见2.4节流水线技术）的方式实现，近期也有部分研究人员提出通过一种拟合方法来完成时间上的并行，不过此类方法往往对算法上有一定要求。空间上并行是目前绝大多数计算问题的并行解决方案，即在同一时刻将整个计算任务按照某种规则在空间上进行分解，在下一时刻开始前同步相关的参数，最典型的代表就是区域分解算法（详见2.2节区域分解方法）。此外，分解计算任务还要考虑负载均衡、通信量等问题，它们直接关系到并行程序的效果。
通过上面的介绍，我们对并行计算有了一个简单了解，下面给出并行计算的常用定义。
定义1.1并行计算是指在并行机上，将一个计算问题分解成多个子任务，分配给不同的处理器，各个处理器之间相互协同，并行地执行子任务，从而达到加速求解，或者求解大规模应用问题的目的。
开展并行计算，必须具备三个基本条件
（1）并行机。并行机包含多个处理器核心，这些处理器核心通过特定硬件相互连接，相互通信。
（2）应用问题必须具有并行度。也就是说，应用可以分解为多个子任务，这些子任务可以并行地执行。将一个应用分解为多个子任务的过程，称为并行算法的设计。
（3）并行编程。在并行机提供的并行编程环境上，具体实现并行算法，编制并行程序，并运行该程序，从而达到并行求解应用问题的目的。下面通过一个数组求和的例子来给出并行算法设计的思路。
例1.1并行计算求和问题
假设，则有。因此，计算S可以并行执行，亦即S_i（i=0，1，2，3）可以同时计算出，进一步如果令S_00=S_0+S_1和S_01=S_2+S_3，可以同时计算S_00和S_01，最后再计算S=S_00+S_01。
1.2 为什么需要并行计算
翻开计算机发展历史，计算性能的提升主导着整个计算机技术发展，提高传统计算机的计算速度一方面受到物理上光速极限和量子效应的限制，另一方面计算机器件产品和材料的生产受到加工工艺的限制，其尺寸不可能做得无限小，因此目前主流处理器已经向双核、四核、多核以及众核的方向发展。此外，随着计算在科学研究和实际应用中发挥越来越大的作用，人们对计算已经产生了依赖，将数值模拟作为许多决策的依据。现在人们已经习惯将计算作为科学研究的第三种手段，和传统的科学研究的理论方法和实验方法并列。
并行计算是人们为了提高求解问题的计算速度而提出的，从20世纪60年代开始，逐渐得到丰富和发展。众所周知，今天的单个计算机芯片的处理能力已经可以达到每秒万亿次的计算能力，这在21世纪初，其计算性能相当于一台巨型计算机。纵然单个计算机的计算能力已经非常强大，仍然无法满足有很多科学与工程计算问题的计算需求，因此，并行计算机是解决这些问题不可或缺的重要工具。也正是因为科技进步的要求，并行计算正逐步渗透到科学研究与工程应用之中。
当今随着大数据时代的来临，对数据进行处理也同样离不开并行计算，可以说，并行计算是无处不在的。比如，我们要了解我们生存的地球，就需要知道天气变化、环境变化、地震运动等自然规律。在充分的数据分析基础上，科学家们提出了一系列数学物理模型，使得我们今天能够对天气进行预报，对地震进行预测，对环境变化进行研究，结果的获得就需要并行计算的支持。尽管目前的预报和预测还不能让我们满意，但已经取得了重要进展。现代天气预报技术已经趋向于成熟，预报的准确性已经很高，进入了数值天气预报阶段，这项工作也正是有现在的高性能计算机的支持，才能够让我们掌握更多大自然的发展规律，为人类的明天提供更加可靠的数据。还有很多科学研究领域，诸如，天体物理中关于宇宙的形成、暗物质作用、材料科学中晶体结构、流体力学中湍流、基因组学中序列拼接、蛋白组学中结构分析等研究领域与问题，同样需要高性能计算机的强大计算能力。
在工业设计应用中，也同样离不开并行计算技术的支持。比如我们如今每天都需要的出行工具汽车，无论是发动机的设计，还是外观设计均需要进行大量的数值模拟。特别是汽车碰撞试验，不能每次都使用实际汽车来进行试验，一是成本高，重要的是还有安全因素。再比如与我们生命息息相关的药物研制，需要用大量的实验数据来支撑，为了获取这些重要的数据，完全由实验获取是非常困难的。一方面每次实验能够得到的数据有限，也存在着危险性；另一方面，为获取大量数据，需要进行多次实验，时间与经费也难以承受。因此，在药物研制领域，已经越来越多的使用超级计算机进行药物筛选，极大地缩短了药物研发周期和新药研制成本。还有很多工业领域的产品设计都依赖高性能计算机，正如我们熟知的飞机设计、高速列车设计、建筑物设计等都需要进行数值模拟，为最终决策提供重要的依据。
在国家安全方面，高性能计算机越来越发挥着不可替代的作用。众所周知，密码已经是我们生活中习以为常的防护手段，登录计算机、建立银行账号等都需要与密码配合，在一定程度上使我们的信息和财产等得到了保护。由此可见，密码是非常重要的，如果泄露，后果不堪设想。在信息传递过程中，为了保证信息安全，通常采用加密手段，使信息不易被获取。然而这种加密手段也可以通过强大的计算能力来解决，主要取决于计算能力是否能够在短时间内获得一个大整数的2个素数因子。再有，许多案件的破获是源于指纹信息，通过对指纹进行比对，可以非常准确地确定犯罪分子。指纹比对的过程，不可能是指纹专家仅凭肉眼来识别，只能借助于高性能计算机在浩瀚的指纹数据库中搜索，锁定目标之后，再由指纹专家进行linebreak确认。
20世纪90年代，美国提出了HPCC计划，是为了解决一大批巨大挑战性问题，其中包括：天气与气候预报，分子、原子与核结构，大气污染，燃料与燃烧，生物学中的大分子结构，新型材料特性，国家安全等有关问题。而近期内要解决的问题包含：磁记录技术，新药研制，高速城市交通，催化剂设计，燃料燃烧原理，海洋模型模拟，臭氧层空洞，数字解剖，空气污染，蛋白质结构设计，金星图像分析和密码破译技术。为此，世界许多国家都大力开展高性能计算机系统的研制，目的是为在技术上获得制高点。我国一直重视高性能计算机系统的研制，天河一号在2010年世界TOP~500排行榜上位列第一名，2013年，我国天河二号再次问鼎世界第一。
1.3并行计算机的发展
并行计算机从20世纪70年代开始，到80年代蓬勃发展和百家争鸣，90年代体系结构框架趋于统一，随着近年来机群技术的快速发展，并行机技术日趋成熟。本节以时间为线索，简介并行计算机发展的各个阶段，以及各类并行机的典型代表和它们的主要特征。
1972年，世界上诞生了第一台并行计算机ILLIACIV，它含32个处理单元，每台处理机拥有局部内存，为SIMD类型机器，对大型流体力学程序，ILLIACIV获得了2到6倍于当时性能最高的CDC7600机器的速度，并在1975年成为可供研究人员通过网络使用的大型计算机。70年代中后期，出现了Cray-1为代表的向量计算机，2002年日本研制的世界上先进的高性能计算机系统——————地球模拟器的处理器就是采用向量机。
进入80年代，MPP并行计算机开始大量涌现，这种类型的计算机早期的典型代表有iPSC/860，nCUBE-2，Meiko。我国也在这个时期，研制成功了向量计算机银河。
从90年代开始，主流的计算机仍然是MPP，例如：IBMSP2，CrayT3D，CrayT3E，IntelParagonXP/S，中国科学院计算技术研究所“曙光1000”等。
目前主要采用的计算机系统结构为：
（1）机群系统。
（2）DSM，SMP系统。
（3）MPP系统。
（4）星群系统。
这里的星群实际上也是一种机群，它包含了异构机群，每个计算结点可以是不同结构的SMP、MPP等构成。在2013年的高性能计算机系统（表~1。1）中，以混合结构完成的系统取得了飞速发展。在这一年TOP500前3中的2台计算机系统都是混合结构的。混合结构能够取得很高的峰值速度，若在实际应用中能够发挥作用，需要进行大量艰苦的努力。
我国高性能计算机的研制水平一直处于世界领先行列，这对我国开展科学研究、促进技术进步，所起到的巨大推动作用是毋庸置疑的。然而我们必须清醒地认识到，在使用高性能计算机方面，与先进国家相比，还有巨大差距。希望我们的工作能够为仁人志士投入到并行计算行列提供力所能及的帮助。
1.4 并行算法复杂性分析
在数值计算中，我们通常需要预先知道一个算法在计算机上能够何时完成，从理论上就可以得出哪些算法具有优势。因此，需要建立分析算法复杂性的手段，从而可以对算法进行定量评估。这里需要首先明确什么是算法复杂性，再者什么是并行算法复杂性。
定义1.2算法复杂性是由四则运算次数和存储空间大小两部分组成。
在接下来的论述中，只针对四则运算次数进行分析，这也是算法复杂性的重点。
下面用两个例子说明如何得到一个算法的复杂性。
例1.2计算x^n的复杂性。首先，我们需要给出计算x^n的算法，针对算法给出计算复杂性。对于一个问题来说，通常其计算复杂性是确定的，因此我们在算法设计时就应该寻找最佳的计算复杂性算法，从而达到快速计算之目的。那么，怎样计算x^n？比如n=13，可以计算x^2=x*x，x^4=x^2*x^2，x^8=x^4*x^4，x^5=x^4*x，最后计算x^13=x^8*x^5，一共需要5次计算。我们的算法就是基于这种方式，按照2的幂次进行计算。对于给定的一个整数n，其2进制表示可以记为：n=2^k+a_k-12^k-1+cdots+a_12+a_0，其中a_i=0或者a_i=1，k=log_2n。据此可以给出计算方法如下：
算法1.1快速计算x^n的算法。
因此可以得出，当所有的a_i均非零时，这个算法的计算复杂性为2k+1，即2log_2n+1，通常亦称之为计算复杂性为O（logn）。通过此算法可以看到，即使一个简单的问题，其计算方法也可以很复杂，但该问题并不适合并行计算。
例1.3计算矩阵乘向量的复杂性。
这是一个科学计算中适合并行计算的常见问题，即矩阵乘向量y=Ax，其中矩阵A是m*n阶的，y与x分别是m和n维向量。记矩阵A的第i列为A_i，则我们有如下计算方法：计算y=Ax的算法。
……