《并 行 计 算.ppt》由会员分享，可在线阅读，更多相关《并 行 计 算.ppt（61页珍藏版）》请在三一文库上搜索。
1、并 行 计 算,第三篇 并行数值算法 第八章 基本通讯操作 第九章 稠密矩阵运算 第十章 线性方程组的求解 第十一章 快速傅里叶变换,第九章 稠密矩阵运算 9.1 矩阵的划分 9.2 矩阵转置 9.3 矩阵-向量乘法 9.4 矩阵乘法,9.1 矩阵的划分 9.1.1 带状划分 9.1.2 棋盘划分,国家高性能计算中心（合肥）,5,2019/6/29,带状划分,1616阶矩阵，p=4 列块带状划分 行循环带状划分,国家高性能计算中心（合肥）,6,2019/6/29,带状划分,示例：p3，27 27矩阵的3种带状划分,9.1 矩阵的划分 9.1.1 带状划分 9.1.2 棋盘划分,国家高性能计算中
2、心（合肥）,8,2019/6/29,棋盘划分,88阶矩阵，p=16 块棋盘划分 循环棋盘划分,国家高性能计算中心（合肥）,9,2019/6/29,棋盘划分,示例：p4，1616矩阵的3种棋盘划分,第九章 稠密矩阵运算 9.1 矩阵的划分 9.2 矩阵转置 9.3 矩阵-向量乘法 9.4 矩阵乘法,9.2 矩阵转置 9.2.1 棋盘划分的矩阵转置 9.2.2 带状划分的矩阵转置,国家高性能计算中心（合肥）,12,2019/6/29,棋盘划分的矩阵转置,网孔连接 情形1: p=n2。 通讯步 转置后,国家高性能计算中心（合肥）,13,2019/6/29,棋盘划分的矩阵转置,情形2: pn2。 -
3、划分: - 算法: 按mesh连接进行块转置(不同处理器间) 进行块内转置(同一处理器内) 通讯步 转置后,国家高性能计算中心（合肥）,14,2019/6/29,棋盘划分的矩阵转置,超立方连接 划分: 算法: 对Aij递归应用进行转置，直至分块矩阵的元素处于同一处理器； 进行同一处理器的内部转置。 运行时间:,国家高性能计算中心（合肥）,15,2019/6/29,棋盘划分的矩阵转置,超立方连接：示例,9.2 矩阵转置 9.2.1 棋盘划分的矩阵转置 9.2.2 带状划分的矩阵转置,国家高性能计算中心（合肥）,17,2019/6/29,带状划分的矩阵转置,划分: Ann分成p个(n/p)n大小的
4、带 算法: Pi有p-1个(n/p)(n/p)大小子块发送到另外p-1个处理器中; 每个处理器本地交换相应的元素,第九章 稠密矩阵运算 9.1 矩阵的划分 9.2 矩阵转置 9.3 矩阵-向量乘法 9.4 矩阵乘法,9.3 矩阵-向量乘法 9.3.1 带状划分的矩阵-向量乘法 9.3.2 棋盘划分的矩阵-向量乘法,国家高性能计算中心（合肥）,20,2019/6/29,带状划分的矩阵-向量乘法,划分(行带状划分): Pi存放xi和ai,0,ai,1,ai,n-1, 并输出yi 算法: 对p=n情形 每个Pi向其他处理器播送xi(多到多播送)； 每个Pi计算； 注: 对pn情形,算法中Pi要播送X
5、中相应的n/p个分量 (1)超立方连接的计算时间 (2)网孔连接的计算时间,国家高性能计算中心（合肥）,21,2019/6/29,带状划分的矩阵-向量乘法,示例,9.3 矩阵-向量乘法 9.3.1 带状划分的矩阵-向量乘法 9.3.2 棋盘划分的矩阵-向量乘法,国家高性能计算中心（合肥）,23,2019/6/29,棋盘划分的矩阵-向量乘法,划分(块棋盘划分): Pij存放ai,j, xi置入Pi,i中 算法: 对p=n2情形 每个Pi,i向Pj,i播送xi(一到多播送)； 按行方向进行乘-加与积累运算，最后一列Pi,n-1收集的结果为yi； 注: 对pn2情形,p个处理器排成 的二维网孔， 算
6、法中Pi,i向Pj,i播送X中相应的 个分量 (1)网孔连接的计算时间Tp(CT): .X中相应分量置入Pi,i的通讯时间: .按列一到多播送时间: .按行单点积累的时间:,国家高性能计算中心（合肥）,24,2019/6/29,棋盘划分的矩阵-向量乘法,示例,国家高性能计算中心（合肥）,25,2019/6/29,带状与棋盘划分比较,以网孔链接为例 网孔上带状划分的运行时间 网孔上棋盘划分的运行时间 棋盘划分要比带状划分快。,第九章 稠密矩阵运算 9.1 矩阵的划分 9.2 矩阵转置 9.3 矩阵-向量乘法 9.4 矩阵乘法,9.4 矩阵乘法 9.4.1 简单并行分块乘法 9.4.2 Canno
7、n乘法 9.4.3 Fox乘法 9.4.4 Systolic乘法 9.4.5 DNS乘法,国家高性能计算中心（合肥）,28,2019/6/29,矩阵乘法符号及定义,A中元素的第1下标与B中元素的第2下标相一致（对准）,国家高性能计算中心（合肥）,29,2019/6/29,矩阵乘法并行实现方法,计算结构：二维阵列 空间对准(元素已加载到阵列中） Cannons , Foxs，DNS 时间对准(元素未加载到阵列中） Systolic,国家高性能计算中心（合肥）,30,2019/6/29,简单并行分块乘法,分块: A、B和C分成 的方块阵Ai,j、Bi,j和Ci,j, 大小均为 p个处理器编号为 ,
8、 Pi,j存放Ai,j、Bi,j和Ci,j。 算法: 通讯:每行处理器进行A矩阵块的多到多播送(得到Ai,k, k=0 ) 每列处理器进行B矩阵块的多到多播送(得到Bk,j, k=0 ) 乘-加运算: Pi,j做 运行时间 (1)超立方连接： 的时间 的时间,国家高性能计算中心（合肥）,31,2019/6/29,简单并行分块乘法,运行时间 (1)超立方连接： (2)二维环绕网孔连接： 的时间： 的时间t2=n3/p 注 (1)本算法的缺点是对处理器的存储要求过大 每个处理器有 个块，每块大小为n2/p, 所以需要 , p个处理器共需要 ， 是串行算法的 倍 (2)p=n2时，t(n)=O(n)
9、, c(n)=O(n3),9.4 矩阵乘法 9.4.1 简单并行分块乘法 9.4.2 Cannon乘法 9.4.3 Fox乘法 9.4.4 Systolic乘法 9.4.5 DNS乘法,国家高性能计算中心（合肥）,33,2019/6/29,Cannon乘法,分块: A、B和C分成 的方块阵Ai,j、Bi,j和Ci,j, 大小 均为p个处理器编号为 , Pi,j存放Ai,j、Bi,j和Ci,j(n p),国家高性能计算中心（合肥）,34,2019/6/29,Cannon乘法,算法原理 (非形式描述) 所有块Ai,j(0i,j )向左循环移动i步(按行移位)； 所有块Bi,j(0i,j )向上循环
10、移动j步(按列移位)； 所有处理器Pi,j做执行Ai,j和Bi,j的乘-加运算; A的每个块向左循环移动一步; B的每个块向上循环移动一步; 转执行 次;,国家高性能计算中心（合肥）,35,2019/6/29,Cannon乘法,示例： A44， B44, p=16,国家高性能计算中心（合肥）,36,2019/6/29,Cannon乘法,示例： A44， B44, p=16,国家高性能计算中心（合肥）,37,2019/6/29,Cannon乘法,示例： A44， B44, p=16,国家高性能计算中心（合肥）,38,2019/6/29,Cannon乘法,算法描述: Cannon分块乘法算法 /输
11、入: Ann, Bnn; 输出: Cnn Begin (1)for k=0 to do for all Pi,j par-do (i) if ik then Ai,j Ai,(j+1)mod endif (ii)if jk then Bi,j B(i+1)mod , j endif endfor endfor (2)for all Pi,j par-do Ci,j=0 endfor,(3)for k=0 to do for all Pi,j par-do (i) Ci,j=Ci,j+Ai,jBi,j (ii) Ai,j Ai,(j+1)mod (iii)Bi,j B(i+1)mod , j e
12、ndfor endfor End,时间分析：,9.4 矩阵乘法 9.4.1 简单并行分块乘法 9.4.2 Cannon乘法 9.4.3 Fox乘法 9.4.4 Systolic乘法 9.4.5 DNS乘法,国家高性能计算中心（合肥）,40,2019/6/29,Fox乘法,分块: 同Cannon分块算法 算法原理 Ai,i向所在行的其他处理器 进行一到多播送； 各处理器将收到的A块与原 有的B块进行乘-加运算; B块向上循环移动一步; 如果Ai,j是上次第i行播送的块，本次选择 向所 在行的其他处理器进行一到多播送; 转执行 次;,国家高性能计算中心（合肥）,41,2019/6/29,Fox乘法
13、,示例： A44， B44, p=16 (a) (b),国家高性能计算中心（合肥）,42,2019/6/29,Fox乘法,示例： A44， B44, p=16 (c) (d),B2,0,B3,0,B2,1,B3,1,B0,1,B3,2,B0,2,B1,2,B2,3,B0,3,B1,3,B3,0,B1,0,B3,1,B0,1,B2,1,B3,2,B1,2,B0,3,B2,3,B0,2,B1,3,B2,0,A0,2 B2,2,A1,3 B3,3,A2,0 B0,0,B1,0,A3,1 B1,1,A0,3 B3,3,A1,0 B0,2,A2,1 B1,1,A3,2 B2,2,9.4 矩阵乘法 9.4
14、.1 简单并行分块乘法 9.4.2 Cannon乘法 9.4.3 Fox乘法 9.4.4 Systolic乘法 9.4.5 DNS乘法,国家高性能计算中心（合肥）,44,2019/6/29,Systolic乘法,a1,4,b4,1,b3,1,b2,1,b2,2,b4,2,b3,2,b2,3,b3,3,b4,3,b2,4,b3,4,b4,4,a1,3,a1,1,a1,2,a2,4,a2,1,a2,2,a2,3,a3,1,a3,2,a3,3,a3,4,b1,1,b1,2,b1,3,b1,4,Step 1,P1,1 c1,1,P1,2 c1,2,P1,3 c1,3,P1,4 c1,4,P2, 1 c
15、2,1,P2,2 c2,2,P2,3 c2,3,P2,4 c2,4,P3,1 c3,1,P3,2 c3,2,P3,3 c3,3,P3,4 c3,4,国家高性能计算中心（合肥）,45,2019/6/29,Systolic乘法,c1,1,c1,2,c1,3,c1,4,c2,1,c2,2,c2,3,c2,4,c3,1,c3,2,c3,3,c3,4,b3,1,b2,1,b2,2,b4,2,b3,2,b2,3,b3,3,b4,3,b2,4,b3,4,b4,4,a1,3,a1,1,a1,2,a2,4,a2,1,a2,2,a2,3,a3,1,a3,2,a3,3,a3,4,b1,1,b1,2,b1,3,b1,
16、4,a1,4,b4,1,+,Step 2,国家高性能计算中心（合肥）,46,2019/6/29,Systolic乘法,c1,1,c1,2,c1,3,c1,4,c2,1,c2,2,c2,3,c2,4,c3,1,c3,2,c3,3,c3,4,b2,1,b2,2,b3,2,b2,3,b3,3,b4,3,b2,4,b3,4,b4,4,a1,1,a1,2,a2,1,a2,2,a2,3,a3,1,a3,2,a3,3,a3,4,b1,1,b1,2,b1,3,b1,4,a1,3,b3,1,+,a1,4,b4,2,+,a2,4,b4,1,+,Step 3,国家高性能计算中心（合肥）,47,2019/6/29,S
17、ystolic乘法,c1,1,c1,2,c1,3,c1,4,c2,1,c2,2,c2,3,c2,4,c3,1,c3,2,c3,3,c3,4,b2,2,b2,3,b3,3,b2,4,b3,4,b4,4,a1,1,a2,1,a2,2,a3,1,a3,2,a3,3,b1,1,b1,2,b1,3,b1,4,a1,2,b2,1,+,a1,3,b3,2,+,a2,3,b3,1,+,a1,4,b4,3,+,a3,4,b4,1,+,a2,4,b4,2,+,Step 4,国家高性能计算中心（合肥）,48,2019/6/29,Systolic乘法,c1,1,c1,2,c1,3,c1,4,c2,1,c2,2,c2,
18、3,c2,4,c3,1,c3,2,c3,3,c3,4,b2,3,b2,4,b3,4,a2,1,a3,1,a3,2,b1,2,b1,3,b1,4,a1,1,b1,1,+,a1,2,b2,2,+,a2,2,b2,1,+,a1,3,b3,3,+,a3,3,b3,1,+,a2,3,b3,2,+,a1,4,b4,4,+,a2,4,b4,3,+,a3,4,b4,2,+,Step 5,国家高性能计算中心（合肥）,49,2019/6/29,Systolic乘法,c1,1,c1,2,c1,3,c1,4,c2,1,c2,2,c2,3,c2,4,c3,1,c3,2,c3,3,c3,4,b2,4,a3,1,b1,3,
19、b1,4,a1,1,b1,2,+,a2,1,b1,1,+,a1,2,b2,3,+,a3,2,b2,1,+,a2,2,b2,2,+,a1,3,b3,4,+,a2,3,b3,3,+,a3,3,b3,2,+,a2,4,b4,4,+,a3,4,b4,3,+,Step 6,国家高性能计算中心（合肥）,50,2019/6/29,Systolic乘法,c1,1,c1,2,c1,3,c1,4,c2,1,c2,2,c2,3,c2,4,c3,1,c3,2,c3,3,c3,4,b1,4,a1,1,b1,3,+,a3,1,b1,1,+,a2,1,b1,2,+,a1,2,b2,4,+,a2,2,b2,3,+,a3,2,
20、b3,2,+,a2,3,b3,4,+,a3,3,b3,3,+,a3,4,b4,4,+,Step 7,国家高性能计算中心（合肥）,51,2019/6/29,Systolic乘法,c1,1,c1,2,c1,3,c1,4,c2,1,c2,2,c2,3,c2,4,c3,1,c3,2,c3,3,c3,4,a1,1,b1,4,+,a2,1,b1,3,+,a3,1,b1,2,+,a2,2,b2,4,+,a3,2,b2,3,+,a3,3,b3,4,+,Step 8,国家高性能计算中心（合肥）,52,2019/6/29,Systolic乘法,c1,1,c1,2,c1,3,c1,4,c2,1,c2,2,c2,3,
21、c2,4,c3,1,c3,2,c3,3,c3,4,a2,1,b1,4,+,a3,1,b1,3,+,a3,2,b2,4,+,Step 9,国家高性能计算中心（合肥）,53,2019/6/29,Systolic乘法,c1,1,c1,2,c1,3,c1,4,c2,1,c2,2,c2,3,c2,4,c3,1,c3,2,c3,3,c3,4,a3,1,b1,4,+,Step 10,国家高性能计算中心（合肥）,54,2019/6/29,Systolic乘法,P1,1 c1,1,P1,2 c1,2,P1,3 c1,3,P1,4 c1,4,P2, 1 c2,1,P2,2 c2,2,P2,3 c2,3,P2,4
22、c2,4,P3,1 c3,1,P3,2 c3,2,P3,3 c3,3,P3,4 c3,4,Over,c1,1 = a1,1 b1,1 + a1,2 b2,1 + a1,3 b3,1 + 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,国家高性能计算中心（合肥）,55,2019/6/29,Systolic乘法,Systolic算法 /输入: Amn, Bnk; 输出: Cmk Begin for i=1 to m
23、par- do for j=1 to k par-do (i) ci,j = 0 (ii) while Pi,j 收到a和b时 do ci,j = ci,j +ab if i m then 发送b给Pi+1,j endif if j k then 发送a给Pi,j+1 endif endwhile endfor endfor End,9.4 矩阵乘法 9.4.1 简单并行分块乘法 9.4.2 Cannon乘法 9.4.3 Fox乘法 9.4.4 Systolic乘法 9.4.5 DNS乘法,国家高性能计算中心（合肥）,57,2019/6/29,DNS乘法,背景: 由Dekel、Nassimi和
24、Sahni提出的SIMD-CC上的矩阵乘法, 处理器 数目为n3, 运行时间为O(logn), 是一种速度很快的算法。 基本思想: 通过一到一和一到多的播送办法，使得处理器(k,i,j)拥有ai,k和bk,j, 进行本地相乘,再沿k方向进行单点积累求和,结果存储在处理器(0,i,j)中。 处理器编号: 处理器数p=n3= (2q)3=23q, 处理器Pr位于位置(k,i,j), 这里r=kn2+in+j, (0i, j, kn-1)。位于(k,i,j)的处理器Pr的三个寄存器 Ar,Br,Cr分别表示为Ak,i,j, Bk,i,j和Ck,i,j, 初始时均为0。 算法: 初始时ai,j和bi,
25、j存储于寄存器A0,i,j和B0,i,j; 数据复制:A,B同时在k维复制(一到一播送)； A在j维复制(一到多播送); B在i维复制(一到多播送); 相乘运算:所有处理器的A、B寄存器两两相乘; 求和运算:沿k方向进行单点积累求和;,国家高性能计算中心（合肥）,58,2019/6/29,示例 C00=1(-5)+27=9 C01=1(-6)+28=10 C10=3(-5)+47=13 C11=3(-6)+48=14,初始加载,(b)A,B沿k维复制,(c)A沿j维复制,(d)B沿i维复制,(e)点积,(f)沿k维求和,B,B,A,A,000,010,001,011,100,110,101,1
26、11,P0,P1,P2,P3,P4,P5,P6,P7,国家高性能计算中心（合肥）,59,2019/6/29,算法描述: /令r(m)表示r的第m位取反； /p, rm=d表示r(0rp-1)的集合, 这里r的二 /进制第m位为d; /输入: Ann, Bnn; 输出: Cnn Begin /以n=2, p=8=23举例, q=1, r=(r2r1r0)2 (1)for m=3q-1 to 2q do /按k维复制A,B, m=2 for all r in p, rm=0 par-do /r2=0的r (1.1) Ar(m) Ar /A(100)A(000)等 (1.2) Br(m) Br /B
27、(100)B(000)等 endfor endfor (2)for m=q-1 to 0 do /按j维复制A, m=0 for all r in p, rm= r2q+m par-do /r0=r2的r Ar(m) Ar /A(001)A(000),A(100)A(101) endfor /A(011)A(010),A(110)A(111) endfor,(3)for m=2q-1 to q do /按i维复制B,m=1 for all r in p, rm= rq+m par-do/r1=r2的r Br(m) Br /B(010)B(000),B(100)B(110) endfor /B(011)B(001),B(101)B(111) endfor (4)for r=0 to p-1 par-do /相乘, all Pr Cr=ArBr endfor (5)for m=2q to 3q-1 do /求和,m=2 for r=0 to p-1 par-do Cr=Cr+Cr(m) endfor endfor End,DNS乘法,国家高性能计算中心（合肥）,60,2019/6/29,示例,DNS乘法,国家高性能计算中心（合肥）,61,2019/6/29,DNS乘法,