仲裁器设计（二）-- Round Robin Arbiter

[导读]仲裁器设计(一) -- 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[3:0]RR PriorityRR Grant[3:0]Fixed Grant

Cycle 00101321000010001

Cycle 10101210301000001

Cycle 20011032100010001

Cycle 30010210300100010

Cycle 41000103210001000

第一个周期，初始状态，我们假设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 );

8 wire[2*NUM_REQ-1:0] double_req = {req,req};

10 wire[2*NUM_REQ-1:0] double_gnt = double_req & ~(double_req - base);

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 );

8 logic [REQ_WIDTH-1:0] pre_req;

10 assign pre_req[0] = 1'b0;

12 assign pre_req[REQ_WIDTH-1:1] = req[REQ_WIDTH-2:0] | pre_req[REQ_WIDTH-2:0];

14 assign gnt = req & ~pre_req;

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

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的设计也来自于这篇论文，里面还有不同设计的面积时序比较。