Round-Robin 调度逻辑算法
- 1 Intro
- 1.1 固定优先级
- 1.2 Round-Robin算法
之前上学还是工作，都接触过调度算法：Round-Robin和weight-Round Robin算法，但只知道它的功能和目的是什么，没有具体了解如何实现的；
现在是工作上需要来基于Verilog的具体实现；
1 Intro
Round-Robin即常说的RR轮询公平调度；原理：当多个request发送到仲裁器时，仲裁器通过轮询方式给request的grant，当一个requestor拿到grant后，它的优先级会降得最低；这样公平保证每个requestor都能拿到grant；
1.1 固定优先级
先介绍一下固定优先级的仲裁算法：即req[3:0]，优先级从低bit到高bit降低；在真值表实现上就是：对req[3:0]进行搜索，低位出现1，则相对应的grant位为1；
上述真值表表达：grant[3:0] = req & (~req+1)；
1.2 Round-Robin算法
回归主题Round_Rogin算法，是按照一定规则（上次获得grant的request，其优先级降为最低，优先级保持 向左递减规律）进行按照clk改变优先级大小；
Key:如何去动态调整优先级
不深究知道：添加hot信号，并进行与req相关运算，可以得到grant的优先级，得到该读热码对应位具有最高优先级，然后优先级循环向左降低；
Verilog代码实现：
module arbiter_hot#(
paramter NUM_REQ = 4
)(
input[NUM_REQ -1:0] req,
input[NUM_REQ -1:0] hot,
input[NUM_REQ -1:0] gnt
);
wire[2*NUM_REQ -1:0] double_req = {req,req};
wire[2*NUM_REQ -1:0] double_gnt = double_req & ~(double_req -base);
assign gnt = double_gnt[NUM_REQ-1:0] | double_gnt[2*NUM_REQ-1:NUM_REQ];
endmodule
从上图可以看出，hot可以很方便的显示优先级和相对应的影响grant的的裁决；即grant = f(req,hot);
现在增加逻辑改变hot的变化体现：优先级改变降低即可；
进一步做出改变即可：
module rr_arbiter#(
parameter NUM_REQ = 4
)(
input clk,
input rst_n,
input [NUM_REQ -1:0] req,
output[NUM_REQ -1:0] gnt
);
// req-->hot
reg[NUM_REQ -1:0] hist_q;
always_ff@(posedge clk) begin
if(!rst_n) begin
hist_q <= {NUM_REQ-1{1'b0},1'b1};// 初始req[0]为最高优先级
end else begin
if(|req) begin
hist_q <= {gnt[NUM_REQ-2:0],gnt[NUM_REQ-1]}; //改变优先级，向左循环移位
end
end
end
//call the module--combinationl logic
arbiter_hot #(
.NUM_REQ(NUM_REQ)
)(
.req(req),
.hot(hist_q),
.gnt(gnt)
)
endmodule
这个算法基本上全涉及运算，从固定优先级到–>循环左移优先级，能够看懂清晰
以上代码未经过搭建TB环境进行验证，仅供逻辑参考。
