并行計算流水線計算

1、a4a3a2 a4 a3 a2 a1 a1 a4 a3 a2 a4 a3P 0P 1P 2P 3P 4 a4aSin SoutaSin Souta1aSin Souta2aSin Souta3a0sum每個處理機（流水線中的中間級）需要執(zhí)行相同的操作：recv (sum,Pi-1);sum = sum + a;send (sum, Pi+1);aSin SoutaSin Souta1aSin Souta2aSin Souta3a0sum實例實例1實例實例1實例實例1實例實例1實例實例1實例實例1實例實例2實例實例2實例實例2實例實例2實例實例2實例實例2實例實例3實例實例3實例實例3實例實例3

2、實例實例3實例實例3實例實例4實例實例4實例實例4實例實例4實例實例4實例實例4實例實例5實例實例5實例實例5實例實例5實例實例5實例實例6實例實例6實例實例6實例實例6實例實例7實例實例7實例實例7P0P1P2P3P4P5時間時間p-1mv假設每個流水線級均用一個流水線周期，對有 p 級流水線和 m 個問題實例而言，算法的執(zhí)行時間： = m + p - 1 個流水線周期第2種情況：每個數據項需要多次操作d0d1d0d1d0d2d1d0d2d3d4d3d1d0d2d0d5d4d2d1d3d1d0d2d7d6d4d3d5d1d0d2d3d8d7d5d4d6d4d3d1d0d2d9d8d6d5d7

3、d1d0d6d5d3d2d4d2d1d3d4d9d8d6d5d7d3d2d4d9d8d6d5d7d4d3d9d8d6d5d7d4d9d8d6d5d7d9d8d6d5d7 TimeP9P8P7P6P5P4P3P2P1P0p-1m輸入序列輸入序列d9d8d7d6d5d4d3d2d1d0P1P2P3P4P5P6P7P8P9P0第3種情況：在進程執(zhí)行結束之前傳遞信息給流水線中的下一個進程，使其能夠開始工作。啟動下一個進程必須的信息傳輸P0P1P2P3P4P5P6P7P8Processor 0Processor 1Processor 2主機Processors多處理機系統(tǒng)多處理機系統(tǒng)因為工作站群機系統(tǒng)因

4、為工作站群機系統(tǒng)NOWs中處理器間的物理連中處理器間的物理連接通常是星形的，所以它不適于流水計算。接通常是星形的，所以它不適于流水計算。 a11 a12 a13 a1n-1 a1n a21 a22 a23 a2n-1 a2n A = a31 a32 a33 a3n-1 a3n . am1 am2 am3 amn-1 amn x1 x2X = x3 xn假設流水線系統(tǒng)擁有n個處理機；第 i 個處理機的局部存儲器中應存有 A 矩陣的第 i 列數據 a1, a2, am，以及 X 的第 i 個分量 xi。1k1a1kxk1k2a1kxk1k1a2kxk1k3a1kxk1k2a2kxk1k1a3kxk

5、1k4a1kxk1k3a2kxk1k2a3kxk1k1a4kxkR11k5a1kxk1k4a2kxk1k3a3kxk1k2a4kxk1k1a5kxkP5P4P3P2P1時間1k5a3kxk1k4a4kxk1k3a5kxkR3 1k5a2kxk1k4a3kxk1k3a4kxk1k2a5kxkR2該算法的執(zhí)行結果是從最后一個進程得到的。PiP2PpP1計算 A*X就轉化為計算： A1 X1 + A2 X2 + Ap Xp處理器Pi（其中1 i p）將Ai 和 Xi 存放在自己的局部存儲器中，各處理器首先計算 Ai Xi ，然后利用通信（流水線方式）實現數據求和。X1(r*1)X2(r*1)Xp(r

6、*1)A = A1 A2 Ap X = (m*r) (m*r) (m*r) compute z = Bw; / z 有m個分量 if (i = 1) R = 0 ; / R 有m個分量 else receive (R , left) ; R = R + z; send (R , right); if (i = 1) receive (R , left);p1p3p2p4計算計算z=Bw計算計算z=Bw計算計算z=Bw計算計算z=BwR=0rec(R, p1)rec(R, p2)rec(R, p3)R=R+zsend(R,p2)send(R,p3)send(R,p4)rec(R,p4)send(

7、R,p1)R=R+zR(1)R=R+zR(2)R=R+zR(3)R(4)結束結束可將結果返回給主進程的雙向流水線機器結構:未排序未排序的數列的數列P0P1Pp-1主進程主進程從進程從進程未排序未排序的數列的數列P0P1Pp-1主進程主進程從進程從進程已排序已排序的數列的數列P0P1P2P3P4流水線時間流水線時間將要被排序的數列：5, 2, 1, 3, 41542354132542315531245423152251152331524P0P1P2P3P4流水線時間流水線時間將要被排序的數列：1, 2, 3, 4, 5 15423541325423115312454231121232314314

8、252923191713117532最終結果Ts =N- 1 2+1 1N- 2 2+1 2N- k 2+1 k+ + =N +1- 1 2 1N +1- 2 2 2N +1- k 2 k+ + =N - 3 2N -8 3N +1- k 2 k+ +當N=1000時,串行算法的時間為1411(單位時間)。0 100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 加速比=1411/7062并行效率 2/2 1加速比=1411/4992.83并行效率 2.83/3 0.94當處理器的個數為 4 時，加速比 = 1411 / 499 2.83P0篩去篩去 2 的倍數的倍數篩去篩去 3 的倍數的倍數P1篩去篩去 5 的倍數的倍數P2進進 程程P1P2P0P3P4時間an-1,0 x0+an-1,1 x1+ an-1,2 x2+ an-1,n-2 xn-2+ an-1,n-1 xn-1 = bn-1an-2,0 x0+an-2,1 x1+ an-2,2 x2+ an-2,n-2 xn-2 = bn-2an-3,0 x0+an-3,1 x1+ an-3,2 x2+ = bn-3 a2,0 x0+a2,1 x1+ a2,2 x2 = b2a1,0 x0+a