第十六章 并行算法.ppt

1、2020/7/24,1,第十六章 并行算法,并行处理技术就是只把一个处理任务分配给多个处理器同时处理，这样可以使得在一个时刻计算机的计算量增加n倍。为并行处理所涉及的计算机称为并行计算机，随着网络的发展，我们可以利用网络上各个点的资源联合进行分布式计算。所谓分布式计算是一门计算机科学，它研究如何把一个需要非常巨大的计算能力才能解决的问题分成许多小的部分，然后把这些部分分配给许多计算机进行处理，最后把这些计算结果综合起来得到最终的结果。,2020/7/24,2,第十六章 并行算法,目录 16.1 并行计算机 16.2 并行算法的基本概念 16.3 并行算法的描述 16.4 SIMD-SM上的非线

2、性方程求根同步并行算法 16.5 SIMD-SM上的同步并行求和算法 16.6 SIMD-CC超立方机器上的同步并行求和算法 16.7 MIMD-SM上的异步并行求和算法,2020/7/24,3,16.1 并行计算机,串行机和并行机都是依据指令对数据进行操作，Flynn分类法就是根据指令流和数据流的个数将计算机分为4类： (1) 单指令流单数据流（Single Instruction Stream,Single Data Stream），简写成SISD，它是指单指令流对单数据流进行操作； (2) 多指令流单数据流（Multiple Instruction Stream,Single Data

3、Stream），简写成MISD,它有很多个处理器，但是由一个控制部件管理，一个数据流被传送给一组处理器，通过处理器上不同指令操作最终得到处理结果； (3) 单指令流多数据流（Single Instruction Stream, Multiple Data Stream），简写成SIMD，是指多个处理器接收不同的指令对相同数据进行操作 ； (4) 多指令流多数据流（Multiple Instruction Stream, Multiple Data Stream），简写成MIMD ，它使用多个控制器来异步地控制多个处理器，从而实现空间上的并行性 。,2020/7/24,4,16.1 并行计算机,

4、MIMD与SIMD计算机的区别 ： SIMD计算机中每台处理器只能执行中央处理器的指令，而MIMD计算机中每台处理器只是接受中央处理器分配的任务，每台处理器各自执行自己的指令，从而达到空间上的并行性。 图16.1、16.2、16.3、16.4分别依次表示了SISD、MISD、SIMD和MIMD的结构情况。,图16.1 SISD,2020/7/24,5,16.1 并行计算机,图16.2 MISD,2020/7/24,6,16.1 并行计算机,图16.3 SIMD,2020/7/24,7,16.1 并行计算机,图16.4 MIMD,2020/7/24,8,16.1 并行计算机,根据Flynn分类法

5、，并行计算机主要分为SIMD和MIMD两类。 SIMD模型还可细分为给予共享存储的SIMD模型和基于互连网络的SIMD模型。 MIMD模型也可细分为基于共享存储的MIMD模型和基于异步通信的互连网络模型。 SIMD共享存储型的每个处理器都是有独立算术运算能力和逻辑判断能力的，然后每个处理器之间的信息交流都是通过一个共享存储器，比如处理器i要送一个数据给处理器j，那么首先要把该数据写到存储器上的某个地址，处理器j再从这个地址中读这个数据，但是因为共享存储器的容量是有限的，如果在同一时刻，多个处理器一起访问同一处理单元时就会发生冲突，所以共享存储模型根据解决冲突的能力还可以分为3类： (1)ERE

6、W(Exclusive-Read Exclusive-Write),即不允许有两个处理器同时读或写一个共享单元；,2020/7/24,9,16.1 并行计算机,(2) CRCW(Concurrent-Read Exclusive-Write) 可允许同时读，但不允许同时写，即允许两个处理器同时读一个共享单元，但只允许一个处理器写某个共享单元； (3) ERCW(Exclusive -Read Concurrent -Write)不允许同时读，但允许同时写； (4) CRCW(Concurrent -Read Concurrent -Write)允许同时读和同时写； 共享存储的MIMD计算模型中

7、所有的处理器也是共享一个公共的存储器，处理器之间的信息交流也是通过公共存储器来完成的。 在基于互连网络的MIMD计算模型中，每个处理器都各自有自己的存储器的（数据都是来自各自的存储器的），信息是通过互连网络进行交流的，在这种模型上设计的算法与互连网络的拓扑结构有关，我们介绍几种比较常见的拓扑结构。,2020/7/24,10,16.1 并行计算机,1、一维线性结构 这是最简单的连接方式，其中N个处理器用N-1条链路连成一行，每个处理器只与其左右紧邻的处理相连接。如图16.5所示： 2、二维网格结构 处理器之间按二维阵列形式排列，每个处理器仅与4个相邻处理器连接，16个处理器，相应的二维网格结构如

8、图16.6,图16.5 一维线性结构,2020/7/24,11,16.1 并行计算机,二维网格结构是一种常用的并行机，特别适用于处理二维问题。,图16.6 二维网格结构,2020/7/24,12,16.1 并行计算机,3、超立方连接结构 一般来说，一个n-立方体由N=2n个结点组成，它们分布在n维上，每维有两个结点，特别地，当n=3时就是人们所熟悉的立方体。处理器在按照超立方体结构连接时要以下式方式连接：当处理器i个处理器j有线连接时当且仅当i与j的二进制表示中仅一位不同。 4-立方体可通过将2个3-立方体的相应结点互连组成，如图16.7。,图16.7超立方连接结构,2020/7/24,13,

9、16.1 并行计算机,4、树形连接方式 二叉树具有很多优良性质，树形连接方式就是利用二叉树这种常用的数据结构组织而成的，一颗4层15个结点的树形连接方式结构如图16.8。,图16.8树形连接方式,2020/7/24,14,16.1 并行计算机,5、洗牌-交换连接方式 洗牌-交换是一种非常有用的互连网络，假设N=2n，交换置换实现二进制地址编号中第0位位填不同的输入端和输出端之间的连接，其表达式为： EX（xn-1xn-2x1x0）= xn-1xn-2x1 洗牌置换是将输入端分成数目相等的两半，前一半和都一般按序一个隔一个地从头至尾一次与输出端相连，其表达式为： SH（xn-1xn-2x1x0）

10、= xn-2x1x0 xn-1 图16.9为处理器数N=8的洗牌-交换万罗，其中虚线表示置换，实线表示洗牌。,图16.9 处理器数N=8的洗牌-交换,返回目录,2020/7/24,15,16.2 并行算法的基本概念,并行算法就是在某类可以同时执行n个进程的并行计算机上求解问题，并且这些进程之间可以互相交换信息，从而可以更快地完成某个问题的求解。 可以从不同的角度将并行算法分为数值算法和非数值算法，SIMD并行算法和MIMD并行算法等等。 数值并行算法是指基于代数运算的一类计算问题的求解算法，如矩阵运算、多项式求值等等。 非数值并行算法是指基于关系运算的一类计算问题的求解算法，如排序、搜索等。

11、算法复杂性和算法的评价 ： 并行算法可以用不同的标准度量，对我们来说最主要的是算法与求解问题规模之间的关系，所以对于并行算法除了研究运行时间还要研究执行该算法所需的处理器的数目。,2020/7/24,16,16.2 并行算法的基本概念,设T是运行时间，n是处理器的规模，那么T与n之间的关系为T=T(n).其中T包含了两部分的时间，其中一部分是指通信时间，即处理器之间通过互联网络传递消息到达目的地的时间。消息很可能由于通信链路被占用而需要等待较长的时间，但我们通常假设处理器之间的通信可以在O(1)的时间内完成，还有一部分的时间为数据在处理器进行运算的时间，就是通常所说的算法的运行时间。 性能指标

12、 1、并行算法的代价C（n） 并行算法的代价定义为并行算法的运算时间T（n）与并行算法所需的处理器数目P（n）的乘积，即 C（n）=T（n）P（n） 它相当于在最坏情况下求解一个问题所有P（n）台所执行的总的运行时间。如果在该并行算法的执行代价的数量级为最坏情况下床性求解此问题的所需的运行时间，那么称这样的并行算法为代价最优的并行算法。,2020/7/24,17,16.2 并行算法的基本概念,2、加速比Sp（n） 假设Ts（n）是最快是串行算法在最坏情况下的执行时间，Tp（n）为并行算法在最坏情况下的运行时间，那么加速比可以定义为 Sp（n）= Ts（n）/Tp（n） Sp（n）表示并行算法对

13、求解该问题的运行时间的改进程度，Sp（n）越大表示并行算法越好。在理想的情况下，用P（n）台处理器去并行求解问题等于用一台处理器求解同一个问题乘以P（n）台。事实上，这两者之间是不可能相等的，这其中有很多因素，比如说在进行并行算法过程中数据需要经过一个互连网络才能到达另一个处理器，在经过互连网络时会消耗掉一部分的时间，因此 T（n）P（n）Ts（n）， 从而有 1 Sp（n）P（n）,2020/7/24,18,16.2 并行算法的基本概念,3、并行算法的效率Ep（n） 并行算法的效率可以定义为算法的加速比与处理器数目之比，即 Ep（n）= Sp（n）/P（n） 0 Ep（n）1 并行算法有好的

14、加速比不一定该处理器的利用率就很高，特别是在处理器数目不固定的情况下，因此并行算法的加速比不能很好地反应出处理器的利用率。所以人们引入了并行算法效率的概念，Ep（n）可以反应出处理器的利用率。 当Ep（n）=1时，则Sp（n）=P（n）， 说明每台处理器都得到了充分的发挥，所以次并行算法的串行模拟为最佳串行算法，事实上Ep（n）=1几乎是不可能的。,返回目录,2020/7/24,19,16.3 并行算法的描述,并行算法的算法描述与串行算法一样，但是并行算法除了可以使用串行算法的语句、函数和过程调用以外，还引入了并行操作特有的并行执行语句。 （1）do step i to step j in p

15、arallel begin step i; step i+1; step j; end 此语句表示编号为i，i+1，j的处理器并行地执行算法步骤step i，step i+1，step j。,2020/7/24,20,16.3 并行算法的描述,（2）for i=j to k parallel do begin End 此语句的意思与（1）相似表示处理器i,i+1,，k并行地执行算法步骤begin end里的语句。这里的“rallel do”0也可以写成“do in parallel”。 （3）upon receiving M message from u do 此语句表示执行结点一旦收到来自u

16、结点的消息M后就执行相应的操作。 （4）send M message to k 此语句表示执行结点把消息M传送给k。 （3）（4）两个语句是描述互连网络模型中并行算法的通信功能。,返回目录,2020/7/24,21,16.4 SIMD-SM上的非线性方程求根同步并行算法,日常生活中存在着一些计算量非常大的数值计算问题（例如天气预报问题），这种计算问题无法在串行机器上很快地得出结果，我们只有把这种计算问题应用在并行计算机上才有可能在较短的时间内获得满足实际应用的需要。本小节我们主要介绍在SIMD-SM机器上的非线性方程求根同步并行算法。 在科学领域内，人们时常会遇到求解 f(x)=0 （1.1）

17、 求解等计算题。像这类问题，我们无法对大部分方程精确求解，而只能使用近似算法来求解。 我们可以把方程（1.1）的根解释成函数f(x)的图像和x轴的交点。f(x)的图像和x轴的交点可以有一个、多个甚至无穷多个，或者是没有交点。 平分法算法 ： 1) 如果一个连续函数的图像在a点和b点上取到的函数值符号相反，那么该函数在这两点之间至少要和x轴相交一次；,2020/7/24,22,16.4 SIMD-SM上的非线性方程求根同步并行算法,2) 开始的时候有一个区间a1,b1，在其端点上，f(x)的符号相反； 3) 计算f(x)在中点c1=(a1+b1)/2上的值 ； 若f(c1)=0，则c1为方程f(

18、x)=0的根 若f(a1)与f(c1)异号，即f(a1) f(c1)0，则令a2,b2=a1,c1; 若f(b1)与f(c1)异号，即f(b1) f(c1) 0，则令a2,b2=c1,b1。 4) 依次做下去，则发现f(cn)=0时，或区间an,bn足够小时，比如|an-bn|0.0001时，我们就认为找到了方程的根。 在SIMD-SM上实现 假设SIMD-SM共有P（n）个处理器，该并行算法地思想是： 1) 假设原始区间为a0,b0,首先将该区间分割成（P（n）+1）等份， 每个处理都并行地计算各个区间的两个端点的值; 2) 如果在a0,b0区间内确实含有函数的零值，那么在（P（n）+1）个

19、区间中肯定存在一个区间的两端点的值的乘积为小于等于零，然后再把这个区间分成（P（n）+1）等份; 3) 依次下去，直到找到函数值或者是包含这个根的区间小到预先设定好的范围，算法描述如下：,2020/7/24,23,16.4 SIMD-SM上的非线性方程求根同步并行算法,算法16.1 SIMD-SM上的非线性方程求根同步并行算法 begin while(a0 -b0)=c do begin s=(a0 -b0)/(p(n)+1)； y0=f(a); yp(n)+1=f(b); for i=1 to p(n) do in parallel begin yk=f(a+k*s); if(yk+1*yk

20、0) then begin a=a+(k-1)*s; b=a+k*s; end end; if(yp(n)*yp(n)+1 0) then a=a+ p(n)*s; end end,2020/7/24,24,16.4 SIMD-SM上的非线性方程求根同步并行算法,该并行算法的总迭代次数为O(log p(n)+1b0-a0)，因此该并行算法的复杂性为： T（n）= O(log p(n)+1b0-a0) 所以并行算法的执行代价为： C（n）=P(n)T(n) = O(P(n)*log p(n)+1b0-a0),返回目录,2020/7/24,25,16.5 SIMD-SM上的同步并行求和算法,因为S

21、IMD-SM共享存储器的的容量是有限的，如果在同一时刻，多个处理器一起访问同一处理单元时就会发生冲突，所以共享存储模型根据解决冲突的能力还可以分为3类，其中的一类EREW(Exclusive-Read Exclusive-Write)计算模型是不允许有两个处理器同时读或写一个共享单，但是现实中我们又需要同时处理同一存储单元的数据，所以我们必须解决这个问题。 SIMD-SM上的同步并行求和算法的过程中要用到一个数据播送算法。假设在p个处理器上要同时处理共享存储器的同一单元的数据X，以下是在SIMD-SM共享存储器中这样解决读写冲突的算法：,2020/7/24,26,16.5 SIMD-SM上的同

22、步并行求和算法,算法16.2 在SIMD-SM上的数据播送算法 begin 处理器P1读取X然后将X复制给共享存储器中的A1; for i=0 to log P-1 do for j=2i+1 to 2i+1 do in parallel 处理器Pj读取Aj-2i然后将其复制给共享存储里中的Aj; end 这个算法的时间复杂性为O(log p). 例16.1 假设有8个处理器要同时读取共享存储器中的某一存储单元数据100。,2020/7/24,27,16.5 SIMD-SM上的同步并行求和算法,根据算法16.2解这一例题的具体过程如下： （1）首先定义一个长度为8的共享存储数组A，它的初始值为

23、空，然后将处理器P1读取数据100并将100写入到A1中； （2）接着，让处理器P2读取数组A1中的数据然后将其写入A2中； （3）然后，处理器P3和P4分别并行地读取数据A1和A2并将其写入A3A4中； （4）之后，处理器P5、P6、P7、P8分别并行地读取数据A1 、 A2 、A3、 A4并将其写入 A5、 A6、 A7、 A8 中。 P1 P2 P3 P4 P5 P6 P7 P8 A1 A2 A3 A4 A5 A6 A7 A8 初始 100 步骤1 100 步骤2 100 100 步骤3 100 100 100 100,2020/7/24,28,16.5 SIMD-SM上的同步并行求和算

24、法,在SIMD-SM上的并行求和算法，它充分结合了数据播送算法思想和上次累加结果的思想来进行下次的并行累加求和操作。具体算法如算法16.3 算法16.3 在SIMD-SM上的并行求和算法 begin for i=0 to log n-1 do for j=2i+1 to n do in parallel begin 处理器Pj从共享存储器中读取Aj-2i; 处理器Pj执行Aj=Aj+Aj-2i; end end 从算法16.3可以看出这个算法的时间复杂性是O(log n)。,2020/7/24,29,16.5 SIMD-SM上的同步并行求和算法,例16.2 假设n=8,原始数据为X=1,3,5

25、,7,9,2,4,6,，试利用并行算法16.3求这8个数据的之和。 (1)首先将这8个数据放在共享存储数组A中。 (2)当第一层循i=0时，做第二层for循环j从2开始，当j=2时，P2从共享存储数组中读取A1,然后P2执行加法操作A2=A1+A2; (3)接着j=3时，P3从共享存储数组中读取A2，然后P3执行加法操作A3=A3+A2,依次执行下去，直到j=n。 (4)然后跳出第二层循环继续做第一层循环i=1，做第二层循环j=3，P3从共享存储器数组中读取A1,P3执行加法操作A3=A3+A1,然后j=4，P4做A4=A4+A2。,2020/7/24,30,16.5 SIMD-SM上的同步并

26、行求和算法,P1 P2 P3 P4 P5 P6 P7 P8 初始 1 3 5 7 9 2 4 6 步骤0 1 4 8 12 16 11 6 10 步骤1 1 4 9 16 24 23 22 21 步骤2 1 4 9 16 25 27 31 37 因此经过3步操作之后，既可以得到8个数据之和且存储在处理器P8上。,返回目录,2020/7/24,31,16.6 SIMD-CC超立方机器上的同步并行求和算法,假设在n-维超立方模型上，n=2m,n个原始数据为X=x0，x1，xn-1，其中m为正整数，每个处理器Pi都可以存储局部变量ai，下面在此模型上构造一个并行求和算法，使得算法结束时a0就是总和

27、。 对超立方体节点用二进制进行编号，要求每相邻的结点之间只有且仅有一位不同。然后将这些结点分为两类，一类是最高位的编号为0，则另一类是最高位的编号为1，然后可以利用超立方模型中结点相邻关系可建立二类处理器集合中元素的一一对应关系，然后可以根据这种对应关系构造并行算法。 算法的思想是： （1）对于n个处理器，首先将最最高位编号为1的处理器的数据传送至最高位编号为0的处理器并进行局部求和；,2020/7/24,32,16.6 SIMD-CC超立方机器上的同步并行求和算法,（2）接着在n/2个处理器上，将次高位编号为1的处理器上的数据传送至次高位编号为0的处理器并惊醒局部求和； （3）然后在n/4个

28、处理器上，再将此次高位编号为1的处理器上的数据传送至此次高位编号为0的处理器上并进行局部求和； （4）依次进行下去直到所有的总和结果存储在处理器P0上。 例16.3 设X=1，2，3，4，5，6，7，8，9，7，2，3，4，5，9，6，n=16，则在SIMD-CC机器上并行求取16个数据之和的过程如图16.10,图16.10（a）,2020/7/24,33,16.6 SIMD-CC超立方机器上的同步并行求和算法,图16.10（b）,2020/7/24,34,16.6 SIMD-CC超立方机器上的同步并行求和算法,图16.10（c）,2020/7/24,35,16.6 SIMD-CC超立方机器上的同步并行求和算法,图16.10（d）,返回目录,2020/7/24,36,16.7 MIMD-SM上的异步并行求和算法,假设共享存储器多处理机系统有P个处理器，其编号为P1，P2，Pp-1,由一个全局变量total-sum存储数据的总和，每个处理器Pi分配一个并发进程都有各自的局部变量local-sum，该局部变量是用来存储部分数据的子和，然后将所求得的local-sum加到全局变量total-sum中。 很明显可以看出此算法存在存储冲突。假如说当一个进程