中国科学技术大学：《并行计算 Parallel Computing》课程教学资源（习题）第九章 稠密矩阵运算

第九章稠密矩阵运算 习题例题: 1、根据9.3.2节所讨论的矩阵-向量乘法,试证明:在p个处理器的超立方上 用SF选路方法进行矩阵ˉ向量乘法,其并行运行时间约为 n/p+t, log p+(3/2)t,(n/p)log p 2、试证明:在超立方上,并行分块矩阵算法和 Cannon乘法的等效率函数约为 f(p)=O(p32);而Fox乘法的等效率函数为f(p)=O(p32logp) 3、根据94.3节所讨论的Fox函数: (1)试写出Fox乘法的形式描述 (2)试分析Fox乘法的主要优点是什么。 4、算法9.7给出了n的平方个处理器的并行系统上用 PRAM-CREW模型施行两个n*n矩阵 相乘的算法。假定存储器的读写事件为t,两个元素的乘加时间为t。试分析该算法 的并行运行时间 算法97PRAM-CREW上矩阵相乘算法 输入:A,xn,Bn× 输出:Cnx (1)将n2个处理器组织成nXn的网孔 (2)for each P.do (2.1)c1,=0 (2.2for k=0 to n-1 do Cii -Cr. b endfor endfor 5、参照图9.14,算法98描述了m*二维 systolic阵列上实现Antn*Bnk=Cmk的 矩阵乘法,它是采用流水线原理,通过在时间上延迟矩阵元素的办法来达到一对下标 合宜的矩阵元素适时相乘的目的

第九章 稠密矩阵运算 习题例题： 1、根据 9.3.2 节所讨论的矩阵-向量乘法，试证明：在 p 个处理器的超立方上， 用 SF 选路方法进行矩阵 - 向量乘法，其并行运行时间约为 n / p t s log p (3/ 2)tw (n/ p)log p 2 + + 。 2、试证明：在超立方上，并行分块矩阵算法和 Cannon 乘法的等效率函数约为 ( ) ( ) 3/ 2 f E p = O p ；而 Fox 乘法的等效率函数为 ( ) ( log ) 3/ 2 f E p = O p p 。 3、根据 9.4.3 节所讨论的 Fox 函数： （1） 试写出 Fox 乘法的形式描述； （2） 试分析 Fox 乘法的主要优点是什么。 4、 算法 9.7 给出了n 的平方个处理器的并行系统上用 PRAM-CREW 模型施行两个 n*n 矩阵 相乘的算法。假定存储器的读写事件为 a t ，两个元素的乘-加时间为 c t 。试分析该算法 的并行运行时间。 5、参照图 9.14，算法 9.8 描述了 m*k 二维 systolic 阵列上实现 Am*n * Bn*k =Cm*k 的 矩阵乘法，它是采用流水线原理，通过在时间上延迟矩阵元素的办法来达到一对下标 合宜的矩阵元素适时相乘的目的

算法98SMD-MC2上 Systolic矩阵相乘算法 输入:Am×n,B2×k 输出:在P,中存有乘积矩阵元素cy Be for i=1 to m par i to k 0 (2) while p收到a和b时do (2.1) 十a (22fi< m then发送b给P+1, endif (2.3)j<kthm发送a给P,+1endf erewhile endor b b b 12345 b bbbbb b b b a11a12a13414a5 ao a22 A23 a 33a34 3,L 2 4,2 图914矩阵A和B的输入加载方式

试问①为了确保a1与b适时在P,相遇矩阵的第i行要比第i1行(2≤i≤m)滞后多少 时间单位?同样B矩阵的第j列要比第j一1列(2≤j≤k)的滞后多少时间单位? ②当jk时,a传送给P,+1吗?当=m时b传送给P1,吗?

试问:①为了确保 i s a , 与 s j b , 适时在 Pi, j 相遇矩阵的第 i 行要比第 i-1 行（2≤i≤m）滞后多少 时间单位?同样,B 矩阵的第 j 列要比第 j 一 1 列(2≤j≤k)的滞后多少时间单位? ②当 j=k 时,a 传送给 Pi, j+1 吗?当 i=m 时.b 传送给 Pi+1, j 吗?