习题解答
第二次作业 2.5 直径为从全0的节点到全1的节点的距离，为k 2019/1/2
第二次作业 对剖宽度： k为奇数时： 将节点可分为两组，一组中N(0)>N(1),设为A组，一组 N(0)<N(1)，设为B组。对剖宽度即为A组和B组之间的边的数量。 由于每次最多只能增加或减少1个1，因此只需考虑边界条件， 即A组的N(0)=N(1)+1和B组N(1)=N(0)+1 在A组边界条件中，与B组相连的节点一定以0开头。这样的节 点数目为： 同理，B组中的节点数目也为 即对剖宽度为2* 2019/1/2
第二次作业 k为偶数时： 与k为奇数时相比，增加了一组 k为偶数时，除了①中两组，还有一组N(0)=N(1)，设为C组。 将C组分为再分为两组，一组以0开头，设为C0，一组以1开头 设为C1。 其中满足红色和蓝色的连线的边的数量即为对剖宽度 从A到C0的连线，A中的节点需要满足的条件为：(1)开头是00 (2)N(0)=N(1)+2;。满足这两个条件的节点数为： 从C0到C1的连线，C0中的节点需要满足的条件为：开头是01。 满足条件的节点数也为 2019/1/2
第二次作业 即可求得对剖宽度为 4* 2019/1/2
节点度为4，网络直径为2n-1，对剖宽度为2n-1 2.6 节点度为4，网络直径为2n-1，对剖宽度为2n-1 2019/1/2
第二次作业 2.7 节点度为2和4，直径为2k，对剖宽度为2k 2019/1/2
(1)计算任务没有串行分量，由Amdahl定律得到的 加速比为 第三次作业 4.2(1)(2) (1)计算任务没有串行分量，由Amdahl定律得到的 加速比为 2019/1/2
(2)同样，没有串行分量时，由Gustafson定律计算 加速比为： 第三次作业 (2)同样，没有串行分量时，由Gustafson定律计算 加速比为： 2019/1/2
第三次作业 4.11 由Amdahl定律，列式： 解得： 2019/1/2
第四次作业 5.8 2019/1/2
第四次作业 节点中的数值代表该节点完成计算并发送局部和的时刻。 t = 28, p = 8, L = 5, o = 2, g = 4 P5: P0的远程子节点，t=(28-1)-9=18 P3,P2,P1: P5的兄弟节点，完成计算的时刻依次为14,10,6 P4: P3的远程子节点，t=(14-1)-9=4 P7: P5的远程子节点，t=(18-1)-9=8 P6: P7的兄弟节点，t=8-2*2=4 2019/1/2
第五次作业 15.3 for(i=0;i<10;i++) buff[i]=data[32*i]; MPI_Send(buff,10,MPI_FLOAT,dest,tag,MPI_COMM_WORLD); 有些人在第三个空填33*i，想太多了。这个间隔是头到头的 2019/1/2
第五次作业 随机生成针的端点和角度位置即可 2019/1/2
在PRAM-CRCW模型下，Hint提供了一个O(1)的算 法，使用n2个处理器 第六次作业 在PRAM-CRCW模型下，Hint提供了一个O(1)的算 法，使用n2个处理器 在PRAM-CREW模型下，由于写是互斥的，无法并 行地将B[j]的值置为false，需要重复n次实现，故时 间复杂度为O(n) 2019/1/2
第六次作业 1.copy A[1..n] to B[1..n] 2.for i=2 to n par-do B[i] = B[i] + B[i-1] endfor 3.for i=1 to n par-do if B[i] = 1 then return i endif 2019/1/2
第七次作业 循环1.2可以并行化。 2019/1/2
在PRAM-CREW模型上执行，进程数为p时，时间 复杂度为o(n2/p) 第七次作业 在PRAM-CREW模型上执行，进程数为p时，时间 复杂度为o(n2/p) Begin for i = n downto 1 do x[i] = b[i] / a[i][i] for j = 1 to i-1 par-do b[j] = b[j] - a[j][i] * x[i] a[j][i] = 0 endfor End 2019/1/2
第七次作业 7.10 2019/1/2
第七次作业 (1) 使用n2个进程时： 得t(n)=O((log n)2)，p(n)=n2 步骤(1)(4)(6)的时间复杂度为O(1) 步骤(2)(3)，对每个C(i)而言，使用n个进程可以在O(log n)时间内 求得相邻的最小顶点。 步骤(5)的时间复杂度为O(log n) 步骤(2)-(6)迭代log n 次 得t(n)=O((log n)2)，p(n)=n2 2019/1/2
第七次作业 (2) 步骤(1)执行后 步骤(2)-(6)第一次迭代 2019/1/2
第七次作业 步骤(2)-(6)第二次迭代 步骤(2)-(6)第三次迭代，保持不变 2019/1/2