中科大多核并行計算課件

第三篇并行數(shù)值算法

第八章基本通訊操作

第九章稠密矩陣運(yùn)算

第十章線性方程組的求解

第十一章快速傅里葉變換

2024/1/211現(xiàn)代密碼學(xué)理論與實踐之五第九章稠密矩陣運(yùn)算

9.1矩陣的劃分

9.2矩陣轉(zhuǎn)置

9.3矩陣-向量乘法

9.3.1帶狀劃分的矩陣-向量乘法

9.3.2棋盤劃分的矩陣-向量乘法

9.3.3矩陣-向量的脈動乘法

9.4矩陣乘法

2024/1/212現(xiàn)代密碼學(xué)理論與實踐之五矩陣-向量乘法

求Y=AX

串行算法計算時間t(n)=O(n2)2024/1/213現(xiàn)代密碼學(xué)理論與實踐之五第九章稠密矩陣運(yùn)算

9.1矩陣的劃分

9.2矩陣轉(zhuǎn)置

9.3矩陣-向量乘法

9.3.1帶狀劃分的矩陣-向量乘法

9.3.2棋盤劃分的矩陣-向量乘法

9.3.3矩陣-向量的脈動乘法

9.4矩陣乘法

2024/1/214現(xiàn)代密碼學(xué)理論與實踐之五帶狀劃分的矩陣-向量乘法（1）

劃分(行帶狀劃分):Pi存放xi和ai,0,ai,1,…,ai,n-1,并輸出yi算法:對p=n情形①每個Pi將其向量元素向其他處理器播送xi(多到多播送)；②每個Pi做相應(yīng)計算；注:對p<n情形,算法中Pi要播送X中相應(yīng)的n/p個分量(1)超立方連接的計算時間

(2)網(wǎng)孔連接的計算時間2024/1/215現(xiàn)代密碼學(xué)理論與實踐之五帶狀劃分的矩陣-向量乘法（2）

示例2024/1/216現(xiàn)代密碼學(xué)理論與實踐之五第九章稠密矩陣運(yùn)算

9.1矩陣的劃分

9.2矩陣轉(zhuǎn)置

9.3矩陣-向量乘法

9.3.1帶狀劃分的矩陣-向量乘法

9.3.2棋盤劃分的矩陣-向量乘法

9.3.3矩陣-向量的脈動乘法

9.4矩陣乘法

2024/1/217現(xiàn)代密碼學(xué)理論與實踐之五棋盤劃分的矩陣-向量乘法（1）

劃分(塊棋盤劃分):Pij存放ai,j,xi置入Pi,i中算法:對p=n2情形

①每個Pi,i將其向量元素向Pj,i播送xi(一到多播送)；②按行方向進(jìn)行乘-加與積累運(yùn)算，最后一列Pi,n-1收集的結(jié)果為yi；注:對p<n2情形,p個處理器排成的二維網(wǎng)孔，算法中Pi,i向Pj,i播送X中相應(yīng)的個分量(1)網(wǎng)孔連接的計算時間Tp(CT):.X中相應(yīng)分量置入Pi,i的通訊時間:.按列一到多播送時間:.按行單點積累的時間:2024/1/218現(xiàn)代密碼學(xué)理論與實踐之五棋盤劃分的矩陣-向量乘法（2）

示例2024/1/219現(xiàn)代密碼學(xué)理論與實踐之五帶狀與棋盤劃分比較以網(wǎng)孔鏈接為例網(wǎng)孔上帶狀劃分的運(yùn)行時間網(wǎng)孔上棋盤劃分的運(yùn)行時間棋盤劃分要比帶狀劃分快。2024/1/2110現(xiàn)代密碼學(xué)理論與實踐之五第九章稠密矩陣運(yùn)算

9.1矩陣的劃分

9.2矩陣轉(zhuǎn)置

9.3矩陣-向量乘法

9.3.1帶狀劃分的矩陣-向量乘法

9.3.2棋盤劃分的矩陣-向量乘法

9.3.3矩陣-向量的脈動乘法

9.4矩陣乘法2024/1/2111現(xiàn)代密碼學(xué)理論與實踐之五矩陣-向量乘法的脈動算法（1）示例2024/1/2112現(xiàn)代密碼學(xué)理論與實踐之五矩陣-向量乘法的脈動算法（2）示例2024/1/2113現(xiàn)代密碼學(xué)理論與實踐之五第九章稠密矩陣運(yùn)算

9.1矩陣的劃分

9.2矩陣轉(zhuǎn)置

9.3矩陣-向量乘法

9.4矩陣乘法

9.4.1簡單并行分塊乘法

9.4.2Cannon乘法

9.4.3Fox乘法

9.4.4Systolic乘法

9.4.5DNS乘法2024/1/2114現(xiàn)代密碼學(xué)理論與實踐之五矩陣乘法符號及定義jiABCA中元素的第2下標(biāo)與B中元素的第1下標(biāo)相一致（對準(zhǔn)）2024/1/2115現(xiàn)代密碼學(xué)理論與實踐之五矩陣乘法并行實現(xiàn)方法計算結(jié)構(gòu)：二維陣列空間對準(zhǔn)(元素已加載到陣列中）

Cannon’s,Fox’s，DNS時間對準(zhǔn)(元素未加載到陣列中）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現(xiàn)代密碼學(xué)理論與實踐之五簡單并行分塊乘法（1）分塊:

A、B和C分成的方塊陣Ai,j、Bi,j和Ci,j,大小均為

p個處理器編號為,Pi,j存放Ai,j、Bi,j和Ci,j。算法:

①通訊:每行處理器進(jìn)行A矩陣塊的多到多播送(得到Ai,k,k=0~)每列處理器進(jìn)行B矩陣塊的多到多播送(得到Bk,j,k=0~)

②乘-加運(yùn)算:Pi,j做運(yùn)行時間

(1)超立方連接：①的時間②的時間2024/1/2117現(xiàn)代密碼學(xué)理論與實踐之五簡單并行分塊乘法（2）運(yùn)行時間

(1)超立方連接：(2)二維環(huán)繞網(wǎng)孔連接：①的時間：②的時間：t2=n3/p注(1)本算法的缺點是對處理器的存儲要求過大每個處理器有個塊，每塊大小為n2/p,

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

(2)p=n2時，t(n)=O(n),c(n)=O(n3)2024/1/2118現(xiàn)代密碼學(xué)理論與實踐之五第九章稠密矩陣運(yùn)算

9.1矩陣的劃分

9.2矩陣轉(zhuǎn)置

9.3矩陣-向量乘法

9.4矩陣乘法

9.4.1簡單并行分塊乘法

9.4.2Cannon乘法

9.4.3Fox乘法

9.4.4Systolic乘法

9.4.5DNS乘法2024/1/2119現(xiàn)代密碼學(xué)理論與實踐之五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現(xiàn)代密碼學(xué)理論與實踐之五Cannon乘法（2）算法原理

(非形式描述，1969年)

①所有塊Ai,j(0≤i,j≤)向左循環(huán)移動i步(按行移位)；所有塊Bi,j(0≤i,j≤)向上循環(huán)移動j步(按列移位)；

②所有處理器Pi,j執(zhí)行Ai,j和Bi,j的乘-加運(yùn)算;

③A的每個塊向左循環(huán)移動一步;

B的每個塊向上循環(huán)移動一步;

④轉(zhuǎn)②執(zhí)行次;2024/1/2121現(xiàn)代密碼學(xué)理論與實踐之五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現(xiàn)代密碼學(xué)理論與實踐之五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現(xiàn)代密碼學(xué)理論與實踐之五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現(xiàn)代密碼學(xué)理論與實踐之五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現(xiàn)代密碼學(xué)理論與實踐之五Cannon乘法（6）時間分析

(1)超立方連接:②和③執(zhí)行次，所以運(yùn)行時間為

(2)二維網(wǎng)孔連接，CT選路模式:②和③執(zhí)行次，所以運(yùn)行時間為

2024/1/2126現(xiàn)代密碼學(xué)理論與實踐之五第九章稠密矩陣運(yùn)算

9.1矩陣的劃分

9.2矩陣轉(zhuǎn)置

9.3矩陣-向量乘法

9.4矩陣乘法

9.4.1簡單并行分塊乘法

9.4.2Cannon乘法

9.4.3Fox乘法

9.4.4Systolic乘法

9.4.5DNS乘法2024/1/2127現(xiàn)代密碼學(xué)理論與實踐之五Fox乘法（1）分塊:

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

①Ai,i向所在行的其他處理器進(jìn)行一到多播送；②各處理器將收到的A塊與原有的B塊進(jìn)行乘-加運(yùn)算;

③B塊向上循環(huán)移動一步;

④如果Ai,j是上次第i行播送的塊，本次選擇向所在行的其他處理器進(jìn)行一到多播送;

⑤轉(zhuǎn)②執(zhí)行次;

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現(xiàn)代密碼學(xué)理論與實踐之五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現(xiàn)代密碼學(xué)理論與實踐之五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現(xiàn)代密碼學(xué)理論與實踐之五Fox乘法（4）運(yùn)行時間

(1)超立方連接:

②、③和④(含①)執(zhí)行次，所以運(yùn)行時間為

當(dāng)p=n2時,t(n)=O(nlogn)(2)二維網(wǎng)孔連接，CT選路模式(思考?)2024/1/2131現(xiàn)代密碼學(xué)理論與實踐之五第九章稠密矩陣運(yùn)算

9.1矩陣的劃分

9.2矩陣轉(zhuǎn)置

9.3矩陣-向量乘法

9.4矩陣乘法

9.4.1簡單并行分塊乘法

9.4.2Cannon乘法

9.4.3Fox乘法

9.4.4Systolic乘法

9.4.5DNS乘法2024/1/2132現(xiàn)代密碼學(xué)理論與實踐之五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現(xiàn)代密碼學(xué)理論與實踐之五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現(xiàn)代密碼學(xué)理論與實踐之五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現(xiàn)代密碼學(xué)理論與實踐之五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現(xiàn)代密碼學(xué)理論與實踐之五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現(xiàn)代密碼學(xué)理論與實踐之五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現(xiàn)代密碼學(xué)理論與實踐之五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現(xiàn)代密碼學(xué)理論與實踐之五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現(xiàn)代密碼學(xué)理論與實踐之五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現(xiàn)代密碼學(xué)理論與實踐之五Systolic乘法（10）c1,1c1,2c1,3c1,4c2,1c2,2c2,3c2,4c3,1c3,2c3,3c3,4a3,1b1,4+Step102024/1/2142現(xiàn)代密碼學(xué)理論與實踐之五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現(xiàn)代密碼學(xué)理論與實踐之五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發(fā)送b給Pi+1,j

endif

ifj<kthen發(fā)送a給Pi,j+1

endif

endwhile

endfor

endforEnd2024/1/2144現(xiàn)代密碼學(xué)理論與實踐之五第九章稠密矩陣運(yùn)算

9.1矩陣的劃分

9.2矩陣轉(zhuǎn)置

9.3矩陣-向量乘法

9.4矩陣乘法

9.4.1簡單并行分塊乘法

9.4.2Cannon乘法

9.4.3Fox乘法

9.4.4Systolic乘法

9.4.5DNS乘法2024/1/2145現(xiàn)代密碼學(xué)理論與實踐之五DNS乘法（1）Motivation:Fromagoodandcommonidea

ji+

11

22

33

nn++...+=ABC2024/1/2146現(xiàn)代密碼學(xué)理論與實踐之五DNS乘法（2）Motivation:Fromagoodandcommonidea(Cont.)

Howtouseprocessorsmoreeffectivelyandpractically?

x11x22x33xnn

...

=...+++nprocessorsforeachresultelementimpliesnxn2=n3timeislog2n2024/1/2147現(xiàn)代密碼學(xué)理論與實踐之五DNS乘法（3）背景:1981年由Dekel、Nassimi和Sahni提出的SIMD-CC上的矩陣乘法,處理器數(shù)目為n3,運(yùn)行時間為O(logn),是一種速度很快的算法?；舅枷?

通過一到一和一到多的播送辦法，使得處理器(k,i,j)擁有ai,k和bk,j,

進(jìn)行本地相乘,再沿k方向進(jìn)行單點積累求和,結(jié)果存儲在處理器(0,i,j)中。處理器編號:

處理器數(shù)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];①數(shù)據(jù)復(fù)制:A,B同時在k維復(fù)制(一到一播送)；

A在j維復(fù)制(一到多播送);B在i維復(fù)制(一到多播送);②相乘運(yùn)算:所有處理器的A、B寄存器兩兩相乘;

③求和運(yùn)算:沿k方向進(jìn)行單點積累求和;

2024/1/2148現(xiàn)代密碼學(xué)理論與實踐之五示例

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維復(fù)制(c)A沿j維復(fù)制(d)B沿i維復(fù)制(e)點積(f)沿k維求和BBAA000010001011100110101111P0P1P2P3P4P5P6P72024/1/2149現(xiàn)代密碼學(xué)理論與實踐之五算法描述://令r(m)表示r的第m位取反；

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

//進(jìn)制