并行计算讲义

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

（2）观察结果显示，除非使用并行处理技术，一个程序在一台型号更新的单处理器计算机上的运行速度，可能比在旧的计算机上的运行速度更慢。

能依照给定算法检测出程序中的并行结构的编程工具还有待开发。

此算法需要能够检测出变ja之间的依赖关系是否规则;而且不管这些依赖是否规则，此算法都能在保证程序正确性的前提下，通过将程序中的一些子任务并行化来加速程序的执行。

（3）提升未来的计算机性能的关键就在于并行程序的开发，这涉及各个层面的工作:算法、程序开发、操作系统、编译器及硬件设备。

（4）并行计算除了要考虑到参与并行计算的处理器的数量，还应该考虑处理器与处理器、处理器与内存之间的通信。

最终计算性能的提升既依赖于算法能够提升的空间，更依赖于处理器执行算法的效率。

而通信性能的提升则依赖于处理器对数据的供应和提取的速度。

（5）内存系统的速度始终比处理器慢，而且由于一次只能进行单个字的读写操作，内存系统的带宽也有限制。

（6）内存系统的速度始终比处理器慢，而且由于一次只能进行单个字的读写操作，内存系统的带宽也有限制。

本书内容主要涉及并行算法与为了实现这些算法而设计的硬件结构。

硬件和软件是相互影响的，任何软件的最终运行环境是由处理器组成的底层硬件设备和相应的操作系统组成.我们在本章开始的部分会介绍一些概念，之后再来讨论为了实现这些概念有哪些方法和限制.1.2自动并行编程对于算法在软件中的实现过程我们都很熟悉。

在编程并不需要了解目标计算机系统的具体细节，因为编译器会处理这些细节.但是在编程和调试时依旧沿用着在单一央处理器(CPU)上顺序处理的模式.从另一方面讲，为了实现并行算法，硬件和软件之间的相互联系需要比我们想象的更加密切。

图1.1展示了基于软件和硬件、利用并行计算机来运行程序的主要步骤和层次。

从最顶层开始，第5层是指应用层，在这一层里描述的是需要并行计算平台实现的应用和问题。

对应所需的输入和输出的格式也在这层进行定义。

某些输人和输出((I/O)接口的描述还需要考虑数据存储的位置和时间相关性。

这一层的结果会被更低一层采纳以便指导并行算法的开发工作。

第4层是算法开发层，这里需要考虑到应用在问题中的实现。

需要应用实现的计算内容决定了算法的具体任务和任务之间的相互依赖关系(interdependence)。

在这一阶段，算法的并行性并不一定会显现出来，因为在探索算法子任务执行的时候仍然在运用传统的线性思考。

在这一阶段，也不需要考虑子任务的时间调度和处理器分配的问题。

可能在现阶段就将这些问题解决的做法看起来很诱人，但是这样做会适得其反，因为这会掩盖程序中潜在的并行性。

该层的结果是一个依赖图，或是一个有向图，或者是一个概括了任务之间依赖关系的临界矩阵。

第3层是并行化层，在这一层将试着释放算法中潜在的并行性。

这一层接收了第4层对算法的描述并且给出了基于软件实现的线程时间调度和处理器分配。

另一种选择是在这一层进行基于超大规模集成电路的硬件实现的任务调度和处理器分配。

本书内容主要集中在这一层上，在图1.1用灰色方形显示。

第2层是代码层，在本层中并行算法用高级语言表示为代码。

使用何种语言取决于目标并行计算在何种平台执行。

图1. 1中右侧的分支表示算法在通用并行计算平台上的实现过程。

这一做法即是我们所说的“并行编程”。

并行计算机程序由所谓的“并发平台”执行，此种平台帮助编程人员管理线程，处理处理器级别的任务执行时间调度。

并发平台包括Cilk++ ,OpenMP,CUDA(compute unified device architecture统一计算设备架构)。

图1. 1中左侧的分支表示并行算法在定制的硬件设备上的实现，例如脉动阵列计算机。

编程人员使用硬件描述语言(HDL )，例如Verilog,或者超高速集成电路硬件描述语言(VHDL)。

第1层的目标是算法的实现，或是在并行计算机平台的应用.实现的途径可以是在并行计算平台上使用多线程，也可以是在特定用途集成电路(ASIC)上或者现场可编程门阵列(FPGA)上使用特定的应用并行处理系统.那么并行计算机自动编程又是什么意思呢?现在我们已经可以进行线性计算机自动编程.程序员用像C,Java,FORTRAN这样的高级语言编写代码，这些代码可以被计算机自动编译，不需要程序员再去做进一步的工作。

更重要的是，程序员编程的时候也不需要了解底层计算平台的硬件细节.甚至在程序员完全不需要知道内存结构，也不知道CPU的信息和产他细节的情况下，代码就可以迅速地转化为结果。

上述的一切能用在并行编程上吗?我们需要的并行编译器要能找到简单环路和解决处理器的分配等问题.而且这种编译器还能轻松地解决现在被称为“让人尴尬的并行算法”(译注:也就是相对独立的可以完全并行执行的算法)的问题[2. 3]。

除此之外，程序员还需要对处理器之间的行为有着充分的了解，并且知道算法需要在何时执行。

1.2自动并行编程IEEE电子工程名词标准词典里对于“算法”一词的定义如下:为了描述在有限步骤内解决某一个问题而定义的过程或者规则。

一个算法的任务或者过程一般是独立的。

有些任务可以并发执行，但有些必须线性地按顺序进行.根据上述的定义，任何算法都是由并行和非并行两部分组成的。

除了某些极端的情况，很难定义某些算法是并行的而某些是完全串行的(即非并行)，后面将探讨如何量化一个算法的并行度。

如果某个算法由W个子任务组成，则称与这个算法有关的操作数是W.定义一个算法的基本组成部分如下:（1）不同的子任务。

（2）子任务之间的依赖关系。

当某一个子任务的输入是另一个子任务的输出时，他们之间则存在依赖关系。

（3）算法的初始输入集。

（4）算法的最终输出集。

我们通常用有向图(以下简称DG)来直观地表示算法的子任务之间的数据依赖关系。

DG 在描述算法的时候表示依赖图，需要用带箭头的线段强调子任务之间的数据流向关系.换句话说，如果一个依赖图的边没有箭头表示方向，就很难从图中得知数据的依赖关系。

定义1.1一个依赖图是边和结点的集合.结点表示算法的子任务，边表示子任务用到的数据.数据包括输人、输出和中间结果.需要注意的是，在一个依赖图中出现的不带箭头的边表示此边连接的两个结点之间没有数据依赖关系，它们只是共用算法中的某一个变量。

这个变量可以是输入、输出或者在算法中作为I\O媒介的中间结果。

定义1.2 DG是有向边和结点的集合。

结点表示算法需要处理的子任务，有向边表示子任务之间的数据依赖关系.一个子任务的输出在一条边的开端部分，箭头指向的一端表示一个子任务的输入。

定义1.3有向无环图(DAG )址指一个没有任何环路的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.8一个DG中的输出结点是指所有的出边都是输出边的结点。

图1.2中，可以看到结点7和9都表示输人结点。

但结点3不是输出结点，因为结点3的一条出边是指向结点7的内部边。

定义1.9一个DG中的内部结点是有至少一条人边和至少一条出边的结点。

1.3.2算法的邻接矩阵一个算法也可以用一个邻接矩阵A来表示。

若算法中有W个子任务，就有一个W×W阶的0-1矩阵来表示这个算法，其中a(i,j)=1表示结点i的输人依赖于结点j的输出，j是源结点而i是目标结点。

当a(i,j) = 0表示结点i的输入不依赖于节点j的输出。

对于任何0<=i<W，a(i，i)=0，因为我们假设在算法中没有输出指向自己的结点，这样一来也不会构成“自环”。

上述定义的邻接矩阵是非对称的，因为当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和结点9都是输出结点，这两列的元素也都用黑体显示。

其他行和列中都有超过1个非零元素，表明这些结点都是内部结点。

若结点i有元素a(i,j)=1则说结点J是结点i的母结点。

依据子任务的依赖关系可以大致将算法分为如下几类:(1)串行算法。

(2)并行算法。

(3)串行一并行算法(SPA).(4)非串行一并行算法(NSPA)(5)正则迭代算法(RIA)最后一类算法可以看做SPA的泛化。

值得一提的是，根据数据或者任务的粒度的不同，算法的分类也随之改变。

例如说，如果矩阵的元素相加是一项基本操作，求两个矩阵的和就可以看做是一个串行算法。

若另一台计算机上的基本操作是相关行列的相加，那我们的算法就变成了基于行列的并行算法。

另一项值得一提的事情是，一些算法的子任务可能会有不同类型的算法。

依旧可以用矩阵相加的运算来说明。

在并行计算机中两组相关行的计算可以同时在两个不同的处理器上执行。

但在每个处理器上相关行上的元素又是串行处理的，因此这个并行算法中就包含了行相加的串行算法。

稍后我们会详细讨论这些分类。

串行算法的特点是由于相互之间存在数据依赖关系，子任务必须一个一个地按顺序执行。

这一类算法的DG 是由一系列关联的子任务构成的队列图1. 3(a)展示了一个串行算法的DG 。

此类算法是用来计算斐波那契数列的。

为了得到n 10，子任务T 10进行了如下计算：n10=n8+n9 (1.4)在此n 0 = 1和n 1=1初始条件已经给出.很明显，为了得到某一位的斐波那契数只能依次计算在它之前的数。

并行算法的特点是由于相互之间不存在数据依赖关系，子任务可以同时并发执行。