中科大多核并行计算课件

第三篇并行数值算法

第八章基本通讯操作

第九章稠密矩阵运算

第十章线性方程组的求解

第十一章快速傅里叶变换

2024/1/211现代密码学理论与实践之五第九章稠密矩阵运算

9.1矩阵的划分

9.2矩阵转置

9.3矩阵-向量乘法

9.3.1带状划分的矩阵-向量乘法

9.3.2棋盘划分的矩阵-向量乘法

9.3.3矩阵-向量的脉动乘法

9.4矩阵乘法

2024/1/212现代密码学理论与实践之五矩阵-向量乘法

求Y=AX

串行算法计算时间t(n)=O(n2)2024/1/213现代密码学理论与实践之五第九章稠密矩阵运算

9.1矩阵的划分

9.2矩阵转置

9.3矩阵-向量乘法

9.3.1带状划分的矩阵-向量乘法

9.3.2棋盘划分的矩阵-向量乘法

9.3.3矩阵-向量的脉动乘法

9.4矩阵乘法

2024/1/214现代密码学理论与实践之五带状划分的矩阵-向量乘法（1）

划分(行带状划分):Pi存放xi和ai,0,ai,1,…,ai,n-1,并输出yi算法:对p=n情形①每个Pi将其向量元素向其他处理器播送xi(多到多播送)；②每个Pi做相应计算；注:对p<n情形,算法中Pi要播送X中相应的n/p个分量(1)超立方连接的计算时间

(2)网孔连接的计算时间2024/1/215现代密码学理论与实践之五带状划分的矩阵-向量乘法（2）

示例2024/1/216现代密码学理论与实践之五第九章稠密矩阵运算

9.1矩阵的划分

9.2矩阵转置

9.3矩阵-向量乘法

9.3.1带状划分的矩阵-向量乘法

9.3.2棋盘划分的矩阵-向量乘法

9.3.3矩阵-向量的脉动乘法

9.4矩阵乘法

2024/1/217现代密码学理论与实践之五棋盘划分的矩阵-向量乘法（1）

划分(块棋盘划分):Pij存放ai,j,xi置入Pi,i中算法:对p=n2情形

①每个Pi,i将其向量元素向Pj,i播送xi(一到多播送)；②按行方向进行乘-加与积累运算，最后一列Pi,n-1收集的结果为yi；注:对p<n2情形,p个处理器排成的二维网孔，算法中Pi,i向Pj,i播送X中相应的个分量(1)网孔连接的计算时间Tp(CT):.X中相应分量置入Pi,i的通讯时间:.按列一到多播送时间:.按行单点积累的时间:2024/1/218现代密码学理论与实践之五棋盘划分的矩阵-向量乘法（2）

示例2024/1/219现代密码学理论与实践之五带状与棋盘划分比较以网孔链接为例网孔上带状划分的运行时间网孔上棋盘划分的运行时间棋盘划分要比带状划分快。2024/1/2110现代密码学理论与实践之五第九章稠密矩阵运算

9.1矩阵的划分

9.2矩阵转置

9.3矩阵-向量乘法

9.3.1带状划分的矩阵-向量乘法

9.3.2棋盘划分的矩阵-向量乘法

9.3.3矩阵-向量的脉动乘法

9.4矩阵乘法2024/1/2111现代密码学理论与实践之五矩阵-向量乘法的脉动算法（1）示例2024/1/2112现代密码学理论与实践之五矩阵-向量乘法的脉动算法（2）示例2024/1/2113现代密码学理论与实践之五第九章稠密矩阵运算

9.1矩阵的划分

9.2矩阵转置

9.3矩阵-向量乘法

9.4矩阵乘法

9.4.1简单并行分块乘法

9.4.2Cannon乘法

9.4.3Fox乘法

9.4.4Systolic乘法

9.4.5DNS乘法2024/1/2114现代密码学理论与实践之五矩阵乘法符号及定义jiABCA中元素的第2下标与B中元素的第1下标相一致（对准）2024/1/2115现代密码学理论与实践之五矩阵乘法并行实现方法计算结构：二维阵列空间对准(元素已加载到阵列中）

Cannon’s,Fox’s，DNS时间对准(元素未加载到阵列中）SystolicA0,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/1/2116现代密码学理论与实践之五简单并行分块乘法（1）分块:

A、B和C分成的方块阵Ai,j、Bi,j和Ci,j,大小均为

p个处理器编号为,Pi,j存放Ai,j、Bi,j和Ci,j。算法:

①通讯:每行处理器进行A矩阵块的多到多播送(得到Ai,k,k=0~)每列处理器进行B矩阵块的多到多播送(得到Bk,j,k=0~)

②乘-加运算:Pi,j做运行时间

(1)超立方连接：①的时间②的时间2024/1/2117现代密码学理论与实践之五简单并行分块乘法（2）运行时间

(1)超立方连接：(2)二维环绕网孔连接：①的时间：②的时间：t2=n3/p注(1)本算法的缺点是对处理器的存储要求过大每个处理器有个块，每块大小为n2/p,

所以需要,p个处理器共需要，是串行算法的倍

(2)p=n2时，t(n)=O(n),c(n)=O(n3)2024/1/2118现代密码学理论与实践之五第九章稠密矩阵运算

9.1矩阵的划分

9.2矩阵转置

9.3矩阵-向量乘法

9.4矩阵乘法

9.4.1简单并行分块乘法

9.4.2Cannon乘法

9.4.3Fox乘法

9.4.4Systolic乘法

9.4.5DNS乘法2024/1/2119现代密码学理论与实践之五Cannon乘法（1）分块:A、B和C分成的方块阵Ai,j、Bi,j和Ci,j大小均为，p个处理器编号为,Pi,j存放Ai,j、Bi,j和Ci,j(n>>p)P0,0P1,0P2,0P3,0P0,1P1,1P2,1P3,1P0,2P1,2P2,2P3,2P0,3P1,3P2,3P3,32024/1/2120现代密码学理论与实践之五Cannon乘法（2）算法原理

(非形式描述，1969年)

①所有块Ai,j(0≤i,j≤)向左循环移动i步(按行移位)；所有块Bi,j(0≤i,j≤)向上循环移动j步(按列移位)；

②所有处理器Pi,j执行Ai,j和Bi,j的乘-加运算;

③A的每个块向左循环移动一步;

B的每个块向上循环移动一步;

④转②执行次;2024/1/2121现代密码学理论与实践之五Cannon乘法（2）示例：A4×4，B4×4,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,3InitialalignmentofAInitialalignmentofB2024/1/2122现代密码学理论与实践之五Cannon乘法（3）示例：A4×4，B4×4,p=16

AandBafterinitialalignmentandshiftsaftereverystepA0,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/1/2123现代密码学理论与实践之五Cannon乘法（4）示例：A4×4，B4×4,p=16

AfterfirstshiftA0,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,3AftersecondshiftA0,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,3AfterthirdshiftA0,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/1/2124现代密码学理论与实践之五Cannon乘法（5）算法描述:Cannon分块乘法算法

//输入:An×n,Bn×n;输出:Cn×nBegin(1)fork=0todoforallPi,jpar-do(i)ifi>kthen

Ai,j

Ai,(j+1)mod

endif(ii)ifj>kthen

Bi,j

B(i+1)mod,j

endif

endfor

endfor(2)forallPi,jpar-doCi,j=0endfor

(3)fork=0todoforallPi,jpar-do(i)Ci,j=Ci,j+Ai,jBi,j(ii)Ai,j

Ai,(j+1)mod(iii)Bi,j

B(i+1)mod,j

endfor

endfor

End初步的时间分析：2024/1/2125现代密码学理论与实践之五Cannon乘法（6）时间分析

(1)超立方连接:②和③执行次，所以运行时间为

(2)二维网孔连接，CT选路模式:②和③执行次，所以运行时间为

2024/1/2126现代密码学理论与实践之五第九章稠密矩阵运算

9.1矩阵的划分

9.2矩阵转置

9.3矩阵-向量乘法

9.4矩阵乘法

9.4.1简单并行分块乘法

9.4.2Cannon乘法

9.4.3Fox乘法

9.4.4Systolic乘法

9.4.5DNS乘法2024/1/2127现代密码学理论与实践之五Fox乘法（1）分块:

同Cannon分块算法算法原理（1987年）

①Ai,i向所在行的其他处理器进行一到多播送；②各处理器将收到的A块与原有的B块进行乘-加运算;

③B块向上循环移动一步;

④如果Ai,j是上次第i行播送的块，本次选择向所在行的其他处理器进行一到多播送;

⑤转②执行次;

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/1/2128现代密码学理论与实践之五Fox乘法（2）示例：A4×4，B4×4,p=16

(a)(b)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,02024/1/2129现代密码学理论与实践之五Fox乘法（3）示例：A4×4，B4×4,p=16

(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,0B0,0B1,0A3,1B1,1A0,3B3,3A1,0B0,2A2,1B1,1A3,2B2,22024/1/2130现代密码学理论与实践之五Fox乘法（4）运行时间

(1)超立方连接:

②、③和④(含①)执行次，所以运行时间为

当p=n2时,t(n)=O(nlogn)(2)二维网孔连接，CT选路模式(思考?)2024/1/2131现代密码学理论与实践之五第九章稠密矩阵运算

9.1矩阵的划分

9.2矩阵转置

9.3矩阵-向量乘法

9.4矩阵乘法

9.4.1简单并行分块乘法

9.4.2Cannon乘法

9.4.3Fox乘法

9.4.4Systolic乘法

9.4.5DNS乘法2024/1/2132现代密码学理论与实践之五Systolic乘法（1）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,4Step1P1,1c1,1P1,2c1,2P1,3c1,3P1,4c1,4P2,1c2,1P2,2c2,2P2,3c2,3P2,4c2,4P3,1c3,1P3,2c3,2P3,3c3,3P3,4c3,42024/1/2133现代密码学理论与实践之五Systolic乘法（2）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+Step22024/1/2134现代密码学理论与实践之五Systolic乘法（3）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+Step32024/1/2135现代密码学理论与实践之五Systolic乘法（4）c1,1c1,2c1,3c1,4c2,1c2,2c2,3c2,4c3,1c3,2c3,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+Step42024/1/2136现代密码学理论与实践之五Systolic乘法（5）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,2+Step52024/1/2137现代密码学理论与实践之五Systolic乘法（6）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+Step62024/1/2138现代密码学理论与实践之五Systolic乘法（7）c1,1c1,2c1,3c1,4c2,1c2,2c2,3c2,4c3,1c3,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+Step72024/1/2139现代密码学理论与实践之五Systolic乘法（8）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+Step82024/1/2140现代密码学理论与实践之五Systolic乘法（9）c1,1c1,2c1,3c1,4c2,1c2,2c2,3c2,4c3,1c3,2c3,3c3,4a2,1b1,4+a3,1b1,3+a3,2b2,4+Step92024/1/2141现代密码学理论与实践之五Systolic乘法（10）c1,1c1,2c1,3c1,4c2,1c2,2c2,3c2,4c3,1c3,2c3,3c3,4a3,1b1,4+Step102024/1/2142现代密码学理论与实践之五Systolic乘法（11）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

+a1,4

b4,1c1,2=a1,1b1,2

+a1,2

b2,2+a1,3

b3,2

+a1,4

b4,2

…………c3,4=a3,1

b1,4

+a3,2b2,4

+a3,3

b3,4+a3,4b4,4

2024/1/2143现代密码学理论与实践之五Systolic乘法（12）

Systolic算法（H.T.Kung）

//输入:Am×n,Bn×k;输出:Cm×kBeginfori=1tompar-doforj=1tokpar-do(i)ci,j=0 (ii)whilePi,j收到a和b时do

ci,j=ci,j+ab ifi<mthen发送b给Pi+1,j

endif

ifj<kthen发送a给Pi,j+1

endif

endwhile

endfor

endforEnd2024/1/2144现代密码学理论与实践之五第九章稠密矩阵运算

9.1矩阵的划分

9.2矩阵转置

9.3矩阵-向量乘法

9.4矩阵乘法

9.4.1简单并行分块乘法

9.4.2Cannon乘法

9.4.3Fox乘法

9.4.4Systolic乘法

9.4.5DNS乘法2024/1/2145现代密码学理论与实践之五DNS乘法（1）Motivation:Fromagoodandcommonidea

ji+

11

22

33

nn++...+=ABC2024/1/2146现代密码学理论与实践之五DNS乘法（2）Motivation:Fromagoodandcommonidea(Cont.)

Howtouseprocessorsmoreeffectivelyandpractically?

x11x22x33xnn

...

=...+++nprocessorsforeachresultelementimpliesnxn2=n3timeislog2n2024/1/2147现代密码学理论与实践之五DNS乘法（3）背景:1981年由Dekel、Nassimi和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,(0≤i,j,k≤n-1)。位于(k,i,j)的处理器Pr的三个寄存器

Ar,Br,Cr分别表示为A[k,i,j],B[k,i,j]和C[k,i,j],初始时均为0。算法:

初始时ai,j和bi,j存储于寄存器A[0,i,j]和B[0,i,j];①数据复制:A,B同时在k维复制(一到一播送)；

A在j维复制(一到多播送);B在i维复制(一到多播送);②相乘运算:所有处理器的A、B寄存器两两相乘;

③求和运算:沿k方向进行单点积累求和;

2024/1/2148现代密码学理论与实践之五示例

C00=1×(-5)+2×7=9C01=1×(-6)+2×8=10C10=3×(-5)+4×7=13C11=3×(-6)+4×8=14

kji初始加载(b)A,B沿k维复制(c)A沿j维复制(d)B沿i维复制(e)点积(f)沿k维求和BBAA000010001011100110101111P0P1P2P3P4P5P6P72024/1/2149现代密码学理论与实践之五算法描述://令r(m)表示r的第m位取反；

//{p,rm=d}表示r(0≤r≤p-1)的集合,这里r的二

//进制