bluebird8880 阅读(44) 评论(0)

流水线处理模式,相对非流水线,本质上是一种生产管理模式的改变。在硬件条件有空闲的前提下,通过划分工作步骤,让硬件处于填满状态,从而提升工作效率。在计算机处理器体系结构中,正是采用这种方式来对指令进行处理。本文从流水线的通用原理和流水线冒险两个角度来聊聊这个话题。

由于编辑器问题导致图片较小,可访问个人博客地址阅读:http://www.lillianyl.com/2017/09/pipeline-processor/

1.流水线的通用原理

1.1 将处理组织成阶段

通常一条指令包含很多操作,可以将它们组织成一定的阶段序列,从而便于放入一个通用框架来进行流水线处理。

操作描述
取指(fetch) 从存储器取指令,再更新PC
译码(decode) 从寄存器堆读出寄存器的值
执行(execute) 运算指令:进行算术逻辑运算;访存指令:计算存储器的地址
访存(memory) load指令:从内存读出数据;store指令:将数据写入内存
写回(write-back) 将数据写回寄存器堆

将指令拆分成不同阶段后,如果每个阶段所用的硬件是相互独立的,那么可以在对应的硬件电路的每个阶段后添加寄存器,从而将单周期处理器改造成了流水线处理器。整个处理过程为:填充流水线---流水线填满---流水线排空。在流水线填满阶段,所有的硬件都处于工作状态,理论上性能为非流水线的5倍。

但实际上收益并没有这么大。每个阶段所用的硬件实际并不是相互独立的;增加的寄存器也会导致延迟增大;每阶段的周期划分也很难做到一致。在后面“流水线的局限性”和“流水线冒险”部分再来详细了解这个问题,先把注意力放到流水线的原理上来。

 

1.2 计算流水线

这是一个非流水线的硬件系统,对应一条指令的执行,执行其中的组合逻辑部分假设需要300ps (1ps=10^(-12)s),寄存器延迟需要20ps,那么时钟周期设置为320ps(这条指令的执行时间为一个周期),吞吐量(指令数/指令执行时间)

1/320ps = 3.12GIPS(每秒千兆指令)。

 

 

假设将系统执行的阶段划分为A,B,C三个阶段,每个阶段需要100ps,那么时钟周期可以设置为120ps,一条执行执行需要3个时钟周期,即360ps。在流水线填满阶段,每周期各进入和结束一条执行,系统吞吐量为 : 1/(120ps) = 8.33GIPS, 提高到了原来的8.33/3.12=2.67倍。

 

1.2 流水线操作的详细说明

以三阶段流水线来说明。在时刻240的时钟上升沿(在后面的数据冒险中,需要以这个概念的理解为基础)来临之前,I2指令的阶段A中的计算结果已经到达第一个流水线寄存器的输入,但该寄存器的状态和输出还保持为指令I1在A阶段中计算的值。I2指令在阶段B中计算的值也已经到达第一个流水线寄存器的输入。当时钟上升沿来临时,这些输入才被加载到流水线寄存器中,引起寄存器输出的变化。如果时钟运行的太快,组合逻辑部分还没计算完毕,这时寄存器的输入还是非法值,就被寄存器读取并输出,就会产生错误。

 

1.3 流水线的局限性

在1.3节前提到的都是理想的流水线系统,每个阶段的时间都是相等的。实际上,各个阶段的时间是不等的。运行时钟是由最慢的阶段决定的。上图将时钟周期设置为170ps, 在每个时钟周期,A和C阶段都会产生空闲,实际的吞吐量为 1 / 170ps = 5.88GIPS, 并没有达到1.1 节中的8.33GIPS.

另外流水线过深,寄存器的增加会造成延迟增大。当延迟增大到时钟周期的一定比例后,也会成为流水线吞吐量的一个制约因素。下面是一些主流浏览器近几十年的变更,目前流水线划分基本稳定在15级左右。阶段划分的越小,周期越短,时钟频率越高,即主频越高,但流水线过深带来的延迟可能使收益下降,所以并不是主频越高性能越好。

主流处理器流水线阶段
1993年,Pentium 5级
1995年,Pentium Pro 12级
1999年,ARM9 5级
2002年,ARM11 8级
2004年,Pentuim4(Prescott) 31级
2006年,Core2 Duo(Merom) 14级
2008年,Core i7(Nehalem) 16级
2013年,Core i7(Haswell) 14级

2.流水线冒险

2.1 带反馈系统的流水线

下述例子来源于《CS:APP》Y86-64指令。

在上述指令序列中,每对相邻的指令之间都有数据相关。第一条指令将结果存放在%rax;第二条指令要读取这个值, 并存入%rbx;第三条指令要读取%rbx。

 

在上述指令序列中,第3条指令产生了一个控制相关。条件测试的结果决定是执行第4行的指令,还是第7行的指令。以上均是流水线引入反馈的例子,硬件结构如下图。将流水线技术引入处理器时,必须正确处理反馈的影响。

 

2.2 数据冒险

2.2.1 用暂停处理数据冒险

一条指令需要使用之前指令的运算结果,但结果还未被写回,这种情况称为数据冒险。先来看一个例子:

在时钟周期为7时,0x017地址的指令执行译码的操作,把寄存器%rdx, %rax的值读入内存。这两个寄存器的值是由0x000, 0x00a处的指令写入的,在周期6的时钟上升沿(1.2中已经阐述过了)到来时,%rdx的值已经发生了变化,为10;周期7的时钟上升沿到来时,%rax的值也已经变化。所以在周期7中,0x017的指令执行译码时,寄存器的值已经写入完毕,因此读取不会出错。

 

来看一下出错的情况:

在时钟周期为6时,0x017地址的指令执行译码的操作,把寄存器%rdx, %rax的值读入内存。这两个寄存器的值是由0x000, 0x00a处的指令写入的。%rdx的值在时钟周期6的上升沿到来时发生变化,但是%rax的值要在时钟周期7的上升沿到来时才变化,所以0x017读取的%rax的值是错误的,图中为0.

 

处理器可以用暂停的方式来避免这种数据冒险:

通过插入气泡(bubble),让指令addq %rdx, %rax停顿在译码阶段(流水线停顿(stall )),直到产生它的源操作数的指令通过了写回阶段。这个阶段并不是什么都不管,而是必须将机械信号保持为状态改变前的值。实现这样的机制并不困难,可以用软件的解决方案,即在指令之中插入nop指令,但是我们一般希望对软件屏蔽细节,所以能过硬件来完成更好。但是流水线暂停会带来吞吐量下降的问题,所以这并不是最佳的方案。

 

2.2.2 用转发处理数据冒险(也叫数据前递(forwadding), 旁路(bypass))

转发的思想是,与其暂停流水线直到写完成,不如简单将要写的值(还在内存中,尚未写入寄存器)传到所需要的地方作为源操作数 。在图中标注的1处:0x00a地址的指令在周期6将%rax和3的值读入内存,赋值给内存的临时变量W_dstE和W_valE;在图中标注的2处,当时钟周期7的上升沿到来时,3的值才会被写入寄存器,但是我们不用等待这个时刻的到来;在图中标注的3处,通过直接把内存中的值W_valE赋值给valB, 0x016地址指令的译码操作可以正确执行。

这种方式在硬件的实现上,由于绕过了寄存器,所以又称为旁路(bypass)。

 

2.2.3 将暂停和转发结合来处理数据冒险(加载/使用冒险)

2.2.2中用转发的方式,来将还在内存中的值,直接传递给下一条指令作为源操作数。但是如果内存读在流水线发生得比较晚,单纯的转发就解决不了。如下例子:

0x032地址的指令在译码阶段需要用到%rbx和%rax作为源操作数,这两个寄存器要分别在时钟周期8的上升沿和时钟周期9的上升沿才写入。对于%rbx,可以使用转发的方式提前从内存获取;但是%rax的值,要等到时钟周期8才写入内存,太晚了。这种情况的数据冒险,发生在使用加载指令(mrmovq和popq时),因此又称为加载/使用冒险,只能采用将流水线暂停一个周期,再转发的方式来解决。

 

暂停了一个时钟周期后,可以直接从内存获取%rax和%rbx的值了。

 

2.2.4 避免ret指令造成的控制冒险

对于ret指令,参考以下程序(来源于《CS:APP》

在上述程序中,指令列出的顺序与它们在程序中执行的程序并不相同。当ret执行执行后,ret执行的下一条指令并不执行,而是返回调用者的地址。因此,需要在流水线中插入3个bubble,让ret指令结束译码、执行、访存阶段(获取到了%rip应该设置的值)后,再正常进行流水线的操作,如下图。

 

2.2.5 避免跳转指令造成的控制冒险

转移指令和流水线本质上是冲突的,因为转移指令是要改变流向,而流水线希望指令依次取出。在处理转移指令时,处理器采用了分支猜测的技术,即猜测分支方向并根据猜测来取指。预测策略有总是选择、从不选择、反向选择、正向不选择等。当猜测错误时,会产生转移开销,包括:

1.将错误执行的指令废除(即“排空流水线”)

2.从转移目标地址重新取指

参考以下程序:

下图展示了如何处理预测错误的分支:

在周期4发现预测错误之前,已经取出了两条指令。在周期5中,流水线往这两条指令中插入bubble(插入气泡是保持机械信号状态不变),在周期6取出跳转指令后面的那条执行。这样这两条错误指令就从流水线上消失了。

 

2.2.6 结构冒险

结构冒险指的是对同一个寄存器的读和写同时发生的情况,其在处理器设计之初就已经考虑并在硬件上解决了:指令的单个阶段的执行其实用不了一个周期,在读和写同时发生时,前半周期用于写,后半周期用于读。

 

3.性能分析

所有插入的气泡,都会导致流水线周期的损失,设执行了Ci条有效指令,Cb条气泡,则共(Ci+Cb)个时钟周期 , 用每指令周期数(CPI, cycles per instruction)来衡量性能(理想情况是不产气泡,即CPI为1):

CPI = (Ci+Cb)/Ci = 1 + (Cb/Ci)

假设条件转移指令占所有指令的20%, 其中40%的几率预测错误,预测错误会产生2个气泡;

假设ret指令占所有指令的2%, 每次产生3个气泡;

假设需要加载指令占所有指令的25%, 其中20%会导致加载/使用冒险,每次产生1个气泡,那么CPI:

CPI =  1 + 20%*40%*2 + 2%*3 + 25%*20%*1 = 1.27

4.参考

1.《深入理解计算机体系统》第三版

2. coursera 北京大学《计算机组成》

3. CMU《cs:app》课程官网