并行计算流水线计算

1、a4a3a2 a4 a3 a2 a1 a1 a4 a3 a2 a4 a3P 0P 1P 2P 3P 4 a4aSin SoutaSin Souta1aSin Souta2aSin Souta3a0sum每个处理机（流水线中的中间级）需要执行相同的操作：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 个问题实例而言，算法的执行时间： = m + p - 1 个流水线周期第2种情况：每个数据项需要多次操作d0d1d0d1d0d2d1d0d2d3d4d3d1d0d2d0d5d4d2d1d3d1d0d2d7d6d4d3d5d1d0d2d3d8d7d5d4d6d4d3d1d0d2d9d8d6d5d7

3、d1d0d6d5d3d2d4d2d1d3d4d9d8d6d5d7d3d2d4d9d8d6d5d7d4d3d9d8d6d5d7d4d9d8d6d5d7d9d8d6d5d7 TimeP9P8P7P6P5P4P3P2P1P0p-1m输入序列输入序列d9d8d7d6d5d4d3d2d1d0P1P2P3P4P5P6P7P8P9P0第3种情况：在进程执行结束之前传递信息给流水线中的下一个进程，使其能够开始工作。启动下一个进程必须的信息传输P0P1P2P3P4P5P6P7P8Processor 0Processor 1Processor 2主机Processors多处理机系统多处理机系统因为工作站群机系统因

4、为工作站群机系统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假设流水线系统拥有n个处理机；第 i 个处理机的局部存储器中应存有 A 矩阵的第 i 列数据 a1, a2, am，以及 X 的第 i 个分量 xi。1k1a1kxk1k2a1kxk1k1a2kxk1k3a1kxk1k2a2kxk1k1a3kxk

5、1k4a1kxk1k3a2kxk1k2a3kxk1k1a4kxkR11k5a1kxk1k4a2kxk1k3a3kxk1k2a4kxk1k1a5kxkP5P4P3P2P1时间1k5a3kxk1k4a4kxk1k3a5kxkR3 1k5a2kxk1k4a3kxk1k3a4kxk1k2a5kxkR2该算法的执行结果是从最后一个进程得到的。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