《并行计算作业参考解答.ppt》由会员分享，可在线阅读，更多相关《并行计算作业参考解答.ppt（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、并行计算作业参考解答5.10 对图5.3所示的单位权有向图，试用布尔邻接矩阵乘法求出其传递闭包。A+I=A+=(A+I)2)2=(A+I)4=1.A是一个大小为n的布尔数组，欲求出最小的下标i且Ai为真，试设计一个常数时间的PRAM-CRCW并行算法。如果使用PRAM-CREW模型，运行时间如何？n2个处理器1.copy A1.n to B1.n/O(1)2.for i=1 to n par-do if Bi=true then/O(1)for j=i+1 to n par-do Bj=false/O(1)endforendif endfor3.for i=1 to n par-doif Bi
2、=true then /O(1)return iendifendforPRAM-CRCW下的时间复杂度为:O(4)PRAM-CREW下第2步Bi=false不能同时写，需要O(n)的时间来写试用分治策略或划分技术设计一个试用分治策略或划分技术设计一个算法求数组算法求数组A1.n的最小元素，要的最小元素，要求用求用O(n/logn)个处理器，时间复个处理器，时间复杂度为杂度为O(logn)。1.采用均匀划分，每个处理器分配logn个元素，求出本处理器中的最小元素时间为：log(log n)。共得到n/logn个局部最小元素。2.对n/logn个局部最小元素用平衡二叉树的算法求最小值（类似算法6.
3、8）。时间为：log(n/log n)=log n-log(log n)3.总的时间为log(log n)+log(n/log n)=log(n)题目11.7(a)A0j=a0+a2wn/2j+a4wn/2j2+an-2wn/2j(n/2-1)A1j=a1+a3wn/2j+a5wn/2j2+an-1wn/2j(n/2-1)其中(wn/2)n/2=1 Bj=a0+a1wnj+a2wnj2+an-1wnj(n-1)其中(wn)n=1 利用wn/2j=wnj2,wnj(n/2)=-1可得：Bj=A0j+wnjA1jBj+n/2=A0j+wnj+n/2A1j=A0j-wnjA1j(b)1.递归策略不同 2.参数传递 vs 返回值 3.步骤（7）中的迭代为算法11.2的一 半(c)谢谢大家！课堂练习1.试画出基于Batcher比较器的双调序列（8，6，4，2，0，1，3，5）的双调归并排序网络，并标出每个Batcher比较器的输入和输出数据。2.给出矩阵A和B的Cannon矩阵乘法的具体计算过程。A=B=