第十六章 并行算法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第十六章 并行算法,并行处理技术就是只把一个处理任务分配给多个处理器同时处理，这样可以使得在一个时刻计算机的计算量增加,n,倍。为并行处理所涉及的计算机称为并行计算机，随着网络的发展，我们可以利用网络上各个点的资源联合进行分布式计算。所谓分布式计算是一门计算机科学，它研究如何把一个需要非常巨大的计算能力才能解决的问题分成许多小的部分，然后把这些部分分配给许多计算机进行处理，最后把这些计算结果综合起来得到最终的结果。,2024/10/4,1,第十六章 并行算法,目录,16.1,并行计算机,16.2,并行算法的基本概念,16.3,并行算法的描述,16.4 SIMD-SM,上的非线性方程求根同步并行算法,16.5 SIMD-SM,上的同步并行求和算法,16.6 SIMD-CC,超立方机器上的同步并行求和算法,16.7 MIMD-SM,上的异步并行求和算法,2024/10/4,2,16.1,并行计算机,串行机和并行机都是依据指令对数据进行操作，,Flynn,分类法就是根据指令流和数据流的个数将计算机分为,4,类：,(1),单指令流单数据流（,Single Instruction,Stream,Single,Data Stream,），简写成,SISD,，它是指单指令流对单数据流进行操作；,(2),多指令流单数据流（,Multiple Instruction,Stream,Single,Data Stream,），简写成,MISD,它有很多个处理器，但是由一个控制部件管理，一个数据流被传送给一组处理器，通过处理器上不同指令操作最终得到处理结果；,(3),单指令流多数据流（,Single Instruction Stream, Multiple Data Stream,），简写成,SIMD,，是指多个处理器接收不同的指令对相同数据进行操作 ；,(4),多指令流多数据流（,Multiple Instruction Stream, Multiple Data Stream,），简写成,MIMD,，它使用多个控制器来异步地控制多个处理器，从而实现空间上的并行性 。,2024/10/4,3,16.1,并行计算机,MIMD,与,SIMD,计算机的区别 ：,SIMD,计算机中每台处理器只能执行中央处理器的指令，而,MIMD,计算机中每台处理器只是接受中央处理器分配的任务，每台处理器各自执行自己的指令，从而达到空间上的并行性。,图,16.1,、,16.2,、,16.3,、,16.4,分别依次表示了,SISD,、,MISD,、,SIMD,和,MIMD,的结构情况。,控制器,处理器,存储器,指令流,数据流,图,16.1 SISD,2024/10/4,4,16.1,并行计算机,控制器,1,控制器,2,控制器,3,处理器,1,存储器,处理器,2,指令流,处理器,3,指令流,指令流,数据流,图,16.2 MISD,2024/10/4,5,16.1,并行计算机,控制器,处理器,1,处理器,2,处理器,n,数据流,1,数据流,n,数据流,2,公共存储器,指令流,图,16.3 SIMD,2024/10/4,6,16.1,并行计算机,控制器,1,控制器,2,控制器,n,处理器,1,处理器,2,处理器,n,公共存储器,指令流,1,指令流,2,指令流,n,数据流,1,数据流,2,数据流,n,图,16.4 MIMD,2024/10/4,7,16.1,并行计算机,根据,Flynn,分类法，并行计算机主要分为,SIMD,和,MIMD,两类。,SIMD,模型还可细分为给予共享存储的,SIMD,模型和基于互连网络的,SIMD,模型。,MIMD,模型也可细分为基于共享存储的,MIMD,模型和基于异步通信的互连网络模型。,SIMD,共享存储型的每个处理器都是有独立算术运算能力和逻辑判断能力的，然后每个处理器之间的信息交流都是通过一个共享存储器，比如处理器,i,要送一个数据给处理器,j,，那么首先要把该数据写到存储器上的某个地址，处理器,j,再从这个地址中读这个数据，但是因为共享存储器的容量是有限的，如果在同一时刻，多个处理器一起访问同一处理单元时就会发生冲突，所以共享存储模型根据解决冲突的能力还可以分为,3,类：,(1)EREW(Exclusive-Read Exclusive-Write),即不允许有两个处理器同时读或写一个共享单元；,2024/10/4,8,16.1,并行计算机,(2),CRCW(Concurrent,-Read Exclusive-Write),可允许同时读，但不允许同时写，即允许两个处理器同时读一个共享单元，但只允许一个处理器写某个共享单元；,(3),ERCW(Exclusive,-Read Concurrent -Write),不允许同时读，但允许同时写；,(4),CRCW(Concurrent,-Read Concurrent -Write),允许同时读和同时写；,共享存储的,MIMD,计算模型中所有的处理器也是共享一个公共的存储器，处理器之间的信息交流也是通过公共存储器来完成的。,在基于互连网络的,MIMD,计算模型中，每个处理器都各自有自己的存储器的（数据都是来自各自的存储器的），信息是通过互连网络进行交流的，在这种模型上设计的算法与互连网络的拓扑结构有关，我们介绍几种比较常见的拓扑结构。,2024/10/4,9,16.1,并行计算机,1,、一维线性结构,这是最简单的连接方式，其中,N,个处理器用,N-1,条链路连成一行，每个处理器只与其左右紧邻的处理相连接。如图,16.5,所示：,2,、二维网格结构,处理器之间按二维阵列形式排列，每个处理器仅与,4,个相邻处理器连接，,16,个处理器，相应的二维网格结构如图,16.6,图,16.5,一维线性结构,2024/10/4,10,16.1,并行计算机,二维网格结构是一种常用的并行机，特别适用于处理二维问题。,图,16.6,二维网格结构,2024/10/4,11,16.1,并行计算机,3,、超立方连接结构,一般来说，一个,n-,立方体由,N=2n,个结点组成，它们分布在,n,维上，每维有两个结点，特别地，当,n=3,时就是人们所熟悉的立方体。处理器在按照超立方体结构连接时要以下式方式连接：当处理器,i,个处理器,j,有线连接时当且仅当,i,与,j,的二进制表示中仅一位不同。,4-,立方体可通过将,2,个,3-,立方体的相应结点互连组成，如图,16.7,。,图,16.7,超立方连接结构,2024/10/4,12,16.1,并行计算机,4,、树形连接方式,二叉树具有很多优良性质，树形连接方式就是利用二叉树这种常用的数据结构组织而成的，一颗,4,层,15,个结点的树形连接方式结构如图,16.8,。,图,16.8,树形连接方式,2024/10/4,13,16.1,并行计算机,5,、洗牌,-,交换连接方式,洗牌,-,交换是一种非常有用的互连网络，假设,N=2n,，交换置换实现二进制地址编号中第,0,位位填不同的输入端和输出端之间的连接，其表达式为：,EX,（,xn-1xn-2x1x0,）,= xn-1xn-2x1,洗牌置换是将输入端分成数目相等的两半，前一半和都一般按序一个隔一个地从头至尾一次与输出端相连，其表达式为：,SH,（,xn-1xn-2x1x0,）,= xn-2x1x0 xn-1,图,16.9,为处理器数,N=8,的洗牌,-,交换万罗，其中虚线表示置换，实线表示洗牌。,0,1,2,3,4,5,6,7,图,16.9,处理器数,N=8,的洗牌,-,交换,返回目录,2024/10/4,14,16.2,并行算法的基本概念,并行算法就是在某类可以同时执行,n,个进程的并行计算机上求解问题，并且这些进程之间可以互相交换信息，从而可以更快地完成某个问题的求解。,可以从不同的角度将并行算法分为数值算法和非数值算法，,SIMD,并行算法和,MIMD,并行算法等等。,数值并行算法是指基于代数运算的一类计算问题的求解算法，如矩阵运算、多项式求值等等。,非数值并行算法是指基于关系运算的一类计算问题的求解算法，如排序、搜索等。,算法复杂性和算法的评价 ：,并行算法可以用不同的标准度量，对我们来说最主要的是算法与求解问题规模之间的关系，所以对于并行算法除了研究运行时间还要研究执行该算法所需的处理器的数目。,2024/10/4,15,16.2,并行算法的基本概念,设,T,是运行时间，,n,是处理器的规模，那么,T,与,n,之间的关系为,T=,T(n,).,其中,T,包含了两部分的时间，其中一部分是指通信时间，即处理器之间通过互联网络传递消息到达目的地的时间。消息很可能由于通信链路被占用而需要等待较长的时间，但我们通常假设处理器之间的通信可以在,O(1),的时间内完成，还有一部分的时间为数据在处理器进行运算的时间，就是通常所说的算法的运行时间。,性能指标,1,、并行算法的代价,C,（,n,）,并行算法的代价定义为并行算法的运算时间,T,（,n,）与并行算法所需的处理器数目,P,（,n,）的乘积，即,C,（,n,）,=T,（,n,）,P,（,n,）,它相当于在最坏情况下求解一个问题所有,P,（,n,）台所执行的总的运行时间。如果在该并行算法的执行代价的数量级为最坏情况下床性求解此问题的所需的运行时间，那么称这样的并行算法为代价最优的并行算法。,2024/10/4,16,16.2,并行算法的基本概念,2,、加速比,Sp,（,n,）,假设,Ts,（,n,）是最快是串行算法在最坏情况下的执行时间，,Tp,（,n,）为并行算法在最坏情况下的运行时间，那么加速比可以定义为,Sp,（,n,）,= Ts,（,n,）,/,Tp,（,n,）,Sp,（,n,）表示并行算法对求解该问题的运行时间的改进程度，,Sp,（,n,）越大表示并行算法越好。在理想的情况下，用,P,（,n,）台处理器去并行求解问题等于用一台处理器求解同一个问题乘以,P,（,n,）台。事实上，这两者之间是不可能相等的，这其中有很多因素，比如说在进行并行算法过程中数据需要经过一个互连网络才能到达另一个处理器，在经过互连网络时会消耗掉一部分的时间，因此,T,（,n,）,P,（,n,）,Ts,（,n,），,从而有,1 Sp,（,n,）,P,（,n,）,2024/10/4,17,16.2,并行算法的基本概念,3,、并行算法的效率,Ep,（,n,）,并行算法的效率可以定义为算法的加速比与处理器数目之比，即,Ep,（,n,）,= Sp,（,n,）,/P,（,n,）,0,Ep,（,n,）,1,并行算法有好的加速比不一定该处理器的利用率就很高，特别是在处理器数目不固定的情况下，因此并行算法的加速比不能很好地反应出处理器的利用率。所以人们引入了并行算法效率的概念，,Ep,（,n,）可以反应出处理器的利用率。,当,Ep,（,n,）,=1,时，则,Sp,（,n,）,=P,（,n,），,说明每台处理器都得到了充分的发挥，所以次并行算法的串行模拟为最佳串行算法，事实上,Ep,（,n,）,=1,几乎是不可能的。,返回目录,2024/10/4,18,16.3,并行算法的描述,并行算法的算法描述与串行算法一样，但是并行算法除了可以使用串行算法的语句、函数和过程调用以外，还引入了并行操作特有的并行执行语句。,（,1,）,do step i to step j in parallel,begin,step i;,step i+1;,step j;,end,此语句表示编号为,i,，,i+1,，,，,j,的处理器并行地执行算法步骤,step i,，,step i+1,，,，,step j,。,2024/10/4,19,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,结点的消息,M,后就执行相应的操作。,（,4,）,send M message to k,此语句表示执行结点把消息,M,传送给,k,。,（,3,）（,4,）两个语句是描述互连网络模型中并行算法的通信功能。,返回目录,2024/10/4,20,16.4 SIMD-SM,上的非线性方程求根同步并行算法,日常生活中存在着一些计算量非常大的数值计算问题（例如天气预报问题），这种计算问题无法在串行机器上很快地得出结果，我们只有把这种计算问题应用在并行计算机上才有可能在较短的时间内获得满足实际应用的需要。本小节我们主要介绍在,SIMD-SM,机器上的非线性方程求根同步并行算法。,在科学领域内，人们时常会遇到求解,f(x,)=0,（,1.1,）,求解等计算题。像这类问题，我们无法对大部分方程精确求解，而只能使用近似算法来求解。,我们可以把方程（,1.1,）的根解释成函数,f(x,),的图像和,x,轴的交点。,f(x,),的图像和,x,轴的交点可以有一个、多个甚至无穷多个，或者是没有交点。,平分法算法 ：,1),如果一个连续函数的图像在,a,点和,b,点上取到的函数值符号相反，那么该函数在这两点之间至少要和,x,轴相交一次；,2024/10/4,21,16.4 SIMD-SM,上的非线性方程求根同步并行算法,2),开始的时候有一个区间,a1,b1,，在其端点上，,f(x,),的符号相反；,3),计算,f(x,),在中点,c1=(a1+b1)/2,上的值 ；,若,f(c1)=0,，则,c1,为方程,f(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,|=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,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,2024/10/4,23,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),返回目录,2024/10/4,24,16.5 SIMD-SM,上的同步并行求和算法,因为,SIMD-SM,共享存储器的的容量是有限的，如果在同一时刻，多个处理器一起访问同一处理单元时就会发生冲突，所以共享存储模型根据解决冲突的能力还可以分为,3,类，其中的一类,EREW(Exclusive,-Read Exclusive-Write),计算模型是不允许有两个处理器同时读或写一个共享单，但是现实中我们又需要同时处理同一存储单元的数据，所以我们必须解决这个问题。,SIMD-SM,上的同步并行求和算法的过程中要用到一个数据播送算法。假设在,p,个处理器上要同时处理共享存储器的同一单元的数据,X,，以下是在,SIMD-SM,共享存储器中这样解决读写冲突的算法：,2024/10/4,25,16.5 SIMD-SM,上的同步并行求和算法,算法,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,。,2024/10/4,26,16.5 SIMD-SM,上的同步并行求和算法,根据算法,16.2,解这一例题的具体过程如下：,（,1,）首先定义一个长度为,8,的共享存储数组,A,，它的初始值为空，然后将处理器,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,2024/10/4,27,16.5 SIMD-SM,上的同步并行求和算法,在,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),。,2024/10/4,28,16.5 SIMD-SM,上的同步并行求和算法,例,16.2,假设,n=8,原始数据为,X=1,3,5,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,。,2024/10/4,29,16.5 SIMD-SM,上的同步并行求和算法,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,上。,返回目录,2024/10/4,30,16.6 SIMD-CC,超立方机器上的同步并行求和算法,假设在,n-,维超立方模型上，,n=2,m,n,个原始数据为,X=x0,，,x1,，,，,xn-1,，其中,m,为正整数，每个处理器,Pi,都可以存储局部变量,ai,，下面在此模型上构造一个并行求和算法，使得算法结束时,a0,就是总和 。,对超立方体节点用二进制进行编号，要求每相邻的结点之间只有且仅有一位不同。然后将这些结点分为两类，一类是最高位的编号为,0,，则另一类是最高位的编号为,1,，然后可以利用超立方模型中结点相邻关系可建立二类处理器集合中元素的一一对应关系，然后可以根据这种对应关系构造并行算法。,算法的思想是：,（,1,）对于,n,个处理器，首先将最最高位编号为,1,的处理器的数据传送至最高位编号为,0,的处理器并进行局部求和；,2024/10/4,31,16.6 SIMD-CC,超立方机器上的同步并行求和算法,（,2,）接着在,n/2,个处理器上，将次高位编号为,1,的处理器上的数据传送至次高位编号为,0,的处理器并惊醒局部求和；,（,3,）然后在,n/4,个处理器上，再将此次高位编号为,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,1,2,3,4,5,6,7,8,9,7,2,3,4,5,9,6,图,16.10,（,a,）,2024/10/4,32,16.6 SIMD-CC,超立方机器上的同步并行求和算法,10,9,5,7,9,11,16,14,图,16.10,（,b,）,2024/10/4,33,16.6 SIMD-CC,超立方机器上的同步并行求和算法,19,20,21,21,图,16.10,（,c,）,2024/10/4,34,16.6 SIMD-CC,超立方机器上的同步并行求和算法,40,41,图,16.10,（,d,）,返回目录,2024/10/4,35,16.7 MIMD-SM,上的异步并行求和算法,假设共享存储器多处理机系统有,P,个处理器，其编号为,P1,，,P2,，,，,Pp-1,由一个全局变量,total-sum,存储数据的总和，每个处理器,Pi,分配一个并发进程都有各自的局部变量,local-sum,，该局部变量是用来存储部分数据的子和，然后将所求得的,local-sum,加到全局变量,total-sum,中。,很明显可以看出此算法存在存储冲突。假如说当一个进程把所求得的部分数据子和,local-sum,加到全局变量,total-sum,中时有另一个进程也要把部分的数据子和加进去，那么就会产生资源冲突，这种冲突会很频繁的发生，因为全局变量总和的相加操作需要异步进行。,我们通常所用的解决冲突的办法是当要访问全局变量时先首先对它进行加锁，使得其他进程无法同时使用这个资源，当访问结束后立即解锁以免耽误其他进程对其进行的操作。,MIMD-SM,机器上的异步并行求和其实是一个进程和,P,个并发子进程组成，每个子进程分别求出分配给他的,n/p,个数据的子和。,2024/10/4,36,16.7 MIMD-SM,上的异步并行求和算法,算法,16.5 MIMD-SM,机器上的异步并行求和算法,begin /,开始主进程,total_sum,=0;,for i=1 to p do in parallel,begin,sub_sum(i,local_sum,);,lock(total_sum,); /,对全局变量,total_sum,加锁,total _sum= total _,sum+local_sum,;,unlock(total_sum,);,end,end,procedure,sub_sum(i,local_sum,) /,并发子进程,begin,local_sum,=0,；,for j=i to n step p do,local_sum,=,local_sum+xj,;,return,local_sum,;,end,2024/10/4,37,16.7 MIMD-SM,上的异步并行求和算法,上述算法在最坏情况下的运算时间，该运算时间有以下几部分组成：,（,1,）生成进程所需要的时间：生成,p,个子进程需要时间为,O(p,);,（,2,）局部求和所需要的时间：每个子进程都需要对,n/p,个数据求和，所以局部求和时间为,O(n/p,);,（,3,）求取总和所需要的时间：因为在任何一个时间只能由一个进程执行总和的操作，相当于,p,个处理器串行地对全局变量,total-sum,进行加锁、解锁操作，所以需要的时间为,O(p,);,（,4,）进程同步所需要的时间：进程是异步并行执行的，所以在最坏情况下,p,个并发进程同步结束需要的时间为,O(p,),。,因此上述算法在最坏情况下的运算时间为，执行代价为：,C(n,)=,P(n)T(n,)=,pO(n/p+p,)=O(n+p,2,),返回目录,2024/10/4,38,