并行算法的一般设计策略

第五章并行算法的一般设计策略习题例题：1、令n是待排序的元素数，p＝2d是d维超立方中处理器的数目。假定开始随机选定主元x，并将其播送给所有其他处理器，每个处理器按索接收到的x，对其n/p个元素按照≤x和＞x进行划分，然后按维进行交换。这样在超立方上实现的快排序算法如下：算法5.6超立方上快排序算法输入：n个元素，B=n/p,d=logp输出：按超立方编号进行全局排序Begin(1)id=processor’slabel(2)fori=1toddo(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∪Celse(i)沿第i维发送B1给其邻者(ii)C=沿第i维接收的子序列(iii)B=B2∪Cendifendfor(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之一不存在）Beginifp=nullthenduel=qelseifq=nullthenduel=pelse(1)j=q-p+1(2)w=WIT(j)(3)ifT(q+w-1)≠P(w)then(i)WIT(q)=w(ii)duel=pelse(i)WIT(p)=q–p+1(ii)duel=qendifendifEnd①令T=abaababaababaababababa。P=abaababa，试计算WIT(i)；②试考虑P=6，q=9的竞争情况。5、对于图5.2(a)的加权有向图，试用算法5.5，逐步求出D2，D4和D8中各元素kijd：266265264263262261260216215214213212211210206205204203202201200ddddddddddddddddddddd266265264263262261260216215214213212211210206205204203202201200ddddddddddddddddddddd(a)D2(b)D4266265264263262261260216215214213212211210206205204203202201200ddddddddddddddddddddd(a)D8小结设计并行算法是一件复杂的事，而并行算法的设计这门学科还属于发展中的一门学科，所以目前尚无一套普遍适用的、系统的设计方法学。本章只是给出一个非常一般的并行算法的设计方法，它不可能也不应该视为设计并行算法的全部方法。重要的是，通过所介绍的设计方法的学习，希望读者能从中得到更多的启迪，补充更多的算例，丰富、完善乃至开拓出更新更好的设计方法。