稠密矩陣運算課件

并行計算

2023/7/221第三篇并行數(shù)值算法

第八章基本通訊操作

第九章稠密矩陣運算

第十章線性方程組的求解

第十一章快速傅里葉變換

2023/7/222第九章稠密矩陣運算

9.1矩陣的劃分

9.2矩陣轉(zhuǎn)置

9.3矩陣-向量乘法

9.4矩陣乘法

2023/7/2239.1矩陣的劃分

9.1.1帶狀劃分

9.1.2棋盤劃分

2023/7/224帶狀劃分16×16階矩陣，p=4列塊帶狀劃分行循環(huán)帶狀劃分2023/7/225帶狀劃分示例：p＝3，27×27矩陣的3種帶狀劃分

2023/7/2269.1矩陣的劃分

9.1.1帶狀劃分

9.1.2棋盤劃分

2023/7/227棋盤劃分8×8階矩陣，p=16塊棋盤劃分循環(huán)棋盤劃分2023/7/228棋盤劃分示例：p＝4，16×16矩陣的3種棋盤劃分

2023/7/229第九章稠密矩陣運算

9.1矩陣的劃分

9.2矩陣轉(zhuǎn)置

9.3矩陣-向量乘法

9.4矩陣乘法

2023/7/22109.2矩陣轉(zhuǎn)置

9.2.1棋盤劃分的矩陣轉(zhuǎn)置

9.2.2帶狀劃分的矩陣轉(zhuǎn)置

2023/7/2211棋盤劃分的矩陣轉(zhuǎn)置網(wǎng)孔連接情形1:p=n2。通訊步轉(zhuǎn)置后2023/7/2212棋盤劃分的矩陣轉(zhuǎn)置情形2:p<n2。

-劃分:-算法:①按mesh連接進(jìn)行塊轉(zhuǎn)置(不同處理器間)②進(jìn)行塊內(nèi)轉(zhuǎn)置(同一處理器內(nèi))通訊步轉(zhuǎn)置后2023/7/2213棋盤劃分的矩陣轉(zhuǎn)置超立方連接劃分:算法:

①

②對Aij遞歸應(yīng)用①進(jìn)行轉(zhuǎn)置，直至分塊矩陣的元素處于同一處理器；

③進(jìn)行同一處理器的內(nèi)部轉(zhuǎn)置。運行時間:

2023/7/2214棋盤劃分的矩陣轉(zhuǎn)置超立方連接：示例

2023/7/22159.2矩陣轉(zhuǎn)置

9.2.1棋盤劃分的矩陣轉(zhuǎn)置

9.2.2帶狀劃分的矩陣轉(zhuǎn)置

2023/7/2216帶狀劃分的矩陣轉(zhuǎn)置

劃分:An×n分成p個(n/p)×n大小的帶算法:

①Pi有p-1個(n/p)×(n/p)大小子塊發(fā)送到另外p-1個處理器中;②每個處理器本地交換相應(yīng)的元素

2023/7/2217第九章稠密矩陣運算

9.1矩陣的劃分

9.2矩陣轉(zhuǎn)置

9.3矩陣-向量乘法

9.4矩陣乘法

2023/7/22189.3矩陣-向量乘法

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

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

2023/7/2219帶狀劃分的矩陣-向量乘法

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

(2)網(wǎng)孔連接的計算時間2023/7/2220帶狀劃分的矩陣-向量乘法

示例2023/7/22219.3矩陣-向量乘法

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

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

2023/7/2222棋盤劃分的矩陣-向量乘法

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

①每個Pi,i向Pj,i播送xi(一到多播送)；②按行方向進(jì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的通訊時間:.按列一到多播送時間:.按行單點積累的時間:2023/7/2223棋盤劃分的矩陣-向量乘法

示例2023/7/2224帶狀與棋盤劃分比較以網(wǎng)孔鏈接為例網(wǎng)孔上帶狀劃分的運行時間網(wǎng)孔上棋盤劃分的運行時間棋盤劃分要比帶狀劃分快。2023/7/2225第九章稠密矩陣運算

9.1矩陣的劃分

9.2矩陣轉(zhuǎn)置

9.3矩陣-向量乘法

9.4矩陣乘法

2023/7/22269.4矩陣乘法

9.4.1簡單并行分塊乘法

9.4.2Cannon乘法

9.4.3Fox乘法

9.4.4Systolic乘法

9.4.5DNS乘法2023/7/2227矩陣乘法符號及定義jiABCA中元素的第1下標(biāo)與B中元素的第2下標(biāo)相一致（對準(zhǔn)）2023/7/2228矩陣乘法并行實現(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,32023/7/2229簡單并行分塊乘法分塊:

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~)

②乘-加運算:Pi,j做運行時間

(1)超立方連接：①的時間②的時間2023/7/2230簡單并行分塊乘法運行時間

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

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

(2)p=n2時，t(n)=O(n),c(n)=O(n3)2023/7/22319.4矩陣乘法

9.4.1簡單并行分塊乘法

9.4.2Cannon乘法

9.4.3Fox乘法

9.4.4Systolic乘法

9.4.5DNS乘法2023/7/2232Cannon乘法分塊: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,32023/7/2233Cannon乘法算法原理(非形式描述)

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

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

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

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

④轉(zhuǎn)②執(zhí)行次;2023/7/2234Cannon乘法示例：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,3InitialalignmentofAInitialalignmentofB2023/7/2235Cannon乘法示例：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,32023/7/2236Cannon乘法示例：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,32023/7/2237Cannon乘法算法描述: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時間分析：2023/7/22389.4矩陣乘法

9.4.1簡單并行分塊乘法

9.4.2Cannon乘法

9.4.3Fox乘法

9.4.4Systolic乘法

9.4.5DNS乘法2023/7/2239Fox乘法分塊:

同Cannon分塊算法算法原理

①Ai,i向所在行的其他處理器進(jìn)行一到多播送；②各處理器將收到的A塊與原有的B塊進(jì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,32023/7/2240Fox乘法示例：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,02023/7/2241Fox乘法示例：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,22023/7/22429.4矩陣乘法

9.4.1簡單并行分塊乘法

9.4.2Cannon乘法

9.4.3Fox乘法

9.4.4Systolic乘法

9.4.5DNS乘法2023/7/2243Systolic乘法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,42023/7/2244Systolic乘法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+Step22023/7/2245Systolic乘法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+Step32023/7/2246Systolic乘法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+Step42023/7/2247Systolic乘法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+Step52023/7/2248Systolic乘法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+Step62023/7/2249Systolic乘法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+Step72023/7/2250Systolic乘法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+Step82023/7/2251Systolic乘法c1,1c1,2c1,3c1,4c2,1c2,2c2,3c2,4c3,1c3,2c3,3c3,4a2,1b1,4+a3,1b1,3+a3,2b2,4+Step92023/7/2252Systolic乘法c1,1c1,2c1,3c1,4c2,1c2,2c2,3c2,4c3,1c3,2c3,3c3,4a3,1b1,4+Step102023/7/2253Systolic乘法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

2023/7/2254Systolic乘法

Systolic算法

//輸入: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

endforEnd2023/7/22559.4矩陣乘法

9.4.1簡單并行分塊乘法

9.4.2Cannon乘法

9.4.3Fox乘法

9.4.4Systolic乘法

9.4.5DNS乘法2023/7/2256DNS乘法背景:

由Dekel、Nassimi和Sahni提出的SIMD-CC上的矩陣乘法,處理器數(shù)目為n3,運行時間為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ù)制(一到多播送);②相乘運算:所有處理器的A、B寄存器兩兩相乘;

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

2023/7/2257示例

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維求和BBAA000010001011100110101111P0P1P2P3P4P5P6P72023/7/2258算法描述://令r(m)表示r的第m位取