中國科技大學并行計算課件9稠密矩陣運算

1、并 行 計 算 中國科學技術大學計算機科學與技術系國家高性能計算中心(合肥)2004年12月2022/9/111現(xiàn)代密碼學理論與實踐之五第三篇 并行數(shù)值算法 第八章 基本通訊操作 第九章 稠密矩陣運算 第十章 線性方程組的求解 第十一章 快速傅里葉變換 2022/9/112現(xiàn)代密碼學理論與實踐之五第九章 稠密矩陣運算 9.1 矩陣的劃分 9.2 矩陣轉置 9.3 矩陣-向量乘法 9.4 矩陣乘法2022/9/113現(xiàn)代密碼學理論與實踐之五9.1 矩陣的劃分 9.1.1 帶狀劃分 9.1.2 棋盤劃分 2022/9/114現(xiàn)代密碼學理論與實踐之五 帶狀劃分1616階矩陣，p=4 列塊帶狀劃分 行

2、循環(huán)帶狀劃分2022/9/115現(xiàn)代密碼學理論與實踐之五 帶狀劃分示例：p3，27 27矩陣的3種帶狀劃分 2022/9/116現(xiàn)代密碼學理論與實踐之五9.1 矩陣的劃分 9.1.1 帶狀劃分 9.1.2 棋盤劃分 2022/9/117現(xiàn)代密碼學理論與實踐之五 棋盤劃分88階矩陣，p=16 塊棋盤劃分 循環(huán)棋盤劃分2022/9/118現(xiàn)代密碼學理論與實踐之五 棋盤劃分示例：p4，1616矩陣的3種棋盤劃分 2022/9/119現(xiàn)代密碼學理論與實踐之五第九章 稠密矩陣運算 9.1 矩陣的劃分 9.2 矩陣轉置 9.3 矩陣-向量乘法 9.4 矩陣乘法2022/9/1110現(xiàn)代密碼學理論與實踐之五

3、9.2 矩陣轉置 9.2.1 棋盤劃分的矩陣轉置 9.2.2 帶狀劃分的矩陣轉置 2022/9/1111現(xiàn)代密碼學理論與實踐之五 棋盤劃分的矩陣轉置網(wǎng)孔連接情形1: p=n2。 通訊步 轉置后2022/9/1112現(xiàn)代密碼學理論與實踐之五 棋盤劃分的矩陣轉置情形2: pn2。 - 劃分: - 算法: 按mesh連接進行塊轉置(不同處理器間) 進行塊內(nèi)轉置(同一處理器內(nèi)) 通訊步 轉置后2022/9/1113現(xiàn)代密碼學理論與實踐之五 棋盤劃分的矩陣轉置超立方連接劃分: 算法: 對Aij遞歸應用進行轉置，直至分塊矩陣的元素處于同一處理器； 進行同一處理器的內(nèi)部轉置。運行時間: 2022/9/111

4、4現(xiàn)代密碼學理論與實踐之五 棋盤劃分的矩陣轉置超立方連接：示例 2022/9/1115現(xiàn)代密碼學理論與實踐之五9.2 矩陣轉置 9.2.1 棋盤劃分的矩陣轉置 9.2.2 帶狀劃分的矩陣轉置 2022/9/1116現(xiàn)代密碼學理論與實踐之五 帶狀劃分的矩陣轉置 劃分: Ann分成p個(n/p)n大小的帶算法: Pi有p-1個(n/p)(n/p)大小子塊發(fā)送到另外p-1個處理器中; 每個處理器本地交換相應的元素 2022/9/1117現(xiàn)代密碼學理論與實踐之五第九章 稠密矩陣運算 9.1 矩陣的劃分 9.2 矩陣轉置 9.3 矩陣-向量乘法 9.4 矩陣乘法2022/9/1118現(xiàn)代密碼學理論與實踐

5、之五9.3 矩陣-向量乘法 9.3.1 帶狀劃分的矩陣-向量乘法 9.3.2 棋盤劃分的矩陣-向量乘法 2022/9/1119現(xiàn)代密碼學理論與實踐之五 帶狀劃分的矩陣-向量乘法 劃分(行帶狀劃分): Pi存放xi和ai,0,ai,1,ai,n-1, 并輸出yi算法: 對p=n情形 每個Pi向其他處理器播送xi(多到多播送)； 每個Pi計算；注: 對pn情形,算法中Pi要播送X中相應的n/p個分量 (1)超立方連接的計算時間 (2)網(wǎng)孔連接的計算時間2022/9/1120現(xiàn)代密碼學理論與實踐之五 帶狀劃分的矩陣-向量乘法 示例2022/9/1121現(xiàn)代密碼學理論與實踐之五9.3 矩陣-向量乘法

6、9.3.1 帶狀劃分的矩陣-向量乘法 9.3.2 棋盤劃分的矩陣-向量乘法 2022/9/1122現(xiàn)代密碼學理論與實踐之五 棋盤劃分的矩陣-向量乘法 劃分(塊棋盤劃分): Pij存放ai,j, xi置入Pi,i中算法: 對p=n2情形 每個Pi,i向Pj,i播送xi(一到多播送)； 按行方向進行乘-加與積累運算，最后一列Pi,n-1收集的結果為yi；注: 對p p)P0,0P1,0P2,0P3,0P0,1P1,1P2,1P3,1P0,2P1,2P2,2P3,2P0,3P1,3P2,3P3,32022/9/1133現(xiàn)代密碼學理論與實踐之五Cannon乘法算法原理 (非形式描述) 所有塊Ai,j(

7、0i,j )向左循環(huán)移動i步(按行移位)； 所有塊Bi,j(0i,j )向上循環(huán)移動j步(按列移位)； 所有處理器Pi,j做執(zhí)行Ai,j和Bi,j的乘-加運算; A的每個塊向左循環(huán)移動一步; B的每個塊向上循環(huán)移動一步; 轉執(zhí)行 次;2022/9/1134現(xiàn)代密碼學理論與實踐之五Cannon乘法示例： A44， B44, 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,3Initi

8、al alignment of AInitial alignment of B2022/9/1135現(xiàn)代密碼學理論與實踐之五Cannon乘法示例： A44， B44, 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,32022/9/1136現(xiàn)代密碼學理論與實踐之五C

9、annon乘法示例： A44， B44, 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,3A1,2B2,

10、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,32022/9/1137現(xiàn)代密碼學理論與實踐之五Cannon乘法算法描述: Cannon分塊乘法算法 /輸入: Ann, Bnn; 輸出: Cnn Begin (1)for k=0 to do for all Pi,j par-do (i) if ik then Ai,j Ai

11、,(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 endfor endfor End時間分析：2022/9/1138現(xiàn)代密碼學理論與實踐之五9.4 矩陣乘法 9.4.1 簡單并行分塊乘法 9.4.2 Cannon乘法 9.4

12、.3 Fox乘法 9.4.4 Systolic乘法 9.4.5 DNS乘法2022/9/1139現(xiàn)代密碼學理論與實踐之五Fox乘法分塊: 同Cannon分塊算法算法原理 Ai,i向所在行的其他處理器進行一到多播送； 各處理器將收到的A塊與原有的B塊進行乘-加運算; B塊向上循環(huán)移動一步; 如果Ai,j是上次第i行播送的塊，本次選擇 向所 在行的其他處理器進行一到多播送; 轉執(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

13、,3B1,3A2,3B2,3A3,3B3,32022/9/1140現(xiàn)代密碼學理論與實踐之五Fox乘法示例： A44， B44, 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,02022/9/1141現(xiàn)代密碼學理論與實踐之五Fox乘法示例： A44， B44, p=16 (c) (d)B2,0B3,0B2

14、,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,22022/9/1142現(xiàn)代密碼學理論與實踐之五9.4 矩陣乘法 9.4.1 簡單并行分塊乘法 9.4.2 Cannon乘法 9.4.3 Fox乘法 9.4.4 Systolic乘法 9.4.5 DNS乘法2022/9/1143現(xiàn)代密碼學理論與實踐之五Systolic乘法a1,4b4,1b3,1b2,

15、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 1P1,1c1,1P1,2c1,2P1,3c1,3P1,4c1,4P2, 1c2,1P2,2c2,2P2,3c2,3P2,4c2,4P3,1c3,1P3,2c3,2P3,3c3,3P3,4c3,42022/9/1144現(xiàn)代密碼學理論與實踐之五Systolic乘法c1,1c1,2c1,3c1,4c2,1c2,2c2,3c2,4c3,1c3,2c3,3c3,4b3,1b2,1b2,2b4,2b3,

16、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 22022/9/1145現(xiàn)代密碼學理論與實踐之五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

17、 32022/9/1146現(xiàn)代密碼學理論與實踐之五Systolic乘法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+Step 42022/9/1147現(xiàn)代密碼學理論與實踐之五Systolic乘法c1,1c1,2c1,3c1,4c2,1c2,2c2,3c2,4c3,1c3,2c3,3c3,4b2,3b2,4b3,4

18、a2,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+Step 52022/9/1148現(xiàn)代密碼學理論與實踐之五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+St

19、ep 62022/9/1149現(xiàn)代密碼學理論與實踐之五Systolic乘法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+Step 72022/9/1150現(xiàn)代密碼學理論與實踐之五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,

20、3+a3,3b3,4+Step 82022/9/1151現(xiàn)代密碼學理論與實踐之五Systolic乘法c1,1c1,2c1,3c1,4c2,1c2,2c2,3c2,4c3,1c3,2c3,3c3,4a2,1b1,4+a3,1b1,3+a3,2b2,4+Step 92022/9/1152現(xiàn)代密碼學理論與實踐之五Systolic乘法c1,1c1,2c1,3c1,4c2,1c2,2c2,3c2,4c3,1c3,2c3,3c3,4a3,1b1,4+Step 102022/9/1153現(xiàn)代密碼學理論與實踐之五Systolic乘法P1,1c1,1P1,2c1,2P1,3c1,3P1,4c1,4P2, 1c2

21、,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,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 2022/9/1154現(xiàn)代密碼學理論與實踐之五Systolic乘法 Systolic算法 /輸入: Amn, Bnk; 輸出: Cmk Begin for i

22、=1 to m 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 發(fā)送b給Pi+1,j endif if j k then 發(fā)送a給Pi,j+1 endif endwhile endfor endfor End2022/9/1155現(xiàn)代密碼學理論與實踐之五9.4 矩陣乘法 9.4.1 簡單并行分塊乘法 9.4.2 Cannon乘法 9.4.3 Fox乘法 9.4.4 Systolic乘法 9.4.5 DNS乘法2022/9/1156現(xiàn)代密碼學理論與實踐之五

23、DNS乘法背景: 由Dekel、Nassimi和Sahni提出的SIMD-CC上的矩陣乘法, 處理器 數(shù)目為n3, 運行時間為O(logn), 是一種速度很快的算法?；舅枷? 通過一到一和一到多的播送辦法，使得處理器(k,i,j)擁有ai,k和bk,j, 進行本地相乘,再沿k方向進行單點積累求和,結果存儲在處理器(0,i,j)中。處理器編號: 處理器數(shù)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, 初

24、始時均為0。算法: 初始時ai,j和bi,j存儲于寄存器A0,i,j和B0,i,j; 數(shù)據(jù)復制:A,B同時在k維復制(一到一播送)； A在j維復制(一到多播送); B在i維復制(一到多播送); 相乘運算:所有處理器的A、B寄存器兩兩相乘; 求和運算:沿k方向進行單點積累求和; 2022/9/1157現(xiàn)代密碼學理論與實踐之五示例 C00=1(-5)+27=9C01=1(-6)+28=10C10=3(-5)+47=13C11=3(-6)+48=14 kji初始加載(b)A,B沿k維復制(c)A沿j維復制(d)B沿i維復制(e)點積(f)沿k維求和BBAA000010001011100110101111P0P1P2P3P4P5P6P72022/9/1158現(xiàn)代密碼學理論與