中国科学技术大学：《并行计算 Parallel Computing》课程教学资源（PPT课件讲稿）第三篇 并行数值算法 第九章 稠密矩阵运算

中国料学火计算机科学与波术系 diversity of and Technology 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 91矩阵的划分 91.1带状划分 91.2棋盘划分

9.1 矩阵的划分 9.1.1 带状划分 9.1.2 棋盘划分

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 带状划分 16×16阶矩阵,p=4 P P 4 5 0123456789101112131415 14 7 (b 列块带状划分图 行循环带状划分 国家高性能计算中心(合肥 2021/2/19

国家高性能计算中心（合肥） 5 2021/2/19 带状划分 ▪ 16×16阶矩阵，p=4 列块带状划分 行循环带状划分 P P P P 0 4 8 12 1 5 9 13 2 6 10 14 3 7 11 15 P P P P ( a ) ( b ) 图9.1 0 1 2 3 3 2 1 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 带状划分 示例:p=3,27×27矩阵的3种带状划分 (a)block (b)cyclic (c)block-cyclic Striped row-major mapping of a 27 X 27 matrix on p=3 processors 国家高性能计算中心(合肥 2021/2/19

国家高性能计算中心（合肥） 6 2021/2/19 带状划分 ▪ 示例：p＝3，27× 27矩阵的3种带状划分

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 91矩阵的划分 91.1带状划分 91.2棋盘划分

9.1 矩阵的划分 9.1.1 带状划分 9.1.2 棋盘划分

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 棋盘划分 8×8阶矩阵,p=16 (0,0)(0,1)(0,2)(0,3)(0,4)(0,5)(0,6)(0,7) (0,0)(0,4)|(0,1)(0,5)(0,2)(0,.6)(0,3)(0,7) P P PI (1,0)(1,1)(,2)(,3)(1,4)(1,5)(1,6)(1,7) (4,0)(4,4)(4,1)(4,5)(4,2)(4,.6)(4,3)(4,7) (2,0)(2,1)(2,2)(2,3)(2,4)(2,5)(2,6)(2,7 (1,0)(1,4)(1,1)(1,5)(1,2)(1,6)(1,3)(1,7) P P P P P6 P7 (3,0)(3,1)(3,2)(3,3)(3,4)(3,.5)(3,6)(3,7) (5,0)(5,4)(5,1)(5,5)k5,2)(6,.6)(5,3)(5,7) (4,0)(4,1)(4,2)(4,3)(4,4)(4,5)(4,6)(4,7) (2,0)(2,4)(2,1)(2,5)k2,2)(2,6)(2,3)(2,7) 1 Pg 5,0)(1)(6,2)(5,3)|(4)(5,5)66)67) (6,0)(6,4)(6,1)(6,5)(6,2)(6,6)(6,3)(6,7) (6,0)(6,1)(6,2)(6,3)(6,4)(6,5)(6,6)(6,7) (3,0)(3,4)(3,1) 5)(3,2)(3,6)(3,3)(3,7) P1 P P P (7,0)(7,1)(7,2)(7,3)(7,4)(7,5)(7,6)(7,7) (7,0)(7,4)(7,1)(7,5)(7,2)(7,6)(7,3)(7,7) 块棋盘划分 图9.2 循环棋盘划分 国家高性能计算中心(合肥 2021/2/19

国家高性能计算中心（合肥） 8 2021/2/19 棋盘划分 ▪ 8×8阶矩阵，p=16 块棋盘划分 循环棋盘划分 ( a ) ( b ) 图9.2 6 10 14 7 11 15 4 8 12 5 9 13 6 10 14 (0,0) (1,0) (2,0) (3,0) (5,0) (4,0) (7,0) (6,0) (0,1) (1,1) (2,1) (3,1) (5,1) (4,1) (7,1) (6,1) (0,2) (1,2) (2,2) (3,2) (5,2) (4,2) (7,2) (6,2) (0,3) (1,3) (0,4) (1,4) (2,3) (3,3) (2,4) (3,4) (5,3) (4,3) (5,4) (4,4) (7,3) (6,3) (7,4) (6,4) (0,5) (1,5) (0,6) (1,6) (2,5) (3,5) (2,6) (3,6) (5,5) (4,5) (5,6) (4,6) (7,5) (6,5) (7,6) (6,6) (0,7) (1,7) (2,7) (3,7) (5,7) (4,7) (7,7) (6,7) (0,0) (2,0) (3,0) (5,0) (4,0) (7,0) (6,0) (1,0) (6,1) (1,1) (0,4) (1,4) (2,1) (3,1) (2,4) (3,4) (5,1) (4,1) (5,4) (4,4) (7,4) (7,1) (6,4) (0,1) (1,2) (0,5) (1,5) (2,2) (3,2) (2,5) (3,5) (5,2) (4,2) (5,5) (4,5) (7,2) (6,2) (7,5) (6,5) (0,2) (1,3) (0,6) (1,6) (2,6) (2,3) (3,6) (5,3) (4,3) (5,6) (4,6) (7,3) (6,3) (7,6) (6,6) (0,3) (3,3) (0,7) (1,7) (2,7) (3,7) (5,7) (4,7) (7,7) (6,7) 3 7 11 15 0 4 8 12 1 5 9 13 P P P2 P3 P0 P1 P2 P P P P P P P P P P P P P P P P P P P P P P P P P

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 棋盘划分 示例:P=4,16×16矩阵的3种棋盘划分 P (a) block (b)cyclic (c)block cyclic Checkerboard mapping of a 16 x 16 matrix on p=2 X 2 processors 国家高性能计算中心(合肥 2021/2/19

国家高性能计算中心（合肥） 9 2021/2/19 棋盘划分 ▪ 示例：p＝4，16×16矩阵的3种棋盘划分

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 第九章稠密矩阵运算 9.1矩阵的划分 9.2矩阵转置 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 92矩阵转置 9.2.1棋盘划分的矩阵转置 9.2.2带状划分的矩阵转置

9.2 矩阵转置 9.2.1 棋盘划分的矩阵转置 9.2.2 带状划分的矩阵转置

中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 棋盘划分的矩阵转置 ■网孔连接 情形1:pP=n2 (0,0) (0,1) (0,0) (1,0)(2,0) (3,0) (1,3) P Pe P P P P (2,0) (2,3) (3,2) 10 P P (3,0) (3,2) (3,3) (0,3) (1,3) (3,3) P15 通讯步 转置后 图9.3 国家高性能计算中心(合肥 2021/2/19 12

国家高性能计算中心（合肥） 12 2021/2/19 棋盘划分的矩阵转置 ▪ 网孔连接 ▪ 情形1: p=n2 。 通讯步 转置后 P (3,0) (1,0) (1,2) (1,3) (2,0) (2,1) (2,3) P (3,1) P (3,2) P P P P ( a ) ( b ) 图9.3 (0,0) (0,1) (0,2) (0,3) (1,0) (1,1) (1,2) (1,3) (2,0) (2,1) (2,2) (2,3) (3,0) (3,1) (3,2) (3,3) (0,1) (0,2) (0,3) P (0,0) (1,1) (2,2) (3,3) 3 7 11 15 2 6 10 14 1 5 9 12 13 0 4 8 3 7 11 15 2 6 14 10 1 9 13 5 P P P P P P P P P P P P P P P P P P P P P P P P 12 P 4 8 0