09-第09章-稠密矩阵运算-并行数值算法-并行计算(共15章)

并行计算中国科学技术大学计算机科学与技术系中国科学技术大学计算机科学与技术系国家高性能计算中心国家高性能计算中心((合肥合肥))20042004年年1212月月第三篇并行数值算法第八章基本通讯操作第九章稠密矩阵运算第十章线性方程组的求解第十一章快速傅里叶变换第九章稠密矩阵运算9.1矩阵的划分9.2矩阵转置9.3矩阵-向量乘法9.4矩阵乘法9.1矩阵的划分9.1.1带状划分9.1.2棋盘划分国家高性能计算中心（合肥）52013/7/24Wednesday带状划分1616××1616阶矩阵，阶矩阵，p=4p=4列块带状划分列块带状划分行循环带状划分行循环带状划分国家高性能计算中心（合肥）62013/7/24Wednesday带状划分示例：示例：pp＝＝33，，2727××2727矩阵的矩阵的33种带状划分种带状划分9.1矩阵的划分9.1.1带状划分9.1.2棋盘划分国家高性能计算中心（合肥）82013/7/24Wednesday棋盘划分88××88阶矩阵，阶矩阵，p=16p=16块棋盘划分块棋盘划分循环棋盘划分循环棋盘划分(b)(a)图9.261014711154812591361014(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,1)(7,4)(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,3)(2,6)(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)371115048121591323012国家高性能计算中心（合肥）92013/7/24Wednesday棋盘划分示例：示例：pp＝＝44，，1616××1616矩阵的矩阵的33种棋盘划分种棋盘划分第九章稠密矩阵运算9.1矩阵的划分9.2矩阵转置9.3矩阵-向量乘法9.4矩阵乘法9.2矩阵转置9.2.1棋盘划分的矩阵转置9.2.2带状划分的矩阵转置国家高性能计算中心（合肥）122013/7/24Wednesday棋盘划分的矩阵转置网孔连接网孔连接情形情形1:p=n1:p=n22。。通讯步通讯步转置后转置后国家高性能计算中心（合肥）132013/7/24Wednesday棋盘划分的矩阵转置情形情形2:pn2:pn22。。--划分划分::--算法算法::①①按按meshmesh连接进行块转置连接进行块转置((不同处理器间不同处理器间))②②进行块内转置进行块内转置((同一处理器内同一处理器内))通讯步通讯步转置后转置后(b)(a)图9.40481215913261014371115(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)4812015913261014371115(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)子块划分成p个大小为Apnpnnn通讯)/(2//2pnttpws计算pn2//2运行时间pntptpnTwsp/22222国家高性能计算中心（合肥）142013/7/24Wednesday棋盘划分的矩阵转置超立方连接超立方连接划分划分::算法算法::①①②②对对AAijij递归应用递归应用①①进行转置，直至分块矩阵的元素处于同一处理进行转置，直至分块矩阵的元素处于同一处理器；器；③③进行同一处理器的内部转置。进行同一处理器的内部转置。运行时间运行时间::子块划分成p个大小为ApnpnnnppnttpnppnttpnppnttpnTwswswsplog)2log)22//log)22222222（递归步：，（选路：，内部转置（2212211122211211AAAAAAAAA转置为＝将国家高性能计算中心（合肥）152013/7/24Wednesday棋盘划分的矩阵转置超立方连接：超立方连接：示例示例9.2矩阵转置9.2.1棋盘划分的矩阵转置9.2.2带状划分的矩阵转置国家高性能计算中心（合肥）172013/7/24Wednesday带状划分的矩阵转置划分划分::AnAn××nn分成分成pp个个((n/p)n/p)××nn大小的带大小的带算法算法::①①PiPi有有pp--11个个((n/p)n/p)××(n/p(n/p))大小子块发送到另外大小子块发送到另外pp--11个处理器中个处理器中;;②②每个处理器本地交换相应的元素每个处理器本地交换相应的元素图9.70123第九章稠密矩阵运算9.1矩阵的划分9.2矩阵转置9.3矩阵-向量乘法9.4矩阵乘法9.3矩阵-向量乘法9.3.1带状划分的矩阵-向量乘法9.3.2棋盘划分的矩阵-向量乘法国家高性能计算中心（合肥）202013/7/24Wednesday带状划分的矩阵-向量乘法划分划分((行带状划分行带状划分):P):Pii存放存放xxii和和aai,0i,0,a,ai,1i,1,,……,a,ai,ni,n--11,,并输出并输出yyii算法算法::对对p=np=n情形情形①①每个每个PPii向其他处理器播送向其他处理器播送xxii((多到多播送多到多播送))；；②②每个每个PPii计算；计算；注注::对对pnpn情形情形,,算法中算法中PPii要播送要播送XX中相应的中相应的n/pn/p个分量个分量(1)(1)超立方连接的计算时间超立方连接的计算时间(2)(2)网孔连接的计算时间网孔连接的计算时间充分大时项是多到多的播送时间后项是乘法时间，前pntptpnptpnptpnTwswsp//log21//)1(log22充分大时项是多到多的播送时间后项是乘法时间，前pntptpnptpntppnTwswsp//)1(221//)1()1(222国家高性能计算中心（合肥）212013/7/24Wednesday带状划分的矩阵-向量乘法示例示例9.3矩阵-向量乘法9.3.1带状划分的矩阵-向量乘法9.3.2棋盘划分的矩阵-向量乘法国家高性能计算中心（合肥）232013/7/24Wednesday棋盘划分的矩阵-向量乘法划分划分((块棋盘划分块棋盘划分):):PPijij存放存放aai,ji,j,x,xii置入置入PPi,ii,i中中算法算法::对对p=np=n22情形情形①①每个每个PPi,ii,i向向PPj,ij,i播送播送xxii((一到多播送一到多播送))；；②②按行方向进行乘按行方向进行乘--加与积累运算，最后一列加与积累运算，最后一列PPi,ni,n--11收集的收集的结果为结果为yyii；；注注::对对pnpn22情形情形,p,p个处理器排成个处理器排成的二维网孔，的二维网孔，算法中算法中PPi,ii,i向向PPj,ij,i播送播送XX中相应的中相应的个分量个分量(1)(1)网孔连接的计算时间网孔连接的计算时间TTpp(CT(CT):):.X.X中相应分量置入中相应分量置入PPi,ii,i的通讯时间的通讯时间::..按列一到多播送时间按列一到多播送时间::..按行单点积累的时间按行单点积累的时间::ptptpnptpnThwsp3loglog2pppn/pttpnthws)1(log)(ptptpnthws)1(log)(ptptpnthws国家高性能计算中心（合肥）242013/7/24Wednesday棋盘划分的矩阵-向量乘法示例示例矩阵向量(d)(c)01矩阵向量10√1(b)(a)√11122国家高性能计算中心（合肥）252013/7/24Wednesday带状与棋盘划分比较以网孔链接为例以网孔链接为例网孔上带状划分的运行时间网孔上带状划分的运行时间网孔上棋盘划分的运行时间网孔上棋盘划分的运行时间棋盘划分要比带状划分快。棋盘划分要比带状划分快。)5.9()1(22wspntptpnT)6.9(3loglog2ptptpnptpnThwsp第九章稠密矩阵运算9.1矩阵的划分9.2矩阵转置9.3矩阵-向量乘法9.4矩阵乘法9.4矩阵乘法9.4.1简单并行分块乘法9.4.2Cannon乘法9.4.3Fox乘法9.4.4Systolic乘法9.4.5DNS乘法国家高性能计算中心（合肥）282013/7/24Wednesday矩阵乘法符号及定义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设jiABC10nkkjikijbacA中元素的第1下标与B中元素的第2下标相一致（对准）国家高性能计算中心（合肥）292013/7/24Wednesday矩阵乘法并行实现方法计算结构：二维阵列计算结构：二维阵列空间对准空间对准((元素已加载到阵列中）元素已加载到阵列中）CannonCannon’’s,Foxs,Fox’’ss，，DNSDNS时间对准时间对准((元素未加