在Hazard寻求解法是否搞错了什麽

tags: IT铁人

Stall

上一次讲到了三种Hazard：

其实都能透过暂停Pipeline来解决，意思是不要急着插入下一个指令，塞几个空格进去，避开Hazard後再来好好执行原先要执行的指令，这个作法就称为Stall。

因为Structural的解决方式很简单，只要把Insturction Memory跟Data Memory分开即可，所以以下讨论Data Hazard跟Control Hazard的解决方法。

Data Hazard解决方法

Data Hazard可以用软件跟硬体的方法解决，软件的分为NOP跟重新排列，硬体则是使用Forwarding。

NOP

通常我们Stall的方法是插入NOP，就是No Operation，以Data Hazard来说，需要写回Register指令的後面两个指令都不能用到该写回的Register，因为这时该Register还没更新到最新的结果，所以我们插入NOP的方式就会像是...

对於这样的指令，因为$2要写回去才能交给其他指令只用，所以要插入两个NOP对齐WB跟ID，这样子前半Cycle可以存入，後半Cycle可以取得更新的资料，就可以避免NOP。

重排指令顺序

重排指令顺序通常是在Compiler负责执行，也就是说在编译程序的时候，它就要想办法把程序重新排列以便避开Data Hazard。

因为只要隔开两格即可避免Data Hazard，我们可以将底下移动後不影响结果的指令向上移动，就能够填补那两格NOP指令，以下提供一个范例：

在这边0和1会在t2发生Data Hazard、3和4会在t4发生Data Hazard。

所以要在不影响结果的状况下调动顺序，我们可以将3拿到0的後面，然後1放在2的後面，如此一来就能保证t2及t4的指令会和原本Data Hazard的指令有两格的差距，即可避免Data Hazard。结果如下：

看起来就像事先把t2跟t4的值先从Data Memory中读出来，在後面没有Hazard的地方做运算避开Hazard。

Forwarding

重新排列顺序有时後会发生无可避免的状况，通常这时候就会直接插入NOP了，不过交给Compiler执行也会稍微耗费时间，所以我们也可以从硬体着手。

Forwarding的概念是这样的，我直接把运算完的结果送到下一个指令要读取的Register的地方，比如说我运算後要把结果存入t2，而後面的指令正好要取t2的数值，那麽我直接把数值交给它即可。

底下有一个范例，像是前三行的R1，後面的指令都直接需要，所以我们就接线过去把数值传给它。

不过因为实际硬体的接线情况比较麻烦，原本的Datapath又会接的更复杂，想了解的同学就自己搜寻一下吧~

以实际生活发生的事情就像是：我去图书馆借书，要还的时候正好有人要借同一本书，那我就直接跟管理员说然後把书交给它。如此一来就可以避免丢进还书箱、图书馆员分类放好、想要的人再去找书完成借书程序。

Control Hazard的解法

至於Control Hazard的解决方，前面提到Control Hazard是因为Branch导致有指令需要丢掉，其实只要插入3个NOP就能解决，因为这时候PC就会指到对的指令位址，Instruction Memory就会输出正确的指令。

所以这样解决就可以了。

Dynamic Branch Prediction

如果不知道结果怎麽样的话，那用猜的不就好了，没错！

既然最差的情况是要等3个NOP，猜错的话也只是舍弃结果再来重新跑指令，但是如果猜对了就没有任何stall，那我们还不如一开始就猜结果，猜对赚到，猜错也不亏。

猜的方式这边要介绍两种，分别是1-bit跟2-bit。

1-bit Prediction Scheme

在这边用Finit State Machine(FSM)表示，不知道这是什麽的同学，这边简单介绍一下，圆圈的部份代表现在的状态，箭头代表遇到什麽情况要转换到哪个State。

以下是1-bit Prediction Scheme的FSM：

概念上就是如果这次的结果是yes，下个结果我就猜是yes，反之同理。

2-bit Prediction Scheme

以下是2-bit Prediction Scheme的FSM：

概念上就是如果发生了连续两次的yes，那麽就相信下个结果也是yes。

如果我现在站在永远yes的状况，只出现了一次no，我仍然相信下次还是yes。

举个例子：

假设我现在在深蓝色的Predict taken的State，然後发生了下列顺序的结果，T代表taken(答案为yes或是我猜测yes)，NT代表not taken(答案为no或是我猜测no)：

发生结果	2-bit猜测	是否match?
>	T	T	yes
>	T	T	yes
>	N	T	no
>	T	T	yes
>	N	T	no
>	N	T	no
>	N	N	yes
>	N	N	yes
>	T	N	no
>	T	N	no
>	N	T	no

这样子发生了11次猜测，只有5次猜对，答对率不到一半，虽然看起来很差，不过这是为了举例做出的结跟，所以跟实际情况有出入。

如果是平常的for回圈，1000次之後才会跳出去，那麽可能只有1~3次会答错，这麽看起来答对率超过99%，是很棒的预测。

这边主要要跟大家说可以用猜测的方式减少Control Hazard发生的机率，实际硬体接线也是很复杂，毕竟还要丢掉不要的指令以及通知Branch发生，这边就不特别说明了。

What we done?

这篇教了大家概念上怎麽解决Hazard，虽然没有跟大家说明硬体的部份，不过杰哥认为知道一下概念就好了，辛苦大家看到这边了~ 最近几篇的内容都蛮硬的，相信不少同学都被吓到了，继续努力吧~