并行计算讲义

1、燕山大学课程讲义并行计算导论授课人：郭栋梁 学时： 32 学时 其中实验课： 8 学时 三级工程： 16 学时 第 1 章 引言1.1 概述单处理器计算机即将成为过时的概念.我们需要考虑如下因素来着手改良提高计算机的性能 : 1 单纯依靠单处理器很难提升现有计算机的性能.即使有一个性能十分强大的单处理器，其功耗也让人无法接受 .想要提升计算机的性能，更加可行的方法是同时使用多个简单处理器，它所能到达的性能可能 是现有单处理器计算机性能的几千倍。 2 观察结果显示，除非使用并行处理技术，一个程序在一台型号更新的单处理器计算机上的运行速度， 可能比在旧的计算机上的运行速度更慢。能依照给定算法检测出

2、程序中的并行结构的编程工具还有待 开发。 此算法需要能够检测出变 ja 之间的依赖关系是否规那么 ;而且不管这些依赖是否规那么， 此算法都能 在保证程序正确性的前提下，通过将程序中的一些子任务并行化来加速程序的执行。 3 提升未来的计算机性能的关键就在于并行程序的开发，这涉及各个层面的工作:算法、程序开发、操作系统、编译器及硬件设备。 4 并行计算除了要考虑到参与并行计算的处理器的数量，还应该考虑处理器与处理器、处理器与内存之 间的通信。最终计算性能的提升既依赖于算法能够提升的空间，更依赖于处理器执行算法的效率。而 通信性能的提升那么依赖于处理器对数据的供给和提取的速度。 5 内存系统的速度始

3、终比处理器慢，而且由于一次只能进行单个字的读写操作，内存系统的带宽也有限制。 6 内存系统的速度始终比处理器慢，而且由于一次只能进行单个字的读写操作，内存系统的带宽也有限 制。本书内容主要涉及并行算法与为了实现这些算法而设计的硬件结构。 硬件和软件是相互影响的， 任何软件 的最终运行环境是由处理器组成的底层硬件设备和相应的操作系统组成.我们在本章开始的局部会介绍一些概念，之后再来讨论为了实现这些概念有哪些方法和限制 .1.2 自动并行编程对于算法在软件中的实现过程我们都很熟悉。 在编程并不需要了解目标计算机系统的具体细节， 因为编译器会处理这些细节.但是在编程和调试时依旧沿用着在单一央处理器C

4、PU上顺序处理的模式.从另一方面讲，为了实现并行算法，硬件和软件之间的相互联系需要比我们想象的更加密切。图1.1 展示了基于软件和硬件、利用并行计算机来运行程序的主要步骤和层次。 从最顶层开始， 第 5 层是指应用层， 在这一层里描述的是需要并 行计算平台实现的应用和问题。对应所需的输入和输岀的格式也在这层进行定义。某些输人和输岀I/O接口的描述还需要考虑数据存储的位置和时间相关性。这一层的结果会被更低一层采纳以便指导并行算法的开发工作。第 4 层是算法开发层， 这里需要考虑到应用在问题中的实现。 需要应用实现的计算内容决定了算法的具体 任务和任务之间的相互依赖关系 interdependen

5、ce 。在这一阶段，算法的并行性并不一定会显现出来，因为在 探索算法子任务执行的时候仍然在运用传统的线性思考。 在这一阶段， 也不需要考虑子任务的时间调度和处理但是这样做会适得其反， 因为这会掩盖或者是一个概括了任务之间依赖关系的临这一层接收了第 4 层对算法的描述并且给器分配的问题。可能在现阶段就将这些问题解决的做法看起来很诱人， 程序中潜在的并行性。该层的结果是一个依赖图， 或是一个有向图， 界矩阵。第 3 层是并行化层， 在这一层将试着释放算法中潜在的并行性。出了基于软件实现的线程时间调度和处理器分配。 另一种选择是在这一层进行基于超大规模集成电路的硬件实1.1 用灰色方形显示。现的任务

6、调度和处理器分配。本书内容主要集中在这一层上，在图第 2 层是代码层， 在本层中并行算法用高级语言表示为代码。 使用何种语言取决于目标并行计算在何种平 台执行。图 1. 1 中右侧的分支表示算法在通用并行计算平台上的实现过程。 这一做法即是我们所说的 “并行编 程。并行计算机程序由所谓的“并发平台执行，此种平台帮助编程人员管理线程，处理处理器级别的任务 执行时间调度。并发平台包括 Cilk+ ,OpenMP,CUDAcompute unified device architecture 统一计算设备架构 。图 1. 1 中左侧的分支表示并行算法在定制的硬件设备上的实现， 例如脉动阵列计算机。

7、编程人员使用硬件 描述语言 HDL ，例如 Verilog, 或者超高速集成电路硬件描述语言VHDL。第 1 层的目标是算法的实现，或是在并行计算机平台的应用 . 实现的途径可以是在并行计算平台上使用多线程，也可以是在特定用途集成电路ASIC上或者现场可编程门阵列FPGA上使用特定的应用并行处理系统.那么并行计算机自动编程又是什么意思呢?现在我们已经可以进行线性计算机自动编程.程序员用像C,Java,FORTRAN这样的高级语言编写代码， 这些代码可以被计算机自动编译， 不需要程序员再去做进一步的工 作。更重要的是，程序员编程的时候也不需要了解底层计算平台的硬件细节.甚至在程序员完全不需要知道

8、内存结构，也不知道 CPU的信息和产他细节的情况下，代码就可以迅速地转化为结果。上述的一切能用在并行编程上吗?我们需要的并行编译器要能找到简单环路和解决处理器的分配等问题而且这种编译器还能轻松地解决现在被称为“让人为难的并行算法译注 :也就是相对独立的可以完全并行执行的算法 的问题 2. 3。除此之外，程序员还需要对处理器之间的行为有着充分的了解，并且知道算法需要在 何时执行。1.2 自动并行编程IEEE 电子工程名词标准词典里对于“算法一词的定义如下:为了描述在有限步骤内解决某一个问题而定义的过程或者规那么。一个算法的任务或者过程一般是独立的。有些任务可以并发执行，但有些必须线性地按顺序进行

9、 .根据上述的定义，任何算法都是由并行和非并行两局部组成的。除了某些极端的情况，很难定义某些 算法是并行的而某些是完全串行的 即非并行 ，后面将探讨如何量化一个算法的并行度。如果某个算法由 W 个子任务组成，那么称与这个算法有关的操作数是W.定义一个算法的根本组成局部如下 ：1不同的子任务。2子任务之间的依赖关系。当某一个子任务的输入是另一个子任务的输出时，他们之间那么存在依赖关系。3算法的初始输入集。4算法的最终输出集。我们通常用有向图以下简称DG来直观地表示算法的子任务之间的数据依赖关系。DG在描述算法的时候表示依赖图，需要用带箭头的线段强调子任务之间的数据流向关系.换句话说，如果一个依赖

10、图的边没有箭头表示方向，就很难从图中得知数据的依赖关系。定义 1.1 一个依赖图是边和结点的集合 .结点表示算法的子任务， 边表示子任务用到的数据 .数据包括输人、 输出和中间结果 .需要注意的是， 在一个依赖图中出现的不带箭头的边表示此边连接的两个结点之间没有数据依赖关系，它们只是共用算法中的某一个变量。这个变量可以是输入、输出或者在算法中作为IO 媒介的中间结果。定义 1.2 DG 是有向边和结点的集合。 结点表示算法需要处理的子任务， 有向边表示子任务之间的数据依赖关系 .一个子任务的输出在一条边的开端局部，箭头指向的一端表示一个子任务的输入。 定义 1.3 有向无环图 (DAG )址指

11、一个没有任何环路的 DG.图1.2是一个例如算法的 DAG,根据源结点和目标结点的关系来加以分类，在一个DAG或者DG里有3种不通过的边。定义1.4 一个DG中的输人边是指只有目标结点而没有任何源结点的边，表述了算法的一个输入。在图 1.2 中，可以粉到有 3 条这样的输人边，分别表示了输人in0 , in1, 和 in2定义1.6 一个DG中的内部边是指既有源结点又有目标结点的边，表述了算法的一个内部变量。 定义1.7 一个DG中的输入结点是指所有的人边都是输入边的结点。在图 1. 2中，可以看到结点 0,1 和 2都表示输人结点。输人结点所表示的子任务在算法输人变量就绪后就 被处理。定义1

12、.8 一个DG中的输岀结点是指所有的岀边都是输岀边的结点。图1.2中，可以看到结点 7和 9都表示输人结点。但结点 3不是输出结点，因为结点 3的一条出边是指向 结点 7 的内部边。定义1.9 一个DG中的内部结点是有至少一条人边和至少一条岀边的结点。1.3.2 算法的邻接矩阵一个算法也可以用一个邻接矩阵A来表示。假设算法中有 W个子任务，就有一个 WX W阶的0-1矩阵来表示这个算法，其中 a(i,j)=1表示结点i的输人依赖于结点j的输岀，j是源结点而i是目标结点。当a(i,j) = 0表示 结点i的输入不依赖于节点 j的输岀。对于任何 0<=i<W，a(i，i)=0，因为我们

13、假设在算法中没有输岀指向自己 的结点，这样一来也不会构成“自环。上述定义的邻接矩阵是非对称的，因为当a(i,j)=1 和 a(j， i)=1 同时生时就会构成一个环路。例如，图 1.2 的邻接矩阵 A 如下。矩阵 A 有一些很有趣的性质值得研究 .假设在 i 行每一个元素都等于 0，那么结点 i 是一个输入结点 ;假设 j 列上都 等于 0，那么结点 j 是一个输岀结点 .可以用等式表示为 :此外其他结点都是内部结点。在矩阵 A 中，第 0,1 和 2行的元素都是 0，表示结点 0、结点 1 和结点 2 都是输人结点，这三行的元素都 用黑体显示。第 7列和第 9列的元素都是 0，说明结点 7和

14、结点 9都是输岀结点，这两列的元素也都用黑体显 示。其他行和列中都有超过1个非零元素，说明这些结点都是内部结点。假设结点i有元素a(i,j)=1那么说结点J是结点 i 的母结点。依据子任务的依赖关系可以大致将算法分为如下几类 :(1) 串行算法。(2) 并行算法。(3) 串行一并行算法 (SPA).(4) 非串行一并行算法 (NSPA)(5) 正那么迭代算法 (RIA)最后一类算法可以看做 SPA 的泛化。值得一提的是，根据数据或者任务的粒度的不同，算法的分类也随 之改变。例如说，如果矩阵的元素相加是一项根本操作，求两个矩阵的和就可以看做是一个串行算法。假设另一 台计算机上的根本操作是相关行列

15、的相加，那我们的算法就变成了基于行列的并行算法。另一项值得一提的事情是， 一些算法的子任务可能会有不同类型的算法。依旧可以用矩阵相加的运算来说明。在并行计算机中两组相关行的计算可以同时在两个不同的处理器上执行。但在每个处理器上相关行上的元素又是串行处理的，因此这个并行算法中就包含了行相加的串行算法。稍后我们会详细讨论这些分类。串行算法的特点是由于相互之间存在数据依赖关系，子任务必须一个一个地按顺序执行。这一类算法的DG是由一系列关联的子任务构成的队列图1. 3(a)展示了一个串行算法的 DGo此类算法是用来计算斐波那契数列的。为了得到 nio,子任务Tio进行了如下计算:(1.4)n10=n8

16、+n9在此no = 1和ni=1初始条件已经给岀.很明显，为了得到某一位的斐波那契数只能依次计算在它之前的数。并行算法的特点是由于相互之间不存在数据依赖关系，子任务可以同时并发执行。此类算法的DG就像是许多独立的子任务组成的一组任务，相互之间没有联系。 图1. 3(b)展示了一个并行算法的 DG, Web效劳器上的数据处理应用就是一种简单的并行算法，每一次数据请求都被看做独立的任务交给不同的处理器来响应.同时运行浏览器，字处理程序等多个程序时操作系统的多任务调度算法也是一种并行算法。1.3.6 SPASPA的特点是子任务被分配推不同层次，每个层次之内的子任务可以并发执行，但是各个层次需按照一定

17、的顺序执行.当需要执行的层次只有一层时，这个SPA就是并行算法。当每一层都只有一个子任务时.这个SPA是串行算法。图1.3(c)展示了 CORDIC算的DG, CORDIC算法就是一个典型的 SPA它有n层迭代，在第i次迭代 时需要执行以下运算：在此等式中x，y和z都是进行迭代的数据.每次迭代之后都会被更新。、打和vi是存在表单中的常量.m是用来控制计算类型的参数，j的数值是预设的.与i有关.此算法每次迭代都会进行这三项操作，这里并不研究该算法的细节。1.3.7 NSPANSPA不属于上述分类中的任何一种，NSPA算法的DG也没有规律可循。根据算法DG是否有环我们将 NSPA分为两大类：(1)

18、 DAGo有向有环图(DCG),图1.4(a)展示了一个DAG算法，图1.4(b)是一个DCG算法.DCG算法常见于离散时间回谈控制系统。输入 信号作为子任务 T。的初始滤波或者愉人信号条件.子任务T1的输出通常是错误信号，然后这个信号会作为一种 反应输入子任务 T2中。NSPA的依赖图有两种典型构造：结点用来表示构成算法的子任务，有向边那么表示子任务之间的数据流向.一个结点的一条岀线表示输岀，入线表示的是输入。假设T的输岀指向Tj ,我们那么说Tj依赖于Ti.在图中我们那么用“结点i的一条有向边指向结点j来表示这种依赖关系。一个算法的DG有如下3个重要属性：(1) Work任务数(W)表示算

19、法完成需要处理的子任务总数。(2) Depth深度(d)表示任f “个输人结点到任意一个输岀结点之间的最大路径长度，也被称为关键路径。(3) Parallelism并行度(P)，也被称为并行程度，表示可以并发执行的最结点数.由此数据可以决定这个算法需要的处理器的数目不会超过P，这样一来在算法执行过程中就不会岀现不必要的空闲处理器第8章会对这些性质进行进一步探讨上实现。此外还会研究如何将这样的算法在并行。1.3.8 RIAKarp等介绍了 RIA的概念.此类算法需要特别加以说明，因为此类算法涵盖范围甚广，包括信号处理、图 像和视频处理，线性代数应用。以及基于网格结构的数字模拟程序，图1.5是一个

20、RIA的依赖图，用作例如的是图像匹配算法。对干RIA算法我们不绘制 DAG来表示.而是用依赖图的概念来表示 .依赖图和DAG类似.但是依赖图中的连接边是无向边.依赖图的具体画法在第9章，第10章以及第11章会详细表达 .RIA 中的任务依赖关系图十分复杂。串行算法和并行算法，甚至SPA 算法的并行度计算都不复杂。但是RIA算法的并行度计算十分困难。矩阵乘算法就是简单的RIA算法，具体见算法1.1算法 1.1 中出现的变量和算法的因子 i,j,k 有着正那么依赖关系。 一般情况下此类算法通过依赖图来进行研究， 依赖图能展示需要执行的子任务之间的关系。 当算法只有 1 个或 2 个因子时， 依赖图

21、是很直观的。 但是矩阵相 乘算法出现了 3 个因子，因此它的依赖图是三维的，很难直观表示。1.3.9 并行算法实现上一节讨论了根据子任务之间的依赖关系不同， 我们将算法分为几个不同的类别， 本节将探讨根据算法的 类型如何将算法在并行计算机上利用软件或硬件实现。这涉及算法的并行化.根据算法的类型不同采取相应并行化的策略。1.4 设计并行计算系统本节讨论的是在设计并行计算系统时需要注意的一些重要问题. 并行计算系统的设计需要考虑许多方面。 设计者需要选择一个能处理预期任务的根底处理器架构。处理器应该是一个简单的单元， 也可以是一个能运行多线程操作系统的超标量处理器。处理器之间的通信应采用内部互联网

22、络 . 此网络应该有能力支持任意两个处理器之间的即时通信。处理器之间的连接方式类似于电信中的信道。 数据交换的方式需要详细的说明。 总线互联是最简单的内部互联网的实现方 式. 数据的交换根本单位是字。 系统有一个时钟负责通知处理器数据是否可用。 如今总线已经被网络芯片 (NoC) 代替 .数据在网络芯片上交换的根本单位是数据包，使用路由器来计算数据之间的传输线路.数据和程序需要储存在特定的内存系统中，设计者可以选择让处理器共享内存模块.或者可以为每一个处理器都分配特定的内存模块。假设采用共享内存的设计，系统需为读和写操作分配不同的内存模块。读和写的顺序需 保证数据完整性 .假设某个数据被某个处

23、理器更改正，其他处理器应被告知此更改以确保数据的正确性.任务或者程序在一个并行计算机上的实现需要考虑如下问题. 任务分割表示将原始程序或应用分为几个程序段，以便稍后将它们分配至各个处理器上 . 粗粒度分割是指分配至各个处理器的程序段体积较大. 细粒度分割那么是指程序段的体积较小。 程序段可以是不同的软件进程或者是线程 .由程序员或者编译器决定分割方式 . 程序 员或者操作系统必须要确保子任务的同步执行以保证程序的正确性和数据的完整性.1.5 并行算法和并行体系结构并行算法和并行体系结构是紧密结合在一起的。在思考并行算法的时候必须要考虑到支撑这个算法的并行 硬件系统。同时，在设计一个并行硬件系统

24、的时候也不能不考虑在其上运行的并行算法.并行计算在一个计算机系统上的实现的层次是不同的，可以通过硬件实现、也可以由软件来实现。数据级并行是指同时对数据的多个位或者多个数据进行运算，例如位并行加法和二进制除法， 向量处理器阵列以及处理多份数据样本的脉动阵列都属于数据级并行。数据级并行是本书的主题。(1) 指令级并行(ILP)是指处理器同时执行多条指令，例如指令流水线的应用。(2) 线程级并行(TLP)。线程是程序的一局部，线程之间共享处理器资源。有些时候线程也被称为轻量级进程。TLP是指由一个或者多个处理器同时执行某个软件的多个线程(3) 进程级并行。进程就是指计算机正在执行的程序。一个进程会占

25、有特定的计算机资源，例如专用的内存空间和存放器。 通常意义的进程级并行就是指多任务处理或者分时计算系统，即在一台或者多台计算机上同时运行几个程序1.6 并行算法和并行体系结构相关概念IEEE 电子工程名词标准词典里将软件的“并行定义为:“分别使用独立的设备，并且在同一时刻转移、产生或者处理构成一个整体的几个独立局部，例如构成一个字符的每一位，或者构成一个字的每一个字符。在 此定义之下，假设一个算法的某些步骤可以分别由不同的硬件同时处理， 我们就可以说此算法是并行的。 定义并 行算法的时候已经默认了存在支持并行算法运行的硬件环境， 这同时说明软件的并行化与执行这个软件代码的 硬件是密不可分的。

26、软件的并行通过使用不同的线程或者进程来实现， 而并行基于硬件的实现那么是通过使用不 同的处理器。当代码中岀现 FOR或者WHILE这类的关键词的时候，能很快得岀此算法可以并行的结论。IEEE电子工程名词标准词典里对于“并行体系结构的定义如下：可以执行并行处理的多处理器结构 。为多个处理器分配任务以保证系统高效率工作是程序员和编译器以及操作系统的职责。在如下领域中我们可以找到许多并行算法的实例 :科学计算领域中的物理仿真，微积分公式求解，风洞测试模拟。计算机图形学领域中的图像处理，视频压缩，以及光线跟踪。医学成像领域中的核磁共振成像 (MRI)以及计算机断层 x线扫描术(CT). 在很多领域，特

27、别是在信息技术领域中，包括在线医疗数据检索、网上银行业务、数据挖掘、数据仓库以及数 据库检索系统中并行算法并没有得到充分应用。通过开发来提升IT 应用的计算机体系结构和软件是当前面临的诸多挑战之一。1.7 算法的实现：两个方面问题图 1.6 展示了本书将探讨的一些问题， 左侧表示算法空间， 右侧表示执行算法的并行体系结构空间 .路径 A 表示的情况如下 :一个具体算法，要满足预期的性能并考虑系统的限制，需要为实现此算法寻求合理的硬 件结构或者处理器阵列。此时的问题简而言之就是为给定的并行算法寻求可行的并行硬件体系结构。路径 B 表示如下一种常见的情况 :并行体系结构或者多核系统是的，要解决的问

28、题是在满足预期的性 能并考虑系统限制的条件下， 为并行算法的实现寻求最优解。 简而言之就是在一个给定的体系结构中研究如何 将并行算法的任务合理地分配至处理器端。这需要程序员、编译器与操作系统一起来解决此问题， 它涉及多线程并行编程技术。不管是选择路径 A 还是 B 都需要解决以下问题 :(1) 将子任务映射至不同的处理器。(2) 遵循算法的数据依赖关系和数据的 I/O 要求，合理调度子任务的执行顺序。(3) 识别 I/O 接口和处理器之间的数据交换。1.8 衡量并行计算的优势本节回忆一下之前的一些重要结论， 列举使用并行计算带来的好处。 但首先要讨论一些用于定量分析的重 要指标。衡量一个并行计

29、算是否优秀的一个重要标准是比照某个任务在单处理器和N 个并行多处理器上的执行时间。N个并行处理器的加速比 S(N)可以定义为：其中Tp(i)表示单处理器系统运行算法的时间，Tp(N)表示多处理器系统运行算法的时间 .理想条件下，忽略处理器和内存之前的通信时间，在一个完全并行化的算法中Tp(N)=Tp (1)/N ，那么上述等式变为 ：但在现实情况中很难得到这样的结果，原因会在以后的章节中说明.无论是并行系统还是单处理器系统，计算数据的读取和写人都是不可防止的步骤.内存的通信开梢是由于处理器和内存之间的信息交换速度的不对称。此外，在并行系统中处理卷之间也有大显数据交换，例如在内部网络中的信息交换

30、和数据的转移.处理器之间的通信主要有如下几点困难需要克服：1内部网络延迟：通过内部互联网络发送数据会产生位传播延迟，数据发送延迟，以及内部队列等待延迟。 影响内部网络延迟的因素有网络拓扑结构，数据的大小，以及网络响应速度等。2 内存带宽限制：无论内存有多大，内存的数据交换和访问只能通过某一个单独的接口.而且一次只能处理一 个字的读或者写操作。3内存冲突：当两个以上的处理器同时访问同一个内存模块时会造成内存冲突。需要一个仲裁机制来决定在 此种情况下由哪一个处理器优先获取访问权限。4 内存墙：由于内存的读写速度远小于处理器的速度，内存墙便诞生了。 解决此问题的方法是使用多级内存, 例如如下结构：存

31、放器-高速缓存器-RAM-电子磁盘-磁盘-光盘在并行处理器系统上运行一个并行算法时我们将会遇见多种延迟，详见表1. 1.N个处理器执行，在此种理.而不会岀现处理器之间的数假设某并行算法有N个独立的子任务，每个子任务都同时可以被一个或想条件下，由于每个子任务都是相对独立的，数据只需在处理器和内存之间交换 据交换理想条件下可以得出如下等式单个处理器读取算法愉人数据所需时间为此等式中.m表示内存访问某个数据块所需要的时间。假设上述等式中的每个子任务都需要输人一个数据块，N个子任务需要输人 N个数据块，那么并行处理器从内存中读取数据的时间可以表示为：表示共享内存受限访问因子。当每个处理器都拥有一份自己

32、需要的数侧备份时，:=1/N.当由主存模块以此为每个子任务分配数据时? =1.在最坏的情况下? >N，此时每个处理器都需要从共享内存中读取数据，从而产生了内存冲突可以把上述内容总结为：假设处理器试图访问同一组内存模块时，将结果写回内存也有可能发生冲突对单一处理器而言，完成一个任务所需的时间包括内存通信时间开销表示如下：考虑到通信开销的加速比计算等式如下：内存不匹配比R的定义如下：R表示从内存读取一个数据块的延迟和处理一个数据块的延迟的比位.根据子任务的粒以及内存读写的速度不同，p应比m小几个数量级。还可以将等式1. 17用N和R表示为：图1.7展示了以N和R为参考量，在 =1的情况下加速

33、比的变化情况。数学模拟结果显示的变化对结果并无显着影响。由以上等式可知，在RN<<1的情况下可以得到最大的加速比，此结果与等式1. 7中忽略通信开销的结论相符合。此种情况发生时我们就称此算法是一个平凡并行算法，将在第7章详细讨论.注意在RN>O. 1时加速比开始迅速下降.当R=1时岀现了通信边界问题，井行化的优势也消失了。这提醒我们内存系统的设计和处理器之间的通信问题是很重要的。第3章还会讨论多核处理器.由于多核处理器将处理单元都染成在一块芯片上，相比于跨芯片的多处理器系统，多核处理器的处理单元之间的通信速率拐到了大辐提升。在多核系统中Tm减小了几个数量级，R值也大幅减小。考

34、虑内存的读写时间，多核处理器间的通信开销表示如下：其中一：?=0，由内存系统和算法决定 .1 =0时表示单处理器系统，处理器之间无数据交换。在某些算法中p的值可能等于log2 N甚至等于N,其原因可能是程序员在编程时完全没有考虑到处理器之间的通信问题。1.9 针对多处理器系统的 Amdahl 法那么假设一个算法或者一个任务由可并行局部 f 和串行局部 1-f 组成，由单一处理器完成这个算法的所需时间那么是 : 等式的第一个局部的右手部 (RHS表示处理器完成串行局部所需的时间。等式的第二个局部的RHS表示完成并行局部的所需时间。假设有 N 个并行处理器来处理此任务，所需时间表示为 :可以将算法

35、的并行局部分配到N个处理器上来实现提速。在Amdahl法那么中，使用N个处理器时的加速比 S(N)表示为 :由此不等式可以看岀，假设要加速某个算法的执行，并行局部f需要十分接近1,特别是在N很大的时候。图1.8中展示了加速比与 N和f的关系。实线表示 f=0. 99,虚线表示f=0. 9，点线表示f=0. 5.可以从这三条 曲线看岀，加速比受f值的影响；同预期的一样，f值越接近1加速比越大；f>O. 5时加速效果更加显着；随着N值 变大，加速比的曲线也趋于饱和。当N值足够大时，等式(1.23)中的加速比可以表示为：由上式可以看岀，假设系统的处理器数目大于 10时，加速比的提升主要依核于能

36、挖掘岀多少程序中的可并 行局部，以及能同时执行多少子任务。图 1.8 证实了这些假设。在 f 取得极限值时，等式 (1. 23)变形为 ： 式的推导过程很简单。在程序完全并行时加速比等于并行处理器的数目。我们能从上述等式中得到什么结论?首先，应该知道或者大致知道给定算法的f 值，知道 f 值可以预测一个多处理器系统的加速比。此外f值也可以帮助我们判断如何将算法映射到多处理器系统上。1.10 Gustafson-Barsis 法那么根据 Amdahl 法那么得岀的加速比值是比拟悲观的，因为在 Amdahl 法那么中可并行化局部 f 的值是固定不变 的，但是 Gustafson 的观测结果表示随着

37、问题规模的增长一个应用的并行度也在增长。为了推导岀 Gustafson-Barsis 公式，首先计算一个任务在 N 个并行处理器上完成的时间为： 假设此任务在单处理器系统上处理完成，其串行局部所需时间不变，并行局部相应改变： 加速比为：图1.9展示了加速比与 f和N的对应关系.实线表示f=0. 99，虚线表示f=0. 9，点线表示f=0.5。从图中可以 看岀即使f的值很小，加速效果依旧很明显；加速比随着N的提高而提高。为了得到加速效果，需满足 ：f(N-1)>>1需注意假设 f 的值很小而 N 的值很大， 加速效果依旧明显 .相比于等式 (1. 24) , Gustafson-ba

38、rsis 公式对加速比 的条件限制比拟宽松 .1.11 并行计算的应用廉价而且强大的并行计算技术的岀现， 将为人们的生活带来无法预见的重大影响。 搜索引擎的技术就是并 行计算的一种应用。 实际上当人们输人关键词的时候搜索已经开始进行了。并行计算技术仍有很大的提升空间，而且有很多可以创新的应用领域。本节将详述这些应用。气象模拟用来预测天气变化， 也用于预测人类活动和各类现象对全球气候的影响。有文献表示现阶段气象模拟的解析度是 200km。然而有许多气象系统的规模要小于200km,因此迫切需要提高解析度。假设有一个高精度的气象模拟模型，将地球划分为无数个1km3 的独立的 3D 单元.地球的外表积

39、大约是510X106 km2，大气的厚度大约是 1000km。我们需要模拟大约 5X 1011个独立的3D气象单元。假设每个单元需要 在一次迭代模拟计算中完成 200 次浮点运算，进行一次迭代计算总计要完成1014次浮点运算操作。假设完成一个完整周期的气象模拟需要做性能需求 ：运算操作总数=1014次运算/每次迭代X106次迭代=1020浮点运算操作(1.32)使用一台每秒能完成 109次浮点运算(FLOPS的计算机来完成上述的计算内容需要1011秒，约等于31个世纪。假设要在一天内完成上述运算，需要系统的性能到达2.8 X 1015FLOPS很显然单处理器计算机无法到达这样的性能要求 .我们

40、需要将计算任务分配至第 3 章 并行计算机3.1 概述算法和多处理器架构相互之间是紧密联系的。 在考虑并行算法的时候不能脱离将要支持这个算法的并行硬 件。反过来，在考虑并行硬件的时候也不能脱离将要运行于其上的并行算法。计算机系统中可以通过硬件和软件的手段在不同的层次实现并行 :(1) 数据级并行，在这一层我们对一个数据的多个位或多个数据同时进行操作。例如位并行加法，乘法， 以及二进制数的除法，向量处理器和处理多数据单元的脉动式阵列(2) 指令级并行(ILP)，在这一层我们在处理器中同时执行多个指令。例如指令流水线的使用。(3) 线程级并行(TLP),线程是程序的一局部，它与其他线程共享处理器资

41、源。线程有时也被称为一个轻量 级的进程。在 TLP中，多个软件线程在一个处理器或多个处理器上同时被执行。(4) 进程级并行。进程是一个在计算机中正在运行的程序。一个进程保存着其拥有的 计算机资源，如内存空间和存放器。当然，这是典型的多任务和分时计算，其中多个程序同 时运行在共享的一台计算机或几台计算机上。3.2 并行计算本节试图说明可用于构建并行计算机系统的不同方案。最着名的处理器分类方式是由弗林基于数据及其被执行的操作而提出的 :(1) 单指令单数据流(SISD)o这是单处理器的情况。(2) 单指令多数据流(SIMD)的。所有的处理器在不同的数据上执行相同的指令。每个处理器都在本地内存存储它

42、自己的数据， 它们之间通过典型的简单通信机制进行数据交换。许多科学和工程应用程序使用这种并行处理机制，这种应用的例子包括图形处理、视频压缩、医学影像分析等。多指令单数据流(MISD)。神经网络和数据流机是这种并行处理器的例子。(4) 多指令多数据流 (MIMD) 。每个处理器在其本地数据上运行各自的指令。这种并行处理器的例子通常来 说就是多核处理器和多线程多处理器。弗林的分类有点粗糙，而且我们还希望在并行计算机中更加详细地探索包括SIMD和MIMD在内的其他领域.处理器之间的同步问题并不在弗林分类标准的考虑范围内。本章将讨论最常用的并行计算机体系结构，而 不是探索其他分类机制。应该指出，上述最

43、后一种处理器类型正在迅速成为一个流行的处理系统:共享内存多处理器。分布式内存多处理器。SIMD 处理器。脉动式处理器。集群什算。网格运算 多核处理器。流多处理器 (SM)3.3 共享内存的多处理器(统一内存访问 UMA )共享内存处理器的流行是由于简单和通用的编程模型， 它使得支持共享代码和数据的并行软件开发变得简单，共享内存处理器的另一个名字是并行随机访问机(PRA M).共享内存或共享地址空间作为处理器之间的一种通信方式。共享内存架构中的所有处理器可以通过互联网络访问一个公用内存的相同地址空间。如图3. 1(a)所示 .通常情况下，这个互联网络是一种总线。似是对于更大的系统来说，网络取代了

44、总线以提高性能.我们所说的性能是指在单位时间内进行的处理器 /内存访问次数 (吞吐址 )，以及从处理器请求内存访问到该 请求被允许之间的时延 (延迟 ).互联网络类型及其性能分析可在文献 28中找到。可以直观地看到， 内存带宽成为系统瓶颈， 因为在一个给定的时问内只能有一个处理器访问内存。 要解决 这个问题，图3. 1(h)的配置用互联网络替代了总线，它允许多个处理器同时访问网络。这种配置还使用多个内 存取代单个内存模块。这使得多个内存读/写操作可以同时发生。共享内存系统以及一般并行计算机的另一个常见问题是缓存一致性，共享内存中的任何信息必须和不同CPU上的本地缓存中的所有副本保持一致。缓存一

45、致性协议用于确保处理器之间的缓存一致性。在共享内存多处理器中， 任何处理器可以访问任何内存模块。 图3.1(b)显示了共享内存多处理器架构 .多个 内存模块允许多个处理器同时访问多个内存模块 .这当然增加了受互连网络限制和内存冲突影响的内存带宽 .内 存冲突在多于一个的处理器试图访问相同的内存模块时发生。任何内存模块设计面临的主要问题是， 它通常只有一个访问端日。所以，无论内存模块有多大、只有一个数据字节可以在任意时间内被访问.在共享内存多处理器中， 每个处理器都认为只有一个内存地址空间并且访问任何内存模块花费相同的时间 这被称为 UMA 多处理器系统 .在许多共享内存多处理器中， 互联网络是

46、一个简单的总线 .这就是两个以及四个奔 腾处理器时的情况。开发共享内存的多处理器并行程序不是太困难， 因为所有的内存读操作对于程序员是不可见的，并且能够以小行程序一样的方式进行编写 .相对来说，写指令的编程更加困难，因为这个操作需要锁定数据访问直到某 些线程完成对数据的处理。程序员必须识别出程序中的临界区、并引人进程间和线程间的同步机制以确保数据的完整性。诸如POSIX 的编程库和诸如OpenMP 的指令通过屏障、锁、监听、互斥和信号量来支持同步。在共享内存多处理器系统中遇到的一个问题是缓存一致性。通常情况下， 处理器在其自己的高速缓存中留有一个在内存模块中的数据副本。现在，如果另一个处理器改

47、变了内存模块中这个块的内容，那么缓存中的内 容就过时了。这时缓存更新政策必须被执行，以确保所有处理器中高速缓存内的副本得到更新。同步也必须被执行， 以确保多个处理器读写数据不产生冲突。 信号量， 互斥体和监听被用来确保数据的完 整性。第 4 章对共享内存处理器有更详细的讨论。3.4 分布式内存多处理器(非统一内存访问 NUMA )在分布式内存多处理器中， 每个内存模块和一个处理器关联在一起， 如图 3. 2 所示。 任何处理器可以直接 访问它自己的内存。 消息传递(MP)机制用于允许一个处理器访问与其他处理器关联的内存模块。消息传递接口(MPI)是一种与语言无关的通信协议。从这个意义上说， 处

48、理器的内存访问不是统一的， 因为它取决于处理器正试图访问哪个内存模块。这被称为 NUMA 多处理器系统。如果分布式内存多处理器是由相同的处理器组成的，那么是一个对称多处理器 (SMP)；如果内存的分布式多处理器是由异构的处理器组成的，那么是一个非对称多处理器(ASMP)。当分布式内存多处理器的互联网络是全球性的，如互联网， 那么这个分布式内存系统通常是由成千上万台计算机集合而成，以合作解决庞大的科学问题，并且这个系统被称内不同的名字，如大规模并行计算、分布式 计算、网格计算等。3.5 SIMD 处理器SIMD可以被归类为一个单一程序多数据流的特殊情况(SPMD)°SIMD处理器属于共

49、享内存多处理系统或分布式内存多处理系统。使用共享内存建立的SIMD，适用于需要频繁交换数据的应用程序，其中一个处理器作为新的数据的生产者，许多其他的处理器作为数据的消费者。每个处理器与其他处理器同步执行相同的任务。 正在执行的任务可能是一个简单的指令、 一个线程或进程。 在处理器之间分布内存可以减少内存带宽问题。许多应用程序应用了 SIMD 处理模型 .只要应用程序是可并行的。这些应用包括生物信息学、 生物医学诊断、流体力学、图像处理、视频处理等。SIMT)能够I着提高应用程序的性能。有些计算机制造商在它们的处理器中参加SIMT)扩展，并且可以运行现有的程序而不需要重新编译。同样地一些容易学习

50、的编程标准也利用了SIMT)架构.例如英特尔C+并行探测编译器。适用干 SIMD 的共享内存模型的一个例子 .是以下方程所描述的递归滤波器其中a(j)和a(j)是滤波器系数，N是滤波器的阶数或长度。请注意.在上面的方程中 b(0)=0。所有的处理器实现上述方程(单指令/程序).但作用于不同的输入数据。处理器 i将负责生产过滤器的输岀采样y(i)并且其他N个处理器可能需要在各自的计算中读取这个值 .当算法的粒度很粗糙时.SIMD机器将被称为SPMD机。3.6 脉动式处理器许多作者认为脉动式处理器属于流水线系统。而事实上.流水线处理是脉动式处理的一个特殊情况。正如我们在第 2 章中看到的 .流水线

51、是一维的 .并且数据流是单向的。一个典型的管道在相邻阶段之间传输数据。脉动阵列可以是一维、二维或是不维的。如果有必要 处理器之间沿着一个或多个方向流动。在流水线系统中 所有的处理单元(PE)通常执行相同的任务。一般来说 .PE 之间的互连模式是从邻点到邻点的.甚至可以是更高维度的。数据沿一个或多个方向在相邻的.每个流水线阶段执行不同的任务。在脉动式处理器中.可能还有一些全局互连。每个 PE 有一个小容量的内存来存储数据和中间结果。脉动架构适合实施数据依赖简单的高度规那么的算法。这些算法包括(1) 线性代数 .矩阵矩阵和矩阵向量乘法 .求解线性方程组。(2) 字符串搜索和模式匹配。(3) 数字滤

52、波器 .例如一维、二维和三维数字滤波器。(4) 在视频数据压缩中的运动估计。(5) 有限域运算 . 如椭圆曲线运算。图 3. 3 显示了一个用于实现矩阵一矩阵乘法算法的简单 SIMD 处理器的例子。 从图中可以看到 .矩阵系数是 以分布式内存的方式被存储在PE上的。我们也看到.处理器之间的通信是从邻点到邻点的。正如垂直箭头所示。并且使用全局布线 .如水平线所示。输入数据必须是主要提供给左边缘上的处理器。输岀数据从处于顶部的处 理器获得。与脉动式架构相关的设计问题有以下几种 :(1) 脉动式处理器旨在实现一个特定的算法。它必须重新设计以实现不同的算法。即使在实施相同的算法 时.问题规模的改变可能

53、需要对系统进行大量的重新设计。(2) 提供大量输入数据给多个处理器对系统输入/输岀(I/O)的带宽是个严重的制约。在一维脉动处理器中.输入通常是先送到一个处理器再经过流水线传输到其他处理器。在其他时间.输人是通过播送总线送到PE或PE阵列的一个边缘的所有PE。这会把脉动式处理器的性能变成受I/O影响的。廉价磁盘冗余阵列(RAID)可以提供一个高内存带宽的大规模存储。这个理念可以应用到闪存而非磁盘。(3) 从多个处理器获取大量的输岀数据对系统I/O 带宽是一个严重的制约。 输岀可以从一个处理器 .从连接所有处理器的总线.或从一个PE阵列的一个边缘获得。RAID可提供高内存带宽的大规模存储。在我们

54、离开本节前 .有必要比拟一下脉动式处理器和 SIMD 处理器 .因为外表上看 .这两种类型的处理器都在 多个数据上执行单一指令。表 3. 1 从架构、内存和任务粒度相关的不同方面比拟了SIMD 和脉动阵列处理器。3.7 集群计算计算机集群是一组两个或两个以上的计算机用于执行给定问题或代码段。通常情况下， 在计算集群中，将 计算机连接在一起的是一个局域网络(LAN)。图3. 4显示了一个集群计算机系统的体系结构集群中的计算机在彼此之间以及共享内存之间通信。因此，集群中处理器的通信主要通过局域网数据包。局域网通常架设在能够支持处理器之间的高速流量的效劳器计算机上。 共享内存必须能够在同一时间与多个

55、处理器通信。根据共享的内存大小，它可以使用 RAID 实现。客户机在集群的处理器之间分配任务并且收集结果。3.8 网格计算(云计算)网格计算是指为用户提供使用分布在广域网(WAN)上的计算资源的效劳。 从这个意义上说.网格计算机是一个分布在广阔的地理区域的大量处理器的集合。网格计算处理的计算任务规模较大.如 N 体模拟、地震模拟、大气和海洋模拟。相对于集群计算。网格计算机是一个大的集群.其中 LAN 被诸如 Internet 的 WAN 取代。本章后面的习题总结了集群计算和云计算之问的主要区别。一些使用云计算实现的应用包括对等(P2P)计算。作为效劳的软件 .像 Google App,Goog

56、le Calendar 和 Google Mail.海量存储。 Web 应用程序和社交网络。3.9 多核系统多核系统通常是指所有处理器都在同一芯片上的多处理器系统。它也可以指处理器在不同的芯片上。但 在同一个封装内 (即一个多芯片模块 )的系统。这种紧密的封装保证了较快的处理器间通信。同时保持了较低的 功耗。对于双核或四核系统， 处理器通信使用一条简单的总线。 对于更多数量的核心 .处理器使用片上网络 (NOC) 进行互连。另一方面，多处理器系统的处理器分布在不同的芯片上.并目 .处理器间互连依靠的是底板总线。继续研究并且得到一种每个芯片都是多核心芯片的多处理器系统是可能的。多核系统的开发主要是为了提高系统的性能同时限制其功耗。换句话说.即使其组成核心是低性能处理器 .多核系统仍具有良好的性能表现。相比之下.多处理器系统的开发提高了系统性能.却很少考虑功耗。一个多处理器系统具有良好的性能并且使组成的处理器也是高性能的。表 3. 2 总结了多核系统与多处理器系统的主要区别。图 3. 5 显示了多核处理器的草图。一个多核系统由以下局部组成(1) 通用的可编程核心。(2) 特殊用途的加速核心。(3) 共享内存模