Chapter 5 流水线计算

适合流水线计算的情形

一个问题被分成一系列的任务，如果：

整个问题的多个实例。
要处理一系列的数据项，每个数据需要多次步骤。
每个进程在完成自身的操作前，能把下一个进程需要的信息向前传送。

类型一

- 每个实例要依次顺序经过p个进程， - 经过开始的p-1个周期后，每个周期完成一个实例。 - p个进程构成的流水线，完成m个问题实例，需要m+p-1 个流水线周期。平均周期为 m+p-1 /m 。当m较大时，趋于1.

类型二

有一串数据必须被顺序处理。每个数据要经过一系列的操作。

类型三

每个进程都能在自己的工作完成前，把下一个进程需要的数据传递出去。

流水线加法-类型1

流水线周期：所有的进程同时运行一个周期。
- ttotal=流水线周期时间×周期数 =（tcomp+tcomm）×周期数
单实例问题：
- 即只有一组数（n个）需要相加,因为只有一组数m=1 所以需要n个周期
- 在一个周期中，每个进程需要完成1次运算，两次数据传递。
  - tcomp=1
  - tcomm=2（tstartup +tdata）
- ttotal = n（1+2（tstartup +tdata））即复杂度为O（n）
多实例问题
- 有m组数需要相加。需要的周期数为m+n-1
- ttotal =（ m+n-1）（1+2（tstartup +tdata））
- 平均每组ta=ttotal/m = （ m+n-1）（1+2（tstartup +tdata）） /m
- 当m很大时，趋近于1.

并行插入排序-类型2

进程p0接受数列的第一个数字。
保存当前接收到的最大数字，且把比这个数小的其他数传给下一个进程。
如果输入的数比当前保存的大，就替换掉当前的数，原先存储的数字往下传递。
每个后继进程都采用同样的算法。
结束后P0中保存最大的数，P1，第二大的数等。

并行复杂度：

n个数，n个进程
周期数为n+n-1 =2n-1
每个周期有一个比较和交换操作，以及一次recv 和send
ttotal=（2n-1）×（1+2（tstartup+tdata））
线性复杂度。

生成素数-类型三

流水线的第一级输入从2开始的一系列连续的数（如果不是（不从2开始，或者不连续），此算法还要修正），剔除所有2的倍数并把余下的数传给下一级。
下一级收到的第一个数必是素数，保存下来，并剔除掉所有此素数的倍数，剩下的数继续往下传。
流水线上所有的节点都按照如此方式处理。

可以并行传送

比较小的素数剔除时消耗的时间多，前面的进程工作量大，后面的进程工作量小。
前面的进程不必等待全部处理完后再往后传送，而是并行进行的。

代码如下：

recv(&x, Pi-1);
for (i = 0; i < n; i++) {
    recv(&number, Pi-1);
    If (number == terminator)break;
    (number % x) != 0) send(&number, P i+1);
}

求解上三角矩阵-类型三

代码稍作改进，不用全收到后再计算。

sum = 0;
for (j = 0; j < i; j++)
 {
    recv(&x[j], Pi-1); 
    send(&x[j], Pi+1);
    sum = sum + a[i][j]*x[j];
}   
x[i] = (b[i] - sum)/a[i][i];
send(&x[i], Pi+1);

复杂度分析

每个进程的工作量不一样。最后一个最大。最大的进程需要进行n次计算。n次接收和发送。复杂度为O（n）

5_流水线计算