现代密码学理论与实践之五

1、并 行 计 算第三篇 并行数值算法 第八章 基本通讯操作 第九章 稠密矩阵运算 第十章 线性方程组的求解 第十一章 快速傅里叶变换 第九章 稠密矩阵运算 9.1 矩阵的划分 9.2 矩阵转置 9.3 矩阵-向量乘法 9.4 矩阵乘法9.1 矩阵的划分 9.1.1 带状划分 9.1.2 棋盘划分 国家高性能计算中心（合肥）52022-4-10 带状划分国家高性能计算中心（合肥）62022-4-10 带状划分9.1 矩阵的划分 9.1.1 带状划分 9.1.2 棋盘划分 国家高性能计算中心（合肥）82022-4-10 棋盘划分国家高性能计算中心（合肥）92022-4-10 棋盘划分第九章 稠密矩阵

2、运算 9.1 矩阵的划分 9.2 矩阵转置 9.3 矩阵-向量乘法 9.4 矩阵乘法9.2 矩阵转置 9.2.1 棋盘划分的矩阵转置 9.2.2 带状划分的矩阵转置 国家高性能计算中心（合肥）122022-4-10 棋盘划分的矩阵转置国家高性能计算中心（合肥）132022-4-10 棋盘划分的矩阵转置子块划分成p个大小为Apnpnnn通讯)/(2/2pnttpws计算pn2/2运行时间pntptpnTwsp/22222国家高性能计算中心（合肥）142022-4-10 棋盘划分的矩阵转置子块划分成p个大小为ApnpnnnppnttpnppnttpnppnttpnTwswswsplog)2log)

3、22/log)22222222（递归步：，（选路：，内部转置（2212211122211211AAAAAAAAA转置为将国家高性能计算中心（合肥）152022-4-10 棋盘划分的矩阵转置9.2 矩阵转置 9.2.1 棋盘划分的矩阵转置 9.2.2 带状划分的矩阵转置 国家高性能计算中心（合肥）172022-4-10 带状划分的矩阵转置第九章 稠密矩阵运算 9.1 矩阵的划分 9.2 矩阵转置 9.3 矩阵-向量乘法 9.4 矩阵乘法9.3 矩阵-向量乘法 9.3.1 带状划分的矩阵-向量乘法 9.3.2 棋盘划分的矩阵-向量乘法 国家高性能计算中心（合肥）202022-4-10 带状划分的矩

4、阵-向量乘法充分大时项是多到多的播送时间后项是乘法时间，前pntptpnptpnptpnTwswsp/log21/)1(log22充分大时项是多到多的播送时间后项是乘法时间，前pntptpnptpntppnTwswsp/)1(221/)1()1(222国家高性能计算中心（合肥）212022-4-10 带状划分的矩阵-向量乘法9.3 矩阵-向量乘法 9.3.1 带状划分的矩阵-向量乘法 9.3.2 棋盘划分的矩阵-向量乘法 国家高性能计算中心（合肥）232022-4-10 棋盘划分的矩阵-向量乘法ptptpnptpnThwsp3loglog2pp pn/pttpnthws) 1(log)(ptp

5、tpnthws) 1(log)(ptptpnthws国家高性能计算中心（合肥）242022-4-10 棋盘划分的矩阵-向量乘法国家高性能计算中心（合肥）252022-4-10带状与棋盘划分比较)5 . 9() 1(22wspntptpnT)6 . 9(3loglog2ptptpnptpnThwsp第九章 稠密矩阵运算 9.1 矩阵的划分 9.2 矩阵转置 9.3 矩阵-向量乘法 9.4 矩阵乘法9.4 矩阵乘法 9.4.1 简单并行分块乘法 9.4.2 Cannon乘法 9.4.3 Fox乘法 9.4.4 Systolic乘法 9.4.5 DNS乘法国家高性能计算中心（合肥）282022-4-

6、10矩阵乘法符号及定义1, 11 , 10, 11, 11 , 10, 11, 01 , 00, 01, 11 , 10, 11, 11 , 10, 11, 01 , 00, 01, 11 , 10, 11, 11 , 10, 11, 01 , 00, 0,)()()(nnnnnnnnnnnnnnnnnnnnijnnijnnijbbbbbbbbbaaaaaaaaacccccccccBACcCbBaA设jiABC10nkkjikijbacA A中元素的第中元素的第1 1下标与下标与B B中元素的第中元素的第2 2下标相一致（对准）下标相一致（对准）国家高性能计算中心（合肥）292022-4-10

7、矩阵乘法并行实现方法A0,0B0,0A1,0B1,0A2,0B2,0A3,0B3,0A0,1B0,1A1,1B1,1A2,1B2,1A3,1B3,1A0,2B0,2A1,2B1,2A2,2B2,2A3,2B3,2A0,3B0,3A1,3B1,3A2,3B2,3A3,3B3,3国家高性能计算中心（合肥）302022-4-10简单并行分块乘法ppppnpn),.,.,(1, 11, 00, 0pppPPP1p10pkkjikijBAC)1(log(221ppntpttwspnptpn/)(3321p国家高性能计算中心（合肥）312022-4-10简单并行分块乘法pntptptpnttwsws221

8、22) 1(2）pntptpnTwsp2322p2)/(2pnO)(2pnOp9.4 矩阵乘法 9.4.1 简单并行分块乘法 9.4.2 Cannon乘法 9.4.3 Fox乘法 9.4.4 Systolic乘法 9.4.5 DNS乘法国家高性能计算中心（合肥）332022-4-10Cannon乘法ppppnpn),.,.,(1, 11, 00, 0pppPPPP0,0P1,0P2,0P3,0P0,1P1,1P2,1P3,1P0,2P1,2P2,2P3,2P0,3P1,3P2,3P3,3pnnp国家高性能计算中心（合肥）342022-4-10Cannon乘法1p1p1p国家高性能计算中心（合肥

9、）352022-4-10Cannon乘法A0,0A1,0A2,0A3,0A0,1A1,1A2,1A3,1A0,2A1,2A2,2A3,2A0,3A1,3A2,3A3,3B0,0B1,0B2,0B3,0B0,1B1,1B2,1B3,1B0,2B1,2B2,2B3,2B0,3B1,3B2,3B3,3Initial alignment of AInitial alignment of B国家高性能计算中心（合肥）362022-4-10Cannon乘法A and B after initial alignment and shifts after every stepA0,0B0,0A1,1B1,0A

10、2,2B2,0A3,3B3,0A0,1B1,1A1,2B2,1A2,3B3,1A3,0B0,1A0,2B2,2A1,3B3,2A2,0B0,2A3,1B1,2A0,3B3,3A1,0B0,3A2,1B1,3A3,2B2,3国家高性能计算中心（合肥）372022-4-10Cannon乘法After first shiftA0,1B1,0A1,2B2,0A2,3B3,0A3,0B0,0A0,2B2,1A1,3B3,1A2,0B0,1A3,1B3,1A0,3B3,2A1,0B0,2A2,1B1,2A3,2B2,2A0,0B0,3A1,1B1,3A2,2B2,3A3,3B3,3After second

11、 shiftA0,2B2,0A1,3B3,0A2,0B0,0A3,1B1,0A0,3B3,1A1,0B0,1A2,1B1,1A3,2B2,1A0,0B0,2A1,1B1,2A2,2B2,2A3,3B3,2A0,1B1,3A1,2B2,3A2,3B3,3A3,0B0,3After third shiftA0,3B3,0A1,0B0,0A2,1B1,0A3,2B2,0A0,0B0,1A1,1B1,1A2,2B2,1A3,3B3,1A0,1B1,2A1,2B2,2A2,3B3,2A3,0B0,2A0,2B2,3A1,3B3,3A2,0B0,3A3,1B1,3国家高性能计算中心（合肥）382022-4

12、-10Cannon乘法时间分析：时间分析：)/()/() 1 ()()(33321pnOpnpOOpOTTTnTp1ppppp1p9.4 矩阵乘法 9.4.1 简单并行分块乘法 9.4.2 Cannon乘法 9.4.3 Fox乘法 9.4.4 Systolic乘法 9.4.5 DNS乘法国家高性能计算中心（合肥）402022-4-10Fox乘法1ppjiAmod)1( ,A0,0B0,0A1,0B1,0A2,0B2,0A3,0B3,0A0,1B0,1A1,1B1,1A2,1B2,1A3,1B3,1A0,2B0,2A1,2B1,2A2,2B2,2A3,2B3,2A0,3B0,3A1,3B1,3A

13、2,3B2,3A3,3B3,3国家高性能计算中心（合肥）412022-4-10Fox乘法A0,0B0,0B1,0B2,0B3,0B0,1A1,1B1,1B2,1B3,1B0,2B1,2A2,2B2,2B3,2B0,3B1,3B2,3A3,3B3,3B1,0B2,0B3,0A0,1B1,1B2,1B3,1B0,1B1,2B3,2B0,2B1,3B2,3B0,3A1,2B2,2A2,3B3,3A3,0B0,0国家高性能计算中心（合肥）422022-4-10Fox乘法B2,0B3,0B2,1B3,1B0,1B3,2B0,2B1,2B2,3B0,3B1,3B3,0B1,0B3,1B0,1B2,1B3,

14、2B1,2B0,3B2,3B0,2B1,3B2,0A0,2B2,2A1,3B3,3A2,0B0,0B1,0A3,1B1,1A0,3B3,3A1,0B0,2A2,1B1,1A3,2B2,29.4 矩阵乘法 9.4.1 简单并行分块乘法 9.4.2 Cannon乘法 9.4.3 Fox乘法 9.4.4 Systolic乘法 9.4.5 DNS乘法国家高性能计算中心（合肥）442022-4-10Systolic乘法a1,4b4,1b3,1b2,1b2,2b4,2b3,2b2,3b3,3b4,3b2,4b3,4b4,4a1,3a1,1a1,2a2,4a2,1a2,2a2,3a3,1a3,2a3,3a3

15、,4b1,1b1,2b1,3b1,4Step 1P1,1c1,1P1,2c1,2P1,3c1,3P1,4c1,4P2, 1c2,1P2,2c2,2P2,3c2,3P2,4c2,4P3,1c3,1P3,2c3,2P3,3c3,3P3,4c3,4国家高性能计算中心（合肥）452022-4-10Systolic乘法c1,1c1,2c1,3c1,4c2,1c2,2c2,3c2,4c3,1c3,2c3,3c3,4b3,1b2,1b2,2b4,2b3,2b2,3b3,3b4,3b2,4b3,4b4,4a1,3a1,1a1,2a2,4a2,1a2,2a2,3a3,1a3,2a3,3a3,4b1,1b1,2b

16、1,3b1,4a1,4b4,1+Step 2国家高性能计算中心（合肥）462022-4-10Systolic乘法c1,1c1,2c1,3c1,4c2,1c2,2c2,3c2,4c3,1c3,2c3,3c3,4b2,1b2,2b3,2b2,3b3,3b4,3b2,4b3,4b4,4a1,1a1,2a2,1a2,2a2,3a3,1a3,2a3,3a3,4b1,1b1,2b1,3b1,4a1,3b3,1+a1,4b4,2+a2,4b4,1+Step 3国家高性能计算中心（合肥）472022-4-10Systolic乘法c1,1c1,2c1,3c1,4c2,1c2,2c2,3c2,4c3,1c3,2c

17、3,3c3,4b2,2b2,3b3,3b2,4b3,4b4,4a1,1a2,1a2,2a3,1a3,2a3,3b1,1b1,2b1,3b1,4a1,2b2,1+a1,3b3,2+a2,3b3,1+a1,4b4,3+a3,4b4,1+a2,4b4,2+Step 4国家高性能计算中心（合肥）482022-4-10Systolic乘法c1,1c1,2c1,3c1,4c2,1c2,2c2,3c2,4c3,1c3,2c3,3c3,4b2,3b2,4b3,4a2,1a3,1a3,2b1,2b1,3b1,4a1,1b1,1+a1,2b2,2+a2,2b2,1+a1,3b3,3+a3,3b3,1+a2,3b3

18、,2+a1,4b4,4+a2,4b4,3+a3,4b4,2+Step 5国家高性能计算中心（合肥）492022-4-10Systolic乘法c1,1c1,2c1,3c1,4c2,1c2,2c2,3c2,4c3,1c3,2c3,3c3,4b2,4a3,1b1,3b1,4a1,1b1,2+a2,1b1,1+a1,2b2,3+a3,2b2,1+a2,2b2,2+a1,3b3,4+a2,3b3,3+a3,3b3,2+a2,4b4,4+a3,4b4,3+Step 6国家高性能计算中心（合肥）502022-4-10Systolic乘法c1,1c1,2c1,3c1,4c2,1c2,2c2,3c2,4c3,1

19、c3,2c3,3c3,4b1,4a1,1b1,3+a3,1b1,1+a2,1b1,2+a1,2b2,4+a2,2b2,3+a3,2b3,2+a2,3b3,4+a3,3b3,3+a3,4b4,4+Step 7国家高性能计算中心（合肥）512022-4-10Systolic乘法c1,1c1,2c1,3c1,4c2,1c2,2c2,3c2,4c3,1c3,2c3,3c3,4a1,1b1,4+a2,1b1,3+a3,1b1,2+a2,2b2,4+a3,2b2,3+a3,3b3,4+Step 8国家高性能计算中心（合肥）522022-4-10Systolic乘法c1,1c1,2c1,3c1,4c2,1c2,2c2,3c2,4c3,1c3,2c3,3c3,4a2,1b1,4+a3,1b1,3+a3,2b2,4+Step 9国家高性能计算中心（合肥）532022-4-10Systolic乘法c1,1c1,2c1,3c1,4c2,1c2,2c2,3c2,4c3,1c3,2c3,3c3,4a3,1b1,4+Step 10国家高性能计