文章目录

前言一、静态调度二、动态调度三、记分板1、记分板的数据结构2、相关性检测四、Tomasulo1、Tomasulo硬件结构2、保留站数据结构3、相关性检测和冒险消除4、具体实现五、对比

前言

乱序CPU中的动态调度算法。

一、静态调度

体系结构中，传统的五级流水线CPU（IF：取指；ID：译码；EX：执行；MEM：访存；WB：写回），为了防止指令之间数据相关导致的 RAW冒险，需要在ID阶段对进行相关性检测和互锁。

对于指令间的相关性，简单看下面一段汇编程序：

其中，ADD指令（省略.D）使用了DIV的目的寄存器F0作为源寄存器，所以DIV和ADD之间数据相关。同理ADD和S之间、SUB和MUL之间也存在数据相关。数据相关会导致产生RAW（Read and Write）冒险，即先读再写冒险。

而ADD和SUB之间，ADD使用了F8作为源寄存器，SUB使用了F8作为目的寄存器，产生了名相关中的反相关，该相关可能会导致WAR（Write and Read）冒险，即先写再读冒险。在顺序CPU中永远不会产生该冒险，因为ADD读F8永远会比SUB写F8早，但是在乱序CPU中需要对该冒险进行检测。同理S和MUL之间也存在反相关。

然后，ADD和MUL之间，同时使用了F6作为目的寄存器，所以两条指令会同时对F6寄存器进行写操作，产生了名相关中的输出相关，可能回导致产生WAW（Write and Write）冒险，即写入顺序相反。

对于顺序CPU来说，检测相关和消除冒险这个过程，可以由编译器进行检测和调度。但是由于顺序CPU的EX和MEM是按指令顺序执行的，所以如果中间存在某条指令长期发生阻塞，可能会产生较大的延迟（气泡），比如：发生了D_Cache缺失、D_TLB缺失或者超流水线CPU。从阻塞的指令开始，之后的指令无论是否和该指令存在依赖关系，都必须等待阻塞停止。整个CPU都会停止运行，直到阻塞结束或者有中断产生（外部中断或者时钟中断）。

二、动态调度

而乱序CPU中，采用了动态调度算法，对指令间的相关性进行实时动态检测，在记分板\保留站中构建了指令的依赖关系图，并时刻监测执行中指令的运行结果，进行解依赖。当某条指令发生阻塞的时候，在该指令之后，与该指令不存在相关关系的指令可以绕过存在相关关系的指令，先行发射。

使用乱序发射可能导致难以实现精确中断，或者分支预测错误之后无法对错误预测的结果进行修正，关于这点可以使用历史记录表\未来记录表解决该问题，暂不讨论。

动态调度算法主要分为：记分板 和 Tomasulo 两种算法。之前的学习中对两种方法不是能很好的区分他们之间的区别。所以进行对比记录。

三、记分板

乱序CPU中，由于指令执行顺序和WB顺序可能与PC（程序计数器）顺序不相同。所以可能会导致名相关的一对指令之间产生WAR冒险和WAW冒险，而顺序CPU中不会产生的WAR和WAW。记分板通过检测并停顿反相关后续指令来防止该冒险的产生。

1、记分板的数据结构

如图由以下几部分组成：

（1）指令状态

记录各记分板中指令的执行状态。

（2）功能单元状态：

记分板的数据结构如图由以下几部分组成：

1，忙：该记分板中的指令是否执行完毕。

2，Op：该记分板中指令执行的运算。

3，Fi：目标寄存器

4，Fj，Fk：源寄存器

5，Qj，Qk：生成源寄存器Fj、Fk的记分板。

6，Rj，Rq：Fj和Fk已经准备好。

（3）寄存器结果状态

将以该寄存器为目的寄存器的指令所在的记分板记录在结果状态中

2、相关性检测

每条指令按PC的顺序从指令存储/I_cache中取出发送给记分板。记分板中对该指令进行如下检测：

1，之前指令中有没有以同一寄存器为目标？——是否存在输出相关。如果存在则暂停发射该指令给ALU，以防止产生WAW冒险。

2，之前的指令中是否有以该指令源寄存器作为目的寄存器？——是否存在数据相关，即Qj，Qk是否有值，如果存在则暂停发射，以防止产生RAW冒险。

3，之前的指令中是否有以该指令目的寄存器作为源寄存器？——是否存在反相关，如果存在，则暂停发射，以防止产生WAR冒险。

四、Tomasulo

1、Tomasulo硬件结构

Tomasulo采用了CDB（Common Data Bus），和分布式的保留站：保留站、载入缓冲区、存储缓冲区

并将操作数保存在保留站中，使得保留站可以用作扩展寄存器，用以实行重命名。

2、保留站数据结构

1，忙：同上。

2，OP：同上。

3，Vj，Vk：源操作数数值。

4，Qj，Qk：生成源操作数数值Vj，Vk的保留站。

5，A：载入和存储指令的存储地址。

6，Qi：用来记录以该寄存器为目的寄存器的指令所在的保留站编号。

3、相关性检测和冒险消除

逐个分析：

1, 对于反相关。前一条指 m 使用了R3作为源寄存器，后一条指令 n 使用了R3作为目的寄存器。

当R3可用时，保留站中的m从R3中提取数据放入m的 Vj 字段，Qj为空。（可以理解为，此时保留站中的Vj是R3的一个副本，其作用和R3相同）。

同时n检测到R3可用，且执行条件满足，将R3的寄存器状态字段更改为n，执行，并将结果写入R3中。此时的R3已经被重命名。再之后，m执行条件满足，可以正常运行而不会产生WAR冒险。

2，对于输出相关。假设前一条指令m和后一条指令n都以寄存器R3作为目的寄存器。

m进入后，m执行条件不满足，暂停。n再进入，n执行条件满足，修改寄存器状态字段为n。则R3中的数据将以n为准。如果在m和n之间存在指令需要用到m的结果，则m运行的时候直接通过CDB将结果送给对应指令。以此来防止产生WAW冒险。

3，对于数据相关。假设假设前一条指令m使用R3作为目的寄存器后一条指令n都以R3作为源寄存器。

则n需要暂停等待m执行完毕并通过CDB广播执行结果后，再执行。

4、具体实现

自己使用verilog实现了一个基于32位MIPS指令级的Tomasulo调度方案。

以一个除法器的保留站为例，这个保留站设立为有3个项。在源码中，定义了：

rsdiv_busy ：保留站繁忙。

rsdiv_fire ：保留站指令已经发送给功能单元但是尚未得到结果（该字段非必要）。

rsdiv_op ：指令操作类型。这里主要分为有符号除和无符号除法。

rsdiv_vj ：保留被除数数值。

rsdiv_vk ：保留除数数值。

rsdiv_qj ：被除数数值所在的源寄存器的qi字段如果不为0，则送入qj。

rsdiv_qk ：除数数值所在的源寄存器的qi字段如果不为0，则送入qi。

// Divider Reservation Station HI:011 LO:110 : 0-2reg[ 2:0] rsdiv_busy ;reg[ 2:0] rsdiv_fire ;reg[ 5:0] rsdiv_op [2:0] ;reg[ 31:0] rsdiv_vj [2:0] ;reg[ 31:0] rsdiv_vk [2:0] ;reg[ 5:0] rsdiv_qj [2:0] ;reg[ 5:0] rsdiv_qk [2:0] ;

寻找空的保留站，为下一个除法指令进入保留站做准备。

使用轮序机制

// Empty div rs line findalways @(posedge clk, negedge rst_n) beginif(rst_n == 1'b0)rsdiv_sel <= 2'd0;elseif(intr_en == 1'b1 &&((intr_type == `D_INTR)) // Write empty rs line && (rsdiv_busy != 3'b111)) case(rsa_sel)2'd0:beginif(rsdiv_busy[1] == 1'b0)rsdiv_sel <= 2'd1;else if(rsdiv_busy[2] == 1'b0)rsdiv_sel <= 2'd2;else rsdiv_sel <= 2'd0;end2'd1:beginif(rsdiv_busy[2] == 1'b0)rsdiv_sel <= 2'd2;else if(rsdiv_busy[0] == 1'b0)rsdiv_sel <= 2'd0;elsersdiv_sel <= 2'd1;end2'd2:beginif(rsdiv_busy[0] == 1'b0)rsdiv_sel <= 2'd0;else if(rsdiv_busy[1] == 1'b0)rsdiv_sel <= 2'd1;elsersdiv_sel <= 2'd2;enddefault:rsdiv_sel <= 2'd0;endcaseend

当有除法指令进入的时候，div_flag拉高，如果除法保留站不为空，则将指令放入由rsdiv_sel找出的保留站中。

同时检查源寄存器的qi字段，r_qi[intr[25:21]或者r_qi[intr[20:16]]如果为0，则证明该指令与之前的指令不存在数据相关。则将rsdiv_qj和rsdiv_qk置0，并将寄存器r[intr[25:21]]或者r[intr[20:16]]中的数据放入rsdiv_vj和rsdiv_vk中。如果存在相关，首先检测CDB，如果CDB此时广播了数据，则直接写入CDB广播的运算结果。否则将r_qi写入保留站。

同时需要不断监听CDB，如果该指令执行完毕，需要将保留站的busy字段拉低，已分配给新的除法指令。一定不能在指令发送给除法器后马上拉低，不然会出现错误。

// RS of div writealways @(posedge clk or negedge rst_n) beginif(rst_n == 1'b0) beginfor(i=0;i<3;i=i+1) beginrsdiv_fire[i] <= 1'b0;rsdiv_busy[i] <= 1'b0;rsdiv_op[i] <= 6'd0;rsdiv_vj[i] <= 32'd0;rsdiv_vk[i] <= 32'd0;rsdiv_qj[i] <= 6'd0;rsdiv_qk[i] <= 6'd0;endendelse begin/****************** 新的div指令放入空槽 ************************/// div & divu 指令放入 div rs 空槽中if((div_flag == 1'b1) && (rsdiv_busy != 3'b111)) begin// Write empty rs line rsdiv_busy[rsdiv_sel] <= 1'b1; rsdiv_op[rsdiv_sel] <= intr[5:0];if(r_qi[intr[25:21]] == 6'd0) begin rsdiv_vj[rsdiv_sel] <= r[intr[25:21]];rsdiv_qj[rsdiv_sel] <= 6'd0;endelse beginif(cdb_en == 1'b1 && cdb_id != 6'd0 && r_qi[intr[25:21]] == cdb_id)beginrsdiv_vj[rsdiv_sel] <= cdb_v;rsdiv_qj[rsdiv_sel] <= 6'd0;endelse beginrsdiv_vj[rsdiv_sel] <= 32'd0;rsdiv_qj[rsdiv_sel] <= r_qi[intr[25:21]];endendif(r_qi[intr[20:16]] == 6'd0) beginrsdiv_vk[rsdiv_sel] <= r[intr[20:16]];rsdiv_qk[rsdiv_sel] <= 6'd0;endelse beginif(cdb_en == 1'b1 && cdb_id != 6'd0 && r_qi[intr[20:16]] == cdb_id)beginrsdiv_vk[rsdiv_sel] <= cdb_v;rsdiv_qk[rsdiv_sel] <= 6'd0;endelse beginrsdiv_vk[rsdiv_sel] <= 32'd0;rsdiv_qk[rsdiv_sel] <= r_qi[intr[20:16]];endendend/****************** 监控CDB，更新 div rs *********************/if(cdb_en == 1'b1 && cdb_id != 6'd0) begin// cdb to rs_divif(cdb_id[5:3] == 3'b110) beginrsdiv_busy[cdb_id[1:0]] <= 1'b0;end// 检查是否有 line 中的 qj qk 匹配if(rsdiv_busy[0] == 1'b1 && rsdiv_qj[0] == cdb_id) beginrsdiv_vj[0] <= cdb_v;rsdiv_qj[0] <= 6'd0;endif(rsdiv_busy[1] == 1'b1 && rsdiv_qj[1] == cdb_id) beginrsdiv_vj[1] <= cdb_v;rsdiv_qj[1] <= 6'd0;endif(rsdiv_busy[2] == 1'b1 && rsdiv_qj[2] == cdb_id) beginrsdiv_vj[2] <= cdb_v;rsdiv_qj[2] <= 6'd0;endif(rsdiv_busy[0] == 1'b1 && rsdiv_qk[0] == cdb_id ) beginrsdiv_vk[0] <= cdb_v;rsdiv_qk[0] <= 6'd0;endif(rsdiv_busy[1] == 1'b1 && rsdiv_qk[1] == cdb_id ) beginrsdiv_vk[1] <= cdb_v;rsdiv_qk[1] <= 6'd0;endif(rsdiv_busy[2] == 1'b1 && rsdiv_qk[2] == cdb_id ) beginrsdiv_vk[2] <= cdb_v;rsdiv_qk[2] <= 6'd0;endend endend

指令放入保留站后，要不断监听来自公共总线（CDB）的广播，检查是否有广播数据的id和自己保留站中的rsdiv_qj和rsdiv_qk相匹配，

如果匹配，则要及时清空rsdiv_qj和rsdiv_qk并将广播的数据记录在rsdiv_vj和rsdiv_vk`中。

并且需要不断检测各保留站中的rsdiv_qj和rsdiv_qk是否已经全部清空，如果两者都被清空，则证明该指令的所有源操作数都已经准备好，可以发送给除法器执行运算了。发送给除法器后，我的做法是将rsdiv_fire为拉高，表明该保留站已经执行但是尚未得到结果，用以防止不断发送同一个保留站给除法器。但是应该没有必要，后续可以删除该字段。

// RS of div firealways @(posedge clk or negedge rst_n) beginif(rst_n == 1'b0) begindat_div_en <= 1'b0;dividend <= 32'd0;divisor<= 32'd0;div_id<= 6'd0;div_op<= 6'd0;endelse begin/****************** div指令执行 ************************/// 如果 rs 011000 准备好if(rsdiv_busy[0]==1'b1 && rsdiv_fire[0]==1'b0 && rsdiv_qj[0] == 6'd0&& rsdiv_qk[0] == 6'd0 && busy_div == 1'b0)beginrsdiv_fire[0] <= 1'b1;dat_div_en <= 1'b1;div_op<= rsdiv_op[0];dividend <= rsdiv_vj[0];divisor <= rsdiv_vk[0];div_id<= 6'b011000;end// 如果 rs 011001 准备好else if(rsdiv_busy[1]==1'b1 && rsdiv_fire[1]==1'b0 && rsdiv_qj[1] == 6'd0 && rsdiv_qk[1] == 6'd0 && busy_div == 1'b0)beginrsdiv_fire[1] <= 1'b1;dat_div_en <= 1'b1;div_op <= rsdiv_op[1];dividend <= rsdiv_vj[1];divisor <= rsdiv_vk[1];div_id <= 6'b011001;end// 如果 rs 011010 准备好else if(rsdiv_busy[2]==1'b1 && rsdiv_fire[2]==1'b0 && rsdiv_qj[2] == 6'd0 && rsdiv_qk[2] == 6'd0 && busy_div == 1'b0)beginrsdiv_fire[2] <= 1'b1;dat_div_en <= 1'b1;div_op <= rsdiv_op[2];dividend <= rsdiv_vj[2];divisor <= rsdiv_vk[2];div_id <= 6'b011010;endelse begindat_div_en <= 1'b0;div_op <= 6'd0;dividend <= 32'd0;divisor <= 32'd0;div_id <= 6'd0;end/****************** 监控CDB，更新 div rs *********************/if(cdb_en == 1'b1 && cdb_id != 6'd0) begin// cdb to rs_divif(cdb_id[5:3] == 3'b110) beginrsdiv_fire[cdb_id[1:0]] <= 1'b0;end endend

对于除法，其目的寄存器为HI（保存商）和LO（保存余数），所以如果检测到是除法指令div_flag，需要将HI和LO寄存器的qi字段（hi_qi && lo_qi）写入保留站编号。这里，我设定的是，除法的话HI的编号设立为{4'b0110, rsdiv_sel}，LO的编号设立为{4'b1100, rsdiv_sel}，同一条除法指令商和余数的编号设计不同为了方便HI和LO寄存器在监听公共总线（CDB）广播的时候，能分辨除法器运算结束后发送的数据是商还是余数。对于其他运算，运算结果只有一个数，所以不需要如此。

// HI & LOalways @(posedge clk or negedge rst_n) beginif(rst_n == 1'b0) beginHI <= 32'd0;LO <= 32'd0;hi_qi <= 6'd0;lo_qi <= 6'd0;endelse begin// 标记 HI & LOif(div_flag == 1'b1) beginhi_qi <= {4'b0110,rsdiv_sel};lo_qi <= {4'b1100,rsdiv_sel};endelse if(mul_flag == 1'b1)beginhi_qi <= {4'b1110,rsmul_sel};lo_qi <= {4'b1000,rsmul_sel}; endelse if(hlw_flag == 1'b1) begincase(intr[5:0])`MTLO: lo_qi <= {4'b1010,rshl_sel};`MTHI: hi_qi <= {4'b1010,rshl_sel};default :;endcaseend endend

同时，寄存器需要不断监听公共总线的广播，当监听到和qi字段相同的广播编号的时候，要及时更新qi字段和寄存器的值。

// HI & LOalways @(posedge clk or negedge rst_n) beginif(rst_n == 1'b0) beginHI <= 32'd0;LO <= 32'd0;hi_qi <= 6'd0;lo_qi <= 6'd0;endelse begin// 监控 CDBif(cdb_en == 1'b1 && cdb_id == hi_qi && (cdb_id[5:3] == 3'b011 || cdb_id[5:3] == 3'b110|| cdb_id[5:3] == 3'b111 || cdb_id[5:3] == 3'b100 || cdb_id[5:3] == 3'b101) ) beginhi_qi <= 6'd0;HI <= cdb_v;endif(cdb_en == 1'b1 && cdb_id == lo_qi&& (cdb_id[5:3] == 3'b011 || cdb_id[5:3] == 3'b110|| cdb_id[5:3] == 3'b111 || cdb_id[5:3] == 3'b100|| cdb_id[5:3] == 3'b101)) beginlo_qi <= 6'd0;LO <= cdb_v;end endend

五、对比

记分板是在传统的顺序CPU结构的基础上进行的调度。对各种相关都只能暂停执行。并且对所有指令的状态都记录在一个统一的记分板上。

Tomasulo，在CPU结构上引入了CDB，并且在保留站中直接保留了源寄存器的数据，可以实现重命名。通过重命名来消除WAW和WAR冒险，只有当RAW冒险的时候才需要停顿。但是也实现过程也更加复杂。并且Tomasulo使用了分布的保留站（保留站、载入缓冲区、存储缓冲区）来分别处理运算指令、载入指令和存储指令。

引用：

计算机体系结构-量化研究方法