verilog实现仲裁器设计_verilog仲裁器

一、仲裁器概述

        在设计仲裁器之前我们首先要弄清楚什么是仲裁器？仲裁器在FPGA中的应用非常的广泛，其本质就是当存在两个或两个以上模块需要占用同一块资源时，对资源此时刻的最终归属权做出判决的角色。举几个简单的例子，在课堂上，老师提出了一个问题，底下多个同学举手，老师最终选择了其中一名同学来回答这个问题，在这个过程中，回答问题的机会就是这个大家同时希望占据的资源，举手的同学们就是前面提到的两个或两个以上的模块，老师就扮演了一个仲裁器的角色。再比如，大家路过信号灯路口，四个方向的车都希望通过路口，只有通过红路灯的合理调度才能避免交通事故的发生，这个过程中，车就是我们的两个及以上模块，道路就是大家同时希望占据的资源，信号灯扮演了仲裁器的角色。

        仲裁器最重要的特点就是只能让一个模块获得访问许可， 以避免混乱的发生，例如课堂上老师一次只会选择一个同学来回答问题，不然谁也听不清别人讲的是什么。由此可见，仲裁器是一种可以避免资源随意访问，实现有序访问的模块。在数字电路中，总线仲裁是一个常见的例子，比如多个master要占用总线来去写数据，那么需要仲裁器来许可哪个master来占用总线。

二、仲裁的优先级

        既然是仲裁，就应该由一个固定的标准，模糊的标准定义只会使得模块的运行效率低下，经过前人大量的实践，得出了两种非常经典的仲裁器设计：固定优先级仲裁和轮询调度仲裁。

1、固定优先级仲裁器

        这是我们最简单的一种仲裁器设计思路，固定优先级，顾名思义就是优先级是固定的，当发生竞争时，高优先级的模块永远可以率先获得访问权限。但是这样做的弊端就是无法保证公平性，但是不可否认的是这确实是一种简单且实用的仲裁器设计思路。

        回到仲裁器设计本身，我们在进行模块设计的过程中，首先就是要明确它的输入，输出和实现的具体功能。假设我们有N个模块同时发出访问请求，在这里我们的输入首先就是各个不同用户的访问请求[N-1:0] req，输出有最终获得访问权限的用户编号[N-1:0] grant（grant为高则代表对应的输入获得仿真请求），功能就是根据用户的优先级给出最后最终的访问结果，根据功能来看，我们的输入还需增加一个用户的优先级排序，否则仲裁器就没有一个合理的判断依据了，不过为了简单起见，我们不妨直接设定req的低位优先级高于高位。明确了模块的功能和输入输出，我们就可以进行端口及输入输出的设计了。

module fixed_prio_arb #(
    parameter req_number = 16       //请求访问的模块数量，这里设置为16，这样写是便于代码的维护
)(
    input [req_number-1:0]  req,    //访问输入，代表有req_number-1个输入，优先级从低到高
    
    output [reg_number-1:0]  grant  //最终的访问许可输出，grant对应位高则获得访问许可
);

        接下来我们进行功能分析，本质上我们就是要找出req中从低位到高位第一个出现的1，那么我们给req减去1会得到什么？假设req的第i位是1，第0到第i-1位都是0，那么减去1之后我们知道低位不够减，得要向高位借位，直到哪一位可以借到呢？就是第一次出现1的位，即从第i位借位，第0到i-1位都变成了1，而第i位变为了0，更高位不变。然后我们再给减1之后的结果取反，然后把结果再和req本身按位与，可以得出，只有第i位在取反之后又变成了1，而其余位都是和req本身相反的，按位与之后是0，这样就提取出来了第一个为1的那一位，也就是我们需要的grant。再考虑一下特殊情况req全0，很明显，按位与之后grant依然都是全0，没有任何问题。

//------------------------------<固定优先级仲裁器设计>-----------------------------
module fixed_prio_arb #(
    parameter req_number = 16       //请求访问的模块数量，这里设置为16，这样写是便于代码的维护
)(
    input [req_number-1:0]  req,    //访问输入，代表有req_number-1个输入，优先级从高到底
    
    output [reg_number-1:0]  grant  //最终的访问许可输出，grant对应位高则获得访问许可
);
 
   assign grant = req & (~(req-1));
//  或者可以写成
// assign grant = req & (~req + 1'b1);
endmodule

       其实，减1再取反，这不是计算2的补码的算法吗？只不过我们书本上学到的给一个数求2的补码的方法是取反再加1，这里倒过来，减1再取反，本质上是一样的。这其实是2的补码的一个特性，即一个数和它的补码相与，得到的结果是一个独热码，独热码为1的那一位是这个数最低的1。所以这个仲裁器的设计方法用一句话概括：request和它的2的补码按位与。

        写到这里其实本来已经可以结束固定优先级这个部分了，但是考虑到之前的部分我们始终默认了低位的优先级高于高位，下面我们来考虑当优先级由用户给定的一种情况，我们假设用户给定了一个优先级次序[N-1:0]base，对于base这个位宽来说，要想实现给出任意优先级的情况显然还是不够的，因此我们设定base为one-hot码，base对应为1的位为优先级最高的，然后这一位向左优先级依次递减，指导最左边后回到第0位，然后向左优先级继续依次递减，直到优先级最高的那一位的右边一位。我们以4bit为例，例如base = 4'b0010;则优先级为 bit[1]>bit[2]>bit[3]>bit[0]。

        接下来我们先给出这种情况下固定优先级仲裁器的HDL设计：

//------------------------------<固定优先级仲裁器设计>-----------------------------
module fixed_prio_arb #(
    parameter NUM_REQ = 16      //请求访问的模块数量，这里设置为16，这样写是便于代码的维护
)(
    input [NUM_REQ-1:0]  req,    //访问输入，代表有NUM_REQ-1个输入
    input [NUM_REQ-1:0]  base,   //给出的优先级设定
    
    output [NUM_REQ-1:0]  grant  //最终的访问许可输出，grant对应位高则获得访问许可
);
 
wire [2*NUM_REQ-1:0] double_req = {req,req};
 
wire [2*NUM_REQ-1:0] double_gnt = double_req & ~(double_req - base);
 
assign grant = double_gnt [NUM_REQ-1:0] | double_gnt[2*NUM_REQ-1:NUM_REQ];
 
endmodule

        这个思路和前面的借位减一的思想具有一致性，里面double_req & ~(double_req-base)其实就是利用减法的借位去找出base以上第一个为1的那一位，只不过由于base值可能比req值要大，不够减，所以要扩展为{req, req}来去减。最后一步的gnt = double_gnt [NUM_REQ-1:0] | double_gnt[2*NUM_REQ-1:NUM_REQ];是因为在经过前面的操作后，那个拥有最高优先级的位会体现在double_gnt的高NUM_REQ位（当req-base不够减时）或者低NUM_REQ(当req-base够减时)。两种按位或就可以得到最终想要的gnt

2、RR轮询调度仲裁器

        之前我们就提到过，固定优先级仲裁器最大的问题就是无法保证公平性， Round Robin就是考虑到公平性的一种仲裁算法。其基本思路是，当一个requestor 得到了grant许可之后，它的优先级在接下来的仲裁中就变成了最低，也就是说每个requestor的优先级不是固定的，而是会在最高（获得了grant)之后变为最低，并且根据其他requestor的许可情况进行相应的调整。这样当有多个requestor的时候，grant可以依次给每个requestor，即使之前高优先级的requestor再次有新的request，也会等后面的requestor都grant之后再轮到它。

        第一种思路：优先级变化，而request不变，既然我们有了之前设计的给定优先级的固定优先级仲裁器，我们只要每次grant之后进行优先级更新，就可以实现我们的RR轮询调度仲裁器了。这里的优先级更新方式是grant以后，被grant的一位优先级变成最低，其他位优先级递增一级，用一个移位逻辑就可以实现了。   

module round_robin_arbiter #(
    parameter NUM_REQ = 16      //请求访问的模块数量，这里设置为16，这样写是便于代码的维护
)(
    input clk,
    input rst_n,
    input [NUM_REQ-1:0]  req,    //访问输入，代表有NUM_REQ-1个输入
    
    output [NUM_REQ-1:0]  grant  //最终的访问许可输出，grant对应位高则获得访问许可
);
 
reg [NUM_REQ-1:0] hist_q;
 
always@(posedge clk or negedge rst_n) begin
  if(!rst_n) 
    hist_q <= 1;                                          //如果复位，设置最低位优先级最高
  else
    hist_q <= {grant[NUM_REQ-2:0], grant[NUM_REQ-1]};     //grant以后，被grant的一位优先级变成最低，其他位优先级递增一级
 
end
 
fixed_prio_arb #(
  .NUM_REQ(NUM_REQ)              //请求访问的模块数量，这里设置为16，这样写是便于代码的维护
)arbiter(
    .req(req),                   //访问输入，代表有NUM_REQ-1个输入
    .base(hist_q),               //给出的优先级设定
    
    .grant(grant)                //最终的访问许可输出，grant对应位高则获得访问许可
);
endmodule

        上面这个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的思路。

module round_robin_arbiter #(
    parameter NUM_REQ = 16      //请求访问的模块数量，这里设置为16，这样写是便于代码的维护
)(
    input clk,
    input rst_n,
    input [NUM_REQ-1:0]  req,    //访问输入，代表有NUM_REQ-1个输入
    
    output [NUM_REQ-1:0] grant  //最终的访问许可输出，grant对应位高则获得访问许可
);
 
    reg   [NUM_REQ-1:0]  mask;          //设置的掩码
    wire  [NUM_REQ-1:0]  masked_req;    //与掩码按位与后的req
    reg   [NUM_REQ-1:0]  request;       //最终进入fiexd_prio_arbiter的req  
    reg   [NUM_REQ-1:0]  grant_ff;
 
//---------------------------<得到掩码后的req>---------------------------------   
assign masked_req = mask & req;    //输入的req与掩码按位与得到掩码后的req
 
//---------------------------<掩码更新>----------------------------------------
always@(posedge clk or negedge rst_n)begin
    if(!rst_n) 
        mask <= {NUM_REQ{1'b1}};                   //如果复位，掩码设置为全1
    else if(|grant_ff == 1'b0)                        //grant按位或为0，又考虑到grant最多只有一个1，即当没有任何一位获得许可时
        mask <= {NUM_REQ{1'b1}};                   //mask更新为全部有效
    else 
        mask <= grant_ff ^ mask;                      //grant为1的位，则mask对应位从1到0，grant为0的位，mask对应位不变
end
//------------------------<选择输出>-------------------------------------------
always@(*)begin
    if(|masked_req == 1'b0)
        request = req;
    else 
        request = masked_req;
end
 
//-----------------------<fixed_prio_arbiter>---------------------------------
always@(posedge clk)begin
    grant_ff = request & (~request + 1'b1);
end
assign grant = grant_ff;
endmodule

三、参考资料：

仲裁器设计（一） -- Fixed Priority Arbiter

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