并行算法设计与分析考题与答案VIP免费

1 《并行算法设计与分析》考题与答案 一、1.3，处理器PI 的编号是： 解：对于n × n 网孔结构,令位于第 j 行，第 k 列（0≤j，k≤n-1）的处理器为Pi（0≤i≤n2-1）。 以 16 处理器网孔为例,n=4（假设j、k 由 0 开始）： 由 p0=p(j,k)=p(0,0) P8=p(j,k)=p(2,0) P1=p(j,k)=p(0,1) P9=p(j,k)=p(2,1) P2=p(j,k)=p(0,2) P10=p(j,k)=p(2,2) P3=p(j,k)=p(0,3) P11=p(j,k)=p(2,3) P4=p(j,k)=p(1,0) P12=p(j,k)=p(3,0) P5=p(j,k)=p(1,1) P13=p(j,k)=p(3,1) P6=p(j,k)=p(1,2) P14=p(j,k)=p(3,2) P7=p(j,k)=p(1,3) P15=p(j,k)=p(3,3) 同时观察 i 和 j、k 之间的关系，可以得出 i 的表达式为：i= j * n+k 2 一、1.6 矩阵相乘（心动算法） a)相乘过程 设 A 矩阵=1212211221214321 B 矩阵=1234432121211212 【注】矩阵元素中 A(i,l)表示自左向右移动的矩阵，B(l,j)表示自上向下移动的矩阵，黑色倾斜加粗标记表示已经计算出的矩阵元素,如 12, C(i,j)= C(i,j)+ A(i,l)* B(l,j) 1、 2、 A(i,l) B(l,j) C(i,j) 12 A(1,1) B(1,1) C(1,1) 1 2 2 C(1,2) 0 C(1,3) 0 C(1,4) 0 C(2,1) 0 C(2,2) 0 C(2,3) 0 C(2,4) 0 C(3,1) 0 C(3,2) 0 C(3,3) 0 C(3,4) 0 C(4,1) 0 C(4,2) 0 C(4,3) 0 C(4,4) 0 A(1,2) B(3,1) C(1,1) 2 1 4 A(1,1) B(1,2) C(1,2) 1 1 1 C(1,3) 0 C(1,4) 0 A(2,1) B(1,1) C(2,1) 1 2 2 C(2,2) 0 C(2,3) 0 C(2,4) 0 C(3,1) 0 C(3,2) 0 C(3,3) 0 C(3,4) 0 C(4,1) 0 C(4,2) 0 C(4,3) 0 C(4,4) 0 3 3、 4、 A(1,3) B(3,1) C(1,1) 3 1 7 A(1,2) B(2,2) C(1,2) 2 2 5 A(1,1) B(1,3) C(1,3) 1 2 2 C(1,4) 0 A(2,2) B(2,1) C(2,1) 1 2 4 A(2,1) B(1,2) C(2,2) 1 1 1 C(2,3) 0 C(2,4) 0 A(3,1) B(1,1) C(3,1) 2 2 4 C(3,2) 0 C(3,3) 0 C(3,4) 0 C(4,1) 0 C(4,2) 0 C(4,3) 0 C(4,4) 0 A(1,4) B(4,1) C(1,1) 4 4 23 A(1,3) B(3,2) C(1,2) 3 2 11 A(1,2) B(2,3) C(1,3) 2 1 4 A(1,1) B(1,4) C(1,4) 1 1 1 A(2,3) B(3,1) C(2,1) 1 1 5 A(2,2) B(2,2) C(2,2) 2 2 5 A(2,1) B(1,3) C(2,3) 1 2 2 C(2,4) 0 A(3,2) B(2,1) C(3,1) 1 1 5 A(3,1) B(1,2) C(3,2) 2 1 2 C(3,3) 0 C(3,4) 0 A(4,1)...