计算机系统结构：流水线技术总结

什么是流水线？

如下图所示的浮点加法流水线

它的时空图

流水线技术的特点：

1. 把整个过程分为若干个子过程，每个子过程由一个专门的功能部件来实现。
2. 流水线中的各段时间应该尽可能相等，否则将引起堵塞，时间最长的段将成为流水线的瓶颈。
3. 流水线的每段后面都要有一个缓冲寄存器，称为锁存器。其作用是在相邻的两段之间传送数据，以提供后面流水段要用到的信息。还有一个作用是隔离各段的工作，避免相邻流水段电路的相互打扰。
4. 流水线技术适合大量重复的时序过程，只有在输入端不断地提供任务，才能充分发挥流水线的效率。
5. 流水线需要有通过时间和排空时间。

流水线的分类

1. 部件级流水线、处理机级流水线、系统级流水线
   部件级流水线是把处理机中的部件进行分段，也叫运算操作流水线，比如上面的浮点加法流水线；
   处理机级流水线又叫指令流水线，每个子过程在独立的功能部件进行；
   系统级流水线是把多个处理机串行连接起来，又叫宏流水线。
2. 单功能流水线、多功能流水线
   单功能流水线：流水线各段之间的连接固定不变，只能完成固定功能，如上面的浮点加法流水线；
   多功能流水线，各段可以进行不同的连接，以实现不同功能，如下面图所示的流水线：
   
3. 静态流水线、动态流水线
   静态流水线是指在同一时间内，多功能流水线中的各段只能按同一种功能的连接方式工作。当流水线要切换到另一种功能时，必须等前面的任务都流出流水线之后，才能改变连接。如下面的时空图中，必须要等到浮点加法的任务的功能段全部流出流水线之后，该流水线才能够改变功能，让定点乘法的流水线进入。
   
   动态流水线是指在同一时间内，多功能流水线的各段可以按照不同的方式连接，同时执行多种功能的流水线。它允许在某些段正在实现某些运算时，另一些段却在实现另一种运算。当然，前提是，任何一个功能段只能参加到一种连接中。如下图所演示的那样。动态流水线的优点是：更加灵活，能提高各段的使用率，能提高处理速度，但其控制复杂度增加了。
   
   由于动态流水线的控制很复杂，所以目前大多数都是静态流水线。
4. 线性流水线、非线性流水线
   线性流水线各段串行连接，没有反馈回路；
   非线性流水线各段除了有串行的连接外，还有反馈回路。非线性流水线常用于递归或者构建多功能流水线。
   
5. 顺序流水线、乱序流水线
   在顺序流水线中，流水线输出端任务流出的顺序与输入端任务流入的顺序完全相同。
   乱序流水线中，流水线的输出端任务流出的顺序与输入端任务流入的顺序可以不同，允许后进入的流水线先完成。

流水线的性能指标

1. 吞吐率：$TP=\frac{n}{T_k}$，n为任务数，$T_k$为处理完$n$个任务所用的时间。
2. 加速比：$S=\frac{T_s}{T_k}$，$T_s$是使用顺序处理方式处理全部任务所用的时间，$T_k$是使用流水方式处理全部任务所用的时间。
3. 效率：$E=\frac{任务实际占用的时空区面积}{总时空区面积}$

流水线设计中的若干问题

1. 瓶颈问题
   当流水线各段时间不等时，时间最长的那一段就成了瓶颈。
   
   消除瓶颈段的两种方法：
   a）细分瓶颈段-把流水线中的瓶颈段切割成几段，使各段执行时间相等。
   
   b）重复设置瓶颈段-重复设置的段并行处理，在时间上依次错开工作
   
   
2. 额外开销
   锁存器的延迟
   时钟偏移开销-流水线中的时钟到达各锁存器的最大插值时间
   采用流水线技术后，虽然可以提高指令的吞吐率，从而提高程序的执行速度，但流水线并不能真正减少单条指令的执行时间。事实上，由于额外开销的存在，单条指令的执行时间反而会增加。
3. 冲突问题
   流水线的指令之间存在相关性，可能要相互等待，从而导致停顿。

非线性流水线的调度

由于反馈回路的存在，当一个任务在流水线中流过时，可能要多次经过某些段，这样就不能每个时钟周期向流水线送入一个新任务。

单功能非线性流水线的最优调度

1. 预约表
   表示一个任务在该流水线中流过时，对各段的使用情况。
   
2. 根据预约表写出禁止表
   对于预约表的每一行的任何一对√，用它们所在的列号相减（大减小），列出各种可能的差值，合并相同的。
   上图预约表的禁止表是： F = { 1 , 5 , 6 , 8 } F=\{1,5,6,8\} F={1,5,6,8}。
3. 根据禁止表写出初始冲突向量$C_0$
   初始冲突向量$C_0$是一个$N$位的二进制位串。
   设$C_0=(c_N{c}_{N-1}...c_2{c}_1)$，（注意这里是从右往左），则：
   $$c_i=\{\begin{array}{rl}1& i\in F\\ y& i\notin F\end{array}$$
   对于上面的例子，$C_0=(10110001)$。
4. 根据初始冲突向量$C_0$画出状态转换图
   假设当前的冲突向量是$C_k$，$j$是允许的时间间隔，则新的冲突向量为
   $$SH{R}^j(C_k)\vee C_0$$
   其中$SH{R}^J$表示逻辑右移$j$位。
   对于上面的例子，状态转换图为：
   
5. 根据状态转换图找到最优调度方案
   根据状态转换图，由初始状态出发，任何一个闭合回路即为一种调度方案。列出所有可能的调度方案，计算出每种方案的平均时间间隔，从中找出其最小者即可。
   
   等时间间隔调度方案，时间间隔最小的为(7)
   不等时间间隔调度方案，时间间隔最小的为(3,4)

多功能非线性流水线的调度

对于多功能流水线来说，由于不同功能的任务可以相互穿插在一起流入流水线，其调度复杂得多。下面仅以双功能（设为功能A和B）非线性流水线为例，说明多功能非线性流水线的最优调度方法。双功能非线性流水线的调度方法与单功能类似，只是其状态转移图中结点状态的表示不同，是由两个冲突向量构成的冲突矩阵，这两个冲突向量分别对应于下一个任务的功能是A类和B类的情况。而且，其初始结点有两个，分别对应于第一个任务是A类和B类的情况。假设当第一个任务是A类时，其冲突矩阵为$M_A^{(0)}$；当第一个任务是B类时，其冲突矩阵为$M_B^{(0)}$，则有：
M A ( 0 ) = [ C A A C A B ] , M B ( 0 ) = [ C B A C B B ] M_A^{(0)}=

$$\begin{bmatrix} C_{AA}\\ C_{AB} \end{bmatrix}$$ ,\quad M_B^{(0)}= $$\begin{bmatrix} C_{BA}\\ C_{BB} \end{bmatrix}$$ MA(0)​=[CAA​CAB​​],MB(0)​=[CBA​CBB​​]
其中， C p q （ p , q ∈ { A , B } ） C_{pq}（p,q\in\{A,B\}） Cpq​（p,q∈{A,B}）表示的是：在一个$p$类任务流入流水线后，对后续$q$类任务的冲突向量，它们可以由预约表求得。
对于后续状态的冲突矩阵由下式求得：
$$SH{R}^{(i)}(M_k)\vee M_r^{(0)}$$
其中，$M_k$为当前状态，$r$表示下一个流入任务的类型（A或B），$i$是当前状态允许流入的$r$型任务的时间间隔。$SH{R}^i(M_k)$表示把当前状态中的各冲突向量逻辑右移$i$位。
举个例子：
找出下面这条双功能非线性流水线单独处理A类任务、单独处理B类任务、混合处理两类任务的最优调度方案：


（1）把两个预约表混合起来：

（2）根据预约表求初始冲突矩阵（注意思考为什么是前减后）
a. A类接A类：禁止表为{2,3}，所以$C_{AA}=(0110)$；
b. A类接B类：禁止表为{2,4}，所以$C_{AB}=(1010)$;
c. B类接A类：禁止表为{1,2,4}，所以$C_{BA}=(1011)$;
d. B类接B类：禁止表为{2,3}，所以$C_{BB}=(0110)$。
因此，初始矩阵为：

（3）由初始冲突矩阵画出状态转换图

（4）由状态转换图找出最优调度方案
只流入A类任务的最优调度为（A.1，A.4）
只流入B类任务的最优调度为（B.1，B.4）
流入A、B类混合任务的最优调度为（B.1，A.3）

一条经典的5段流水线

1. 取指（IF）
   以程序计数器（PC）中的内容作为地址，从存储器中取出指令并放入指令寄存器（IR）；
   PC值加4（假设每条指令占4字节），指向顺序的下一条指令。
2. 指令译码/读寄存器周期（ID）
   对指令进行译码，并用IR中的寄存器地址去访问通用寄存器组，读出所需的操作数；
   对IR中的立即数进行扩展
3. 执行/有效地址计算周期（EX）
   ALU对上一个周期中准备好的操作数进行运算或处理。在这个阶段，不同类型的指令进行的操作不同。
   （1）load和store指令：ALB把指令中所指定的寄存器的内容与偏移量相加，形成访存有效地址；
   （2）寄存器-寄存器 ALU 指令：ALU按照操作码指定的操作对从通用寄存器组中读出的数据进行运算；
   （3）寄存器-立即数 ALU 指令：ALU按照操作码指定的操作对从通用寄存器组中读出的操作数和指令中给出的立即数进行运算；
   （4）分支指令：ALU把指令中给出的偏移量与PC值相加，形成转移目标的地址。同时，对在前一个周期读出的操作数进行判断，确定分支是否成功。
4. 存储器访问/分支完成周期（MEM）
   （1）load和store指令：load指令根据上一个周期计算出的有效地址从存储器中读出的相应的数据；store把指定的数据写入这个有效地址对应的存储单元。
   （2）分支指令：如果分支“成功”，就把前一个周期中计算好的转移目标地址送入PC。分支指令执行完成；否则，就不进行任何操作。
5. 写回周期（WB）
   把结果写入通用寄存器组。对于ALU运算来说，这个结果来自ALU，而对于load指令来说，这个结果来自存储器。

还要解决流水处理带来的一些问题：

1. 保证不会在同意时钟周期要求同一个功能段做两件不同的工作。例如，不能要求ALU既做有效地址计算，又同时做算术运算。RISC指令集比较简洁，所以该要求不难实现；
2. 为了避免IF段的访存（取指令）与MEM段的访存（读写数据）发生冲突，必须采用分离的指令存储器和数据存储器，或者仍采用一个公用的存储器，但要采用分离的指令Cache和数据Cache，一般采用后者。
3. ID段要对通用寄存器组进行读操作，而WB段要对通用寄存器组进行写操作，为了解决对同一通用寄存器的访问冲突，把写操作安排在时钟周期的前半拍完成，把读操作安排在后半拍完成。

流水线时空图的另外的画法：

相关与流水线冲突

相关（Dependence）是指两条指令之间存在某种依赖关系。
考虑两条指令$i$和$j$，$i$在$j$的前面。

1. 数据相关
   如果下述条件之一成立，则称指令$j$与指令$i$数据相关：
   （1）指令$j$使用指令$i$产生的结果；
   （2）指令$j$与指令$k$数据相关，而指令$k$又与指令$i$数据相关。
   其中第（2）个条件表明，数据相关具有传递性。
   例如，下面这一段代码存在数据相关：
   
   其中箭头表示必须保证的执行顺序。它由产生数据的指令指向使用该数据的指令。
   当数据的流动是经过寄存器时，相关的检测比较直观和容易，因为统一寄存器在所有指令中的名称都是唯一的。而当数据的流动是经过存储器时，检测就比较复杂了，因为形式上相同的地址其有效地址未必相同，如某条指令中的10(R5) 与另一条指令中的10(R5)可能不同，因为R5的内容发生了变化；而形式不同的地址其有效地址却可能相同。
2. 名相关
   两条指令使用了相同的寄存器或存储单元的名字，但它们之间并没有数据流动。
   （1）反相关：指令$j$所写的名与指令$i$所读的名相同
   （2）输出相关：指令$j$所写的名与指令$i$所写的名相同。输出相关的指令的执行顺序不能颠倒，以保证最后的结果是指令$j$写进去的。
   名相关的两条指令之间并没有数据流动，只是使用了相同的名而已。因此可以通过改变指令中操作数的名来消除。对于寄存器操作数进行换名称为寄存器换名（Register Renaming）。寄存器换名既可以用编译器静态实现，也可以用硬件动态完成。
   考虑下述代码：
   
   DIV.D和ADD.D存在反相关，进行寄存器换名可以消除：
   
3. 控制相关
   控制相关是指由分支指令引起的相关，它需要根据分支指令的执行结果来确定后面该执行哪个分支上的指令。
   例如：
   
   这里的 if p1 和 if p2 编译成目标代码以后都是分支指令。语句S1与p1控制相关，S2与p2控制相关，S与p1和p2均无关。
   控制相关带来了两个限制：
   （1）与一条分支指令控制相关的指令不能被移到该分支之前；否则这些指令就不受该分支控制了。上面的例子，S1不能移到p1之前；S2不能移到p2之前；
   （2）不能把S移到if语句的then部分中。
   流水线冲突有以下三种类型。

结构冲突：因硬件资源满足不了指令重叠执行的要求而发生的冲突；

	例如，有些流水线处理机只有一个存储器，数据和指令都存放在这个存储器中。在这种情况下，当执行load指令需要存取数时，若又要同时完成其后某条指令的“取指令”，就会发生访存冲突，如下图带阴影的M所示。
1

为了消除这种冲突，可以在前一条指令访问存储器时，将流水线停顿一个时钟周期，该停顿周期往往被称为“气泡”。用时空图来表示就是：


可以看出，为消除结构冲突引入的停顿将推迟流水线的完成时间，从而影响流水线的性能。由于这种冲突出现的频度不低，因此一般是采用分别设置独立的指令存储器和数据存储器的方法。或者一个存储器，但是采用两个分离的Cache：指令Cache、数据Cache。

数据冲突：当指令在流水线中重叠执行时，因需要用到前面指令的结果而发生的冲突；

例如：

DADD之后的所有指令都要用到DADD指令的计算结果，如图：

DADD指令在其WB段（第5个时钟周期）才将计算结果写入寄存器R1，但是DSUB指令在其ID段（第3个时钟周期）就要从寄存器R1读取该结果，这就是一个数据冲突。若不采取措施防止这一情况发生，则DSUB指令读到的值就是错误的。XOR指令也受到这种冲突的影响，它在第4个时钟周期从R1读出的值也是错误的。而AND指令则可以正常执行，这是因为它在第5个时钟周期的后半拍才从寄存器读数据的，而DADD指令在第5个时钟周期的前半拍已将结果写入寄存器。

考虑两条指令$i$和$j$，且$i$在$j$之前进入流水线，可能发生的数据冲突有以下几种：

a. 写后读冲突（Read After Write, RAW）：指令$j$用到指令$i$的计算结果，而且在$i$将结果写入寄存器之前就去读该寄存器，因而得到的是旧值。对应于数据相关。

b. 写后写冲突（Wirte After Write, WAW）：指令$j$和指令$i$的结果寄存器相同，而且$j$在$i$写入之前就对该寄存器进行了写入操作，最后在结果寄存器中留下的是$i$写入的值，而不是$j$写入的值。对应于输出相关。
写后写冲突仅发生在：流水线中不止一个段可以进行写操作；或者指令顺序被重新排列。前面的简单的5段流水线只在WB写了寄存器，所以不会发生写后写冲突。

c. 读后写冲突（Read After Write, RAW）：指令$j$的目的寄存器和指令$i$的源操作数寄存器相同，而且$j$在$i$读取该寄存器之前就先对它进行了写操作，导致$i$读到的值是错误的。这种冲突是由反相关引起的。这在前面所述的简单5段流水线中不会发生，因为该流水线所有的读操作（在ID段）都在写操作（WB段）之前发生。读后写冲突仅发生在这样的情况下：有些指令的写操作提前了，而有些指令的读操作滞后了；或者指令被重新排序了。

可以使用定向技术减少数据冲突引起的停顿。
对于前面例子中的数据冲突，简单的处理方法是暂停流水线中DADD之后的所有指令，直到DADD指令将计算结果写入寄存器R1之后，再让DADD之后的指令继续执行，但这种暂停会导致性能下降。
可以建立数据旁路，将数据直接从产生的地方送到使用的地方，如图：

需要停顿的数据冲突：
但并不是所有的数据冲突都可以通过定向技术来解决，如图：

DADD要使用LD指令的结果，如虚线所示，这显然是无法实现的。解决办法就是停顿。

依靠编译器解决数据冲突
为了减少停顿，对于无法使用定向技术解决的数据冲突，可以通过在编译时让编译器重新组织指令顺序来消除冲突，这种技术称为“指令调度”(Instruction Scheduling)或“流水线调度”(Pipeline Scheduling)。
举个例子，考虑下面的表达式：

这两个式子编译后形成的代码为：

在这个代码序列中，DADD Ra, Rb, Rc 与 LD Rc, C之间存在数据冲突，DSUB Rd, Re, Rf 与 LD Rf, F 之间存在数据冲突。为了保证流水线能正确执行，必须在指令执行过程中插入两个停顿周期（分别在DADD和DSUB执行前）。
将指令顺序调整为：

再加上相应的数据旁路，就可以消除数据冲突，不必在执行过程中插入任何停顿的周期。

控制冲突：流水线遇到分支指令或其它会改变PC值的指令所引起的冲突。

在流水线中，控制冲突可能会比数据冲突造成更多的性能损失，所以同样需要得到很好的处理。
执行分支指令的结果有两种：一种是分支“成功”，PC值改变为分支转移的目标地址；另一种则是“不成功”或者“失败”，这时PC值保持正常递增，指向顺序的下一条指令。对分支指令“成功”的情况来说，是在条件判定和转移地址计算都完成后，才改变PC值的。对于上面的5段流水线来说，改变PC值是在MEM段进行的。
处理分支指令最简单的方法是“冻结”或者“排空”流水线。即一旦在流水线的译码段ID检测到分支指令，就暂停其后所有指令的执行，直到分支指令到达MEM段、确定是否成功并计算出新的PC值为止。然后，按照新的PC值取指令，如下图所示：

在这种情况下，分支指令给流水线带来了三个时钟周期的延迟。而且无论分支成功还是失败，都是一样的排空等待。
分支指令在目标代码中出现的频度是不低的，统计结果表明，每三四条指令就有一条是分支指令。所以排空的处理办法所带来的性能损失是相当大的。

另外采取的办法是：提前判断（或猜测）分支是否成功，尽早计算出分支目标地址。可以把它们提前到ID段完成（比如BEQZ，只需要判断指定寄存器中的数是否为0，ID段已经读取寄存器的同时就可以做，计算出分支目标地址是将PC+IMM<<2,ID段已经取出IR中的立即数，并且能做符号扩展，当然也能做加法），这样就可以把分支延迟减少到一个时钟周期。

进一步减少分支延迟的方法有很多种，下面只介绍三种通过软件来处理的方法：

预测分支失败

方法是沿失败的分支继续处理指令，当确定分支失败时，就将分支指令看成一条普通指令，正常流动；当确定分支成功时，就把分支之后取出的指令转换为空操作，并按分支目标地址重新取指令执行

预测分支成功

当流水线检测到分支指令后，一旦计算出了分支目标地址，就开始从该目标地址取指令执行。
在上面的5段流水线中，由于判断分支是否成功与分支目标地址计算式在同一流水段完成的，所以这种方法对减少该流水段的分支延迟没有任何好处。但在其它的一些流水线处理机中，特别是哪些具有隐含设置条件码或分支条件更复杂（因而更慢）的流水线处理机中，在确定分支是否成功之前，就能得到分支的目标地址。这时采用这种方法便可以减少分支延迟。
注意：这和预测分支失败不是一种方法，仔细品！

延迟槽

在分支指令后添加延迟槽：
分支指令
延迟槽
后继指令
具体延迟槽里放的指令是由编译器来选择的。实际上，延迟槽能否带来好处完全取决于编译器能否把有用的指令调度到延迟槽中，这也是一种指令调度技术。常用的调度方法有三种：从前调度、从目标处调度、从失败处调度。
举例，如图：

a) 从前调度
把位于分支指令之前的一条独立的指令移到延迟槽。
b）从目标处调度
如图，分支指令之前数据存到了R1寄存器，然后R1寄存器被用于了分支指令的判断，所以不能把分支指令之前的这条指令调到延迟槽。
但是可以将分支指令跳转地址的第一条指令调到延迟槽，然后把分支跳转地址修改为第一条指令所在地址的后面，这实际上是预测了分支会成功，如果失败，相当于延迟槽中的指令就无用了。而且这要求分支地址计算在下一条指令进入之前完成。
c）从失败处调度
即将分支指令后面的第一条指令放入延迟槽，正常运行。