1-7 流水线技术

流水线简介

流水线技术是指在程序执行时，多条指令重叠进行操作的一种任务分解技术。

把一个任务分解为若干顺序执行的子任务，不同的子任务由不同的执行机构来负责执行，而这些执行机构可以同时并行工作。

如iPhone的屏幕、存储、组装等工作分别由很多供应链厂商来做

流水线概述

如下图，I任务为Input输入，C任务为Compute计算，P任务为Print打印输出

在$t_1$时刻，只进行$I_1$任务的输入
在$t_2$时刻，进行$C_1$任务计算和$I_2$任务的输入
在$t_2$时刻，进行$P_1$任务输出、$C_2$任务计算和$I_3$任务的输入
……

$I_1$、$C_1$、$P_1$的执行必须严格按照$I_1$，$C_1$，$P_1$的顺序，而$C_1$与$I_2$，$P_1$与$C_2$、$I_3$是可以同时执行的

注意：流水线建立时间和流水线排空时间之内，并未满负荷工作

计算流水线执行时间

等差数列的通项公式为： $$ a_n = a_1 + (n - 1)d $$

其中：

$a_n$ 表示数列的第n项，

$a_1$ 是数列的第一项（起始项）

d 是等差数列的公差（即任意相邻两项之差），且对于所有正整数 ( n ) 都成立，

n 是数列中的项数，表明我们要找的是数列中的第几项。

假定有某种类型的任务，可分成k个子任务，每个子任务需要时间t，共有n个任务

则完成单个任务所需的时间为$kt$.
若以传统的方式，完成k个任务所需的时间是 $nkt$
使用流水线技术，花费的时间是 $kt + (n-1)t$ = $(k + n - 1)t$，该时间远小于上面的$nkt$
注意，如果每个子任务所需的时间不同，其时间取决于执行顺序中最慢的那一个，即t应当取$max(t_1, t_2, …, t_k)$。

笔者注：由下图可以看出，以流水线方式完成任务所需时间由两个部分组成

传统方式执行完n个子任务如下图的A、B、C所需的时间kt
第n个任务$I_n$长出$I_1$的部分(实际上长出几格是关于n的，首项为0，公差为1的等差数列)所需时间，该时间与n有关，为(n-1)t

注意：以下引用中k为子任务数量而非流水线任务数量

计算机流水线执行时间的计算通常基于流水线的基本概念，其中流水线执行能够同时处理指令的不同阶段，从而提高处理器的效率。在理想情况下（无流水线冲突或 stalls），计算流水线执行时间的公式如下：

理论公式：

如果一条指令经过 k 个阶段（例如：取指、译码、执行、写回等），每个阶段的时间分别为 t1, t2, …, tk，则这条指令的执行时间是这些阶段时间之和。

对于 n 条连续的指令，第一条指令完整执行，后续的 n-1 条指令则可以在不同阶段重叠执行。

因此，流水线执行 n 条指令所需的总时间 T_pipeline 理论上为：
$$
T_{pipeline} = t_1 + t_2 + … + t_k + (n - 1) * max(t_1, t_2, …, t_k)
$$

实践公式：

在实际应用中，流水线周期（Pipeline Cycle Time, Δt）定义为流水线中各个阶段中最长的时间，也就是瓶颈阶段的时间。

执行 n 条指令所需的流水线时间也可以简化为：
$$
T_{pipeline} = (k + n - 1) * Δt
$$

举个例子：

假设流水线有三个阶段，取指（2ns）、分析（2ns）、执行（1ns），流水线周期Δt 是这三个阶段中的最大值，即 2ns。

若要执行 100 条指令，使用理论公式计算流水线执行时间，首先确定单条指令的执行时间（这里是 2ns + 2ns + 1ns = 5ns），然后加上剩余 99 条指令对应的流水线周期时间（99 * 2ns）。

使用实践公式，则直接计算为：$(3 + 100 - 1) * 2ns$。

请注意，在实际情况中，可能会因为数据依赖、控制转移等原因导致流水线停顿（pipeline stall），此时实际执行时间将会增加，需根据具体情况进行修正计算。

案例分析

若指令流水线把一条指令分为取指令、分析和执行三部分，三部分的时间分别是取指令2ns，分析2ns，执行1ns。最长的是2ns，因此100条指令全部执行完毕所需要的时间是：

按照流水线执行，则t = 2ns，n = 100
第一条指令顺序执行2ns+2ns+1ns = 5ns
后面100-1条指令流水线执行(100-1) x 2ns = 198ns
(2ns+2ns+1ns)+(100-1)x2ns=203ns，现在考试选这个，即第一条顺序执行，后面n-1条按照流水线执行
2ns+2ns+2ns+(100-1)x2ns=204ns，早期考试选这个，即所有指令都按照流水线执行

流水线执行时间公式

综上推导过程和案例分析可知，考试考察的流水线执行时间公式实际为
$$
T_p = t_1 + t_2 + … + t_k + (n - 1) * max(t_1, t_2, …, t_k)
$$
其中，n为连续的指令数量即流水线上任务数量，k为每个指令内子任务数量

流水线的吞吐率

流水线吞吐率公式1

指在单位时间内（基本是1秒）流水线所完成的任务数量或输出的结果数量。
$$
T_p = \frac{n}{T_k}
$$

其中，n为任务数，Tk是处理完成n个任务所用的时间

上面案例的吞吐率为
$$
T_p = \frac{n}{T_k}= \frac{100}{203*10^{-9}}=4.93 * 10^8/s
$$

流水线吞吐率公式2

吞吐率另一个公式：
$$
p= \frac{1}{\Delta t}=\frac{1}{max（t_1，t_2…t_k)}
$$

加速比

定义：指不采用流水线的执行时间/采用流水线的执行时间，用来衡量并行系统或程序并行化的性能和效果

如上面的案例中的速比为500/203=2.46(如果不采用流水线，则执行100条指令需要500ns)

案例分析

解析：

由题意得，子任务数量k = 4，流水线任务数量n = 8，各个子任务执行时间如图所示
流水线执行时间为
$$
T_p = t_1 + t_2 + … + t_k + (n - 1) * max(t_1, t_2, …, t_k) = 7 \Delta t + (8-1) * max（t_1….t_k) = 7 \Delta t + 7 * 3\Delta t = 28\Delta t
$$
流水线吞吐率为8/28$\Delta$ t ，选择C

概念与术语的理解

流水线时间公式
流水线吞吐率公式
加速比公式

例题

解析：

第一空：为方便输入，以下用t代指$\Delta$t，顺序执行
$$
T = (4 + 2 + 3)t * 600 = 5400t
$$
第二空：为方便输入，以下用t代指$\Delta$t，流水线执行
$$
T_p = (4 + 2 + 3)t + (600 -1) * max(4,2,3) * t = 2405t
$$

解析：根据吞吐率公式2：吞吐率是最长流水段操作时间的倒数