并行算法的設(shè)計(jì)與分析(12)

1、并行算法的設(shè)計(jì)與分析第12章 矩陣運(yùn)算Matrix multiplication is the most studied parallel algorithms. It is a good algorithm to learn because it shows many ideas about parallelism.12.2 矩陣乘積12.2.1 矩陣乘積串行算法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, 0

2、1 , 00 , 0,)()()(nnnnnnnnnnnnnnnnnnnnijnnijnnijbbbbbbbbbaaaaaaaaacccccccccBACcCbBaA設(shè)jiABC10nkkjikijbac i, j=0n-1 A中元素的第2下標(biāo)與B中元素的第1下標(biāo)相一致（對(duì)準(zhǔn)） 串行算法時(shí)間復(fù)雜度O(n3)12.2.2 SIMD-MC2上矩陣乘積并行算法Cannon 算法1. 策略：劃分將A、B和C分成 個(gè)方塊陣Ai,j、Bi,j和Ci,j, 其大小均為p個(gè)處理器編號(hào)為 , Pi,j存放Ai,j、Bi,j和Ci,j (n p)ppppnpn),.,.,(1, 11, 00, 0pppPPPP0

3、,0P1,0P2,0P3,0P0,1P1,1P2,1P3,1P0,2P1,2P2,2P3,2P0,3P1,3P2,3P3,3個(gè)元素npn個(gè)塊p12.2.2 SIMD-MC2上矩陣乘積并行算法Cannon 算法2. 算法思想 并行旋轉(zhuǎn)元素（初始數(shù)據(jù)對(duì)準(zhǔn)）以使得處理器Pi,j準(zhǔn)備好Ai,s和 Bs,j以計(jì)算Ci,j ： 所有塊Ai,j (0i, j )向左左循環(huán)移動(dòng) i 步； 所有塊Bi,j (0i, j ) 向上上循環(huán)移動(dòng) j 步； 并行計(jì)算點(diǎn)積： 所有處理器Pi,j做執(zhí)行Ai,j和Bi,j的乘-加運(yùn)算： Ci,j = Ci,j +Ai,j*Bi,j; 重新對(duì)準(zhǔn)數(shù)據(jù)： A中的每個(gè)塊向左循環(huán)移動(dòng)1

4、步; B中的每個(gè)塊向上循環(huán)移動(dòng)1步; 迭代執(zhí)行步- 執(zhí)行 次;1p1p1p12.2.2 SIMD-MC2上矩陣乘積并行算法Cannon 算法3. 算法描述算法12.6 Mesh上Cannon矩陣乘積算法 輸入: Ann, Bnn; 輸出: Cnn Begin(1) for k=1 to n do / 旋轉(zhuǎn)矩陣元素，數(shù)據(jù)對(duì)準(zhǔn)旋轉(zhuǎn)矩陣元素，數(shù)據(jù)對(duì)準(zhǔn) for all Pi,j par-do (i) if ik then Ai,j Ai, (j+1)mod n / 1個(gè)路由步個(gè)路由步 endif (ii) if jk then Bi,j B(i+1)mod n, j / 1個(gè)路由步個(gè)路由步 endif

5、 endfor endfor (2) for all Pi,j par-do Ci,j=0 endfor (3)for k=1 to n do for all Pi,j par-do (i) Ci,j=Ci,j+Ai,jBi,j / 旋轉(zhuǎn)矩陣元素，數(shù)據(jù)對(duì)準(zhǔn)旋轉(zhuǎn)矩陣元素，數(shù)據(jù)對(duì)準(zhǔn) (ii) Ai,j Ai, (j+1)mod n / 1個(gè)路由步個(gè)路由步 (iii)Bi,j B(i+1)mod n, j / 1個(gè)路由步個(gè)路由步 endfor endfor End12.2.2 SIMD-MC2上矩陣乘積并行算法Cannon 算法4. 算法復(fù)雜度 tc(n)=O(n)+O(1)+O(n)=O(n)，

6、tr(n)=2n+2n=4n路由步 t(n)= tc(n) + tr(n) =O(n)+4n=O(n) c(n)=n2O(n)= O(n3)，執(zhí)行代價(jià)最優(yōu) Sp(n)=O(n3)/O(n)= O(n2)，線性加速5. 算法討論 如果MESH機(jī)器只有p個(gè)處理器，那么每個(gè)處理器就要處理一個(gè)矩陣塊。 此時(shí)，要求每個(gè)處理器具有較大的局部存儲(chǔ)空間，而且每個(gè)處理器串行地執(zhí)行矩陣乘積算法計(jì)算A矩陣塊和B矩陣塊的乘積。12.2.2 SIMD-MC2上矩陣乘積并行算法Cannon 算法6. 示例A0,0A1,0A2,0A3,0A0,1A1,1A2,1A3,1A0,2A1,2A2,2A3,2A0,3A1,3A2,

7、3A3,3B0,0B1,0B2,0B3,0B0,1B1,1B2,1B3,1B0,2B1,2B2,2B3,2B0,3B1,3B2,3B3,3Initial alignment of AInitial alignment of B12.2.2 SIMD-MC2上矩陣乘積并行算法Cannon 算法6. 示例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

8、,1B1,2A0,3B3,3A1,0B0,3A2,1B1,3A3,2B2,312.2.2 SIMD-MC2上矩陣乘積并行算法Cannon 算法 1 2 3 9 8 7 Aij 循環(huán)左移一列設(shè)：A= 4 5 6 B=6 5 4 求C=AB 結(jié)點(diǎn)內(nèi)容：Bij 循環(huán)上移一行 7 8 9 3 2 1 Cij初始： 1 2 3 旋轉(zhuǎn)對(duì)準(zhǔn)旋轉(zhuǎn)對(duì)準(zhǔn)1： 1 2 3 旋轉(zhuǎn)對(duì)準(zhǔn)旋轉(zhuǎn)對(duì)準(zhǔn)2 ： 1 2 3 旋轉(zhuǎn)對(duì)準(zhǔn)旋轉(zhuǎn)對(duì)準(zhǔn)3： 1 2 3 9 8 7 k=1 9 5 4 k=2 9 5 1 k=3 9 5 1 4 5 6 i1 5 6 4 i2 5 6 4 i3 5 6 4 6 5 4 j1 6 2 1 j2 6

9、 2 7 j3 6 2 7 7 8 9 8 9 7 9 7 8 9 7 8 3 2 1 3 8 7 3 8 4 3 8 4賦初賦初 1 2 3 計(jì)算對(duì)準(zhǔn)計(jì)算對(duì)準(zhǔn)1： 2 3 1 計(jì)算對(duì)準(zhǔn)計(jì)算對(duì)準(zhǔn)2 ： 3 1 2 計(jì)算對(duì)準(zhǔn)計(jì)算對(duì)準(zhǔn)3：1 2 3 值零值零 9 5 1 k=1 6 2 7 k=2 3 8 4 k=3 9 5 1 0 0 0 9 10 3 21 16 10 30 24 18 5 6 4 6 4 5 4 5 6 5 6 4 6 2 7 3 8 4 9 5 1 6 2 7 0 0 0 30 12 28 48 44 48 84 69 54 9 7 8 7 8 9 8 9 7 9 7 8

10、3 8 4 9 5 1 6 2 7 3 8 4 0 0 0 27 56 32 90 96 41 138 114 90 12.2.3 SIMD-CC模型上的矩陣乘法v 背景：由Dekel、Nassimi和Sahni 于1981年提出SIMD-CC上的矩陣乘法(DNS乘法), 處理器數(shù)目為n3, 運(yùn)行時(shí)間為O(logn), 是一種速度很快的算法。v 基本思想： 通過(guò)一到一和一到多的播送辦法，使得處理器(k,i,j)擁有ai,k和bk,j，進(jìn)行本地相乘，再沿k方向進(jìn)行單點(diǎn)積累求和，結(jié)果存儲(chǔ)在處理器(0,i,j)中。v 處理器編號(hào)：處理器數(shù)p=n3= (2q)3=23q, 處理器Pr位于位置(k,i,

11、j), 這里r=kn2+ i n+j, (0i, j, kn-1)。位于(k,i,j)的處理器Pr的三個(gè)寄存器Ar,Br,Cr分別表示為Ak,i,j, Bk,i,j和Ck,i,j, 初始時(shí)它們的值均為0。v 算法步驟：初始時(shí)ai,j和bi,j存儲(chǔ)于寄存器A0,i,j和B0,i,j; 數(shù)據(jù)復(fù)制：A,B同時(shí)在k維復(fù)制(一到一播送)；A在j維復(fù)制 (一到多播送); B在i 維復(fù)制(一到多播送); 相乘運(yùn)算：所有處理器的A、B寄存器兩兩相乘; 求和運(yùn)算：沿k方向進(jìn)行單點(diǎn)積累求和; DNS算法(A,B,C) / 令r(m)表示r 的第m位取反；p, rm=d表示r (0rp-1)的集合, / r 的二進(jìn)

12、制第 m 位為d; / 輸入: Ann, Bnn; 輸出: Cnn Begin (1) for m=3q-1 to 2q do /按 k 維復(fù)制A, B； q=logn for all r in p, rm=0 par-do (1.1) Ar(m) Ar / 1個(gè)路由步個(gè)路由步 (1.2) Br(m) Br / 1個(gè)路由步個(gè)路由步 (2) for m=q-1 to 0 do /按 j 維復(fù)制A for all r in p, rm= r2q+m par-do Ar(m) Ar ； / 1個(gè)路由步個(gè)路由步 (3) for m=2q-1 to q do /按i維復(fù)制B for all r in p

13、, rm= rq+m par-do Br(m) Br / 1個(gè)路由步個(gè)路由步 (4) for r=0 to p-1 par-do /相乘 Cr=ArBr / O(1)時(shí)間時(shí)間 (5) for m=2q to 3q-1 do /求和 for r=0 to p-1 par-do Cr=Cr+Cr(m) / 1個(gè)路由步，個(gè)路由步，O(1)時(shí)間時(shí)間 End 復(fù)雜度：t(n)=5logn+O(logn)=O(logn),p(n)=n3,c(n)=O(n3logn),Sp(n)=O(n3/logn)示例BACBA求87654321kji101P5111P7100P4110P6001P1011P3000P0

14、010P2初始加載(b)A,B沿k維復(fù)制AA(c)A沿j維復(fù)制BB(d)B沿i維復(fù)制(e)點(diǎn)積(f)沿k維求和 /輸入: Amn, Bnk; 輸出: Cmk Begin for i=1 to m par- do for j=1 to k par-do (i) ci,j = 0 (ii) while Pi,j 收到a和b時(shí) 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 End12.4 矩陣乘法： Systolic算法12.4 矩陣乘法12.4

15、Systolic乘法(H.T. Kung) 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,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,412.4 矩陣乘法12.4 Systolic乘法(H.T. Kung) c1,1c1,2c1,3c1,4c2,1c2,2c2,

16、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+Step 212.4 矩陣乘法12.4 Systolic乘法(H.T. Kung) 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,1

17、b1,2b1,3b1,4a1,3b3,1+a1,4b4,2+a2,4b4,1+Step 312.4 矩陣乘法12.4 Systolic乘法(H.T. Kung) 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 412.4 矩陣乘法12.4 Systolic乘法(H.T. Kung) c1,1c1,2c1,

18、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+Step 512.4 矩陣乘法12.4 Systolic乘法(H.T. Kung) 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+Step 612.4 矩陣乘法12.4 Systolic乘法(H.T. Kung) 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 712.4 矩陣乘法12.4.4 Systolic乘法(H.T.