适用于RISC CPU的转移指令的原理及仿真

1 引言
在RISC CPU的设计当中，转移指令的处理对处理器的性能的影响非常关键。转移指令决定着程序的执行顺序，在程序中的使用频率很高。RISC CPU中程序是以流水线的方式执行的，当程序顺序执行时，下一条指令的地址与前一条指令的内容无关 ；而在执行转移指令时要根据转移指令的执行结果来确定下一条指令的地址，也就是说下一条指令的地址在转移指令执行之前是未知的，造成流水线的不连贯，影响了CPU的效率。
转移指令处理的方法很多，可分为预测法和非预测法，预测法又包含静态预测和动态预测，静态预测如总预测跳转、正向不跳转反向跳转，动态预测如2比特计数器(2BC) 、BTC；非预测法如延时跳转等[1]。这些基本方法合理组合之后可以得到很好的效果。
本文介绍的RISC CPU对转移指令的处理方法，为5级流水线作业，分别是取指、译码、执行、访存、回写，对转移指令的处理在取指级和译码级完成；译码级给出转移指令所包含的详细信息，取指级包含有地址计算单元，转移目标Cache (BTC)，跳转判断单元等。对转移指令的处理使用了延时跳转、2BC以及BTC方法。
2转移指令的原理
该RISC CPU的指令集中包含有条件转移指令和非条件转移指令。所有的转移指令均使用延时转移，每条转移指令后面跟随一条延时槽指令；采用2BC预测条件转移是否跳转，而BTC则保存转移目标为固定地址的转移指令执行后的信息。以下分别介绍在该RISC CPU设计中转移指令的设计以及延时转移、BTC、2BC的具体实现方法。
2.1 转移指令类型及格式
该RISC CPU的指令集中包含条件转移指令（BCC）和非条件转移指令（CALL和RET），其编码格式为图1所示。CALL指令包含2位的操作码和30位的地址。BCC指令包含8位操作码， 4位条件码(Condition Code)，19位偏移量以及1位用来区分指令是否带A参数(即ANNUL操作)。所有的BCC指令使用相同的操作码，不同的BCC指令用条件码来区分，共有16类BCC指令；偏移量为带符号数，在低位用00扩展后可以对±220的相对地址寻址。RET指令包含8位的操作码和两个5位的寄存器地址。

2.2 延时转移
在该RISC CPU中，由于转移指令只有在译码级才被识别，跳转与否在译码级才能决定，因此在取下一条指令之前必须等待一个时钟周期。为了减少流水线中的气泡，紧跟转移指令后面插一条与跳转不相关的指令，即延时槽指令，不管跳转是否发生，该指令都执行。延时槽指令的插入由编译器完成，当编译器找不出这样的指令时，就插一条NOP指令。考虑到减轻编译器的难度，我们也采用了带 A参数的转移：当指令带有A参数时，延时槽指令从转移目标程序中取出，因此转移发生时，延时槽指令执行，而转移不发生时，则禁止延时槽指令进入译码级。因一般而言非条件转移指令出现的频率远低于条件转移指令出现的频率，非条件转移指令的延时槽指令相对来说容易找到，所以非条件转移指令不采用A参数选项，而条件转移指令采用A参数选项。
2.3 2BC与BTC的设计
2BC与BTC对提高转移指令的执行效率起重要的作用。在RISC CPU中，转移指令执行后，有很大的概率会执行更多次。对于转移目标为固定地址的转移指令（BCC和CALL），在其次执行时使用BTC存储相关的信息，当再次执行时，直接读出这些信息，控制程序的执行顺序，而不需要转移指令本身进流水线。这可大大提高效率，但对于转移目标不确定的间接转移指令（如RET），BTC是无效的。另外，条件转移指令（BCC）是否跳转也是不确定的，本设计中采用2BC进行预测。

BTC为全相联Cache，总共有16个单元，每个单元包含的信息有：TAG存储执行过的转移指令的地址、DI存储延时槽指令、CC存储条件码、TP 存储转移指令类型、AN存储A参数携带标志，HI存储转移执行情况的历史记录，即2BC，VI指示行数据是否有效。BTC包含BTC存储、BTC命中以及BTC检查三种工作任务。以下分别介绍2BC以及每种任务下BTC的工作情况。　

2.3.1　2BC的作用及工作原理

因为转移指令执行之后，转移目标地址、延时槽指令都保存在BTC中了，当该指令再次执行时，这些信息就直接从Cache读出，因此在取指级就可以得到跳转目标地址和延时槽指令。对于非条件转移指令，跳转总是执行，因此BTC命中时就可以直接决定下一条指令的地址为转移目标地址，而当前周期DI被送到指令总线上；但对于条件转移指令，跳转与否是根据条件码和ALU的标志位来决定的。如果转移指令前面一条指令的执行结果改变标志位，而当BTC命中时该指令还在译码级，则跳转与否需要等待一个时钟周期才能决定。为了避免因为等待而造成流水线的停顿，采用2BC当前的状态预测跳转是否执行，在接下来的时钟周期，标志位有效之后，再检查预测是否正确，如果不正确，就进行更正。当预测准确时，采用2BC 与BTC可以使转移指令的执行时间缩短一个周期。即使预测不准确，与不采用预测相比也不会有损失。2BC的工作原理如图2所示，初始值为Nx（次不跳转执行）或Tx(次跳转执行)，t表示跳转执行，n表示跳转不执行。当HI为N或Nx时，预测跳转不发生；当HI为T或Tx时，预测跳转发生。

2.3.2　BTC存储
当转移指令次执行时，BTC在当前时钟启动存储任务，把该指令执行的信息写入对应的单元中，对于BCC指令，确定2BC的初始状态。同时也把该行的VI置为有效。BTC采用随机替换策略确定数据入口：在复位或Cache清零之后，按顺序填充Cache，如果BTC写满，则随机选通一行进行替换。
2.3.3　BTC命中
在取指周期开始时如果发现当前取指地址包含在BTC的TAG中，并且对应行的VI也有效，则认为BTC命中，从而启动命中任务：读出命中行的数据，把DI送到指令总线，如果是CALL指令，转移目标地址作为下一条指令的地址；如果是BCC 指令则需要判断跳转是否发生：当标志位有效时，根据条件码与标志位判断，否则根据HI进行预测，然后确定下一条指令的地址：跳转时为转移目标地址，不跳转为PC+2。对于带Ａ参数的BCC指令，在跳转不执行时，要禁止DI在下一时钟进入译码级。BTC命中的流程如图3。

2.3.4　 BTC检查
如果前一周期BTC命中，则在当前周期开始时启动BTC检查任务；如果前一周期BTC是根据HI预测BCC的跳转，那么在当前时钟标志位有效后，要重新判断跳转决定是否正确，如果不正确就要进行更正，给出正确的取指地址，请求在下一时钟禁止译码级或执行级。同时还要根据终的跳转情况和HI的更新算法更新HI。BTC检查的流程图如图4。

3结论
整个RISC CPU用Verilog HDL语言进行了描述，并针对标准程序进行了仿真，仿真结果表明，采用上述方法处理转移指令可以明显提高流水线的吞吐率。由于在转移指令后面插入了延时槽指令，转移指令的执行与程序顺序执行时完全相同； BTC的使用虽然在硬件上增加了一些开销，但使转移指令再次执行时基本不占用流水线资源，大大提高了CPU的效率。