《并行算法的一般设计策略PPT71页》由会员分享，可在线阅读，更多相关《并行算法的一般设计策略PPT71页（71页珍藏版）》请在金锄头文库上搜索。
1、第四章 并行算法的一般设计策略1设计并行算法一般有3种策略：（1）检查和开拓现有串行算法中固有的并行性，直接将其并行化，该方法并不是对所有问题总是可行的，但对很多应用问题仍不失为一种有效的方法；（2）从问题本身的描述出发，根据问题的固有属性，从头设计一个全新的并行算法，这种方法有一定难度，但所设计的并行算法通常是高效的；（3）借助已有的并行算法求解新问题。 24.1 4.1 串行算法的直接并行化串行算法的直接并行化方法描述发掘和利用现有串行算法中的并行性，直接将串行算法改造为并行算法。评注由串行算法直接并行化的方法是并行算法设计的最常用方法之一；并非所有的串行算法都可以并行化；一个好的串行算法
2、并不能并行化为一个好的并行算法，相反一个不好的串行算法则有可能产生很优秀的并行算法，例如枚举排序不是一种好的串行算法。但是将其直接并行化后可以得到比较好的并行算法 ；显著优点：无需考虑算法的稳定性、收敛性等复杂问题。3积分算法的直接并行化积分算法的直接并行化-的计算的计算4计算计算的串行的串行C代码代码#define N 1000000main() double local, pi = 0.0, w;long i;w=1.0/N;for (i = 0; iaj thenk=k+1 end ifend for(3)bk= aiend forEnd18枚举排序的并行算法枚举排序的并行算法 对该算法
3、的并行化是很简单的，假设对一个长为n的输入序列使用n个处理器进行排序，只需每个处理器负责完成对其中一个元素的定位，然后将所有的定位信息集中到主进程中，由主进程负责完成所有元素的最终排位。 19枚举排序并行算法枚举排序并行算法输入：无序数组a1an输出：有序数组b1bnBegin(1)P0播送a1an给所有Pi(2)for all Pi where 1in para-do (2.1)k=1 (2.2)for j = 1 to n doif (ai aj) or (ai = aj and ij) then k = k+1end if end for(3)P0收集k并按序定位End 步骤步骤的时间复
4、杂度为的时间复杂度为O（n）；步骤）；步骤中主进中主进程完成的数组元素重定位操作的时间复杂度为程完成的数组元素重定位操作的时间复杂度为O（n），通信复杂度分别为），通信复杂度分别为O（n）；同时）；同时中中的通信复杂度为的通信复杂度为O（n2）；所以总的计算复杂度）；所以总的计算复杂度为为O（n），总的通信复杂度为），总的通信复杂度为O（n2）。）。2021冒泡排序串行算法冒泡排序串行算法 串行冒泡排序算法包括两个循环，每次操作比较两个相邻的元素，然后通过交换使之符合指定的排序。以下是串行冒泡排序算法： void BUBBLE_SORT(n) for i:=n-1 downto 1 do fo
5、r j:=1 to i do compare-exchange (aj,aj+1); 22冒泡排序的步骤冒泡排序的步骤23可以通过一些手段来提高其性能，比如当没有发现交换时便结束循环等，不过这并不改变算法运行的时间复杂度O(n2)。冒泡排序顺次比较相邻的元素，这在本质上是一个串行的过程，很难并行化。将顺次的比较过程并行化将导致算法错误，得不到预想的结果。考虑到内循环的下一次迭代的“冒泡”动作可以在前一次迭代完成之前开始，只要下一次“冒泡”动作不影响前一次迭代，所以可以开发流水线并行算法。24流水线并行流水线并行25一维线性网络中的奇偶置换冒泡排序一维线性网络中的奇偶置换冒泡排序设待排序的元素数
6、目为n，以n为偶数来说明奇偶置换排序。奇偶置换排序用n个阶段完成对n个元素的排序，每一个阶段需要n/2个比较+交换操作。这n个阶段分成两类，分别称为奇操作阶段和偶操作阶段。设 是待排序的序列，在每个奇操作阶段，奇数索引的元素与自己的右邻居进行比较并在必要时交换，同样，在每个偶操作阶段，偶数索引的元素与自己的右邻居进行比较和交换。经过n个阶段进行这样的操作后，整个序列便处于有序状态。26对对8 8个数进行奇偶互换排序个数进行奇偶互换排序27void ODD-EVEN(n) for( i=1 ,i= n ,i+) if i is odd then for(j=0,j= n/2-1,j+) comp
7、are-exchange(a2j+1,a2j+2); if i is even then for( j=1 ,j= n/2-1 ,j+) compare-exchange(a2j,a2j+1); 串行奇偶置换冒泡排序程序串行奇偶置换冒泡排序程序28串行奇偶置换冒泡排序的并行化串行奇偶置换冒泡排序的并行化 void ODD-EVEN_PAR(n) id=processors label for( i=1,i= n,i+) if i is odd then if id is odd then compare-exchange_min(id+1); else compare-exchange_max
8、(id-1); if i is even then if id is even then compare-exchange_min(id+1); else compare-exchange_max(id-1); 29（归并排序）（归并排序）MergesortMergesortA classical sequential sorting algorithm using divide-and-conquer approach. Unsorted list first divided into half. Each half is again divided into two. Continued
9、until individual numbers are obtained.Then pairs of numbers combined (merged) into sorted list of two numbers. Pairs of these lists of four numbers are merged into sorted lists of eight numbers. This is continued until the one fully sorted list is obtained.30MergesortMergesort的并行化的并行化使用树状进程分配的归并排序使用
10、树状进程分配的归并排序Tcomp=2p-2-logpTcomm=2(logp)tstartup+2ntdata31奇偶归并排序奇偶归并排序奇偶归并排序将两个有序序列归并为一个有序序列，对于给定的两个序列an和bn，该算法描述如下： 1、每个序列的奇数下标索引的元素，即a1,a3,an-1和b1,b3,bn-1被归并为一个有序序列c1,c2,cn； 2、每个序列的偶数下标索引的元素，即a2,a4,an和b2,b4,bn被归并为一个有序序列d1,d2,dn。 3、最后的有序序列e1,e2,e2n通过以下方法得到： e2i=minci+1,di e2i+1=maxci+1,di32Odd-Even
11、Merging of Two Sorted ListsOdd-Even Merging of Two Sorted Listse2i=minci+1,di e2i+1=maxci+1,di每个序列的奇、偶数下每个序列的奇、偶数下标索引的元素分别被归标索引的元素分别被归并为一个有序序列并为一个有序序列33快速排序的并行化快速排序的并行化Tcomp=n+n/2+n/4+.=2nTcomm=(logp)tstartup+ntdata34在专用网络在专用网络HypercubeHypercube超立方体上的排序超立方体上的排序Hypercube network has structural charac
12、teristics that offer scope for implementing efficient divide-and-conquer sorting algorithms, such as quicksort.35超立方体上的并行化超立方体上的并行化基本思路： 一个d维的超立方体可以看作是由两个d-1维的超立方体互联而成，利用这一点，可以把一个d维的超立方体存储的一个序列划分成两个子序列而分别存放到两个d-1维的超立方体上，使得每个d-1维立方体的每个处理器都跟另外一个立方体的某处理器直接相连。这样，一个大于界的子序列与小于界的子序列可以分别放在不同的超立方体上。36Suppose
13、 a list of n numbers placed on one node of a d-dimensional hypercube.List can be divided into two parts according to the quicksort algorithm by using a pivot determined by the processor, with one part sent to the adjacent node in the highest dimension.Then the two nodes can repeat the process.1. 1.
14、整个序列在一个处理器上整个序列在一个处理器上37ExampleExample3-dimensional hypercube with the numbers originally in node 000:38数据最初放在节点数据最初放在节点000000时的超立方体快速排序算法时的超立方体快速排序算法 Finally, the parts sorted using a sequential algorithm, all in parallel. If required, sorted parts can be returned to one processor in a sequence tha
15、t allows processor to concatenate sorted lists to create final sorted list.392. 2. 最初数据散布在所有处理器上最初数据散布在所有处理器上假设待排序数最初均匀地、不按任何特殊顺序地分布在节点上；一个2d个节点的超立方体由两个2d-1个节点的超立方体组成，它们通过每个立方体中第d维节点之间的链路互联；快速排序并行算法的步骤：首先将超立方体看成两个子立方体，位于高端子立方体中的处理器的地址首位为1，位于低端子立方体中的处理器的地址首位为0。成对的地址分别为0xxx和1xxx的处理器称为“伙伴”，其中x是相同的。40具体
16、步骤具体步骤1、一个处理器（如p0）选择（或计算）一个合适的轴元素，并通过广播把它送到立方体中所有其它处理器；2、低端子立方体中的处理器将大于该轴元素的数传送给他们位于高端子立方体中的伙伴处理器。高端子立方体中的处理器将小于该轴元素的数传送给他们位于低端子立方体中的伙伴处理器。3、每个处理器将收到的序列和本身的序列拼接。给定一个d维超立方体，经过这些步骤以后，低端d-1维子立方体中的数都小于或等于轴元素，而高端d-1维子立方体中的数都大于轴元素。4、两个d-1维子立方体重复递归调用第2、3步，其中每个子立方体中的一个进程为该子立方体选择轴元素并通过广播传送到子立方体中的其他进程，递归调用d次后
17、终止。5、为了完成排序，每个处理器中的数需要串行进行排序。最后按数字顺序访问处理器即可从处理器中检索数。 41422 2 矩阵运算（转置、乘法）矩阵运算（转置、乘法）矩阵运算是数值计算中最重要的一类运算,特别是在线性代数和数值分析中,它是一种最基本的运算。矩阵的划分：条带状划分和棋盘划分 为了对一个矩阵进行并行操作，必须将其进行划分并映射到不同的处理器上，尤其是科学计算中矩阵的规模一般都很庞大的情况下更是如此。条带状划分（Striped Partitioning） 条带状划分就是把矩阵按照行或列分成几部分，分别映射到各个处理器。如果分到每个处理器的各行或列是连续的，则称为块带状划分（Block
18、-Striped）； 相对的，如果是按照行号或者列号取模而进行的矩阵划分则称为循环带状划分（Cyclic-Striped）。434个处理器上1616矩阵的均匀条带状划分和映射(a) 列方向上的块带状划分； (b) 行方向的循环带状划分44棋盘划分（棋盘划分（Checkerboard Checkerboard PartitioningPartitioning） 棋盘划分把矩阵划分为若干个子矩阵并映射到不同的处理器上，每个处理器都不包含完整的行和列。和条带状划分类似，棋盘划分也可以分为块棋盘划分和循环棋盘划分。4516个处理器上88矩阵的均匀块棋盘划分和映射462.1 2.1 矩阵的转置矩阵的转置
19、 转置（Transposition）是基本的矩阵运算。一个矩阵A的转置记为AT，它是将矩阵A的元素沿对角线互换而得到的。矩阵转置的串行算法很简单，只需要把上三角（不包括对角线）的元素循环一遍，每个元素与其对称位置的元素交换位置即可，整个过程只需要一个单位的多余空间，时间复杂度为O(n2)。47单处理器上矩阵转置算法单处理器上矩阵转置算法 输入：矩阵Ann 输出：矩阵Ann的转置ATnn Begin for i=2 to n do for j=1 to i-1 do 交换ai,j和aj,i endfor endfor End48棋盘划分的矩阵转置棋盘划分的矩阵转置二维网格互联结构上的矩阵转置设处
20、理器数目pn2，则整个nn的矩阵分成p个大小为 的子块，这些子块自然影射到网格互联结构的p个处理器上。算法可以分两步来完成：第一步，将各个子块看作一个整体进行子块转置，这一步由各处理器互相通信；第二步，各处理器分别对自己的内部子块进行局部转置。4916个处理器上块棋盘划分的88矩阵的转置 子块间转置子块间转置 子块内转置子块内转置 50为了避免对应子块交换数据时处理器发生死锁，可令下三角子块先向与之对应的上三角子块发送数据，然后从上三角子块接收数据；上三角子块先将数据存放在缓冲区buffer中，然后从与之对应的下三角子块接收数据；最后再将缓冲区中的数据发送给下三角子块。 51算法 块棋盘划分的
21、矩阵转置算法输入：矩阵Ann 输出：矩阵Ann的转置ATnnBegin 对所有处理器my_rank(my_rank=0,p-1)同时执行如下的算法: (1) 计算子块的行号 v=my_rank/ sqrt(p), 计算子块的列号 u=my_rank mod sqrt(p) (2) if (uv) then /*对存放下三角块的处理器*/ (2.1)将所存的子块发送到其对角块所在的处理器中 (2.2)接收其对角块所在的处理器中发来的子块 else /*对存放上三角块的处理器*/ (2.3)将所存的子块在缓冲区buffer中做备份 (2.4)接收其对角块所在的处理器中发来的子块 (2.5)将buf
22、fer中所存的子块发送到其对角块所在的处理器中 end if (3)for i=1 to m do /*处理器内部局部转置*/ for j=1 to i do 交换ai,j和aj,i end for end for End52532.2 2.2 矩阵向量乘法矩阵向量乘法 一个矩阵与向量相乘，结果得到一个向量。矩阵向量相乘的串行算法具有O(n2)的时间复杂度。单处理器上矩阵-向量乘算法输入：Ann，Bn1 输出：Cn1Begin for i=0 to n-1 do ci= 0 for j=0 to n-1 do ci=ci + ai,j*bj end for end forEnd 54矩阵矩阵-
23、 -向量乘法的并行算法向量乘法的并行算法矩阵-向量乘法同样可以有带状划分(Striped Partitioning)和棋盘划分(Checker Board Partitioning)两种并行算法。以下仅讨论行带状划分矩阵-向量乘法, 列带状划分矩阵-向量乘法是类似的。设处理器个数为p，对矩阵A按行划分为p块，每块含有连续的m行向量， ，这些行块依次记为A0, A1, , Ap-1，分别存放在标号为0,1,p-1的处理器中，同时将向量B 广播给所有处理器。各处理器并行地对存于局部数组a中的行块Ai和向量B做乘积操作。 55行带状划分的矩阵-向量乘并行算法输入：Ann，Bn1输出：Cn1Begin
24、 对所有处理器my_rank(my_rank=0, p-1)同时执行如下的算法:for i=0 to m-1 do c(i)=0.0 for j=0 to n-1 doci = ci+ai,j*bj end for end forEnd假设一次乘法和加法运算时间为一个单位时间，不难得出行带状划分的矩阵-向量乘算法并行计算时间Tp=n2/p，若处理器个数和向量维数相当，则其时间复杂度为O(n)。 56 矩阵相乘及其串行算法矩阵相乘及其串行算法由矩阵乘法定义容易给出其串行算法，若一次乘法和加法运算时间为一个单位时间，则显然其时间复杂度为O(mnk) 。单处理器上矩阵相乘算法输入：Amn，Bnk输出
25、：CmkBegin for i=0 to m-1 do for j=0 to k-1 doci,j=0for r=0 to n-1 do ci,j= ci,j+ai,r*br,j end for end forend forEnd57简单的矩阵并行分块乘法算法简单的矩阵并行分块乘法算法 矩阵乘法也可以用分块的思想实现并行，即分块矩阵乘法(Block Matrix Multiplication)，将矩阵A按行划分为p块(p为处理器个数)，设 ，每块含有连续的u行向量，这些行块依次记为A0,A1, ,Ap-1，分别存放在标号为0,1, p-1的处理器中。对矩阵B按列划分为p块，记 ，每块含有连续的
26、v列向量，这些列块依次记为B0,B1, ,Bp-1，分别存放在标号0,1, , p-1为的处理器中。将结果矩阵C也相应地同时进行行、列划分，得到pp个大小为uv的子矩阵，记第i行第j列的子矩阵为Cij，显然有Cij= A iB j，其中，A i 大小为un，B j大小为nv。 58矩阵相乘并行算法中的数据交换矩阵相乘并行算法中的数据交换 59开始，各处理器的存储内容如上图所示。此时各处理器并行计算Cii= A iBi, 其中i=0,1,p-1，此后第i号处理器将其所存储的B的列块送至第i-1号处理器（第0号处理器将B的列块送至第p-1号处理器中，形成循环传送），各处理器中的存储内容如图 (b)
27、所示。它们再次并行计算Cij= A iB j，这里j=(i+1)modp。B的列块在各处理器中以这样的方式循环传送p-1次并做p次子矩阵相乘运算，就生成了矩阵C的所有子矩阵。编号为i的处理器的内部存储器存有子矩阵Ci0,Ci1,Ci(p-1)。为了避免在通信过程中发生死锁，奇数号及偶数号处理器的收发顺序被错开，使偶数号处理器先发送后接收；而奇数号处理器先将B的列块存于缓冲区buffer中，然后接收编号在其后面的处理器所发送的B的列块，最后再将缓冲区中原矩阵B的列块发送给编号在其前面的处理器 60 矩阵并行分块乘法算法矩阵并行分块乘法算法 输入：Amn, Bnk, 输出：CmkBegin 对所有
28、处理器my_rank(my_rank=0,p-1)同时执行如下的算法: (1)目前计算C的子块号l=(i+my_rank) mod p (2)for z=0 to u-1 do for j=0 to v-1 do cl,z,j=0 for s=0 to n-1 do cl,z,j=cl,z,j+ az,s*bs,j end for end for end for (3)计算左邻处理器的标号mm1=(p+my_rank-1) mod p 计算右邻处理器的标号mp1=(my_rank+1) mod p61 (4)if (ip-1) then (4.1)if (my_rank mod 2= 0) t
29、hen /*编号为偶数的处理器*/ (i)将所存的B的子块发送到其左邻处理器中 (ii)接收其右邻处理器中发来的B的子块 end if (4.2)if (my_rank mod 2 0) then /*编号为奇数的处理器*/ (i)将所存的B子块在缓冲区buffer中做备份 (ii)接收其右邻处理器中发来的B的子块 (iii)将buffer中所存的B的子块发送到其左邻处理器中 end if end ifEnd623 3 图论及组合优化图论及组合优化图论在计算机科学、信息科学、人工智能、网络理论、系统工程、控制论、运筹学和经济管理等领域有着广泛的应用。但很多图论问题虽易表达，却难以求解，其中有相
30、当多的图论问题均属NP完全问题。本节主要介绍工程实用简单图论问题的并行算法。 633.1 最小生成树最小生成树 一个无向连通图G的生成树是指满足如下条件的G的子图T：T和G顶点数相同；T有足够的边使得所有顶点连通，同时不出现回路。如果对G的每条边指定一个权值，那么，边权总和最小的生成树称为最小代价生成树，记为MCST（Minimum Cost Spanning Tree），常简称为最小生成树（记为MST）。最小生成树问题就是给定G，找出G的一个最小生成树T的问题。64最小生成树串行算法最小生成树串行算法Sollin算法(Sollin Algorithm)是众多用于求解MST问题的算法之一，其原
31、理为：算法开始时，图中的N个顶点视为一片森林，每个顶点视为一棵树；算法主循环的流程中，森林里每棵树同时决定其连向其它树的最小邻边，并将这些边加入森林中，实现树的合并；循环到森林中只剩一棵树时终止。由于森林中树的数目每次至少减少一半，所以只要N次循环就可以找出MST。算法中以D(i)为顶点i所在的树的编号， edge(i) 和closet(i)为树i连向其它树的最小邻边和其长度，则Sollin算法的形式描述见下述算法，其时间复杂度为O(N2N)。 65Sollin MST算法算法 输入：无向图G的边权矩阵W输出：G的最小生成树的边集合Tprocedure Sollin-MSTBegin/* 以下
32、所有顶点初始化为一棵孤立的树 */ (1)for i=0 to N-1 do D(i) = i endfor (2)T初始化为空集 66(3) while |T| N-1 do /* 以下为各树寻找连向其它树的最小边权 */ (3.1)for 每棵树i do closet(i) = endfor (3.2)for 图G中每条边(v,u) do if D(v)D(u) and w(v,u)0 and D(j)D(i) and a(i, j)W(i) then C(i) = D(j) W(i) = a(i,j) J(i) = j endif endfor () if W(i)=MAX thenC(
33、i) = D(i)endif endfor70/* 以下各处理器为所负责的树找出外连的最短边对应源程序中C_to_C()函数 */ (2.2) for 每棵树i par_do ()tempj = N+1 () tempw = MAX () for 每个顶点j do if D(j)=i and C(j)i and W(j)tempw then C(i) = C(j) tempw = W(j) tempj = j endif endfor () if tempjN and J(tempj)N then 通知处理器0将边(tempj, J(tempj)加入MST数组 endifendfor71 (2.3) for i=0 to N-1 par_do D(i) = C(i) endfor (2.4) for i=1 to N do /* 以下对应源程序中CC_to_C()函数 */ for j=0 to N-1 par_do C(j) = C(C(j) endfor endfor /* 以下对应源程序中CD_to_D()函数 */ (2.5) for i=0 to N-1 par_do D(i) = min C(i), D(C(i) endfor endwhileEnd
