《[计算机软件及应用]并行计算4算法》由会员分享，可在线阅读，更多相关《[计算机软件及应用]并行计算4算法（145页珍藏版）》请在金锄头文库上搜索。
1、并行算法,1 一般设计方法,并行算法的一般设计方法,串行算法的直接并行化 从问题描述开始设计并行算法 借用已有算法求解新问题,串行算法的直接并行化,设计方法描述 快排序算法的并行化,设计方法的描述,方法描述 发掘和利用现有串行算法中的并行性，直接将串行算法改造为并行算法。 许多并行编程语言都支持通过在原有的串行程序中加入并行原语（例如某些通信命令等）的方法将串行程序并行化。,设计方法的描述,评注 由串行算法直接并行化的方法是并行算法设计的最常用方法之一； 不是所有的串行算法都可以直接并行化的；某些串行算法有内在的串行性，比如在某些串行算法中，每一步都要用到上一步的结果。只有当上一步完全结束后，
2、下一步才能开始。这样，各步之间就不能并行，只能考虑其它的并行化办法。例如模拟退火算法，每个温度下迭代的出发点是上一个温度下迭代的结束点。这样就很难直接将各个温度的迭代并行起来。,设计方法的描述,评注 一个好的串行算法并不能并行化为一个好的并行算法；另一方面，不好的串行算法并行化后也可能是优秀的并行算法。例如，串行算法中是没有冗余计算的。但是在并行算法中，使用适当的冗余计算也可能使并行算法效率更高。加入冗余计算的并行算法就可能比直接由串行算法并行化得到的算法效率高。又比如，枚举不是一种好的串行算法。但是将其直接并行化后可以得到比较好的并行算法。 许多数值串行算法可以并行化为有效的数值并行算法。,
3、设计方法的描述,假设我们想用求和的方法进行数值积分。设被积函数为f(x)，积分区间为a,b。为了积分，将区间a,b均匀分成N个小区间，每个小区间长 ，根据积分的定义 是第i 个小区间左端点的坐标，而 是f(x)在第i 个小区间上积分的近似值。如果使用串行算法，可以用循环和叠加完成上述求和。这个串行算法可以直接并行化。,设计方法的描述,假设有k台处理器，可以把这N个小区间上的计算任务分到各处理器：0号处理器负责第 个小区间上的计算和累加，1号处理器负责第 个小区间上的计算和累加，k-1号处理器负责第 个小区间上的计算和累加。k个处理器并行地计算出部分和，然后再把结果加到一起。,设计方法的描述,快
4、排序算法的并行化,算法 PRAM-CRCW上的快排序二叉树构造算法 输入：序列(A1,An)和n个处理器 输出：供排序用的一棵二叉排序树 Begin (1)for each processor i do (2)repeat for each processor iroot do (1.1)root=i if (AiAfi)(Ai=Afiifi) then (1.2)fi=root (2.1)LCfi=i (1.3)LCi=RCi=n+1 (2.2)if i=LCfi then exit else fi=LCfi endif end for else (2.3)RCfi=i (2.4)if i=
5、RCfi then exit else fi=RCfi endif endif end repeat End,从问题描述开始设计并行算法,方法描述 从问题本身描述出发，不考虑相应的串行算法，设计一个全新的并行算法。 评注 挖掘问题的固有特性与并行的关系； 设计全新的并行算法是一个挑战性和创造性的工作； 利用串的周期性的PRAM-CRCW算法是一个很好的范例；,并行串匹配算法,给定长度为n的正文串T和长度为m的模式串P，找出P在T中所有出现的位置称为串匹配问题。 研究发现，两串能否匹配是与串本身的特性有关的。这种特性，就是串的周期性。 串可以分为周期的和非周期的。 可以引入见证函数（Witnes
6、s Function）来判断串的周期性。确定了串的周期性后就可以先研究非周期串的匹配，然后在此基础上再研究周期串的匹配。,并行串匹配算法,对于非周期串的研究，就是如何利用见证函数快速地找出P在T中的位置。为此，引入竞争函数duel(p,q) 。 先把正文串分成小段，借助于见证函数并行地计算竞争函数值，找出那些可能匹配的位置。然后逐步扩大正文串分段的长度，并计算竞争函数值，在可能匹配的位置中排除那些不可能匹配的位置。最后在剩下的可能位置中验证哪些是符合要求的位置。,并行串匹配算法,假设T=abaababaababaababaababa，n=23，P=abaababa，m=8。由见证函数可知P是非
7、周期串。因为P只可能在前16个位置上与T匹配，所以在找所有“可能位置”时只考虑T的前16个字符。 匹配时，先要计算见证函数值，然后由其计算 的值，找到可能匹配的位置。 计算duel(p,q)时，可以所有的块并行计算。先将P和T分成长度为2的块，用模式块(ab) 与正文块(ab)(aa)(ba)(ba)(ab)(ab)(aa)(ba)进行匹配可知模式块(ab)在位置1，4，6，9，11，14，16（即duel(p,q)的获胜者）出现匹配。 再把P与T划分成长度为4的块，用模式块(abaa)与正文块(abaa)(baba)(abab)(aaba)进行匹配, 可知在位置1，6，11，16出现匹配（位
8、置4、9、14被淘汰）； 最后用模式串(abaababa)在正文串的位置1，6，11，16进行检查，排除那些不匹配的位置。本例中这4个位置都匹配。,借用已有算法求解新问题,设计方法描述 利用矩阵乘法求所有点对间最短路径,设计方法的描述,方法描述 找出求解问题和某个已解决问题之间的联系； 改造或利用已知算法应用到求解问题上。 评注 这是一项创造性的工作； 使用矩阵乘法算法求解所有点对间最短路径是一个很好的范例。,利用矩阵乘法求所有点对间最短路径,计算原理 设在一有向图中，各弧都赋予了非负整数权。图中一条路径的长度定义为该路径上所有的弧的权的和。图中两结点之间的最短路径是指它们之间长度最短的路径。
9、 设G为一个含有n个结点的有向图。矩阵W=(wij)是G中各弧上的权构成的矩阵，即W的元素wij是G中结点vi到结点vj的弧上的权（如果vi到vj无弧，则令wij=）。我们的目的是计算G中所有结点对之间的最短路。为此，记dij为结点vi到结点vj的最短路长，并记D=(dij)。用dij k表示从vi到vj至多经过k-1个中间结点的所有路径的长度的最小值，记Dk=(dijk) 。因此dij 1=wij（ij）， dij 1=0 （i=j）。如果假设G中不包含权为负的有向圈，则dij = dij n-1，D=Dn-1,利用矩阵乘法求所有点对间最短路径,根据组合最优原理（Combinatorial
10、Optimization Principle）有 从而可以从D1 开始，逐次计算出D2 ， D4 ， D8，Dn-1=D。为了从Dk/2计算Dk，可以借用标准的矩阵乘法。矩阵乘法执行的计算是 只需将矩阵乘法中的乘法操作换成加法操作，把矩阵乘法中的求和换“求最小值“操作即可。,利用矩阵乘法求所有点对间最短路径,计算原理 有向图G=(V,E)，边权矩阵W=(wij)nn，求最短路径长度矩阵D=(dij)nn，dij为vi到vj的最短路径长度。假定图中无负权有向回路，记d(k)ij为vi到vj至多有k-1个中间结点的最短路径长，Dk=(d(k)ij)nn，则 (1) d(1)ij=wij 当 ij
11、(如果vi到vj之间无边存在记为) d(1)ij=0 当 i=j (2) 无负权回路 dijd(n-1)ij (3) 利用最优组合原理：d(k)ij=min1lnd(k/2)il+d(k/2)lj 视：”+” “”， “min” “”，则上式变为 d(k)ij=1lnd(k/2)ild(k/2)lj (4) 应用矩阵乘法：D1 D2 D4 D2logn (= Dn) SIMD-CC上的并行算法：p139算法5.5,并行算法,2 基本设计技术,并行算法的基本设计技术,划分设计技术 分治设计技术 平衡树设计技术 倍增设计技术 流水线设计技术,划分设计技术,均匀划分技术 方根划分技术 对数划分技术
12、功能划分技术,均匀划分技术,划分方法 n个元素A1n分成p组，每组A(i-1)n/p+1in/p，i=1p 示例：MIMD-SM模型上的PSRS排序 begin (1)均匀划分：将n个元素A1n均匀划分成p段，每个pi处理 A(i-1)n/p+1in/p (2)局部排序：pi调用串行排序算法对A(i-1)n/p+1in/p排序 (3)选取样本：pi从其有序子序列A(i-1)n/p+1in/p中选取p个样本元素 (4)样本排序：用一台处理器对p2个样本元素进行串行排序 (5)选择主元：用一台处理器从排好序的样本序列中选取p-1个主元，并 播送给其他pi (6)主元划分：pi按主元将有序段A(i-
13、1)n/p+1in/p划分成p段 (7)全局交换：各处理器将其有序段按段号交换到对应的处理器中 (8)归并排序：各处理器对接收到的元素进行归并排序 end.,均匀划分技术,例 PSRS排序过程。N=27，p=3，PSRS排序如下：,方根划分技术,划分方法 n个元素A1n分成A(i-1)n(1/2)+1in(1/2)，i=1n(1/2) 示例：SIMD-CREW模型上的 Valiant归并(1975年发表) /有序组A1p、B1q, (假设p=q), 处理器数 begin (1)方根划分: A,B分别按 ； (2)段间比较: A划分元与B划分元比较(至多 对)， 确定A划分元应插入B中的区段；
14、(3)段内比较: A划分元与B相应段内元素进行比较，并插入适当的位置； (4)递归归并: B按插入的A划分元重新分段，与A相应段(A除去原划分元) 构成了成对的段组，对每对段组递归执行(1)(3)，直至A 组为0时，递归结束; 各组仍按 分配处理器； end.,方根划分技术,方根划分技术,对数划分技术,划分方法 n个元素A1n分成A(i-1)logn+1ilogn，i=1n/logn 示例：PRAM-CREW上的对数划分并行归并排序 (1)归并过程: 设有序组A1n和B1m ji=rank(bilogm:A)为bilogm在A中的位序，即A中小于等于bilogm的元素个数 (2)例：A=(4,
15、6,7,10,12,15,18,20), B=(3,9,16,21) n=8, m=4 =logm=log4=2 = j1=rank(blogm:A)=rank(b2:A)=rank(9:A)=3, j2=8 B0: 3, 9 B1: 16, 21 A0: 4, 6, 7 A1: 10, 12, 15, 18, 20 A和B归并化为(A0, B0)和(A1, B1)的归并,功能划分技术,划分方法 n个元素A1n分成等长的p组，每组满足某种特性。 示例：(m, n)选择问题(求出n个元素中前m个最小者) 功能划分：要求每组元素个数必须大于m； 算法：p148算法6.4 输入：A=(a1,an); 输出：前m个最小者； Begin (1) 功能划分：将A划分成g=n/m组，每组含m个元素； (2) 局部排序：使用Batcher排序网络将各组并行进行排序； (3) 两两比较：将所排序的各组两两进行比较，从而形成MIN序列； (4) 排序-比较：对各个MIN序列，重复执行第(2)和第(3)步，直至 选出m个最小者。 End,功能划分技术,分治设计技术,并行分治设计步骤 双调归并网络,并行分治设计步骤,将输入划分成若干个规
