稠密矩阵运算

  • 格式:doc
  • 大小:46.00 KB
  • 文档页数:3

第九章 稠密矩阵运算

习题例题:

1、根据9.3.2节所讨论的矩阵-向量乘法,试证明:在p个处理器的超立方上,用SF选路方法进行矩阵-向量乘法,其并行运行时间约为ppntptpnwslog)/()2/3(log/2。

2、试证明:在超立方上,并行分块矩阵算法和Cannon乘法的等效率函数约为)()(2/3pOpfE;而Fox乘法的等效率函数为)log()(2/3ppOpfE。

3、根据9.4.3节所讨论的Fox函数:

(1) 试写出Fox乘法的形式描述;

(2) 试分析Fox乘法的主要优点是什么。

4、 算法9.7给出了n的平方个处理器的并行系统上用PRAM-CREW模型施行两个n*n矩阵相乘的算法。假定存储器的读写事件为at,两个元素的乘-加时间为ct。试分析该算法的并行运行时间。

5、参照图9.14,算法9.8描述了m*k二维systolic阵列上实现nmA**knB*=kmC*的

矩阵乘法,它是采用流水线原理,通过在时间上延迟矩阵元素的办法来达到一对下标

合宜的矩阵元素适时相乘的目的。

试问:①为了确保sia,与jsb,适时在jiP,相遇矩阵的第i行要比第i-1行(2≤i≤m)滞后多少时间单位?同样,B矩阵的第j列要比第j一1列(2≤j≤k)的滞后多少时间单位?

②当j=k时,a传送给1,jiP吗?当i=m时.b传送给jiP,1吗?