第五章并行算法的一般设计策略 习题例题: 1、令n是待排序的元素数,p=24是d维超立方中处理器的数目。假定开始随机选定主元 x,并将其播送给所有其他处理器,每个处理器按索接收到的x,对其m个元素按照≤x和 >x进行划分,然后按维进行交换。这样在超立方上实现的快排序算法如下: 算法56超立方上快排序算法 输入:n个元素,B=mp,d=logp 输出:按超立方编号进行全局排序 (1)id= processor's label (2)for i=l to d do (2.1)x=pivot /*选主元*/ (22)划分B为B1和B2满足B1≤B<B (2.3)if第i位是零then (i)沿第i维发送B2给其邻者 (i)C=沿第i维接收的子序列 (iiiB=B1UC (i)沿第i维发送B1给其邻者 (i)C=沿第i维接收的子序列 (ili) B= B2UC dfor 3)使用串行快排序算法局部排序B=mp个数 ①试解释上述算法的原理 ②试举一例说明上述算法的逐步执行过程 2、①令T= babaababaa。P=abab,试用算法54计算两者的匹配情况。 ②试分析KMP算法为何不能简单并行化 3、给定序列(33,21,13,54,82,33,40,72)和8个处理器,试按照算法52构造 棵为在 PRAM-CRCW模型上执行快排序所用的二叉树 4、计算duel(p,q函数的算法如下 算法57计算串匹配的duel(p,q)的算法 输入:WT(1:nm+1),1≤p<q≤nm+1,p-q)<m2 输出:返回竞争幸存者的位置或者nul(表示p和q之一不存在) fp=null then duel=g else if g =null then duel= p else (1)=q-P+1
第五章 并行算法的一般设计策略 习题例题： 1、 令 n 是待排序的元素数，p＝2 d 是 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 endif endfor (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 之一不存在） Begin if p=null then duel= q else if q =null then duel= p else (1) j= q - p +1
(2)W=WITV (3)if T(o+w-1)* P(w)then (1)wI(q) (ii)duel= D)WIT(p)=q-p+l endif endif End ①令T= abaababaababaababababa。P= abaababa,试计算WIT() ②试考虑P=6,q=9的竞争情况 5、对于图52(a)的加权有向图,试用算法55,逐步求出D,D和D中各元素d d10 di d2 didi dis di6 dio di di d di4 dis di dao dai da2 d 3 da das da dio da d 2 d3 dai ds di (a)D (b)D dio di di di di dis di d 2 d2 d2 d2 d2 小结 设计并行算法是一件复杂的事,而并行算法的设计这门学科还属于发展中的一门 学科,所以目前尚无一套普遍适用的、系统的设计方法学。本章只是给出一个非 常一般的并行算法的设计方法,它不可能也不应该视为设计并行算法的全部方 法。重要的是,通过所介绍的设计方法的学习,希望读者能从中得到更多的启迪, 补充更多的算例,丰富、完善乃至开拓出更新更好的设计方法
(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 endif endif End ① 令 T = abaababaababaababababa。P = abaababa，试计算 WIT(i)； ② 试考虑 P=6，q=9 的竞争情况。 5、 对于图 5.2(a)的加权有向图，试用算法 5.5，逐步求出 D2，D4 和 D8 中各元素 k ij d ： 2 66 2 65 2 64 2 63 2 62 2 61 2 60 2 16 2 15 2 14 2 13 2 12 2 11 2 10 2 06 2 05 2 04 2 03 2 02 2 01 2 00 d d d d d d d d d d d d d d d d d d d d d 2 66 2 65 2 64 2 63 2 62 2 61 2 60 2 16 2 15 2 14 2 13 2 12 2 11 2 10 2 06 2 05 2 04 2 03 2 02 2 01 2 00 d d d d d d d d d d d d d d d d d d d d d (a) D2 (b) D4 2 66 2 65 2 64 2 63 2 62 2 61 2 60 2 16 2 15 2 14 2 13 2 12 2 11 2 10 2 06 2 05 2 04 2 03 2 02 2 01 2 00 d d d d d d d d d d d d d d d d d d d d d (a) D8 小结 设计并行算法是一件复杂的事，而并行算法的设计这门学科还属于发展中的一门 学科，所以目前尚无一套普遍适用的、系统的设计方法学。本章只是给出一个非 常一般的并行算法的设计方法，它不可能也不应该视为设计并行算法的全部方 法。重要的是，通过所介绍的设计方法的学习，希望读者能从中得到更多的启迪， 补充更多的算例，丰富、完善乃至开拓出更新更好的设计方法