《最新并 行 计 算PPT课件》由会员分享，可在线阅读，更多相关《最新并 行 计 算PPT课件（62页珍藏版）》请在金锄头文库上搜索。
1、并 行 计 算第三篇 并行数值算法 第八章 基本通讯操作 第九章 稠密矩阵运算 第十章 线性方程组的求解 第十一章 快速傅里叶变换 2024/7/302现代密码学理论与实践之五 棋盘划分 示例：示例：p p4 4，16161616矩阵的矩阵的3 3种棋盘划分种棋盘划分 2024/7/309现代密码学理论与实践之五第九章 稠密矩阵运算 9.1 矩阵的划分 9.2 矩阵转置 9.3 矩阵-向量乘法 9.4 矩阵乘法2024/7/3010现代密码学理论与实践之五9.2 矩阵转置 9.2.1 棋盘划分的矩阵转置 9.2.2 带状划分的矩阵转置 2024/7/3011现代密码学理论与实践之五 棋盘划分的
2、矩阵转置网孔连接 情形情形1: p=n1: p=n2 2。 通讯步通讯步 转置后转置后2024/7/3012现代密码学理论与实践之五 棋盘划分的矩阵转置 情形情形2: pn2: pn2 2。 - - 划分划分: : - - 算法算法: : 按按meshmesh连接进行块转置连接进行块转置( (不同处理器间不同处理器间) ) 进行块内转置进行块内转置( (同一处理器内同一处理器内) ) 通讯步通讯步 转置后转置后2024/7/3013现代密码学理论与实践之五 棋盘划分的矩阵转置超立方连接 划分划分: : 算法算法: : 对对A Aijij递归应用递归应用进行转置，直至分块矩阵的元素处于同一处理进
3、行转置，直至分块矩阵的元素处于同一处理器；器； 进行同一处理器的内部转置。进行同一处理器的内部转置。 运行时间运行时间: : 2024/7/3014现代密码学理论与实践之五 棋盘划分的矩阵转置超立方连接：示例示例 2024/7/3015现代密码学理论与实践之五9.2 矩阵转置 9.2.1 棋盘划分的矩阵转置 9.2.2 带状划分的矩阵转置 2024/7/3016现代密码学理论与实践之五 带状划分的矩阵转置 划分划分: Ann: Ann分成分成p p个个(n/p)n(n/p)n大小的带大小的带 算法算法: : PiPi有有p-1p-1个个(n/p)(n/p)(n/p)(n/p)大小子块发送到另外
4、大小子块发送到另外p-1p-1个处理器中个处理器中; ; 每个处理器本地交换相应的元素每个处理器本地交换相应的元素 2024/7/3017现代密码学理论与实践之五第九章 稠密矩阵运算 9.1 矩阵的划分 9.2 矩阵转置 9.3 矩阵-向量乘法 9.4 矩阵乘法2024/7/3018现代密码学理论与实践之五9.3 矩阵-向量乘法 9.3.1 带状划分的矩阵-向量乘法 9.3.2 棋盘划分的矩阵-向量乘法 2024/7/3019现代密码学理论与实践之五 带状划分的矩阵-向量乘法 划分划分( (行带状划分行带状划分): P): Pi i存放存放x xi i和和a ai,0i,0,a,ai,1i,1
5、,a,ai,n-1i,n-1, , 并输出并输出y yi i 算法算法: : 对对p=np=n情形情形 每个每个P Pi i向其他处理器播送向其他处理器播送x xi i( (多到多播送多到多播送) )； 每个每个P Pi i计算；计算； 注注: : 对对pnpn情形情形, ,算法中算法中P Pi i要播送要播送X X中相应的中相应的n/pn/p个分量个分量 (1) (1)超立方连接的计算时间超立方连接的计算时间 (2) (2)网孔连接的计算时间网孔连接的计算时间2024/7/3020现代密码学理论与实践之五 带状划分的矩阵-向量乘法 示例示例2024/7/3021现代密码学理论与实践之五9.3
6、 矩阵-向量乘法 9.3.1 带状划分的矩阵-向量乘法 9.3.2 棋盘划分的矩阵-向量乘法 2024/7/3022现代密码学理论与实践之五 棋盘划分的矩阵-向量乘法 划分划分( (块棋盘划分块棋盘划分): ): P Pijij存放存放a ai,ji,j, x, xi i置入置入P Pi,ii,i中中算法算法: : 对对p=np=n2 2情形情形 每个每个P Pi,ii,i向向P Pj,ij,i播送播送x xi i( (一到多播送一到多播送) )； 按行方向进行乘按行方向进行乘- -加与积累运算，最后一列加与积累运算，最后一列P Pi,n-1i,n-1收集的收集的结果为结果为y yi i；注注
7、: : 对对pnp p)(n p)P0,0P1,0P2,0P3,0P0,1P1,1P2,1P3,1P0,2P1,2P2,2P3,2P0,3P1,3P2,3P3,32024/7/3033现代密码学理论与实践之五Cannon乘法算法原理 (非形式描述) 所有块所有块A Ai,ji,j(0i,j )(0i,j )向左循环移动向左循环移动i i步步( (按按行移位行移位) )； 所有块所有块B Bi,ji,j(0i,j )(0i,j )向上循环移动向上循环移动j j步步( (按按列移位列移位) )； 所有处理器所有处理器P Pi,ji,j做执行做执行A Ai,ji,j和和B Bi,ji,j的乘的乘-
8、-加运算加运算; ; AA的每个块向左循环移动一步的每个块向左循环移动一步; ; B B的每个块向上循环移动一步的每个块向上循环移动一步; ; 转转执行执行 次次; ;2024/7/3034现代密码学理论与实践之五Cannon乘法示例： A A4444， B B4444, p=16, p=16 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 AIn
9、itial alignment of B2024/7/3035现代密码学理论与实践之五Cannon乘法示例： A A4444， B B4444, p=16, p=16 A and B after initial alignment and shifts after every stepA0,0B0,0A1,1B1,0A2,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,32024/7/3036现代密码学理论与实践之五Cannon
10、乘法示例： A A4444， B B4444, p=16, p=16 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 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
11、,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,32024/7/3037现代密码学理论与实践之五Cannon乘法算法描述: Cannon分块乘法算法 /输入输入: A: Annnn, B, Bnnnn; ; 输出输出: C: Cnnnn Begin Begin (1)for k=0 to do (1)for
12、 k=0 to do for all P for all Pi,ji,j par-do par-do (i) if ik then (i) if ik then A Ai,ji,j A Ai,(j+1)modi,(j+1)mod endif endif (ii)if jk then (ii)if jk then B Bi,ji,j B B(i+1)mod , j(i+1)mod , j endif endif endfor endfor endfor endfor (2)for all P (2)for all Pi,ji,j par-do C par-do Ci,ji,j=0 endfor
13、=0 endfor (3)for k=0 to do(3)for k=0 to do for all P for all Pi,ji,j par-do par-do (i) C (i) Ci,ji,j=C=Ci,ji,j+A+Ai,ji,jB Bi,ji,j (ii) A (ii) Ai,ji,j A Ai,(j+1)modi,(j+1)mod (iii)B (iii)Bi,ji,j B B(i+1)mod , j(i+1)mod , j endfor endfor endfor endfor End End时间分析：时间分析：2024/7/3038现代密码学理论与实践之五9.4 矩阵乘法 9
14、.4.1 简单并行分块乘法 9.4.2 Cannon乘法 9.4.3 Fox乘法 9.4.4 Systolic乘法 9.4.5 DNS乘法2024/7/3039现代密码学理论与实践之五Fox乘法分块: 同同CannonCannon分块算法分块算法算法原理 A Ai,ii,i向所在行的其他处理器向所在行的其他处理器进行一到多播送；进行一到多播送； 各处理器将收到的各处理器将收到的A A块与原块与原有的有的B B块进行乘块进行乘- -加运算加运算; ; BB块向上循环移动一步块向上循环移动一步; ; 如果如果A Ai,ji,j是上次第是上次第i i行播送的块，本次选择行播送的块，本次选择 向所向所
15、 在行的其他处理器进行一到多播送在行的其他处理器进行一到多播送; ; 转转执行执行 次次; ; 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,32024/7/3040现代密码学理论与实践之五Fox乘法示例： A A4444， B B4444, p=16, p=16 (a) (b) (a) (b)A0,0B0,0B1,0B2,0B3,0B0,1A1,1B1,1B2,1B3,1B0,2B1,2
16、A2,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,02024/7/3041现代密码学理论与实践之五Fox乘法示例： A A4444， B B4444, p=16, p=16 (c) (d) (c) (d)B2,0B3,0B2,1B3,1B0,1B3,2B0,2B1,2B2,3B0,3B1,3B3,0B1,0B3,1B0,1B2,1B3,2B1,2B0,3B2,3B0,2B1,3B2,0A0,2B2,2A1,3B3,3A2,0
17、B0,0B1,0A3,1B1,1A0,3B3,3A1,0B0,2A2,1B1,1A3,2B2,22024/7/3042现代密码学理论与实践之五9.4 矩阵乘法 9.4.1 简单并行分块乘法 9.4.2 Cannon乘法 9.4.3 Fox乘法 9.4.4 Systolic乘法 9.4.5 DNS乘法2024/7/3043现代密码学理论与实践之五Systolic乘法a1,4b4,1b3,1b2,1b2,2b4,2b3,2b2,3b3,3b4,3b2,4b3,4b4,4a1,3a1,1a1,2a2,4a2,1a2,2a2,3a3,1a3,2a3,3a3,4b1,1b1,2b1,3b1,4Step
18、1P1,1c1,1P1,2c1,2P1,3c1,3P1,4c1,4P2, 1c2,1P2,2c2,2P2,3c2,3P2,4c2,4P3,1c3,1P3,2c3,2P3,3c3,3P3,4c3,42024/7/3044现代密码学理论与实践之五Systolic乘法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,2b1,3b1,4a1,4b4,1+Step 220
19、24/7/3045现代密码学理论与实践之五Systolic乘法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 32024/7/3046现代密码学理论与实践之五Systolic乘法c1,1c1,2c1,3c1,4c2,1c2,2c2,3c2,4c3,1c3,2c3,3c3,4b2,2b2,3b3,3b2,4b3,
20、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 42024/7/3047现代密码学理论与实践之五Systolic乘法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,2+a1,4b4,4+a2,4b4,3+a3,4b4
21、,2+Step 52024/7/3048现代密码学理论与实践之五Systolic乘法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 62024/7/3049现代密码学理论与实践之五Systolic乘法c1,1c1,2c1,3c1,4c2,1c2,2c2,3c2,4c3,1c3,2c3,3c3,4b1,4a1,1b1,3+a3,1
22、b1,1+a2,1b1,2+a1,2b2,4+a2,2b2,3+a3,2b3,2+a2,3b3,4+a3,3b3,3+a3,4b4,4+Step 72024/7/3050现代密码学理论与实践之五Systolic乘法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 82024/7/3051现代密码学理论与实践之五Systolic乘法c1,1c1,2c1,3c1,4c2,1c2,2c2,3c2,4c3,1c3,2c3,3c3,4a2,1
23、b1,4+a3,1b1,3+a3,2b2,4+Step 92024/7/3052现代密码学理论与实践之五Systolic乘法c1,1c1,2c1,3c1,4c2,1c2,2c2,3c2,4c3,1c3,2c3,3c3,4a3,1b1,4+Step 102024/7/3053现代密码学理论与实践之五Systolic乘法P1,1c1,1P1,2c1,2P1,3c1,3P1,4c1,4P2, 1c2,1P2,2c2,2P2,3c2,3P2,4c2,4P3,1c3,1P3,2c3,2P3,3c3,3P3,4c3,4Overc1,1 = a1,1 b1,1 + a1,2 b2,1 + a1,3 b3,1
24、 + a1,4 b4,1 c1,2 = a1,1 b1,2 + a1,2 b2,2 + a1,3 b3,2 + a1,4 b4,2 c3,4 = a3,1 b1,4 + a3,2 b2,4 + a3,3 b3,4 + a3,4 b4,4 2024/7/3054现代密码学理论与实践之五Systolic乘法 Systolic算法 /输入输入: A: Amnmn, B, Bnknk; ; 输出输出: C: Cmkmk Begin Begin for i=1 to m par- do for i=1 to m par- do for j=1 to k par-do for j=1 to k par-d
25、o (i) c (i) ci,ji,j = 0 = 0 (ii) while P (ii) while Pi,j i,j 收到收到a a和和b b时时 dodo c ci,ji,j = c = ci,ji,j +ab +ab if i m then if i m then 发送发送b b给给P Pi+1,ji+1,j endif endif if j k then if j k then 发送发送a a给给P Pi,j+1i,j+1 endif endif endwhile endwhile endfor endfor endfor endfor End End2024/7/3055现代密码学
26、理论与实践之五9.4 矩阵乘法 9.4.1 简单并行分块乘法 9.4.2 Cannon乘法 9.4.3 Fox乘法 9.4.4 Systolic乘法 9.4.5 DNS乘法2024/7/3056现代密码学理论与实践之五DNS乘法 背景背景: : 由由DekelDekel、NassimiNassimi和和SahniSahni提出的提出的SIMD-CCSIMD-CC上的矩阵乘法上的矩阵乘法, , 处理器处理器 数目为数目为n n3 3, , 运行时间为运行时间为O(logn), O(logn), 是一种速度很快的算法。是一种速度很快的算法。 基本思想基本思想: : 通过一到一和一到多的播送办法，使
27、得处理器通过一到一和一到多的播送办法，使得处理器(k,i,j)(k,i,j)拥有拥有a ai,ki,k和和b bk,jk,j, , 进行本地相乘进行本地相乘, ,再沿再沿k k方向进行单点积累求和方向进行单点积累求和, ,结果存储在处理器结果存储在处理器(0,i,j)(0,i,j)中。中。 处理器编号处理器编号: : 处理器数处理器数p=np=n3 3= (2= (2q q) )3 3=2=23 3q q, , 处理器处理器P Pr r位于位置位于位置(k,i,j), (k,i,j), 这里这里r=knr=kn2 2+in+j, (0i, j, kn-1)+in+j, (0i, j, kn-1
28、)。位于。位于(k,i,j)(k,i,j)的处理器的处理器P Pr r的的三个寄存器三个寄存器 A Ar r,B,Br r,C,Cr r分别表示为分别表示为Ak,i,j, Bk,i,jAk,i,j, Bk,i,j和和Ck,i,j, Ck,i,j, 初始时均为初始时均为0 0。 算法算法: : 初始时初始时a ai,ji,j和和b bi,ji,j存储于寄存器存储于寄存器A0,i,jA0,i,j和和B0,i,j; B0,i,j; 数据复制数据复制:A,B:A,B同时在同时在k k维复制维复制( (一到一播送一到一播送) )； A A在在j j维复制维复制( (一到多播送一到多播送); B); B在
29、在i i维复制维复制( (一到多一到多播送播送); ); 相乘运算相乘运算: :所有处理器的所有处理器的A A、B B寄存器两两相乘寄存器两两相乘; ; 求和运算求和运算: :沿沿k k方向进行单点积累求和方向进行单点积累求和; ; 2024/7/3057现代密码学理论与实践之五示例示例 C00=1(-5)+27=9C00=1(-5)+27=9C01=1(-6)+28=10C01=1(-6)+28=10C10=3(-5)+47=13C10=3(-5)+47=13C11=3(-6)+48=14C11=3(-6)+48=14 kji初始加载(b)A,B沿k维复制(c)A沿j维复制(d)B沿i维复制
30、(e)点积(f)沿k维求和BBAA000010001011100110101111P0P1P2P3P4P5P6P72024/7/3058现代密码学理论与实践之五算法描述算法描述: : / /令令r r(m)(m)表示表示r r的第的第mm位取反；位取反； /p, rp, rmm=d=d表示表示r(0r(0rrp-1p-1) )的集合的集合, , 这里这里r r的二的二 /进制第进制第mm位为位为d;d; / /输入输入: A: Annnn, B, Bnnnn; ; 输出输出: C: Cnnnn Begin / Begin /以以n=2, p=8=2n=2, p=8=23 3举例举例, q=1,
31、 r=(r, q=1, r=(r2 2r r1 1r r0 0) )2 2 (1)for m=3q-1 to 2q do / (1)for m=3q-1 to 2q do /按按k k维复制维复制A,B, A,B, m=2m=2 for all r in p, r for all r in p, rmm=0 par-do =0 par-do /r r2 2=0=0的的r r (1.1) A (1.1) Ar r(m)(m) A Ar r /A(100)A(100)A(000)A(000)等等 (1.2) B(1.2) Br r(m)(m) B Br r /B(100)B(100)B(000)B
32、(000)等等 endforendfor endfor endfor (2)for m=q-1 to 0 do / (2)for m=q-1 to 0 do /按按j j维复制维复制A, A, m=0m=0 for all r in p, r for all r in p, rmm= r= r2q+m2q+m par-do / par-do /r r0 0=r=r2 2的的r r A Ar r(m)(m) A Ar r /A(001)A(001)A(000),A(100)A(000),A(100)A(101)A(101) endfor endfor /A(011)A(011)A(010),A(
33、110)A(010),A(110)A(111)A(111) endfor endfor(3)for m=2q-1 to q do /(3)for m=2q-1 to q do /按按i i维复制维复制B,B,m=1m=1 for all r in p, r for all r in p, rmm= r= rq+mq+m par-do par-do/r r1 1=r=r2 2的的r r B Br r(m)(m) B Br r /B(010)B(010)B(000),B(100)B(000),B(100)B(110)B(110) endfor endfor /B(011)B(011)B(001),
34、B(101)B(001),B(101)B(111)B(111) endfor endfor (4)for r=0 to p-1 par-do / (4)for r=0 to p-1 par-do /相乘相乘, , all Pall Pr r C Cr r=A=Ar rBBr r endforendfor (5)for m=2q to 3q-1 do / (5)for m=2q to 3q-1 do /求和求和, ,m=2m=2 for r=0 to p-1 par-dofor r=0 to p-1 par-do C Cr r=C=Cr r+C+Cr r(m)(m) endfor endfor endfor endfor End EndDNS乘法2024/7/3059现代密码学理论与实践之五示例示例 DNS乘法2024/7/3060现代密码学理论与实践之五kjiDNS乘法2024/7/3061现代密码学理论与实践之五
