第九章稠密矩阵运算 习题例题: 1、根据9.3.2节所讨论的矩阵-向量乘法,试证明:在p个处理器的超立方上, 用SF选路方法进行矩阵ˉ向量乘法,其并行运行时间约为 n2/p+t,logp+(3/2),(n/√p)gp。 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矩阵 相乘的算法。假定存储器的读写事件为L,两个元素的乘加时间为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 的 矩阵乘法，它是采用流水线原理，通过在时间上延迟矩阵元素的办法来达到一对下标 合宜的矩阵元素适时相乘的目的