中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 棋盘划分的矩阵转置 情形2:p<n2 划分:An划分成D个大小如×1子块 P 算法:①桉me连接进行块转置(不同处理器)∥2yp(4+4n2/p)-通讯 ②进行块内转置(同一处理器内) 计算 Tn=nn+2、P+21,n2/√P…运行时间 2p 2 o)(0.|02(3)0.4(05)06(07 0)x(01)(20,(21)(40x(41)(60x(61 P P P P3 PI P2 (1.o)(.1)(.2)(1,3)(a,4)(15a,6)a1, (1,0)(,1)(3,0)*(3,1)(5,0)x(5,1)(7,0)(7,1) (2,0)(2,1)(2,2)(2,3)(2,4)(2,5)(2,6)(2, 0n2),(0.3)(22)x(2,3)(42)x(4,3)(6,2)x(63) P4 P P4 P (3,0)1(3,1)(3,2)(3,3)(3,4)(3,5)(3,6)(3,7) (1,2)(,3)(3,2)*(3,3)(5,2)x(5,3)(7,2)“(7,3) (4,0)(4,1)(4,2)(4,3)(434)(4,5)(4,6)(,7) 4)x(.5)(2,4)x(2,5)(4,4)x(4,5)(6,4)x(6,5) P10 lI P P (5,0)(5,1)(5,2)(5,3)|(5,4)(5,5)(5,6)( (1,4)“(1,5)(3,4)“(3,5)(5,4)“(5,5)(7,4)“(7,5) (6,0)(6,1)(6,2)(6,3)(6,4)(6,5)(616)|(6, (06)x(0,7(2.6),(2.7)(4,6)x(,7)(6.6)x(6,7 P P P (7,0)(7,1)(7,2)(7,3)(7,4)(7,5)(7,6)(, (1,6)“(1,7)(3,6)“(3,7)(5,6)*(5,7)(7,6)“(7,7 通讯步 转置后 国家高性能计算中心(合肥 2021/2/19 图9.4
国家高性能计算中心（合肥） 13 2021/2/19 棋盘划分的矩阵转置 ▪ 情形2: p<n2 。 - 划分: - 算法: ①按mesh连接进行块转置(不同处理器间) ②进行块内转置(同一处理器内) 通讯步 转置后 P P P P P P P P P P P P ( b ) ( a ) 图9.4 P P P P P P P P P P P P P P P P 0 4 8 12 1 5 9 13 2 6 10 14 3 7 11 15 (0,0) (1,0) (0,2) (1,2) (1,4) (0,4) (1,6) (0,6) (0,1) (1,1) (0,3) (1,3) (1,5) (0,5) (1,7) (0,7) (2,0) (3,0) (2,2) (3,2) (3,4) (2,4) (3,6) (2.6) (2,1) (3,1) (2,3) (3,3) (3,5) (2,5) (3,7) (2,7) (4,0) (5,0) (4,2) (5,2) (5,4) (4,4) (5,6) (4,6) (4,1) (5,1) (4,3) (5,3) (5,5) (4,5) (5,7) (4,7) (6,0) (7,0) (6,2) (7,2) (7,4) (6,4) (7,6) (6,6) (6,1) (7,1) (6,3) (7,3) (7,5) (6,5) (7,7) (6,7) 4 8 12 P0 P 1 5 9 13 P 2 6 10 14 P 3 7 11 15 (1,0) (2,0) (3,0) (5,0) (4,0) (7,0) (6,0) (0,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) (2,3) (3,3) (5,3) (4,3) (7,3) (6,3) (0,4) (1,4) (2,4) (3,4) (5,4) (4,4) (7,4) (6,4) (0,5) (1,5) (2,5) (3,5) (5,5) (4,5) (7,5) (6,5) (0,6) (1,6) (2,6) (3,6) (5,6) (4,6) (7,6) (6,6) (0,7) (1,7) (2,7) (3,7) (5,7) (4,7) (7,7) (6,7) Ann划分成p个大小为n p n p 子块 // 2 p(t s +t w n 2 / p)通讯 计算 p n 2 // 2 t p t n p运行时间 p n Tp s w 2 2 / 2 2 2 = + +
中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 棋盘划分的矩阵转置 ■超立方连接 划分:A,划分成p个大小为几×1子块 算法: ①将A44转置对4 21 ②对A递通归应用①迸行转置,直至分块矩阵的元素处于同一处理器; ⑦进行同一处理器的内部转置。 ■运行时间: +2(+1")og√p∥内部转置,选路9b)递归步:gvp P P P (ts +t )log p 2p 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 14 2021/2/19 棋盘划分的矩阵转置 ▪ 超立方连接 ▪ 划分: ▪ 算法: ① ②对Aij递归应用①进行转置，直至分块矩阵的元素处于同一处理器； ③进行同一处理器的内部转置。 ▪ 运行时间: Ann划分成p个大小为n p n p 子块 p p n t t p n p p n t t p n p p n t t p n T s w p s w s w )log 2 2 ) log 2 2 )log // 2 2 2 2 2 2 2 = + + = + + + （ （ 内部转置 ，选路：（ ，递归步： 12 22 11 21 21 22 11 12 A A A A A A A A 将A＝ 转置为
中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 棋盘划分的矩阵转置 ■超立方连接:示例 (0.0)(0,1)|(0,2)(0.3)|(0.4)(0.5)(o.,6)(0 (0,0)(0,1)(0,2)(0,3)(4,0)(4,1)(4.2)(4.3) Po PI P2 P3 PI P3 (1.0)/(1,1)(1.2)A1.3)(1.4(1.5)(n,6)(1,7) 1.0)A1),2)0.360)62(53 (20)(2,1)「(2,2)(2,3)(6,0(6,1)「(6 P PA P5 P (3.0)3.1)(.2)\3.3)(3.4/8.5)(3.6/(8. (30)(3,1)(3.2)(3.3)(7.0)(7.)(7.2)(.3 40)/41)(42)/N43) (45)《46\(47 (0.4)(0,5)(0.6)(0.7)(4.4)(4,5)(4.6) F Ps : Pu (5,0)(5,1)(5,2)\(5.3)(5.4)/(5,5)(5,6)/(5,7) (1,4) 5)(1,6)1(1,7)(5,4)A5,5)( (24)(25(262.(4)(6.5)6967) P P PI (7,0)(7,1)(7,2)(7.3)(7.4)(7.5)(7,6)(7,7) (3,4)(3,5)(3,6)(3.7)(7.4)(7.5)(7,6)(7.7) 国家高性能计算中心(合肥 2021/2/19 15
国家高性能计算中心（合肥） 15 2021/2/19 棋盘划分的矩阵转置 ▪ 超立方连接：示例 (0,5) (1,5) P P P (2,5) (3,5) P P P P (5,5) (4,5) P P P P (7,5) (6,5) P (0,0) (0,1) (1,0) (1,1) (0,2) (0,3) (1,2) (1,3) P (0,4) (0,5) (1,4) (1,5) P (0,6) (0,7) (1,6) (1,7) P (2,0) (2,1) (3,0) (3,1) P (2,2) (2,3) (3,2) (3,3) P (2,4) (2,5) (3,4) (3,5) P (2,6) (2,7) (3,6) (3,7) (5,0) (5,1) (4,0) (4,1) (5,2) (5,3) (4,2) (4,3) P (5,4) (5,5) (4,4) (4,5) P (5,6) (5,7) (4,6) (4,7) P (7,0) (7,1) (6,0) (6,1) P (7,2) (7,3) (6,2) (6,3) P (7,4) (7,5) (6,4) (6,5) P (7,6) (7,7) (6,6) (6,7) (a) (b) 图9.6 0 4 8 12 1 5 9 2 6 10 14 3 7 11 15 0 8 4 12 1 9 5 13 6 2 10 14 7 3 11 15 (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) P P P P P P P P (0,2) (1,2) (2,2) (3,2) (5,2) (4,2) (7,2) (6,2) (0,3) (1,3) (2,3) (3,3) (5,3) (4,3) 13 (7,3) (6,3) (0,4) (1,4) (2,4) (3,4) (5,4) (4,4) (7,4) (6,4) (0,6) (1,6) (2,6) (3,6) (5,6) (4,6) (7,6) (6,6) (0,7) (1,7) (2,7) (3,7) (5,7) (4,7) (7,7) (6,7)
中国料学火计算机科学与波术系 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 带状划分的矩阵转置 划分:An×n分成P个n/p)×n大小的带 P P1 P2 算法 图9.7 ①Pi有p-1个(/p)×(n/)大小子块发送到另外p-1个处理器中; ②每个处理器本地交换相应的元素 国家高性能计算中心(合肥 2021/2/19 17
国家高性能计算中心（合肥） 17 2021/2/19 带状划分的矩阵转置 ▪ 划分: An×n分成p个(n/p)×n大小的带 ▪ 算法: ①Pi有p-1个(n/p)×(n/p)大小子块发送到另外p-1个处理器中; ②每个处理器本地交换相应的元素 P P P P n 图9.7 0 1 2 3