单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,*,《,并行计算,》,作业参考解答,,,,,5.10,对图,5.3,所示的单位权有向图，试用布尔邻接矩阵乘法求出其传递闭包A+I=,,,,A,+,=((A+I),2,),2,=(A+I),4,=,,,,A,是一个大小为,n,的布尔数组，欲求出最小的下标,i,且,A[i,],为真，试设计一个常数时间的,PRAM-CRCW,并行算法如果使用,PRAM-CREW,模型，运行时间如何？,,,,n,2,个处理器,1. copy A[1..n] to B[1..n],//O(1),,2. for i=1 to n par-do if,B[i,]=true then//O(1),,for j=i+1 to n par-do,B[j,]=false //O(1),endfor,,,endif,,,endfor,,3. for i=1 to n par-do,,if,B[i,]=true then //O(1) return i,,,endif,,,endfor,PRAM-CRCW,下的时间复杂度为,:O(4),,PRAM-CREW,下第,2,步,B[i,]=false,不能同时写，需要,O(n,),的时间来写,,,,,试用分治策略或划分技术设计一个算法求数组,A[1..n],的最小元素，要求用,O(n/logn,),个处理器，时间复杂度为,O(logn,),。
1.,采用均匀划分，每个处理器分配,logn,个元素，求出本处理器中的最小元素时间为：,log(log,n),共得到,n/logn,个局部最小元素2.,对,n/logn,个局部最小元素用平衡二叉树的算法求最小值（类似算法,6.8,）时间为：,log(n,/log n)=log n -,log(log,n),,3.,总的时间为,log(log,n) +,log(n,/log n) =,log(n,),,题目,11.7,,(a)A,[0],j,=a,0,+a,2,w,n/2,j,+a,4,w,n/2,j·2,+…+a,n-2,w,n/2,j·(n/2-1),A,[1],j,=a,1,+a,3,w,n/2,j,+a,5,w,n/2,j·2,+…+a,n-1,w,n/2,j·(n/2-1),其中,(w,n/2,),n/2,,= 1,B,j,=a,0,+a,1,w,n,j,+a,2,w,n,j·2,+…+a,n-1,w,n,j·(n-1),其中,(,w,n,,),n,,= 1,利用,w,n/2,j,=,,w,n,j·2,,,,w,n,j·(n/2),= -1,可得：,,B,j,=A,[0],j,+w,n,j,A,[1],j,B,j+n/2,=A,[0],j,+w,n,j+n/2,A,[1],j,=A,[0],j,-w,n,j,A,[1],j,,(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=,,,,。
