[计算机软件及应用]并行计算4算法

《[计算机软件及应用]并行计算4算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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)foreachprocessorido(2)repeatforeachprocessori<>rootdo(1.1)root=iif(Ai

5、CfiendifendifendrepeatEnd从问题描述开始设计并行算法方法描述从问题本身描述出发，不考虑相应的串行算法，设计一个全新的并行算法。评注挖掘问题的固有特性与并行的关系；设计全新的并行算法是一个挑战性和创造性的工作；利用串的周期性的PRAM-CRCW算法是一个很好的范例；并行串匹配算法给定长度为n的正文串T和长度为m的模式串P，找出P在T中所有出现的位置称为串匹配问题。研究发现，两串能否匹配是与串本身的特性有关的。这种特性，就是串的周期性。串可以分为周期的和非周期的。可以引入见证函数（WitnessFunction）来判断串的周期性。确定了串的周期性后就可以先

6、研究非周期串的匹配，然后在此基础上再研究周期串的匹配。并行串匹配算法对于非周期串的研究，就是如何利用见证函数快速地找出P在T中的位置。为此，引入竞争函数duel(p,q)。先把正文串分成小段，借助于见证函数并行地计算竞争函数值，找出那些可能匹配的位置。然后逐步扩大正文串分段的长度，并计算竞争函数值，在可能匹配的位置中排除那些不可能匹配的位置。最后在剩下的可能位置中验证哪些是符合要求的位置。并行串匹配算法假设T=abaababaababaababaababa，n=23，P=abaababa，m=8。由见证函数可知P是非周期串。因为P只可能在前16个位置上与T匹配，所以在找所有“

7、可能位置”时只考虑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，1