并行算法与并行程序设计第02章 并行算法

第二章并行算法教师：彭四伟一、问题的并行性把有唯一输入向量和唯一输出向量的一个程序段在某一环境下的一次执行称为一个进程。设有一组程序段A1…An，若{Ai}在n个处理机上同时执行的结果等同于{Ai}以任意顺序执行的结果，则称{Ai}为可并行执行的。一、问题的并行性设两个程序段A、B，如果

(IA∩OB)∪(OA∩IB)∪(OA∩OB)≠Φ，

则称A和B数据相关，否则称之为数据无关。设两个语句L1和L2，如果

L1的执行结果能够决定L2是否执行，

则称L2控制相关于L1。一、问题的并行性设两个程序段A、B，且A先于B，若A与B数据相关或控制相关，则称A是B的父进程。父进程关系可以传递，称为祖先进程。记α(A,B)为A是B的父进程，αT即祖先进程关系。设某一程序P中的进程集合W，于是G=（W,α）可以构成一张图，称为进程流程图。A1：x=1A2：y=2A3：s=2*x+yA4：t=x*x*yA5：u=3*s-tA6：v=cos(t)A7：z=u*v+1如下例所示：u,vzA7tvA6s,tuA5x,ytA4x,ysA3yA2xA1输入输出进程输入输出表如下：A7A7A6A7A5A5，A6A4A5A3A3，A4A2A3，A4A1子进程父进程进程关系表如下：BeginA1A2A3A4A5A6A7End进程流程图如下：二、并行算法的性能指标对问题规模n，所动用的处理器的数目p(n)，运行时间或最坏运行时间tp(n)。粒度：并行单元的规模，通常将循环级及以下称为小粒度，子程序级称为大粒度。工作量Wp(n)：Wp(n)=tp(n)*p(n)，直观上即模拟该并行算法的串行算法的计算量。工作量越小，算法的性能越好。如果对同一问题，并行算法A与串行算法B的工作量同阶，称A对B工作量有效，若A对最坏情况下的最优算法B工作量有效，称A工作量有效。加速比Sp(n)：Sp(n)=ts(n)/tp(n)，其中ts(n)是解同一问题在最坏情况下的最优串行算法的运行时间。加速比反映运行时间的改进倍数。由于并行算法可以用串行算法来模拟，模拟的串行算法的运行时间不超过p(n)*tp(n)，所以有1≤Sp(n)≤p(n)。工作效率Ep(n)：Ep(n)=Sp(n)/p(n)，反映算法所占用的处理器的工作效率，即工作饱满程度。工作效率越高，算法的性能越好。由1≤Sp(n)≤p(n)，有1/p(n)≤Ep(n)≤1。三、并行求和倍增法求和倍增法是并行分治的一种简化形式。其基本思想是将原问题反复分解为等规模的两个子问题，在逐步分解的过程中，子问题个数成倍增加。将各个子问题恰当地映射到各台处理机上，即可实现计算过程的并行化。intPSum(intL[],ints,intt){if(s==t)returnL[s];intk=(s+t)/2;returnPSum(L,s,k)+PSum(L,k+1,t);}三、并行求和倍增法求和计算序列L[0..n-1]的和，记为S(0,n-1)。S(0,7)S(0,3)S(4,7)S(0,1)S(2,3)S(4,5)S(6,7)三、并行求和倍减法求和计算序列L[0..n-1]的和，记为S(0,n-1)。设可用处理器为n/2个。intPSum(intL[],intn){ k=n/2; while(k>0) { forallPii=0..k-1do { L[i]+=L[i+k]; } k/=2; } returnL[0];}四、平衡树法平衡树法的基本思想用一棵平衡二叉树组织并行计算，输入元素存放在叶结点，然后逐层并行地计算一直到根结点。四、平衡树法以求最大值问题为例计算序列L[0..n-1]中的最大值。不失一般性，设n=2m，A是一个大小为2n-1的数组，采用完全二叉树的存储结构，将序列分别存放到n个叶结点中，在树的同一层各结点上作并行计算，逐层递推，直到得到最终结果。fork=m-1to0doforallPii=0…2k-1doj2k-1+i;A[j]max(A[2*j+1],A[2*j+2]);四、平衡树法平衡树法的评估以平衡树法求解最大值是一个EREW算法，计算时间tp(n)=O(logn)，运用处理器最多为p(n)=n/2，工作量为O(nlogn)，不是工作量有效的算法。平衡树方法的优点是在树中能快速存取信息，对数据的传递、压缩、抽取和前缀计算均十分有用。五、向量法向量法的基本思想以向量方式描述计算过程；以并行方式执行向量计算。五、向量法以矩阵计算为例对n阶矩阵，串行加法的计算量为n2，若动用n个（或n2个）处理器，分别处理每行（或列）的相加运算，则可以得到计算量亦为n2，工作量有效。五、向量法以矩阵计算为例矩阵相乘：C=A*Bfori=1tondo forj=1tondo ci,j=0 fork=1tondo ci,j+=ai,k*bj,kfori=1tondo forallPjj=1tondo ci,j=0 //Ci.=0 fork=1tondo //Ci.=∑ai,k*Bk. forallPjj=1tondo ci,j+=ai,k*bk,j串行算法：并行算法：六、线性递推问题一般性线性递推问题对一个k阶，N式的线性递推式，

如下所示：x1= b1x2= a21x1+b2x3= a31x1+a32x2+b3x4= a41x1+a42x2+a43x3+b4……xN= aN1x1+aN2x2+…+aN,N-1xN-1+bN展开式如下：forallPkk=1…NdoS[k]=b[k];fori=2toN{ forallPkk=i…Ndo S[k]+=x[i-1]*a[k][i-1]; x[i]=S[i];}可得算法如下：六、线性递推问题一阶线性递推问题有一阶线性递推式如下：x1= b1x2= a2b1+b2x3= a3a2b1+a3b2+b3x4= a4a3a2b1+a4a3b2+a3b3+b4x5= a5a4a3a2b1+a5a4a3b2+a5a4b3+a5b4+b5x6= a6a5a4a3a2b1+a6a5a4a3b2+a6a5a4b3+a6a5b4+a6b5+b6x7= a7a6a5a4a3a2b1+a7a6a5a4a3b2+a7a6a5a4b3+a7a6a5b4+a7a6b5+a7b6+b7x8= a8a7a6a5a4a3a2b1+a8a7a6a5a4a3b2+a8a7a6a5a4b3+a8a7a6a5b4+a8a7a6b5+a8a7b6+a8b7+b8展开式如下：定义：则xi=Q(i,1)forallPkk=1…Ndo{ P[k]=a[k]; Q[k]=b[k];}for(L=1;L<N;L+=L){ forallPkk=1…Ndo if(k-L>=1) { C[k]=P[k]*Q[k-L]+Q[k]; Q[k]=C[k]; C[k]=P[k]*P[k-L]; P[k]=C[k]; }}可得并行算法如下：可推导得到：P(i,i-k+1)*Q(i-k,i-2k+1)+Q(i,i-k+1)=Q(i,i-2k+1)约定P(i,i+1)=1，aj=1(j≤1)，bj=0(j<1)设初始值：P[i]=P(i,i)=ai，Q[i]=Q(i,i)=bi设已知某一阶线性递推式的系数向量如下：a=(1,3,2,7,1,4,2,5)Tb=(2,1,9,3,2,4,6,3)T七、线性代数方程组高斯消去法for(k=1;i<N;i++){ for(j=k+1;j<=N+1;j++)A[k][j]/=A[k][k]; for(i=1;i<=N;i++) if(i!=k) for(j=k+1;j<=N+1;j++) A[i][j]-=A[i][k]*A[k][j];}串行求解算法：for(k=1;i<N;i++){ forallPjj=k…NdoA[k][j+1]/=A[k][k]; for(i=1;i<=N;i++) if(i!=k) forallPjj=k…Ndo A[i][j+1]-=A[i][k]*A[k][j+1];}并行求解算法：八、一元多项式的计算一元多项式的一般式八、一元多项式的计算一元多项式的串行最优解法PN(x)=((…(aNx+aN-1)x+aN-2)x+…+a1)x+a0X0=1 P0=a0X1=X0*x P1=P0+a1*X1X2=X1*x P2=P1+a2*X2......XN=XN-1*x PN=PN-1＋aN*XN八、一元多项式的计算并行解法作推导如下：令a(1)i=(a2i+a2i+1x)，可将关于x的多项式看作关于x2的多项式：不失一般性，设N+1=2μ，反复利用上述方法，可得：其中：由此得到并行计算步骤：第1步：第2步：第3步：…………第μ步：在并行计算过程中同时计算八、一元多项式的计算一阶线性递推解法Y0= anY1= x*Y0+an-1Y2= x*Y1+an-2……Yi= x*Yi-1+an-i……Yn= x*Yn-1+a0PN(x)=((…(aNx+aN-1)x+aN-2)x+…+a1)x+a0令xai，aibn-i，即得一阶线性递推公式，代入一阶线性递推算法即可。九、指针跳越技术指针跳越技术是设计关于静态链表快速操作并行算法的一个有力工具。012345678data-1925179861302215next5704832616117981519223025九、指针跳越技术表序问题已知n个元素，构成一个静态单链表，要求计算每个元素到表尾的距离d[i]，即计算：6117981519223025voidD(slistL,intd[],inti){ if(L[i].next==0) d[i]=0; else { D(L,d,L[i].next); d[i]=d[L[i].next]+1; }}串行递归算法描述如下：voidD(slistL,intd[]){ StackS;InitStack(S); for(inti=0;L[i].next!=0;i=L[i].next) Push(S,L[i].next); Pop(S,i); d[i]=0; while(!EmptyStack(S)) { Pop(S,j); d[j]=d[i]+1; i=j; }}串行非递归算法描述如下：九、指针跳越技术表序问题使用指针跳越技术，用n个处理器并行对n个元素进行处理。012345678data-1925179861302215next570483261P1P2P3P4P5P6P7P8forallPii=1…ndo if(next[i]==0)d[i]=0;elsed[i]=1;while(存在next[i]!=0){ forallPii=1…ndo if(next[i]!=0) { d[i]+=d[next[i]]; next[i]=next[next[i]]; }}算法描述如下：611798151922302511111110611798151922302576543210第三趟跳越611798151922302544443210第二趟跳越611798151922302522222210第一趟跳越12345678data1925179861302215next70483261d1011111122122202dnextdata720418061522306198172519876543211次跳越42144403dnextdata200167001522306198172519876543212次跳越42175603dnextdata000000001522306198172519876543213次跳越九、指针跳越技术指针跳越操作将破坏原有的链结构，因此在操作前应复制原链结构，在复制的链结构上进行跳越操作。可证明算法的正确性。在循环过程中，以每个元素为链头的子表中的d值之和，恰好等于该元素到表尾的距离。在指针跳越过程中，将越过的元素的d值累积到被操作元素上，以保证上述性质仍然成立。当元素没有后继元素时，其d值即是到表尾的距离值。注意：在对多个next指针进行更新时，要求读写操作保持同步，即读取next值的操作要先于任何next的写入操作。由于每次跳越将使一个子表被分裂成两个子表，因此计算时间为O(logn)。九、指针跳越技术表前缀的并行计算表前缀计算问题由一个二元可结合运算⊕来定义，对一个输入序列<x1…xn>，其输出是序列<y1…yn>，满足：y1=x1，且yk=yk-1⊕xk=x1⊕x2⊕…⊕xk,k=2,3,…,n即每一个yk是输入序列的前k个元素的“累积”。表序计算可以看作表前缀的一个特例（须先将表颠倒）。为描述方便，定义如下符号：[i,j]=xi⊕xi+1⊕…⊕xj，1≤i≤j≤n则有：[k,k]=xk，[i,k]=[i,j]⊕[j+1,k]，yk=[1,k]forallPii=1…ndo y[i]=x[i];while(存在next[i]!=0){ forallPii=1…ndo { if(next[i]!=0) { y[next[i]]=y[i]⊕y[next[i]]; next[i]=next[next[i]]; } }}并行算法描述如下：611798151922302511111111611798151922302512345678第三趟跳越611798151922302512344444第二趟跳越611798151922302512222222第一趟跳越九、指针跳越技术前缀运算中的循环终止条件的判断对已知表长n的情况下，循环步长不超过logn。对未知表长n的情况下，表头元素的循环步数最多，通过判断表头元素的next是否已变为0来作为循环的终止条件。可以通过O(1)的运算找到表头单元。forallPii=1…ndo{ h[i]=1; if(next[i]!=0)h[next[i]]=0; if(h[i]==1)head=I;}九、指针跳越技术应用举例中位元素定位查找链表中序号为K的元素。数组的前缀运算yk=yk-1⊕xk=x1⊕x2⊕…⊕xk蓝色链表问题链表中有红蓝两色的结点，将蓝色结点挑出组成一个新的链表。循环链表的标识问题在循环链表上应用指针跳越技术，如何标识跳越的结束状态。十、欧拉回路技术欧拉回路一个图的欧拉回路是指经过图中每条弧恰好一次的一条回路。一个有向强连通图有欧拉回路的充要条件是该图中每个结点的出度等于入度。无向连通图可以转换为有欧拉回路的有向强连通图。十、欧拉回路技术二叉树的欧拉回路构造构造思路通过对二叉树进行变形，构造欧拉回路；将每个结点分解为三个单链子结点A、B、C；令A为父结点入口，左子出口；令B为左子入口，右子出口；令C为右子入口，父结点出口；欧拉回路链的顺序为：A——左子树——B——右子树——C十、欧拉回路技术二叉树的欧拉回路构造构造规则若一个结点有左子，则令结点的A指向左子结点的A，否则令结点的A指向结点的B；若一个结点有右子，则令结点的B指向右子结点的A，否则令结点的B指向结点的C；若一个结点是父结点的左子，则令C指向父结点的B；若是父结点的右子，则令C指向父结点的C；根结点的C指向空；十、欧拉回路技术计算二叉树各结点的层次定义根结点为0层；定义子结点的层数为父结点的层数加1；0层1层2层3层十、欧拉回路技术计算二叉树各结点的层次利用欧拉回路计算先构造二叉树的欧拉回路；令各结点的A的初值为1，B的初值为0，C的初值为-1；对该链进行前缀加和运算；各结点C中所得到的结果即该结点的层次；A——左子树——B——右子树——C十、欧拉回路技术计算二叉树遍历序设A初值为1，B初值为0，C初值为0，

前缀计算后，A中即为前序的编号；设A初值为0，B初值为1，C初值为0，

前缀计算后，B中即为中序的编号；设A初值为0，B初值为0，C初值为1，

前缀计算后，C中即为后序的编号；根据欧拉回路链序：A——左子树——B——右子树——C十、欧拉回路技术计算二叉树上各结点为根的子树的规模根据欧拉回路链序：A——左子树——B——右子树——C在前序遍历序计算中，每个结点的C-A+1即子树规模；在中序和后序遍历序计算中，每个结点的C-A的值即子树规模；十、欧拉回路技术二叉树的蓝色链表问题设在一棵有n个结点的二叉树T中，某些结点标记为蓝色结点，将二叉树T中的所有没有蓝色祖先的蓝色结点连成一个链表。对蓝色元素初始化为A=1，B=0，C=-1；对红色元素初始化为：A=0，B=0，C=0；构造欧拉回路，进行前缀计算后，结点的C中为“蓝深度”，即蓝色祖先结点的个数。将所有有蓝色祖先的结点的颜色全改为红色，用链表的蓝色链算法剔除其中的无蓝色祖先的结点。十、欧拉回路技术多叉有序树的欧拉回路十一、MIMD算法算术表达式的同步MIMD算法例：(A+B(C+D*E*F))+G变形为：A+G+B*C+B*D*E*FP1P2P3P4a1=A+GP(r1)a1+=a2P(r3)a1+=a3a2=B*CV(r1)a3=B*DP(r2)a3*=a4V(r3)a4=E*FV(r2)十一、MIMD算法区间分割法解代数方程的根求单调连续函数f(x)=0的根。设已知两端l~u，对区间进行n+1等分，令y[0]=f(l)，y[n+1]=f(u)。lu…………十一、MIMD算法同步牛顿迭代法解代数方程的根迭代公式：P0P1while未达到精度{ y=f(x); wait(y’) x=x–y/y’;}while未达到精度{ wait(x) y’=f’(x);}并行进程如下：P0P1y0=f(x0)y0’=f’(x0)x1=x0–y0/y0’y1=f(x1)y1’=f’(x1)x2=x1-y1/y1’…………并行计算过程如下：十一、MIMD算法异步牛顿迭代法解代数方程的根P1P2While未达到精度{ y=f(x); x=x–y/y’;}While未达到精度{ y’=f’(x);}十二、MIMD算法异步枚举排序算法用n个进程并行计算各元素在排序后序列中的位置。i01234567X1593233819214T4891519213233十二、MIMI算法异步快速排序算法在快速排序过程中，每一步划分完成后，所得到的两个待排序子序列是相互独立的，可以创建两个并行进程分别对这两个子序列进行递归快速排序。intQSort(L,s,t){ if(s>=t)return0; k=Partition(L,s,t); QSort(L,s,k-1); QSort(L,k+1,t); return1;}十二、并行分治分治通过将一个问题分解成若干个性质相同的子问题，并递归地对子问题进行求解，然后将各子问题的解加以合并构造出原问题的解。分治步骤将问题的输入进行均匀划分，构成规模大致相等的若干个同类的子问题；递归求解各子问题；将各子问题的解归并成为原问题的解；十二、并行分治并行分治F(I){ if输入足够小then OAnswer(I); else {

分解输入：I1,…Ik；

forallPii=1…kdo Oi

F(Ii,Oi); OCombine(O1,…Ok); }}十二、并行分治最近点对问题d1d2d2d十三、划分法划分法与分治法相似，划分原理也是将原问题进行分解，分别求解，再归并子问题的解。所不同的是，分治法采用简单的分解方法，因此设计的难点在于如何归并子问题的解，而划分方法则讲究分解的方法，以获得简单的归并策略。十三、划分法有序序列归并设A=(a1,a2,…,an)，

B=(b1,b2,…,bm)，

是U上的单调增序列，且A∩B=Ф。

将A和B归并到：

C=(c1,c2,…,cm+n)。十三、划分法有序序列归并定义：对U上的有序序列列X=(x1,x2,…,xt)，x∈U，x在X上的位序rank(x:X)为X中小于等于x的元素个数。归并问题即求rank(x:A∪B)，x∈A∪B。分别求出rank(ai:B)和rank(bj:A)，即可得到rank(x:A∪B)=rank(x:A)+rank(x:B)。这样就可以在O(logn)时间内用O(nlogn)工作量完成合并的任务。但这样的解法不是一个工作量有效的算法。通过进一步划分，可以得到工作量有效的解法。十三、划分法有序序列归并可以在O(logn)的时间内将A和B划分成p对子序列(Ai,Bi)，i=0,1,…,p-1，

使得Ai和Bi中的每一个元素均大于Ai-1和Bi-1中的元素。

经过这样划分，合并问题就转化为子序列对（Ai,Bi）的合并问题了。Aa1…aj[1]aj[1]+1…aj[2]aj[2]+1…aj[3]……anBb1…bLbL+1…b2Lb2L+1…b3L……bmCPartition(A,B,n,m){ lm/p; j[0]0; j[p]n; forallPii=1…p-1do j[i]rank(bi*l:A); forallPii=0…p-1do { Bi

(bi*l+1,…,b(i+1)*l); Ai

(aj[i]+1,…,aj[i+1]); }}十四、流水线技术基本思想将一个计算任务t分成一系列连续子任务t1,t2,…,tm，使得一旦完成了子任务ti，其后继的子任务ti+1就可以立即开始，并以同样的速率进行计算。十四、流水线技术归并排序设输入长度为n=2r，用p(n)=r+1个处理器并行完全合并排序的任务。设处理器编号从1到r+1，其中首处理器有一个输入，尾处理器有一个输出，其他处理器各有两个输入和两个输出。各处理器同步运行，在一个时间步内，P1从原始输入序列中读取一个数并将其作为结果输出，Pi(i=2…r+1)接收从Pi-1输出的两个长度为2i-2的子序列，并将其合并为一个长度为2i-1的子序列。从P1到Pr，每一个处理器交替地在上面和下面两条输出线上产生合并子序列。除P1外，每个处理器Pi当其前一个处理器的一条输出线上已经产生了长为2i-2的子序列，另一条输出线上出现了第一个元素时，就可以开始归并了。设Pi和Pi+1之间通过的队列为q2i和q2i+1，即q2i和q2i+1是Pi的输出序列，Pi+1的输入序列。如下图所示：设n=2r，p(n)=r+1，算法描述如下：P1:j2;fork=1tondo{ xkq1; qjxk; j=5-j;}Pi:i=2…rj0;k1;whilek<=ndo{ ifq2(i-1)+j已装满2i-2个元素and q2(i-1)+(1-j)已出现1个元素then { form=1to2i-1do q2i+jmin(q2(i-1)+j,q2(i-1)+(1-j)); j1-j; kk+2i-1; }}Pr+1:ifq2r已装满2r-1个元素，且q2r+1已出现1个元素then{ form=1to2rdo q2(r+1)min(q2r,q2r+1);}十四、流水线技术排序问题每个进程一次从前一个进程接收待排序序列中的一个数，保存当前接受到的最大的数字，把比这个数小的其他数传给下一个进程。第一个进程P0直接从待排序序列接收数据。P0P1P2P3P44|3|1|2|512345P0P1P2P3P4-----4|3|1|2|55----4|3|1|25----4|3|1252---4|3152---431531--42542--315431-254321十四、流水线技术质数生成问题生成从2~n的所有质数。埃拉托色尼筛选法从2开始，依次删除2的所有倍数；对余下的每个数字重复这个过程；只须考察从2到n1/2的数即可；对被考察数i，只须测试i2~n的所有数即可；2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,202,3,5,7,9,11,13,15,17,192,3,5,7,11,13,17,19十四、流水线技术质数生成问题顺序解法for(i=2;i<=n;i++) prime[i]=1;for(i=0;i<=sqrt_n;i++) if(prime[i]==1) for(j=i*i;j<=n;j+=i) prime[j]=0;十四、流水线技术质数生成问题流水线解法第一个流水线级输入一系列连续的数，然后剔出所有2的倍数，并把余下的数传递给第二级流水线；第二级剔出所有3的倍数并把余下的数传递给第三级流水线；以此类推；流水线的个数与质数的个数的方根相同；P0P1P2xn-1,...,x1,x0数序列倍数比较第1个质数第2个质数第3个质数进行埃拉托色尼筛选的流水线：P0:x0

receive(X);while(!EOF(X)){ xreceive(X); if(x%x0!=0)send(P1,x);}Pi:xi

receive(Pi-1);while(!EOF(X)){ xreceive(Pi-1); if(x%xi!=0)send(Pi+1,x);}十五、接力技术基本思想让两种算法接力，产生一个求解该问题的新算法，使得既有耗时少的特性又有工作量有效性较高的特性。先用需要较少时间（速度较快）的算法求解给定的问题，直到问题的规模减到某一个阈值为止；再用工作量有效性较高的算法，继续求解，直到获得最终的解答。十五、接力技术求解最大值的常数时间算法对n个元素的数组，可以动用n2个处理器，在O(1)的时间内求解出最大值。A1A2A3mA1?F?FA2TTTTA3?F?FforallPii=1…ndo m[i]true;forallPi,ji=1…n,j=1…ndo if(A[i]<A[j])m[i]false;forallPii=1…ndo if(m[i]==true)maxA[i];十五、接力技术求解最大值的重对数时间算法设n个元素的序列，定义一棵以n个元素为叶结点的重对数深度平衡树如下：

树中每一个非叶子结点u的子结点的个数为以u为根的子树上的叶结点的个数的平方根。则第0层为树根，有一个结点，第1层为n1/2个结点，每个结点为根的子树上有n/n1/2=n1/2个叶子，所以每个结点有n1/4个子结点，可以证明，以第i层上每一个结点为根的子树上有个叶子结点，第i层上共有个结点，可知这样一棵树的高度为loglogn+1，因此称为重对数深度平衡树。在重对数深度平衡树上，除第0层外，对每一层按父结点分组，对每一组用常数时间算法求解最大值，结果放在其父结点中。可证明，共须n个处理器，经过loglogn+1个并行步完成计算，时间复杂度为O(loglogn)。216个叶子根28个结点，每个分28个叶结点28*24个结点，每个分24个叶结点28*24*22个结点，每个分22个叶结点28*24*22*2个结点，每个分2个叶结点十五、接力技术对数深度树和重对数深度树算法接力第一步，利用对数深度平衡树方法向上逐层进行计算，经过logloglogn层的选拔后停下来。第二步，以第一步选拔出的最大值候选结点为叶结点，按重对数时间算法进行继续计算，直到所求的解。第一步所需时间为O(logloglogn)，工作量为O(nlogloglogn)，在第一步结束时，剩下的结点数为：n’=n/2logloglogn=n/loglogn。则第二步需要的时间为O(loglogn’)=O(loglogn)，工作量为O(n’loglogn)=O(n)。从而进一步提高了工作量的有效性。十六、递归的并行随机消元法基本思想运用递归，且在递归的每一阶段用最短的时间，并随机地消去尽量多的元素，以迅速地压缩问题的规模，直到规模为0，递归不再深入，再返回并逐步拼接原问题的解。以前缀计算为例。十六、递归的并行随机消元法递归消元可以通过O(1)时间的操作将一个单链表改造成为一个双向链表。对于规模为n的双向链表，拟使用p个处理器，每个处理器负责处理链中的n/p个元素。先将n个元素任意地分配给各处理器，一经分配，归属关系在递归过程中不再改变。十六、递归的并行随机消元法递归消元第一步：消元各处理器按如下两条原则并行地消去表中的一些元素：

①每一个处理器每次最多消去它所管辖的一个元素；

②不同时消去当前表中相邻的两个元素。

在消去当前表中它所辖的一个元素之前，都要取出该元素及其下一个元素的前缀当前值作⊕运算，并用运算的结果更新下一个元素的前缀当前值，除非是表尾元素。十六、递归的并行随机消元法递归消元第二步：递归当第一步得到的新链表的长度不为0时，递归消元。第三步：回收各处理器并行地收回在第一步被自己消去的元素，接入递归返回的链表，然后取出该元素与其前一个元素的前缀当前值作⊕运算，并用运算的结果更新该元素的前缀当前值，除非是表首元素。PiNovnextP114[4,4]621[1,1]332[2,2]5P247[7,7]853[3,3]165[5,5]9P379[9,9]088[8,8]796[6,6]4[1,1][2,2][3,3][4,4][5,5][6,6][7,7][8,8][9,9][1,1][2,2][3,3][4,5][6,6][7,8][1,2][3,5][6,6][1,5]空表[1,5][1,2][1,5][1,6][1,1][1,2][1,3][1,5][1,6][1,8][1,1][1,2][1,3][1,4][1,5][1,6][1,7][1,8][1,9]P1P1P2P1P2P3P2P3P3十六、递归的并行随机消元法递归消元可见，在递归消元过程中，被消去元的前缀值累积到了后面的元素上；在递归返回时，回收的元素从前面的元素中获得了尚未被累积的前缀值。因此保证了在递归结束时，每个元素都获得了其前面的所有元素的前缀累积值。并行消元时的两条原则保证了消元过程中不会出现冲突，且消元和回收都可以在O(1)时间内完成。十六、递归的并行随机消元法选择待消元的方法在两条消元原则下，消去尽量多的元素，且耗费时间尽量少，最好是O(1)。因此可以采用随机消元法。方法如下：(1) 各处理器从所分管的元素中挑选一个未消去的元素作为候选元素；(2) 随机地（抛硬币）决定是否给该元素打一个标记；(3) 如果元素被标记，而元素next未标记，则消去该元素，否则不消去该元素；十六、递归的并行随机消元法算法分析在每一个递归步中，每个处理器以至少1/4的概率消去一个元素，对p个处理器，每个处理器分管n/p个元素，因此在高概率下，消元的期望时间为O(n/p)。则总工作量为O(n)。十七、确定性破对称技术基本概念破对称：打破并行操作的对称性，即避免两个处理器同时被分派对同一个单元进行处理或同时不被分派进行处理。前面的随机消元中的抛硬币方法就是一种不确定的破对称技术。确定性破对称技术：利用处理器的编号来打破对称性。例如前面的例子中，通过让下标较小的处理器先访问来打破对称性。十七、确定性破对称技术确定性破对称算法要求从静态链表中选出一部分元素，这部分元素在链表中两两不相邻，且数目是链表中元素总数的常分数倍。n个处理器和O(log*n)的计算时间，其中log*n定义为：log*x=min{i|log(i)x<=1,i>=0};log(i)x定义为：对1≤n≤265536，有0≤log*n≤5，因此对一般的实际应用，log*n是一个小常数。十七、确定性破对称技术确定性破对称算法确定性破对称算法分为两个部分：第一部分：在O(log*n)时间内给出链表的“6-着色”。第二部分：将6-着色转化为表的一个“极大独立集”，该极大独立集将至少包含链表中的n/3个元素，且这些元素中任何两个元素在链表中不相邻。十七、确定性破对称技术无向图着色与极大独立集无向图G=(V,E)的一个着色是一个映射Ｃ：ＶＮ，使得对所有u,v∈Ｖ，如果Ｃ(u)=C(v)，则(u,v)不属于Ｅ，即相邻点不同色。在链表上进行６-着色，可用的颜色号为{0,1,2,3,4,5}，且相邻元素不同色。虽然可以用O(logn)的时间并行地对链表进行2-着色，将奇、偶元素分别着以不同的颜色，但通常只要有一种O(1)的着色就可以了。下面的算法在O(log*n)的时间对n个元素的链表进行6-着色。十七、确定性破对称技术无向图着色与极大独立集G=(V,E)的一个独立集是其顶点集V的一个子集V’，使得E中的每条边最多只与V’中的一个顶点相关联。极大独立集是一个不能再并入其他任何顶点的独立集。最大独立集是图G的一个规模最大的独立集。求极大独立集是一个易解的问题，求最大独立集却是一个NP-完全问题。虽然对一个链表可以通过O(logn)时间分别标出奇偶点，从而得到两个最大独立集，但速度不够快。而只要我们能求得链表的极大独立集，则可知极大独立集中的元素个数不小于n/3（每三个元素中，至少有一个元素属于极大独立集）。十七、确定性破对称技术链表6-着色算法思想对链表中的每一个元素迭代地计算出一个着色序列C0[x],C1[x],…,Cm[x]。链表的初始着色C0是一个n-着色，每一次迭代产生一种新的着色，最后的着色Cm是一个6-着色。可以证明，m=log*n。初始着色C0可以定义为C0[x]=P(x)。每一种颜色的编号可通过logn个bit位来描述。十七、确定性破对称技术链表6-着色迭代规则设Ck用了r位表示每一种颜色，通过查看每个元素的相邻元素next[x]来确定新的颜色。设Ck[x]=a=<ar-1ar-2…a1a0>，

Ck[next[x]]=b=<br-1br-1…b1b0>，Ck[x]≠Ck[next[x]]，

因此必存在一个最小下标i，使得ai≠bi，0≤i≤r-1，

则i可以用logr个bit位表示。x的新颜色值定义为i与ai的连接，

令Ck+1[x]=<i,ai>=<ilogr-1ilogr-2…i0ai>，若x是表尾，则定义Ck+1[x]=<0,…0a0>。这样一来，新颜色的位数最多为logr+1位。ck[x]:01101101ck[next[x]]:10011001ck+1[x]:0101十七、确定性破对称技术链表6-着色迭代规则证明可以证明，Ck+1仍是一个合法的着色。对非表尾元素x，Ck[x]≠Ck[next[x]]，按Ck+1[x]的定义，设Ck+1[x]=<i,ai>，

Ck+1[next[x]]=<j,bj>，

若i≠j，则Ck+1[x]≠Ck+1[next[x]]；

若i=j，则必有ai≠bj，所以Ck+1[x]≠Ck+1[next[x]]。ck[x]:01101101ck[n