并行算法的一般设计策略

精品文档---下载后可任意编辑第五章 并行算法的一般设计谋略习题例题：1、 令 n 是待排序的元素数，p＝2d是 d 维超立方中处理器的数目。假定开始随机选定主元x，并将其播送给所有其他处理器，每个处理器按索接收到的 x，对其 n/p 个元素根据≤ x和＞x 进行划分，然后按维进行交换。这样在超立方上实现的快排序算法如下：算法 5.6 超立方上快排序算法输入： n 个元素，B = n/p, d = log p输出： 按超立方编号进行全局排序Begin(1)id = processor’s label(2)for i=1 to d do(2.1) x = pivot / * 选主元 * /(2.2) 划分 B 为 B1和 B2满足 B1 ≤B＜B2(2.3) if 第 i 位是零 then (i) 沿第 i 维发送 B2给其邻者 (ii) C = 沿第 i 维接收的子序列 (iii) B= B1∪C else (i) 沿第 i 维发送 B1给其邻者 (ii) C = 沿第 i 维接收的子序列 (iii) B= B2∪C endifendfor(3)使用串行快排序算法局部排序 B = n/p 个数End① 试解释上述算法的原理。② 试举一例说明上述算法的逐步执行过程。2、 ① 令 T = babaababaa。P =abab，试用算法 5.4 计算两者的匹配情况。② 试分析 KMP 算法为何不能简单并行化。3、 给定序列〔33，21，13，54，82，33，40，72〕和 8 个处理器，试根据算法 5.2 构造一棵为在 PRAM-CRCW 模型上执行快排序所用的二叉树。4、 计算 duel(p, q)函数的算法如下：算法 5.7 计算串匹配的 duel(p, q) 的算法输入： WIT〔1: n-m+1〕，1≤p＜q≤n-m+1，(p - q) ＜ m/2输出： 返回竞争幸存者的位置或者 null〔表示 p 和 q 之一不存在〕Beginif p=null then duel= q else精品文档---下载后可任意编辑 if q =null then duel= p else (1) j= q - p +1 (2) w=WIT(j) (3) if T(q+w-1) ≠ P(w) then (i) WIT(q) = w (ii) duel= p else (i) WIT(p) = q – p +1 (ii) duel= q endifendifEnd① 令 T = abaababaababaababababa。P = abaababa，试计算 WIT(i)；② 试考虑 P=6，q=9 的竞争情况。5、 对于图 5.2(a)的加权有向图，试用算法 5.5，逐步求出 D2，D4和 D8中各元素dijk：[d002d012d022d032d042d052d062¿][d102d112d122d132d142d152d162¿][ ⋮¿]¿¿¿¿ [d002d012d022d032d042d052d062¿][d102d112d122d132d142d152d162¿][ ⋮¿]¿¿¿¿(a) D2 (b) D4[d002d012d022d032d042d052d062¿][d102d112d122d132d142d152d162¿][ ⋮¿]¿¿¿¿(a) D8小结设计并行算法是一件复杂的事，而并行算法的设计这门学科还属于开展中的一门学科，所以目前尚无一套普遍适用的、系统的设计方法学。本章只是给出一个非常一般的并行算法的设计方法，它不可能也不应该视为设计并行算法的全部方法。重要的是，通过所介绍的设计方法的学习，希望读者能从中得到更多的启迪，补充更多的算例，丰富、完善乃至开拓出更新更好的设计方法。