前言

本文的主题是仲裁器（Arbiter），主要是讲述仲裁器中各种算法的实现原理、优缺点、逻辑实现；在此处记录是为了以后开发中如有同样功能需要实现，就可以通过本文档重新拾取记忆

背景

在实际应用场景中，经常会出现多个源同时请求发送数据到同一个目的地，为了协调从各个源发来的数据，因此出现固定优先级、轮询调度、并行前缀轮询等算法用于处理该场景，不同的算法其所解决问题的角度不同，如 “轮询调度” 是为了保证各个源都有发送数据的机会，因此从算法的角度上保证了公平性；又如 “加权轮询调度” 是在 “轮询调度” 的基础上添加了一点点的 “偏心” ，由于某些场景下并非所有数据源都能 “一视同仁” ，所以通过权重的方式处理某些数据源实现 “连续多次请求的场景”

当前仅记录有以下算法

  • 固定优先级
  • 轮询调度
  • 并行前缀轮询

算法

固定优先级

概述：
固定优先级（Fixed Priority）是最简单的一种仲裁算法。从字面意思来看，就是每个模块的优先级是固定的；如果有出现多个模块同时产生 request 信号请求，则该模块按照优先级排序，响应优先级高的模块 grant。但是这样的算法就会缺乏公平性

举例说明

在课堂回答问题的时候，老师规定，回答问题按照学号进行排序，学号越靠前优先级越高

当老师需要学生回答问题时，学号2、15、18、31同时举手，老师将按照举手同学的学号，让学号最小的同学（学号2）去回答问题，这就是固定优先级

但是按照固定优先级去排序的话，学号越靠后能回答问题的几率越小，这样对学号靠后的同学不公平；这就是该算法的缺点了，由于是固定了优先级，所以无法保证各个同学的公平性

逻辑实现：

Info
 

1
2
3
4
5
6
7
8
9
10
module fix_pri_arbiter #(
   parameter                     N     = 16
)(
   input    wire  [N-1:0]        req         ,
   output   wire  [N-1:0]        gnt
);

   assign gnt = req & (~(req-1));
 
endmodule

这里的计算结果是 grant = req & (~(req - 1))

首先我们需要理解 (req - 1) 的目的是为了提取从右往左数的第一个 1 ，而这里所使用的思路是向高位的 1 借位
我们对其进行减 1 时，实际因为低位的 0 不够减，而向高位的 1 进行借位，被借走的 1 的 bit 位发生了翻转，而其左侧的bit位值保持不变、右侧由于原本并没有 1 ，那么我们将减 1 后的结果取反，就可以找到对应发生变化的 bit 位了

500
假设 req = 8’h1011_0100 ，(req - 1) = 8’h1011_0011
这时我们发现，我们只要把 (req - 1)取反并把他们与起来，就可以把这个 1 给挑出来
500
这样，我们就可以将 req 与 ~(req - 1)与起来，得到我们从右往左的第一个 1 了




轮询调度

概述：
轮询调度（Round Robin） 是一种考虑到公平性的一种仲裁算法。其思路是当一个 request 获得了 grant 之后，其优先级则降为最低，其他 request 则根据 grant 的情况作相应优先级的调整，也就是每个 request 的优先级都是不固定的，这样，所有的模块都有最高优先级的时候

举例说明

Cycle Request Priority Grant
0 0110 3210 0010
1 0111 1032 0100
2 0011 0321 0001
3 0010 2103 0010
4 0010 1032 0010
优先级：0 > 1 > 2 > 3
  • 在 Cycle 0 时刻，Req[2] 和 Req[1] 都发起了请求。此时 Req[0] 的优先级是最高的，但是他并没有发起请求，因此我们查看下一级的优先级 Req[1]，因为 Req[1] 发起了请求，故 Req[1] 获得了 Grant
  • 在 Cycle 1 时刻，Req[2]、Req[1]、Req[0]都发起了请求。由于上一次 Req[0] 获得了 Grant，因此在本次仲裁中，Req[0]的优先级降到最低，其左边的bit位优先级最高，然后依次降低。根据此时的优先级顺序来看，Req[2]发起了请求并且其优先级最高，故 Req[2] 获得Grant
  • 在 Cycle 2 时刻，Req[1]、Req[0]都发起了请求。同理可知，Req[2] 的优先级降到最低，根据优先级顺序和发起请求判断，Req[0] 获得 Grant
  • 在 Cycle 3 时刻，Req[1]发起了请求。同理可知，Req[0] 的优先级降到最低，根据优先级顺序和发起请求判断，Req[1] 获得 Grant
  • 在 Cycle 4 时刻，Req[1]发起了请求。同理可知，Req[1] 的优先级降到最低，但是按照优先级顺序查看下来，其他bit位都没有发起请求，因此最后还是轮到了 Req[1] 获得 Grant

逻辑实现：
首先，该算法的优先级是根据上一次获得的 Grant 不断进行调整的，规则是上一次获得 Grant 的左侧 bit 位将获得最高优先级。这里的设计思路是在固定优先级的基础上，添加掩码操作

即根据上次的 Grant 结果，mask 上次的 Grant 结果及右侧 bit，只对左侧的 bit 位找从右往左数的第一个 1 。若上一次的 Grant 是 Req 的最高 bit 位，则不进行掩码操作，按照正常的固定优先级找到从右往左的第一个 1

Info
 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
module round_robin_arbiter #(
    parameter                               N   =   4
)(
    input   wire                            clk             ,
    input   wire                            rst             ,
    input   wire    [N-1:0]                 req             ,
    output  wire    [N-1:0]                 gnt
);

//------------------------- Signal -------------------------
wire    [N-1:0]                             req_mask        ;
wire    [N-1:0]                             mask_pri        ;
wire    [N-1:0]                             unmask_pri      ;
reg     [N-1:0]                             pri_reg         ;

//------------------------ Process -------------------------
assign req_mask = req & pri_reg;
assign mask_pri[0]       = 1'b0;
assign mask_pri[N-1:1]   = mask_pri[N-2:0] | req_mask[N-2:0];
assign unmask_pri[0]     = 1'b0;
assign unmask_pri[N-1:1] = unmask_pri[N-2:0] | req[N-2:0];
assign gnt = (|req_mask == 1'b1) ? (req_mask & ~mask_pri):(req & ~unmask_pri);

always @(posedge clk) begin
    if(rst == 1'b1)            pri_reg <= {N{1'b1}};
    else if(|req_mask == 1'b1) pri_reg <= mask_pri;
    else                       pri_reg <= unmask_pri;
end 

endmodule




并行前缀轮询

概述：
并行前缀轮询调度（Parallel Prefix Round Robin）是在轮询调度（Round Robin）的基础上进行优化。把超前进位加法器（carry lookahead adder）的设计思路套用在仲裁器上。相比轮询调度，其功耗更低、逻辑级数更少

举例说明

同轮询调度，此处省略

原理详解：
RR仲裁器的计算公式如下
Gi=Ri∗(Pi+Ci−1)G_i = R_i * (P_i + C_{i-1})
Ci=R~i∗(Pi+Ci−1)C_i = \tilde{R}_i * (P_i + C_{i-1})

Info

  • P：Priority（优先级）
  • R：Request（请求）
  • C：Priority transfer carry（传优先级给下一位）
  • G：Grant（许可）

这里再重新定义一个 X
Xi=Pi+Ci−1X_i = P_i + C_{i-1}

我们把 X 代入 GiG_i 和 CiC_i 中，并把 CiC_i 代入 XiX_i ，那么这里的表达式将变成
Gi=Ri∗XiG_i = R_i * X_i
Ci=R~i∗XiC_i = \tilde{R}_i * X_i
Xi=Pi+R~i−1∗Xi−1X_i = P_i + \tilde{R}_{i-1} * X_{i-1}

可以看出，我们要计算对应第 i bit 的 Grant ，只需要把 XiX_i 计算出来即可
接下来我们看一下超前进位加法器（carry lookahead adder）是怎么做的

超前进位加法器的公式如下
Gi=ai∗biG_i = a_i * b_i
Pi=ai⊕biP_i = a_i \oplus b_i
Ci=Gi+Pi∗Ci−1C_i = G_i + P_i * C_{i-1}
Si=Pi⊕CiS_i = P_i \oplus C_i

Info

  • a：加数
  • b：被加数
  • G：Generate（进位产生信号）
  • P：Propagate（进位传递信号）
  • C：Carry（进位）
  • S：Summary（总和）

我们把 CiC_i 展开，得到
Ci=Gi+Pi∗Ci−1C_i = G_i + P_i * C_{i-1}
    =Gi+Pi∗Gi−1+Pi∗Pi−1∗Ci−2\ \ \ \ = G_i + P_i * G_{i-1} + P_i * P_{i-1} * C_{i-2}

为了表达简单，Brent–Kung将这个表达式定义一种运算符（我们只需要关注这里有一个新的运算符）
(Gi,Pi)∘(Gi−1,Pi−1)=(Gi+Pi∗Gi−1,Pi∗Pi−1)(G_i,P_i) \circ (G_{i-1},P_{i-1}) = (G_i + P_i * G_{i-1},P_i * P_{i-1})

那么，我们把 CiC_i 完整展开，我们要计算 Ci=A+B∗Ci−1C_i = A+B *C_{i-1} ，实际上就是按照公式（1）算出来的表达式左侧
    (Ai,Bi)∘(Ai−1,Bi−1)...∘(A1,B1)∘(A0,B0)\ \ \ \ (A_i,B_i) \circ (A_{i-1},B_{i-1}) ... \circ (A_1,B_1) \circ (A_0,B_0)
=(Ai+Bi∗Ai−1+Bi∗Bi−1∗Ai−2...Bi∗Bi−1...B1∗A0,Bi∗Bi−1...∗B1∗B0)= (A_{i}+B_{i}*A_{i-1}+B_{i}*B_{i-1}*A_{i-2}...B_{i}*B_{i-1}...B_1*A_0,B_{i}*B_{i-1}...*B_1*B_0) （1）

对比发现，超前进位加法器的 CiC_i 的表达式跟我们的 XiX_i 很像
Ci=Gi+Pi∗Ci−1C_i = G_i + P_i * C_{i-1}
Xi=Pi+R~i−1∗Xi−1X_i = P_i + \tilde{R}_{i-1} * X_{i-1}

PiP_i 相当于超前进位加法器的 GiG_i 、R~i−1\tilde{R}_{i-1}相当于超前进位加法器的 PiP_i
所以，对于仲裁器而言，我们有
    (Pi,R~i−1)∘(Pi−1,R~i−2)...∘(P1,R~0)∘(P0,R~−1)\ \ \ \ (P_i,\tilde{R}_{i-1}) \circ (P_{i-1},\tilde{R}_{i-2}) ... \circ (P_1,\tilde{R}_0) \circ (P_0,\tilde{R}_{-1})
=(Pi+R~i−1∗Pi−1+R~i−1∗R~i−2∗Pi−2+...R~i−1∗R~i−2∗...R~0∗P0,R~i−1∗R~i−2...∗R~0∗R~−1)= (P_i+\tilde{R}_{i-1}*P_{i-1}+\tilde{R}_{i-1}*\tilde{R}_{i-2}*P_{i-2}+...\tilde{R}_{i-1}*\tilde{R}_{i-2}*...\tilde{R}_0*P_0,\tilde{R}_{i-1}*\tilde{R}_{i-2}...*\tilde{R}_0*\tilde{R}_{-1})

这里对表达式的左、右侧重新定义了一下
PGi:0=Pi+R~i−1∗Pi−1+R~i−1∗R~i−2∗Pi−2+...R~i−1∗R~i−2∗...R~0∗P0PG_{i:0} = P_i+\tilde{R}_{i-1}*P_{i-1}+\tilde{R}_{i-1}*\tilde{R}_{i-2}*P_{i-2}+...\tilde{R}_{i-1}*\tilde{R}_{i-2}*...\tilde{R}_0*P_0
PPi:0=R~i−1∗R~i−2...∗R~0∗R~−1PP_{i:0} = \tilde{R}_{i-1}*\tilde{R}_{i-2}...*\tilde{R}_0*\tilde{R}_{-1}

那么我们以一个4bit的仲裁器举例
X3=P3+R~2∗P2+R~2∗R~1∗P1+R~2∗R~1∗R~0∗P0X_3 = P_3 + \tilde{R}_2 * P_2 + \tilde{R}_2 * \tilde{R}_1 * P_1 + \tilde{R}_2 * \tilde{R}_1 * \tilde{R}_0 * P_0
X2=P2+R~1∗P1+R~1∗R~0∗P0+R~1∗R~0∗R~3∗P3X_2 = P_2 + \tilde{R}_1 * P_1 + \tilde{R}_1 * \tilde{R}_0 * P_0 + \tilde{R}_1 * \tilde{R}_0 * \tilde{R}_3 * P_3
X1=P1+R~0∗P0+R~0∗R~3∗P3+R~0∗R~3∗R~2∗P2X_1 = P_1 + \tilde{R}_0 * P_0 + \tilde{R}_0 * \tilde{R}_3 * P_3 + \tilde{R}_0 * \tilde{R}_3 * \tilde{R}_2 * P_2
X0=P0+R~3∗P3+R~3∗R~2∗P2+R~3∗R~2∗R~1∗P1X_0 = P_0 + \tilde{R}_3 * P_3 + \tilde{R}_3 * \tilde{R}_2 * P_2 + \tilde{R}_3 * \tilde{R}_2 * \tilde{R}_1 * P_1

我们把运算符套用在上面，得到下图以及下方电路
X3=(P3,R~2)∘(P2,R~1)∘(P1,R~0)∘(P0,R~3)X_3 = (P_3,\tilde{R}_2) \circ (P_2,\tilde{R}_1) \circ (P_1,\tilde{R}_0) \circ (P_0,\tilde{R}_3)
X2=(P2,R~1)∘(P1,R~0)∘(P0,R~3)∘(P3,R~2)X_2 = (P_2,\tilde{R}_1) \circ (P_1,\tilde{R}_0) \circ (P_0,\tilde{R}_3) \circ (P_3,\tilde{R}_2)
X1=(P1,R~0)∘(P0,R~3)∘(P3,R~2)∘(P2,R~1)X_1 = (P_1,\tilde{R}_0) \circ (P_0,\tilde{R}_3) \circ (P_3,\tilde{R}_2) \circ (P_2,\tilde{R}_1)
X0=(P0,R~3)∘(P3,R~2)∘(P2,R~1)∘(P1,R~0)X_0 = (P_0,\tilde{R}_3) \circ (P_3,\tilde{R}_2) \circ (P_2,\tilde{R}_1) \circ (P_1,\tilde{R}_0)

300

下图的每个黑点对应的就是我们上述定义的运算符，而灰点则只取了运算符的左侧式子（PGi:0PG_{i:0}），最终得到类似下方的电路
300

逻辑代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
module fast_arbiter #(
    parameter                           N           =   12
)(
    input   wire                        clk                 ,
    input   wire                        rst                 ,
    input   wire    [N-1:0]             req                 ,
    output  wire    [N-1:0]             gnt
);

//------------------------- Funtion -------------------------
function PG (input pri ,req ,pri_next);
    PG = pri | (req & pri_next);
endfunction

function PP (input req ,req_next);
    PP = req & req_next;
endfunction

localparam LAYER = $clog2(N);

//------------------------- Signal --------------------------
wire    [N  -1:0]                       pg [LAYER-1:0]      ;
wire    [N  -1:0]                       pp [LAYER-1:0]      ;
reg     [N  -1:0]                       pri_reg             ;

wire    [N*2-1:0]                       pri_temp [LAYER:0]  ;
wire    [N*2-1:0]                       req_temp [LAYER:0]  ;
genvar                                  i,j                 ;

//------------------------- Process -------------------------
generate for (i=0;i<LAYER;i=i+1) begin
    if(i==0) begin 
        assign pri_temp[i] = {2{pri_reg}}; 
        assign req_temp[i] = {2{~req   }}; 
    end else begin 
        assign pri_temp[i] = {2{pg[i-1]}}; 
        assign req_temp[i] = {2{pp[i-1]}}; 
    end 

    for (j=0;j<N;j=j+1) begin
        if(i==0) begin 
            assign pg[i][j] = PG(pri_temp[i][N+(j  )],req_temp[i][N+(j-1)],pri_temp[i][N+(j-1)]);
            assign pp[i][j] = PP(                     req_temp[i][N+(j-1)],req_temp[i][N+(j-2)]);
        end else if((i == N-1) && (N != (1 << LAYER))) begin
            assign pg[i][j] = PG(pri_temp[i][N+(j  )],req_temp[i][N+(j  )],pri_temp[i-1][N+(j-(1<<i))]);
            assign pp[i][j] = PP(                     req_temp[i][N+(j  )],req_temp[i-1][N+(j-(1<<i))]);
        end else begin
            assign pg[i][j] = PG(pri_temp[i][N+(j  )],req_temp[i][N+(j  )],pri_temp[i][N+(j-(1<<i))]);
            assign pp[i][j] = PP(                     req_temp[i][N+(j  )],req_temp[i][N+(j-(1<<i))]);
        end 
    end 
end 
endgenerate

assign gnt = req & pg[LAYER-1];

always @(posedge clk) begin
    if(rst == 1'b1)       pri_reg <= {{N-1{1'b0}},1'b1};
    else if(|gnt == 1'b1) pri_reg <= {gnt[N-2:0],gnt[N-1]};
    else;
end

endmodule




参考文档

  1. 数字电路设计之仲裁器 Arbiter （一）
  2. 数字电路设计之仲裁器 Arbiter （二）
  3. 数字电路设计之仲裁器 Arbiter （三）
  4. Fast Arbiters for On-Chip Network Switches