流水线通用原理

在之前的SEQ模型中，由于一条指令的所有部分必须在一个时钟周期内完成，所以时钟周期无比的慢，所以系统的吞吐量就很慢，吞吐量即每秒能够处理的指令数量。

流水线系统的思路和工厂流水线一样，比如一个服装工厂流水线需要通过裁剪、缝合、贴商标、装袋这四个步骤，想象一下是当一件衣服的这四个步骤全部完成之后再开启下一件衣服的步骤快，还是第一件衣服的裁剪过程完毕后到达缝合阶段，就让下一件衣服进入裁剪阶段快。肯定是第二种，这就是流水线思想。

非流水线时，一个指令要在一个时钟周期内完成，流水线化之后，每一个阶段都是一个时钟周期。

同时也要注意，流水线的前提是每一个阶段之间都是相互独立的，它们不会相互影响，即一个处于裁剪阶段的衣服不会影响到另一个处于缝合阶段的衣服。我们下面为了讲解流水线的工作过程会把指令拆开成几个阶段，并假设它们都是独立的。当我们了解了流水线的工作流程后，我们会把目光移向现实，即拆解后的指令中的各个部分并非独立的。

计算流水线

我们还是要把目光放到计算上，一个指令的执行可以看作是一个输入进入到一个大的组合逻辑电路中，组合逻辑电路经过一段时间的延时产生结果，结果保存到寄存器中。单位ps是皮秒，也就是\(10^{-12}\)秒。组合逻辑电路会产生一些延时（这里是300ps），结果寄存器的装载又需要一些延迟（这里是20ps）。

有了量化指令执行时间的方法后，下面给出系统吞吐量的公式：

\[吞吐量T=\frac{1条指令}{指令进入系统的时间间隔（其实也就是时钟周期）}\times \frac{1000ps}{1ns}\\

\]

上图中的未流水线化的系统的吞吐量是

\[T=\frac{1}{(300+20)ps}\times \frac{1000ps}{1ns} \approx 3.12GIPS

\]

单位GIPS是每秒钟执行多少千兆个指令，也就是每秒执行几十亿个指令。

除了吞吐量外，另一个量化指标是延迟，延迟是一条指令完整执行所需要的时间，这里就是\(300+20=320\)。

一个流水线系统如下所示，指令被分割成若干个阶段，下图中是3个，每个阶段都有一个保存结果的寄存器，它用于保存此阶段的状态，然后下阶段时读取。因为下个阶段已经是另一个时钟周期了，所以下个阶段能读取到上个阶段写入的值。稍后我们会看到寄存器是如何被流水线中的指令写入的。

上面使用流水线后，系统的吞吐量得到了很大提升，因为指令进入系统的间隔小了（\(100ps+20ps\)），也可以理解为指令进入系统的频率快了。

\[吞吐量T=\frac{1}{(100+20)ps} \times \frac{1000ps}{1ns} = 8.33GIPS\\

...\\

延迟=(100 + 20) \times 3 = 360ps

\]

这里我们也注意到，将指令拆分为多个阶段以带来吞吐量提升的副作用是，由于每个阶段附加的结果寄存器，延时也会越来越大。并且吞吐量的提升有个瓶颈，在稍后的习题中我们会体会到这一点，达到瓶颈后再拆分，吞吐量不会上升，延时会越来越大。

结果寄存器的值推进

当你的流水线像上图一样被拆分成三段时，你的系统中同时执行的指令最多就只会有三个。每一个时钟周期，都会有一个系统中最老的指令执行完毕，退出流水线，也会有一个新的指令进入流水线。下面我们看看这三条指令如何共用三个结果寄存器而不会产生错乱。

在时间刻度120之前，I1的A阶段的输出已经写入到第一个寄存器的输入端，但直到120后时钟上升沿到来时，这个输出才会到达第一个寄存器的输出端，被I1的B阶段读取。当然，I2的A阶段也能读取到这个寄存器的值，关键的是它不会去读取，因为它是指令的第一个阶段。

而当I2需要读取第一个寄存器时，那就是I2的B阶段了，此时I1已经不需要第一个寄存器了，它在C阶段，它需要的是第二个寄存器。

所以，每条指令的每个阶段读取它上一个阶段（如果有的话）保存的寄存器值，并且将结果输出到本阶段的寄存器输入端，等待下一个时钟上升沿把该输出推到寄存器的输出端，然后被本条指令的下一个阶段（如果有的话）读取。就是这样循环往复的过程。

流水线的局限性

不一致的划分

虽然但是...我们很难将流水线中的每个阶段的时间长度划分成一样的。而且，流水线的特性就是：时钟周期的时间受最长的阶段影响。因为时钟周期如果比某个阶段所需的时间长一些，那没啥问题，因为时钟会处理好它的输出结果让下一个阶段能读到，但如果时钟周期比某个阶段所需要的时间短，那它的操作还没完成，下一个阶段就开始了，并且会从寄存器中读到错误的值，然后世界就毁灭了。

下图是一个例子

习题4.28

流水线过深，收益反而下降

吞吐量的计算总是能带给我们一种假象，就是当我们无限的细分指令的阶段时，系统性能就会得到无限的提升。吞吐量提升的同时，每个阶段需要的结果寄存器的延时也会变大，所以需要权衡。

现代处理器通常采用很深（15或更多）的流水线。处理器架构师将指令划分成很小的阶段，保证每阶段的延时更小，电路设计者也会尽力的设计寄存器，让寄存器的延迟更小。

习题4.29

\[latency(k) = (\frac{300}{k} + 20) \times k = 300 + 20k\\

T(k) = \frac{1}{\frac{300}{k} + 20} \times \frac{1000ps}{10ns}

\]

\[lim_{k->\infty}T(k)=50GIPS

\]

要注意的是，当k趋近于无穷时，由于寄存器延迟不会改变，所以吞吐量是有上界的，但是指令执行延迟则是会趋近于无穷。

带反馈的流水线系统

上面我们的所有内容都基于一个假设：指令之间是独立的

独立，代表它们不会共用寄存器文件中某个相同的寄存器，某一条指令是否执行不会与其它指令相关。

一旦两条指令不独立，那么将它们放到相同的流水线中就非常危险：

想象1和2行两条指令在流水线中共同执行，它们同时操作%rax%，它们可能得到由对方的某个阶段设置的结果，而非自己需要的结果。

想象第2条，3条和第4条指令，第二条的计算结果会影响到第三条的判断，第三条的判断会影响到是该执行第7条还是第4条。当一条的结果会给另一条带来副作用时，它们怎么能一起执行？

在SEQ中，修改的寄存器文件的值和新的PC计数器的值都会通过下图右面的被称作反馈线路的东西写回，写回在整个指令处理的最后阶段。

在SEQ中，这个反馈线路写入的东西都会被传递给下一条指令，因为指令件是无交叉的顺序执行。但如果你把这种反馈线路设计引入到阶段数为k的流水线系统中，反馈将不会传递给下一条指令，而是会被传递后面第k条指令。

Y86-64流水线实现

SEQ+ —— 重新安排计算阶段

SEQ+在SEQ的基础上做了一写改动，我们把PC的计算挪到最开始的阶段，而非最后的阶段。除此之外再没有其它改动，它只是我们稍后将处理器流水线化的一个前置工作，目前还解决不了上面所述的那些指令间的副作用问题。

WHAT？？PC计算怎么能挪到最开始的阶段？就像下面的指令jXX，更新PC的阶段实际上依赖了前面阶段的状态信号，ifun，Cnd，valC和valP，在一些其它操作上，还有可能依赖valM、icode等。所以怎么可能在这些状态还没得到的情况下更新PC？

SEQ+使用的办法是，维护一些状态寄存器pIcode、pCnd、pValM等来保存上面那些状态，这些寄存器保存的是前一个时钟周期里产生的状态信号，而当一个新的时钟周期开始时，处理器会根据这些状态寄存器中的值来计算该执行指令的PC。

读者请注意，现在只是在运算阶段排序上做出了一个调整，实际上稍后就会看到，这第一个阶段计算出来的PC只是一个预测的PC。毕竟按照这种模型，当前指令的PC确定时，它的上一条指令才执行到确定PC的后一个阶段而已。

可以看到，SEQ+中没有实际的PC寄存器，每条指令的PC都是动态计算的。所以我们可以以与概念模型不同甚至大相径庭的任意方式来实现处理器中的任何细节来提高性能，只要最终效果与概念模型中宣称的效果一样即可。在你产品上工作的人只关心产品是否正确，是否高效，不关心底层的实现细节。这也是公有设计，私有实现的一个体现。

插入流水线寄存器

下面我们将SEQ+流水线化，这需要我们在每个阶段中插入流水线寄存器。

1. F：保存程序计数器的预测值


2. D：位于取指和译码阶段期间，保存最新取出的指令信息，即将由译码阶段进行处理


3. E：位于译码和执行阶段期间，保存最新的译码指令和从寄存器读出的值的信息，即将由执行阶段进行处理


4. M：位于执行和访存阶段期间，保存最新的指令执行结果，即将由访存阶段进行处理。还将保存用于处理条件转移的分支条件和分支目标信息。


5. W：位于访存阶段和反馈路径之间，反馈路径将计算出来的值提供给寄存器文件写，而当完成ret指令时，它还要向PC选择逻辑提供返回地址。

通过向SEQ+中添加流水线寄存器，我们创建了一个新的CPU，命名为PIPE-，名字中的-代表与最终的CPU相比，它的性能还是要差一些。下图是PIPE-CPU的硬件结构。

上面的硬件结构十分复杂，对于我这种对硬件理解十分浅薄的很难理解，不过我们并不需要完全理解这张图。所以对该图的解释，本篇文章里就没有了，该图中的连线与Y86-64指令集中的各个阶段之间的关联是一致的，原书中对次进行了一些介绍。

对信号进行重新排列和标号

从上图的结构中，可以看到顺序实现中的valC、srcA、stat这种信号值在每个流水线寄存器中都有保存，这些版本会随着指令一起流过系统。

为了清晰，我们将这些值与相应的流水线寄存器的名字联系起来，比如D_stat，代表流水线寄存器D中的stat信号，也就是取指后译码前的stat信号。类似的还有E_stat、M_stat。同时我们还需要为在某个阶段刚刚计算出来的还没存到流水线寄存器中的信号命名，它们的命名方式为小写的阶段名加信号名，比如在执行阶段的stat为e_stat，访存阶段的为m_stat。

整个处理器的实际状态Stat是根据流水线寄存器W中的值通过写回阶段中的块计算出来的。

预测下一个PC

流水线模型让我们在每一个时钟周期里都必须加载一个新的指令，但由于条件分支命令jXX的下一条指令究竟执行啥需要等到几个时钟周期之后，jXX已经完成了执行阶段才能确定，对于ret，则是需要等到访存阶段才能确定。对于其它指令，包括call和无条件jmp，我们都能在取指阶段完成后就确定下一条指令的地址，所以，通过预测在一开始就确定下一条指令的PC，在大部分情况下预测是可靠的，能达到每个时钟周期加载一条指令的效果。对于条件转移来说，我们可以预测条件满足或不满足，但预测总会出错，出错时就要有相应的补救机制。在PIPE-的实现中总是选择假设条件满足。

在PIPE-的实现中，ret指令没有做任何预测，只是简单的暂停接收新指令，直到ret通过写回阶段。但由于调用和返回总是成对出现，所以高性能的CPU设计会通过一个栈来预测ret的返回值，这个预测通常要比分支预测可靠。

流水线冒险

PIPE-目前还没解决两个非独立的指令会互相影响的问题，但已经为此做了足够的努力，现在我们可以直接在PIPE-上构建一些逻辑来解决这些问题。

非独立指令之间的影响主要是数据相关和控制相关的，处理器在执行非独立指令时就像在冒险，因为有可能出现错误的情况，所以就有数据冒险和控制冒险。

下面是一个例子，两条irmovq指令分别存储%rdx和%rax，后面的addq对这两个寄存器中的值相加。前两条指令和后面的addq不是独立的，因为前两条的结果会影响到addq。

在周期6时，第二个irmovq指令正在执行了写回阶段，addq还没有开始执行，到周期7时，第二个irmovq已经将它的值写回，所以addq会读到两个正确的值。addq能正确处理的原因是中间被插入了三条nop指令，它们不会修改处理器的任何状态，只是为了给addq的执行带来一些延迟。

下图在上一个的基础上拿掉了一个nop，我不理解的是，指令的F阶段不是预测PC并取指吗，不会做译码操作啊，所以我感觉两个nop也没啥问题啊。顺着书来吧，如果有能解释的请帮帮孩子。

按（书上的）这个来说，一条指令的操作数只要被它前面三条指令修改过就会出现数据冒险。

可能发生冒险的地方有：

1. 程序寄存器：如上面所示


2. 程序计数器：这个是控制冒险的范畴，如ret指令


3. 内存：我们的处理器没有这种情况，因为我们的设计中对内存的读写都在访存阶段，后一个指令到达访存阶段时，前一个指令必然已经完成访存阶段了。


4. 条件码寄存器：我们的处理器也没有这种情况，写这些寄存器的操作都在执行阶段写入，读这些寄存器的操作都在执行或访存阶段读，和内存一样，这里不存在冒险。


5. 状态寄存器：

用暂停来处理数据冒险

即动态插入名为bubble的，和nop功能一样的指令，目的是为了延迟后面可能会出现冒险的指令的执行。

用转发来避免数据冒险

你必须在一条指令的译码阶段暂停执行的原因是：上一条指令计算出的结果必须等到写回阶段才能写入到寄存器中。实际上，最早在执行阶段它可能就已经计算完了结果并保存到M_valE中。同样，在访存阶段和写回阶段都存在这种可行的转发，e_valE、m_valM、M_valE、W_valM和W_valE都可以作为转发端口。所以，转发技术就是将本条指令在译码阶段要读取的寄存器值直接转发到上一条指令的某个结果上。从硬件上看，这只是相当于一次流水线寄存器的访问。

下图就是第二条指令对%rax的写入（本来写入到流水线寄存器）直接被addq指令所读取。

下面是加上五条转发线和对应硬件的图。

加载/使用数据冒险

并非所有数据冒险都能用转发技术处理。转发技术只能处理后一条指令需要的数据前一条指令已经计算出来由于尚未走完写回阶段而没写到寄存器文件中的情况。

考虑下一条指令需要上一条指令的访存阶段拿出的值作为源操作数时，就没法使用转发技术。因为访存发生在流水线很靠后的部分，下一条指令的译码阶段就算来了，上一条的访存也没执行呢。

这时可以通过结合暂停和转发来避免这种数据冒险。

避免控制冒险

对于ret指令，我们的处理器选择的方法就是简单的暂停，前面也说过了。

对于条件分支，我们的处理器会选择条件满足的分支来执行，而当逻辑分支在执行阶段发现我们选择的条件分支是错的时，错误的分支已经有两条指令被加载并执行了。好在它们还没有产生任何作用，因为它们还没到执行阶段，前面的所有操作都是只读的。CPU只需要简单的扔掉它们就行。只是有两个时钟周期浪费掉了。