作者：李虹江
原文：https://mp.weixin.qq.com/s/r-nckE5nGz9mc5KqjPXKYg
本文授权转自IC加油站微信号，未经作者授权，严禁二次转载。
上一篇老李讲了固定优先级仲裁器Fixed Priority Arbiter 仲裁器设计（一） -- Fixed Priority Arbiter
里面提到了，固定优先级仲裁的一个问题就是公平性。以上篇文章里同学举手老师点名的例子来说，如果老师每次都叫学号小的，那学号大的同学会觉得不公平，因为被老师点到的机会小。单纯回答问题的话可能还好，如果我们假设每回答一个问题积一分，最后成绩按照回答问题的个数来计算的话，那么很显然这种方式对学号大的同学太不公平了。所以，仲裁器的公平性问题是在设计中我们必须要考虑的。
Round Robin就是考虑到公平性的一种仲裁算法。其基本思路是，当一个requestor 得到了grant许可之后，它的优先级在接下来的仲裁中就变成了最低，也就是说每个requestor的优先级不是固定的，而是会在最高（获得了grant)之后变为最低，并且根据其他requestor的许可情况进行相应的调整。这样当有多个requestor的时候，grant可以依次给每个requestor，即使之前高优先级的requestor再次有新的request，也会等前面的requestor都grant之后再轮到它。
我们以4个requestor为例来说明，下面这个表格Req[3:0]列表示实际的request，为1表示产生了request；RR Priority这一列为当前的优先级，为0表示优先级最高，为3表示优先级最低；RR Grant这一列表示根据当前Round Robin的优先级和request给出的许可；Fixed Grant表示如果是固定优先级，即按照3210，给出的grant值。
第一个周期，初始状态，我们假设req[0]的优先级最高，req[1]其次，req[3]最低，当req[2]和req[0]同时为1的时候，根据优先级，req[0]优先级高于req[2]，grant = 0001。
第二个周期，因为req[2]在前一个周期并没有获得grant，那么它继续为1，而这个时候req[0]又来了一个新的request，这个时候就能够看出round robin和fixed priority的差别了。对于fixed priority， grant依然给0，即0001。但是round robin算法的要求是：因为上一个周期req[0]已经被grant了，那么它的优先级变为最低的3，相应的，req[1]的优先级变为最高，因为它本来就是第二高的优先级，那么当req[0]优先级变为最低了之后它自然递补到最高，那么这个时候产生的许可grant就不能给到req[0]，而是要给到req[2]。
同理，第三个周期，req[2]因为在前一个周期grant过，它的优先级变为3最低，req[3]的优先级变为最高。后面的周期大家可以自己顺着分析下来。
换句话说，因为被grant的那一路优先级在下一个周期变为最低，这样让其他路request都会依次被grant到，而不会出现其中某一路在其他路有request的情况下连续被grant的情况，所以round-robin在中文中也被翻译成“轮询调度”。
好，下面我们来讲round robin的RTL 实现。老李这次就不讲特例了，直接介绍几种参数化的写法。
首先看第一种思路，即优先级是变化的，回想一下我们之前讲的Fixed Priority Design，我们都假定了从LSB到MSB优先级是由高到低排列的。那么我们有没有办法先设计一个fixed priority arbiter，它的优先级是一个输入呢？看下面的RTL
1 module arbiter_base #(parameter NUM_REQ = 4)
2 (
3 input [NUM_REQ-1:0] req,
4 input [NUM_REQ-1:0] base,
5 output [NUM_REQ-1:0] gnt
6 );
7
8 wire[2*NUM_REQ-1:0] double_req = {req,req};
9
10 wire[2*NUM_REQ-1:0] double_gnt = double_req & ~(double_req - base);
11
12 assign gnt = double_gnt[NUM_REQ-1:0] | double_gnt[2*NUM_REQ-1:NUM_REQ];
13 endmodule在这个模块中，base是一个onehot的信号，它为1的那一位表示这一位的优先级最高，然后其次是它的高位即左边的位，直到最高位后回到第0位绕回来，优先级依次降低，直到为1那一位右边的这位为最低。咱们以4位为例，如果base = 4'b0100, 那么优先级是bit[2] > bit[3] > bit[0] > bit[1]。
这个设计的思路和老李前一篇仲裁器设计（一） -- Fixed Priority Arbiter最后那个1行设计的思路很像，里面double\_req & ~(double\_req-base)其实就是利用减法的借位去找出base以上第一个为1的那一位，只不过由于base值可能比req值要大，不够减，所以要扩展为{req, req}来去减。当base=4‘b0001的时候就是咱们上一篇里面的最后的算法。当然base=4'b0001的时候不存在req不够减的问题，所以不用扩展。
那么好了，既然有了可以根据输入给定优先级的固定优先级仲裁器（这句话有点绕，你仔细琢磨一下），那么接下来的任务就简单了，每次grant之后，我把我的优先级调整一下就可以了呗。而且这个设计妙就妙在，base要求是一个onehot signal，而且为1的那一位优先级最高。我们前面说过，grant一定是onehot，grant之后被grant的那一路优先级变为最低，它的高1位优先级变为最高，所以，我只需要一个history\_reg，来去记录之前最后grant的值，然后只需要将grant的值左移一下就变成了下一个周期的base。比如说，假设我上一个周期grant为4'b0010，那么bit[2]要变为最高优先级，那只需要base是grant的左移即可。RTL代码如下
module round_robin_arbiter #(parameter NUM_REQ = 4)
(
input clk,
input rstn,
input [NUM_REQ-1:0] req,
output [NUM_REQ-1:0] gnt
);
logic [NUM_REQ-1:0] hist_q, hist_d;
always_ff@(posedge clk) begin
if(!rstn)
hist_q <= {{NUM_REQ-1{1'b0}}, 1'b1};
else
if(|req)
hist_q <= {gnt[NUM_REQ-2:0, gnt[NUM_REQ-1]};
end
arbiter_base #(
.NUM_REQ(NUM_REQ)
) arbiter(
.req (req),
.gnt (gnt),
.base (hist_q)
);
endmodule我们注意到，和Fixed Priority Arbiter不同，Round robin arbiter不再是纯的组合逻辑电路，而是要有时钟和复位信号，因为里面必须要有个寄存器来记录之前grant的状态。
上面这个Round Robin Arbiter的设计，好处就是思路简单明了，代码行数也很短，在你理解了Fixed Priority Arbiter之后，理解这个设计就很容易。但是这个设计也有缺点，即在面积和timing上的优化不够好。相比于我们接下来要介绍的设计，在request位数大(比如64位）的时候timing和area都要差一些，所以其实老李见并没有见到公司里采用这个设计，而更多的时候采用的是下面的设计。
前面的思路是换优先级，而request不变，另一个思路是优先级不变，但是我们从request入手：当某一路request已经grant之后，我们人为地把进入fixed priority arbiter的这一路req给屏蔽掉，这样相当于只允许之前没有grant的那些路去参与仲裁，grant一路之后就屏蔽一路，等到剩余的request都依次处理完了再把屏蔽放开，重新来过。这就是利用屏蔽mask的办法来实现round robin的思路。
这个思路还是会用到前面一讲里Fixed Priority Arbiter的写法，如何来产生屏蔽信号mask呢？回看下面这段RTL
1 module prior_arb #(
2 parameter REQ_WIDTH = 16
3 )(
4 input [REQ_WIDTH-1:0] req,
5 output [REQ_WIDTH-1:0] gnt
6 );
7
8 logic [REQ_WIDTH-1:0] pre_req;
9
10 assign pre_req[0] = 1'b0;
11
12 assign pre_req[REQ_WIDTH-1:1] = req[REQ_WIDTH-2:0] | pre_req[REQ_WIDTH-2:0];
13
14 assign gnt = req & ~pre_req;
15
16 endmodule里面的pre\_req的意义是什么？就是如果第i位的req为第一个1，那么pre\_req从i+1位开始每一位都是1，而第0位到第i位都是0。这其实就是我们要找的mask! 只需要把req和上一个周期的pre\_req AND起来，那么我们自然就得到了一个新的request，这个request里之前grant的位以及之前的位都被mask掉了，允许通过的是在之前优先级更低的那些位，如果那些位上之前有request但是没有被grant，现在就可以轮到他们了。每次新的grant之后mask里0的位数会变多，从而mask掉更多位，直到所有的低优先级的request都被grant了一次之后，req AND mask的结果变成全0了，这个时候就说明我们已经轮询完毕，要重新来过了。
硬件实现上我们需要两个并行的Fixed Priority Arbiter，它们一个的输入是request AND mask之后的masked\_request，另一个就是原本的request，然后我们在它们两个arbiter的output中选择一个grant。如下图所示
当masked\_request不是全0，即存在没有被mask掉的request时，我们选择上面的这一路Mask Grant，否则我们选择下面这一路Unmasked Grant。
而又因为对于上面这一路来说，当masked\_request为全0的时候，Mask Grant也是全0，这个时候可以把Mask Grant和Unmask Grant直接按位OR起来就行，所以其实图上最后显示的Mux可以用下面简单的AND门和OR门实现
下面是这个设计的代码，依然是参数化的表达，可以满足任意数目的request。
module round_robin_arbiter #(
parameter N = 16
)(
input clk,
input rst,
input [N-1:0] req,
output[N-1:0] grant
);
logic [N-1:0] req_masked;
logic [N-1:0] mask_higher_pri_reqs;
logic [N-1:0] grant_masked;
logic [N-1:0] unmask_higher_pri_reqs;
logic [N-1:0] grant_unmasked;
logic no_req_masked;
logic [N-1:0] pointer_reg;
// Simple priority arbitration for masked portion
assign req_masked = req & pointer_reg;
assign mask_higher_pri_reqs[N-1:1] = mask_higher_pri_reqs[N-2: 0] | req_masked[N-2:0];
assign mask_higher_pri_reqs[0] = 1'b0;
assign grant_masked[N-1:0] = req_masked[N-1:0] & ~mask_higher_pri_reqs[N-1:0];
// Simple priority arbitration for unmasked portion
assign unmask_higher_pri_reqs[N-1:1] = unmask_higher_pri_reqs[N-2:0] | req[N-2:0];
assign unmask_higher_pri_reqs[0] = 1'b0;
assign grant_unmasked[N-1:0] = req[N-1:0] & ~unmask_higher_pri_reqs[N-1:0];
// Use grant_masked if there is any there, otherwise use grant_unmasked.
assign no_req_masked = ~(|req_masked);
assign grant = ({N{no_req_masked}} & grant_unmasked) | grant_masked;
// Pointer update
always @ (posedge clk) begin
if (rst) begin
pointer_reg <= {N{1'b1}};
end else begin
if (|req_masked) begin // Which arbiter was used?
pointer_reg <= mask_higher_pri_reqs;
end else begin
if (|req) begin // Only update if there's a req
pointer_reg <= unmask_higher_pri_reqs;
end else begin
pointer_reg <= pointer_reg ;
end
end
end
end
endmodule这里稍微多讲解几句，当no\_req\_masked之后，pointer\_reg并不是要更新到1111或是1110，而是要根据这个时候的request来，比如说这个时候request是0010，那么新的mask就要调整为1100，重新把bit[0], bit[1]都mask掉。
可以看出，这个设计利用两个N位的arbiter并行计算，critical path只比单独的fixed priority arbiter多了mask这一步和最后的mux这一级，在timing上表现是非常好的。面积上相比于前面一种做法2N的加法器也要少一些。
关于Round-robin还有其他的思路，比如将request进行rotate，从而达到改换优先级的目的，然后再根据history来rotate 回来。还有比如并行放N个fixed priority arbiter，把所有的priority order都实现了，然后再在N个grant中选择一个，这些设计在面积和时序上都各有牺牲，而且参数化设计不是很容易写，老李这里就不细讲了。感兴趣的同学可以点击原文链接，看一篇论文里的详细讲解，老李关于方法2的设计也来自于这篇论文，里面还有不同设计的面积时序比较。
推荐阅读
更多数字芯片设计类文章请关注数字芯片实验室。
