94MIMD共享存储模型的并行算法

19.4MIMD共享存储模型的并行算法（一）异步枚举排序算法枚举排序(EnumerationSort)是一种最简单的排序算法，通常也称为秩排序(RankSort)。对于基于枚举比较原理的异步排序算法，为了排序n个数的序列S=(x1,x2,…,xn)，算法要生成n个进程。进程i(1≤i≤n)将xi与S中其余元素进行比较，并且使用局部变量k及下所有小于xi的元素的数目。当所有的比较都完成时，就将xi置入排序序列中的k+1的位置上，因此每个进程都可能彼此独立地执行，而无通信的要求。令X是存在共享存储器中长度为n的数组，开始时放入被排序的序列，当算法结束时，结果置于共享存储器中的T数组内，变量i,j,k是算法生成的每个进程的局部变量[1007]。该并行算法的描述如下：1234567891011121314151617181920算法9.4.1MIMD-CREW模型上的异步枚举排序算法输入：S=(x1,x2,…,xn)置于共享存储器的X数组中输出：已排序的序列置于共享存储器的T数组中ENUERSORT{for(i=1;i=n;i++){CreateProcessi;}Processi:k=0;for(j=1;j=n;j++){if(X(i)X(j)){kk+1;}elseif((X(i)==X(j)&&ij)){kk+1;}}T(k+1)=X(i);}在该并行算法中有，由于每个处理器至多确定数组X中的n/p个元素的位置，而每确定一个元素的位置需O(n)时间，因此对X进行排序需n/p×O(n)时间。例9_8设S=(8,6,6,9,7)，p(n)=2。创建进程的过程中，假定由P1生成5个进程，此后所有的进程均等待开始。假定使用“先进先出”的调度策略。进程1和2分别由P1和P2执行，它们同时计算元素8和6的次第，然后将其分别置于T数组的相应位置上，如图9_19(a)所示。欲知下一进程有哪一个处理器启动执行，需研究进程1和2的执行时间。假定比较操作和赋值操作大致用相同的时间，当执行2X(i)X(j),X(i)=X(j)和ij以及k=0,k=k+1和T(k+1)=X(i)时，进程1和2分别需要14和17各时间步，如图9_19(b)所示。所以进程3应由P1启动执行，之后3个时间步P2启动执行进程4。这两个进程负责将元素6和9分别置于数组T的相应位置上，此时进程3需要18个时间步，进程4需要13个时间步，所以进程4比进程3早结束。下一进程5由P2启动。之后当进程3执行完后，因无等待的进程，所以P1变为空闲。当进程5执行15个时间步后，元素7便放到数组T的相应位置上。算法总共需要45个时间步。(a)数组T的变化过程(b)进度调度图9_19异步枚举排序数组变化及进程调度（二）单源点最短路径并行算法假设一有向图各边赋于非负整数，某条路径的长度就是沿该路径所有边权之和。最短路径问题，就是对每一点对i和j，丘照期间任何最短长度的路径。单源点最短路径，即在一个图中寻找从一个指定顶点到所有其他定点的最短路径。(a)单处理机上的Moore算法。在Moore算法中，设源点为s∈V。从s到其他各顶点的最短路径长度用一维数组dist存储。首先置dist(s)=0,dist(v)=∞，其中v≠s，且v∈V。算法使用了一个队列queue。开始执行时队列中仅含有源点s；以后每次只要队列非空，就将排头顶点u从队列中移去，令其作为本次搜索的顶点，然后检查u的所有射出边(u,v)∈E：若dist(u)+w(u,v)dist(v)，则此时就找到了一条从s到v的更短路径，置dist(v)=dist(u)+w(u,v)；若v不再搜索队列中，则把v加到队尾。如此重复进行，直到整个待搜索队列空时，算法就终止。12345678910算法9.4.2_1SISD机器上的单源点最短路径算法输入：有向加权图G(V,E)的权矩阵输出：从源s到其余顶点i(i≠s)的最短路径dist(i),i∈VSISDSHORTESTPATH{(1)for(i=1;i=n;i++)/*初始化*/{INITIALIZE(i);}(2)将s插入队列queue中;(3)while(队列非空){SEARCH;}}StatusSEARCH{31112131415161718192021222324252627282930(3.1)dequeuevertexu;/*从队列中删去顶点u*/(3.2)for(eachedge(u,v)∈E){new_distdist(u)+w(u,v);if(new_distdist(v)){dist(v)new_dist;}if(visnotinthequeue){enqueuevertexv;}}}StatusINITIALIZE{(1.1)dist(s)0;(1.2)dist(v)∞;(v≠s,v∈V)(1.3)queue0;}(b)Moore算法的并行化Deo等人基于MIMD紧耦合共享存储模型实现了Moore算法的并行化。直观上讲，算法9.4.2_1有两处可并行化的地方：一是SEARCH的第(3.2)步；二是主算法的第(3)步。前者，任何一个顶点均可能有多条射出边，它们都可并行地被检查；后者，在任何时候都可能有多个顶点在队列中，因此有可能每次检查多个顶点的射出边。由于后者可产生较大的加速，而且当G是个稀疏图时，并行度受定点射出变得影响，所以选用后者。首先，队列用源点初始化。然后创建了许多异步进程，每个进程都从队列中删除一个顶点，检查其射出边，将已发现有更短路径的顶点加入到队列。算法的第(1)步采用预调度方法很容易并行化。而第(3)步的while循环需作适当的修改，以能反映并执行SEARCH过程时一些异步进程的存在。显然，当一个进程发现队列为空时，就停止执行是不合适的。因而必须采用两个变量联合使用的办法，以决定什么时候无工作可做：第一个是数组变量waiting，它记住哪一个进程正处于等待状态；第二个是布尔变量halt，仅当队列为空和所有进程处于等待状态时为真。INITIALIZE过程置数组waiting中的第一个元素为假。SEARCH过程也必须作适当的修改。因为队列的插入、删除操作不是原子操作，所以执行上述操作时必须给队列上锁：其次，在一个进程将刚找到的v路径new_dist与当前的最短路径dist(v)比较之前，变量dist(v)也必须上锁，否则两个进程有可能同时修改它；最后，若一个进程发现队列为空时，则置waiting中的相应元素为真。若进程1处于等待状态，则它要检查每个进程是否都处在等待状态，如果是，则halt置为真，而进程1检查每个进程是否处于等待状态时，队列也必须上锁。该并行算法的描述如下：算法9.4.2MIMD-SM模型上单源点最短路径算法41234567891011121314151617181920212223242526272829303132333435363738394041输入：有向加权图G的权矩阵W输出：从源s到其余顶点i(i≠s)的最短路径dist(i),i∈VMIMDSHORTESTPATH{parfor(i=1;i=p;i++)/*p为进程数*/{for(j=i;j=n;j=j+p)/*初始化*/{INITIALIZE(j);}}enqueues;/*s入队*/halt=FALSE;parfor(i=1;i=p;i++){while(nothalt){SEARCH(i);}}}StatusSEARCH(i){lockthequeue;/*队列上锁*/if(queueisempty)/*队列空时，等待进程为真*/{waiting(i)TRUE;if(i==1)/*进程1等待时，其它进程均须等待*/{halt=waiting(2)∧waiting(3)∧…∧waiting(p);}unlockthequeue;/*队列开锁*/}else{dequeueu;/*从队列中删除u*/waiting(i)FALSE;unlockthequeue;/*队列开锁*/for(everyedge(u,v)inGraph)/*检查每条射出边*/{new_distdist(u)+w(u,v);lock(dist(v))/*dist(v)上锁*/if(new_distdist(v)){542434445464748495051525354dist(v)new_dist;/*更新new_dist*/unlock(dist(v));/*dist(v)开锁*/if(vqueue){lockthequeue;/*队列上锁*/enqueuev;/*v入队*/unlockthequeue;/*队列开锁*/}}else{unlock(dist(v));}/*dist(v)开锁*/}}}（二）最小生成树并行算法一个无向连通图G的生成树是指满足如下条件的G的子图T：(1)G和T具有相同的顶点数；(2)在T中有足够的边能连接G所有的顶点，但不出现回路。最小生成树，即最小代价生成树(MinimumCostSpanningTree)，它是加权连通无向图的所有生成树中权值最小的生成树。(a)Sollin顺序求MST算法算法开始时，图的n个孤立顶点视为一片森林，而每个顶点均视为一棵树；算法共迭代logn次，每次迭代时，森林中的每棵树，同时决定其最小的邻边，并将它们加入到森林中(即合并各棵树)；此过程重复到森林中只剩下一棵树。因为森林中树的数目，每次都以2的倍数减少，所以迭代至多需要nlog次就可找到MST；而每次迭代时，找顶点的最小邻边至多执行O(n2)次比较。因此Sollin的顺序算法的复杂度为O(n2logn)。函数FIND(v)找顶点v所在的树的名字，UNION(v,u)合并包括顶点v和u的两棵树。123456算法9.4.3_1SISD机器上的SollinMST算法输入：无向图G的加权矩阵W输出：G的最小生成树T(树以边的形式存储)SOLLIN-MST{(1)for(i=1;i=n;i++)/*初始化*/{vertexiisinitiallyinseti;}(2)T0;/*T就是MST*/678910111213141516171819202122232425262728293031323334(3)while(|T|n-1){(3.1)for(eachtreei)/*每棵树i找不在同一树中的最小边权*/{closest(i)∞;}(3.2)for(each(v,u)∈E){if(FIND(v)≠FIND(u))/*v和u属于不同的连通片*/{if(w(v,u)closest(FIND(v))){closest(FIND(v))w(v,u);edge(FIND(v))(v,u);}}}(3.3)for(eachtreei){(3.3.1)(v,u)edge(i);(3.3.2)if(FIND(v)≠FIND(u)){(3.3.2.1)TT∪{(v,u)};/*加入新的树边*/(3.3.2.2)UNION(v,u);/*合并成较大的树*/}}}}(b)Quinn的并行化算法在共享存储的MIMD机系统上，Sollin算法可按如下思路并行化：首先，应设法对第(3)步while循环进行并行化，但遗憾的是因循环之间存在着先后制约关系，即在第k+1次循环之前，第k次循环的子树必须同一个有最小权值的边关联的另一棵子树归并，所以while语句的并行化是有限的。其次，考虑循环体内的并行化。算法的第(3.1)步通过适当的预调度可以使其并行化，设第t次循环时已有nt棵子树：若ntp，则把nt棵子树较均匀的分配到p个处理器中，每个处理器约有pnt/棵子树；否则，这nt棵子树就分配给nt个处理器。算法的第(3.2)步并行化的最有效做法是：首先，每个处理器检查它内部的顶点的边，然后再检查不在同一处理器上树之间的边。算法的第(3.3)步并行化稍微复杂些。图9_20示出了此情况，假定一个处理器企图将树B与其最近的树A进行归并，变量edge(A)