并行计算讲义

《并行计算讲义》由会员分享，可在线阅读，更多相关《并行计算讲义（50页珍藏版）》请在金锄头文库上搜索。

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

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

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

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

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

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

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

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

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

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

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

12、。定义1.8 一个DG中的输岀结点是指所有的岀边都是输岀边的结点。图 1.2 中，可以看到结点 7 和 9 都表示输人结点。但结点 3 不是输出结点，因为结点 3 的一条出边是指 向结点 7 的内部边。定义1.9 一个DG中的内部结点是有至少一条人边和至少一条岀边的结点。1.3.2 算法的邻接矩阵一个算法也可以用一个邻接矩阵A来表示。若算法中有 W个子任务，就有一个 W X W阶的0-1矩阵来表示这个算法，其中a(i,j)=1表示结点i的输人依赖于结点j的输岀，j是源结点而i是目标结点。当a(i,j) = 0表示 结点i的输入不依赖于节点 j的输岀。对于任何 0=iW，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)展示了一个串行算法的DG。此类算法是用来计算斐波那契数列的。为了得到 ng,子任务Tio进行了如下计算：n 10=n8+n9(1.4)在此no = 1和ni=1初始条件已经给岀.很明显，为了得到某一位的斐波那契数只能依次计算在它之前的数。并行算法的特点是由于相互之间不存在数据依赖关系，子任务可以同时并发执行。此类算法的DG就像是许多独立的子任务组成的一组任务，相互之间没有联系。图1. 3(b)展示了一个并行算法的 DG, Web服务器上的数据处理应用就是一种简单的并行算法，每一次数据请求都被看做独立的任务交给不同的处理器来响应.同时运行浏览器，字处理程序等多个程序时操作系统的多任务调度算法也是一种并行算法。1.