Round-robin and priority arbiters

Fixed priority: small, and unfair under load

An arbiter picks one of several requesters in each cycle and tells it so with a grant. Here the grant is one-hot: one bit per requester, at most one bit set. A transfer happens at an edge where a grant is set and the shared resource is ready.

A fixed-priority arbiter grants the lowest-numbered request. It is a priority chain: test request 0, then 1, then 2, and the first one set wins. It needs no state and only 5 cells and 2 levels of logic on this flow.

Its only promise is order. If requester 0 asks in every cycle, nobody else is ever served. That is starvation: a requester that keeps asking and never gets a transfer.

Round robin: a pointer and two chains

A round-robin arbiter remembers who is first in line in a small register, the pointer. It grants the first request at or after the pointer, wrapping round to requester 0. After a transfer, the pointer moves to the requester just after the winner.

// arb4: one grant per cycle among four requesters, in round-robin order.
// A transfer happens at an edge where grant is not 0000 and ready is 1.
module arb4 (
  input  logic       clk,
  input  logic       rst_n,      // active-low, asynchronous
  input  logic [3:0] req,        // req[i] = 1: requester i has a transfer to make
  input  logic       ready,      // 1 when the resource takes the granted transfer
  output logic [3:0] grant       // one-hot, or 0000 when nobody asks
);
  logic [1:0] ptr_q;             // the requester first in line

  // A priority chain: the lowest set bit of v wins.
  function automatic logic [3:0] first(input logic [3:0] v);
    casez (v)
      4'b???1: return 4'b0001;
      4'b??10: return 4'b0010;
      4'b?100: return 4'b0100;
      4'b1000: return 4'b1000;
      default: return 4'b0000;
    endcase
  endfunction

  logic [3:0] upper;             // the requests at or after the pointer
  always_comb begin
    upper = req & (4'b1111 << ptr_q);
    if (upper != 4'b0000) grant = first(upper);   // chain 1: from the pointer up
    else                  grant = first(req);     // chain 2: wrap round to requester 0
  end

  logic [1:0] win;               // the number of the granted requester
  assign win = {grant[3] | grant[2], grant[3] | grant[1]};

  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n)                          ptr_q <= 2'd0;
    else if (grant != 4'b0000 && ready)  ptr_q <= win + 2'd1;   // taken: the next one is first in line
    else if (grant != 4'b0000)           ptr_q <= win;          // not taken: the winner stays first
endmodule

Move the pointer only on a transfer

Fairness is counted in transfers, never in grants. A grant that is offered but not taken has served nobody. Watch what happens when the pointer moves on every grant instead.

else if (grant != 4'b0000)
  ptr_q <= win + 2'd1;

else if (grant != 4'b0000 && ready)
  ptr_q <= win + 2'd1;
else if (grant != 4'b0000)
  ptr_q <= win;

The second rule is about the stalled grant itself. A grant drives the select of the mux that carries the winner's data to the resource. Once that data is offered, it must stay until it is taken. AXI-Stream states it for its own valid: once asserted, it stays asserted with the same data until the handshake.

Part 2 of the bench tests this. Requester 3 asks alone and is granted, but ready is 0. In the next cycle requester 2 starts asking, and it sits between the pointer and the winner.

What fairness costs

Fairness costs state and a second chain: 32 cells against 5, and 9 levels of logic against 2. The last row keeps the same rules in a different shape and costs 24 cells and 5 levels more. Two ways of writing the same behaviour can differ that much, so measure both.

The lab

Run the lab as shipped: requester 0 makes all 8 transfers in part 1, and the grant moves once in part 2. Lint warns that clk, rst_n and ready are unused, which is true of fixed priority. Paste the round-robin module above over it and run again: 2, 2, 2, 2, and no grant moves. Then try the left-hand pointer line of the compare block and read the counts.

Try it

Each line is one cycle, named after the edge that starts it; "transfer" means the granted requester transfers at the next edge. In part 1 requester 0 wins every cycle. In part 2 requester 2 arrives at e20 and takes the grant from requester 3 in the middle of its stall.

With the round-robin module the grant in part 1 runs 0001, 0001, 0010, 0010, 0100, 0100, 1000, 1000 and repeats. The summary reads part 1 transfers: 2 2 2 2, part 1 longest wait: 7 cycles, 3 transfers to others and grant moved during a stall: 0. Synthesize reports 32 cells, 2 flops and 9 levels of logic.

`timescale 1ns/1ps
module tb;
  logic clk = 0;
  always #5 clk = ~clk;                   // rising edges at 5, 15, 25, ...
  logic rst_n = 1;                        // falls at 1 ns: a real edge, so an asynchronous reset acts before any clock
  int edge_n = -1;
  always @(posedge clk) edge_n = edge_n + 1;
  logic [3:0] req = 4'b0000, pending = 4'b0000;
  logic       ready = 1'b0;
  logic [3:0] grant;
  int got[4];                            // part 1: transfers per requester
  int wait_c[4], wait_g[4];              // cycles waited, and transfers to the others meanwhile
  int longest_c = 0, longest_g = 0, moved = 0;
  logic [3:0] stalled = 4'b0000;         // last cycle's grant, if it was not taken
  arb4 dut (.clk(clk), .rst_n(rst_n), .req(req), .ready(ready), .grant(grant));
  // Advance to the next rising edge, wait for the design to settle, then print one line.
  task automatic tick();
    @(posedge clk); #1;
    if (edge_n >= 2) begin
      if (edge_n <= 17) begin                // part 1
        req = 4'b1111; ready = (edge_n % 2 == 1);
      end else begin                         // part 2: each requester asks until its transfer
        if (edge_n == 19) pending[3] = 1'b1;
        if (edge_n == 20) pending[2] = 1'b1;
        req = pending; ready = (edge_n == 21 || edge_n == 23);
      end
      #1;
      if (stalled != 4'b0000 && (req & stalled) != 4'b0000 && grant != stalled) moved++;
      if (edge_n <= 17)
        for (int i = 0; i < 4; i++)
          if (grant[i] && ready) begin got[i]++; wait_c[i] = 0; wait_g[i] = 0; end
          else if (req[i]) begin
            wait_c[i]++; if (ready && grant != 4'b0000) wait_g[i]++;
            if (wait_c[i] > longest_c) longest_c = wait_c[i];
            if (wait_g[i] > longest_g) longest_g = wait_g[i];
          end
      stalled = ready ? 4'b0000 : grant;
      if (edge_n > 17 && ready) pending = pending & ~grant;
      if (ready && grant != 4'b0000) $display("e%0d req=%b ready=%b grant=%b  transfer", edge_n, req, ready, grant);
      else                           $display("e%0d req=%b ready=%b grant=%b", edge_n, req, ready, grant);
    end
  endtask
  initial begin
    #1 rst_n = 0; tick(); tick(); rst_n = 1;   // asserted at 1 ns, edges 0 and 1 in reset, released 1 ns after edge 1
    repeat (23) tick();
    $display("part 1 transfers: %0d %0d %0d %0d", got[0], got[1], got[2], got[3]);
    $display("part 1 longest wait: %0d cycles, %0d transfers to others", longest_c, longest_g);
    $display("grant moved during a stall: %0d", moved);
    $finish(0);                             // quiet: no "$finish called" line
  end
endmodule

Check yourself

// arb4: one grant per cycle among four requesters, in round-robin order.
// A transfer happens at an edge where grant is not 0000 and ready is 1.
module arb4 (
  input  logic       clk,
  input  logic       rst_n,      // active-low, asynchronous
  input  logic [3:0] req,        // req[i] = 1: requester i has a transfer to make
  input  logic       ready,      // 1 when the resource takes the granted transfer
  output logic [3:0] grant       // one-hot, or 0000 when nobody asks
);
  logic [1:0] ptr_q;             // the requester first in line

  // A priority chain: the lowest set bit of v wins.
  function automatic logic [3:0] first(input logic [3:0] v);
    casez (v)
      4'b???1: return 4'b0001;
      4'b??10: return 4'b0010;
      4'b?100: return 4'b0100;
      4'b1000: return 4'b1000;
      default: return 4'b0000;
    endcase
  endfunction

  logic [3:0] upper;             // the requests at or after the pointer
  always_comb begin
    upper = req & (4'b1111 << ptr_q);
    if (upper != 4'b0000) grant = first(upper);   // chain 1: from the pointer up
    else                  grant = first(req);     // chain 2: wrap round to requester 0
  end

  logic [1:0] win;               // the number of the granted requester
  assign win = {grant[3] | grant[2], grant[3] | grant[1]};

  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n)                          ptr_q <= 2'd0;
    else if (grant != 4'b0000 && ready)  ptr_q <= win + 2'd1;   // taken: the next one is first in line
    else if (grant != 4'b0000)           ptr_q <= win;          // not taken: the winner stays first
endmodule

`timescale 1ns/1ps
module tb;
  logic clk = 0;
  always #5 clk = ~clk;                   // rising edges at 5, 15, 25, ...
  logic rst_n = 1;                        // falls at 1 ns: a real edge, so an asynchronous reset acts before any clock
  int edge_n = -1;
  always @(posedge clk) edge_n = edge_n + 1;
  logic [3:0] req = 4'b0000;
  logic       ready = 1'b1;
  logic [3:0] grant;
  string s = "grants:";
  arb4 dut (.clk(clk), .rst_n(rst_n), .req(req), .ready(ready), .grant(grant));
  // Advance to the next rising edge, wait for the design to settle, then print one line.
  task automatic tick();
    @(posedge clk); #1;
    if (edge_n >= 2) begin
      req = 4'b1111; #1;
      s = {s, $sformatf(" %0d", grant[1] ? 1 : grant[2] ? 2 : grant[3] ? 3 : 0)};
    end
  endtask
  initial begin
    #1 rst_n = 0; tick(); tick(); rst_n = 1;   // asserted at 1 ns, edges 0 and 1 in reset, released 1 ns after edge 1
    repeat (5) tick();
    $display("%s", s);
    $finish(0);                             // quiet: no "$finish called" line
  end
endmodule

ptr_q <= (win == 2'd3) ? 2'd0 : win + 2'd1;

ptr_q <= 2'((win + 3'd1) % 3'd4);

ptr_q <= win + 2'd1;

ptr_q <= (win == 2'd3) ? 2'd3 : win + 2'd1;