文章目录
前言一、静态调度二、动态调度三、记分板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使用了分布的保留站(保留站、载入缓冲区、存储缓冲区)来分别处理运算指令、载入指令和存储指令。
引用:
计算机体系结构-量化研究方法