这是一条备忘录.

顺序流水线存在一些hazards

这里仅记录 data hazards.

以五级流水线为例.

  • 写后读(RAW): 发生写后读是因为寄存器的写回操作发生在第五个流水级(WB),寄存器的读操作发生在第二个流水级(ID).假设对R寄存器的写指令之后,紧跟着对R寄存器的读指令,当执行到读指令的第二个流水级(ID)时,正执行到写指令的第三个流水级(EXE),所以此时R寄存器仍为旧值.
  • 读后写(WAR)
  • 写后写(WAW)

只有RAW是在 in-order 流水线中存在的 hazard.引入乱序以后,才会出现WAR和WAW.

详情查google.

通过阻塞或者前递技术(forwarding)可以解决RAW的问题.

因为在forwarding的实现中,也用到了阻塞技术,所以这里只说forwarding.

forwarding如何实现?

  • forwarding以后,还需要阻塞吗? 如果是将前一条指令执行阶段的结果forwarding到后一条指令的执行阶段,则不需要阻塞;如果是将前一条指令访存阶段的结果forwarding到后一条指令的执行阶段,则需要阻塞一拍.
  • 将哪个阶段的结果forwarding到哪个阶段? 如果前一条指令是在执行阶段就能拿到结果(计算指令在执行阶段可以拿到结果),需要将前一条指令 执行阶段 的结果forwarding到后一条指令的 执行阶段;如果前一条指令在访存阶段才能拿到结果(访存指令在访存阶段才能拿到结果),需要将后一条指令阻塞一拍,并将前一条指令 访存阶段 的结果forwarding到后一条指令的 执行阶段.
  • 如何知道要用前递的数据还是从寄存器读出的数据? 给ALU的源操作数加个多路选择器,多路选择器的一个输入是寄存器堆,另一个输入是前递来的数据. 假设第一条指令是写R寄存器的指令i(指令i是运算指令),第二条指令是读寄存器的指令j. 我个人的想法是,在ID时维护寄存器的"状态",在对指令i进行ID时,记录一下寄存器R正在被写,且结果在EXE阶段可以出来,这个状态我们可以用01来代表;当对指令j进行ID时,发现寄存器R的状态是01,就可以产生一个信号,告诉处理器下个EXE阶段要选择前递过来的数据. 假设第一条指令是写R寄存器的指令i(指令i是访存指令),第二条指令是读寄存器的指令j. 在对指令i进行ID时,记录一下寄存器R正在被写,且结果在WB阶段可以出来,这个状态我们可以用10来代表;当对指令j进行ID时,发现寄存器R的状态是10,就可以产生一个信号,告诉处理器IF,ID,EXE单元都需要阻塞一拍,且下个EXE阶段要选择前递过来的数据. 当然,在实际开发时,要记录下每个寄存器的状态是浪费资源的,其实只用记录下每个阶段的指令会影响到哪个寄存器就好,这样,如果指令j在ID时发现处于EXE阶段的指令会影响到寄存器R,就取上一条指令EXE阶段前递过来的结果;如果指令j在ID时发现出于MEM阶段的指令会影响到寄存器R,就阻塞一拍,并取上一条指令MEM阶段前递过来的结果.

乱序

以下只是一个备忘,原文来自计算机体系结构 第三版 9.5.2.

核心思想

乱序处理器的核心思想是把会被阻塞的指令先暂存到保留站中等待,这样就不会影响后面的不相关指令发射.在每个周期,如果保留站中存在等待的指令,就先检查该指令的相关问题是不是已经解决,如果相关问题已经解决,就优先发射保留站中的这条指令(比如保留站中的一条指令在等待上一条指令写入寄存器R,如果检测到寄存器R已经被写入新值,就发射这条指令).

乱序会引入WAW和WAR相关

在顺序流水线中,不存在WAW相关(如果两条指令都需要写寄存器R,第一条指令写寄存器R的时间是n,第二条指令写寄存器R的时间至少是n+1,因为一个周期最多执行一次写寄存器的操作)和WAR相关(如果第一条指令i读寄存器R,第二条指令j写寄存器R,指令i读寄存器的时间是n,指令j写寄存器的时间至少是j+3,因为读寄存器是在ID阶段,写寄存器是在WB阶段).

但是在乱序流水线中,在静态流水线中被阻塞的指令是需要先待在保留站中的,所以后面的和这条指令存在WAW和WAR相关的指令进行写操作可能先于这条指令,这时就出现了WAW相关或者WAR相关.

Tomasulo算法

1966年,Robert Tomasulo在IBM 360/91中首次提出了对于动态调度处理器设计影响深远的Tomasulo算法。该算法在CDC6000记分板方法基础上做了进一步改进。面对RAW相关所引起的阻塞，两者解决思路是一样的，即将相关关系记录下来，有相关的等待，没有相关的尽早送到功能部件开始执行。但是Tomasulo算法实现了硬件的寄存器重命名，从而消除了WAR和WAW相关，也就自然不需要阻塞了。

Tomasulo算法不能保证精确例外.

硬件实现的寄存器重命名

总结一下寄存器重命名的内涵：发生写后写冒险时找一个新的寄存器存放新值，发生读后写冒险时也找一个新的寄存器存放新值。

旧值存储在逻辑寄存器中,新值往重命名后的物理寄存器中写.

根据 胡伟武老师的计算机体系结构第二版, Tomasulo算法可以通过保留站来实现硬件的寄存器重命名.

寄存器堆中,除了要保存寄存器的值,每个寄存器还有一个域用于维护当前发射的所有指令中,最后写这个寄存器的指令在几号保留站中.

寄存器堆和保留站都监听结果总线,如果寄存器堆发现第i号保留站向寄存器R写了值,则寄存器堆更新这个寄存器R;如果保留站中某条指令在等待保留站i的写入结果,则直接使用这个结果.这样就实现了寄存器的硬件重命名.

通过ROB实现精确例外

精确例外就要求指令对CPU的状态更改是有序的,这里我们只考虑对寄存器的修改.

Tomasulo算法已经通过保留站实现了指令的乱序执行,为了保证指令对寄存器的修改是顺序的,在指令发射的时候,需要通过重排序缓存(ROB)来维护指令原来的顺序,ROB是一个FIFO的结构,当指令发射时,需要将这条指令的信息记录到ROB中(主要记录这条指令是什么,它要写哪个寄存器,写的值是多少,这个值在指令发射的时候为空),并将ROB的号码在寄存器的相应的域中(在没有ROB只有Tomasulo时,这个域保存的是保留站的号码或者说ID),这个域的意义是当前发射的所有指令中,最后写这个寄存器的指令在ROB中的位置.当指令执行完毕后,先将值写回ROB中,如果ROB的队列头部的值已经写回,则将这个值写回相应的寄存器并通知保留站中等待这个寄存器的指令.

当发射一条新指令时,如果要读取的寄存器状态域不为空,表示这个寄存器的值还没被写回,则这条新指令需要监听ROB的相应条目.

TODO 精确例外与外部设备

CPU的状态还包括外部设备的状态,但是在设计流水线时,只考虑了对寄存器状态的修改,这样会出问题吗?

比如下面的几条指令,第二条指令为除法指令,第三条指令为 store 指令,向内存的 0x10 地址写入寄存器 e 的值.

  mul a, b, c
  div d, a, a
  st 0x10, e

因为 st 指令不依赖于前两条指令,所以 st 指令可以在 div 指令还没执行的时候先执行,如果ROB不限制 st 指令的提交,且 div 指令会出现 除以零异常,在发生异常时,内存 0x10 处已经被写入了新值.

乱序会引入精确异常的问题

在乱序流水线中, 后面的指令会先于前面的指令执行 ,这句话的含义是指后面的指令会先于前面的指令更改处理器的状态(比如寄存器的值),如果前面的指令发生了异常,且后面的指令已经修改了寄存器的值,这时就违背了 精确异常.

这个问题的解决办法是在流水线中加入重排序缓存(ROB, Reorder Buffer)来维护指令的有序结束.

总结

乱序流水线要实现的目标是,指令有序发射,乱序执行,有序结束.有序发射和乱序执行是通过保留站来实现的,有序结束是通过ROB来实现的.

其他

计分板

计分板引入了一些硬件结构,保证顺序发射,乱序执行,有序提交,但是不能保证精确例外.

Functional unit status 记录每个部件的状态,用于判断是否存在结构相关,以及已经存在的数据相关是否已经解决.存在结构相关意味着后面的指令还不能发射,已经存在的数据相关解决了意味着被这个相关阻塞的指令可以执行了.通过这个部件中的 Ri和Rj标志位 解决了WAR相关(执行完成的指令看是读取这两个寄存器的功能单元的Ri和Rj是否为yes,如果是yes,表示能读但是还没读,这种情况下就不能写).通过 Ri和Rj的标志位 解决了RAW相关,如果Ri或者Rj有一个是no,表示不能读,因为有别的部件还没把结果写上来(通过 register result status 这个部件可以知道哪个寄存器还在等待哪个部件写),当别的部件把值写上来,先把Ri或Rj标志位改成yes,然后在下一周期读寄存器,读完将Ri和Rj改成no(确保存在WAR相关的指令可以将数据写回寄存器).

Register result status 记录每个寄存器正在被哪个功能单元写,通过这个结构保证不存在WAW相关,也就是说, 只有一条指令可以写某个寄存器,如果一个寄存器已经正在被一条指令写,下一条写这个寄存器的指令还不能发射.

这一部分参考了这篇博客和这个视频.