中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 第九章稠密矩阵运算 9.1矩阵的划分 92矩阵转置 9.3矩阵-向量乘法 94矩阵乘法
第九章 稠密矩阵运算 9.1 矩阵的划分 9.2 矩阵转置 9.3 矩阵-向量乘法 9.4 矩阵乘法
中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 9.3矩阵-向量乘法 9.3.1带状划分的矩阵-向量乘法 9.3.2棋盘划分的矩阵-向量乘法
9.3 矩阵-向量乘法 9.3.1 带状划分的矩阵-向量乘法 9.3.2 棋盘划分的矩阵-向量乘法
中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 带状划分的矩阵-向量乘法 划分(行带状划分):P存放X和a10,a1,…,atn1,并输出y ■算法:对p=n情形 ①每个P向其他处狸器播送×(多到多播送); ②每个P计算; ■注:对p<n情形,算法中P要播送X中相应的冂/P个分量 )超立方连接的计算时间 心+ t, log p+-1(P-1)∥前1项是乘法时间,后2项是多到多的播送时间 +t,logp+mt1∥p充分大时 (2)网孔连接的计算时间 Tn=+2(Vp-1)+t(p-1)∥前项是乘法时间,后2项是多到多的播送时间 21,(p-1)+mtn∥p充分大时 国家高性能计算中心(合肥 2021/2/19 20
国家高性能计算中心（合肥） 20 2021/2/19 带状划分的矩阵-向量乘法 ▪ 划分(行带状划分): Pi存放xi和ai,0,ai,1,…,ai,n-1 , 并输出yi ▪ 算法: 对p=n情形 ①每个Pi向其他处理器播送xi (多到多播送)； ②每个Pi计算； ▪ 注: 对p<n情形,算法中Pi要播送X中相应的n/p个分量 (1)超立方连接的计算时间 (2)网孔连接的计算时间 充分大时 前 项是乘法时间，后 项是多到多的播送时间 t p nt p p n t p p n t p p n T s w p s w log // log ( 1) // 1 2 2 2 = + + = + + − 充分大时 前 项是乘法时间，后 项是多到多的播送时间 t p nt p p n t p p n p t p n T s w p s w 2 ( 1) // 2( 1) ( 1) // 1 2 2 2 = + − + = + − + −
中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 带状划分的矩阵-向量乘法 矩阵A 向量x 处理器 ■示例 P n/p (a) (b) 矩阵A 向量 Pn回 (c) (d) 国家高性能计算中心(合肥 9?2/19
国家高性能计算中心（合肥） 21 2021/2/19 带状划分的矩阵-向量乘法 ▪ 示例 矩阵 A 0 1 p-1 n/p 向量 x 处理器 0 1 p-1 n (a) (b) 0 0 0 0 0 1 1 1 1 1 p-1 矩阵 A 0 1 p-1 向量 y (c) (d) 图9.8 P0 P1 Pp-1 P0 P1 Pp-1 P0 P1 Pp-1 P0 P1 Pp-1 p-1 p-1 p-1 p-1
中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 9.3矩阵-向量乘法 9.3.1带状划分的矩阵-向量乘法 9.3.2棋盘划分的矩阵-向量乘法
9.3 矩阵-向量乘法 9.3.1 带状划分的矩阵-向量乘法 9.3.2 棋盘划分的矩阵-向量乘法