Turning a priority encoder into a fair one

A priority encoder always favours bit 0. Put one in front of a shared resource, keep requester 0 busy, and requester 3 never gets a turn: four requesters asking every cycle give 0, 0, 0, 0 forever.

Round robin fixes this with one register, last_q, the index of the previous winner. The search starts just above it and wraps. Each requester still asking is served before anyone gets a second turn, so nobody waits more than N - 1 grants. The search itself is plain combinational logic built from the prio_enc of the previous lesson.

Construction (a): a mask and two priority encoders

Follow req from the left. The upper path asks who is waiting above the last winner; the lower path is the fallback when nobody is.

• Mask: {N{1'b1}} << (last + 1) sets every bit strictly above last. When last is N - 1 the shift clears everything, so the search wraps.

• Two encoders: both are the lowest-index-wins prio_enc. The masked one finds the first requester above last; the unmasked one finds the first requester overall.

• Mux: valid_m decides. If anyone above last asks, they go first; otherwise the lowest requester wins, which is the wrap-around.

• Register: last_q loads the winner only when valid is 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// snippet: construction (a), full listing under Testbench
module rr_pick_mask #(parameter int N = 4, localparam int W = (N > 1) ? $clog2(N) : 1) (
  input  logic [N-1:0] req,
  input  logic [W-1:0] last,
  output logic [W-1:0] idx,
  output logic         valid
);
  logic [N-1:0] mask, req_m;
  logic [W-1:0] idx_m, idx_u;
  logic         valid_m, valid_u;
  assign mask  = {N{1'b1}} << (last + 1);   // 1 strictly above last; all 0 when last = N-1
  assign req_m = req & mask;
  prio_enc #(.N(N)) pe_masked   (.req(req_m), .idx(idx_m), .valid(valid_m));
  prio_enc #(.N(N)) pe_unmasked (.req(req),   .idx(idx_u), .valid(valid_u));
  assign idx   = valid_m ? idx_m : idx_u;   // someone above last asks: they go first
  assign valid = valid_u;
endmodule

Requests 1101, cycle by cycle

Requesters 0, 2 and 3 ask every cycle (req = 4'b1101, bit 3 on the left). After reset last_q is 3, so requester 0 has the first turn. These rows are printed by the testbench below.

Each requester waits at most two grants, one less than the three requesters asking. That is the fairness bound the bench checks.

Construction (b): search a doubled vector

The second construction removes the mux. Write the request vector twice, {req, req}, and start the search at bit last + 1. A search that runs off the top of the lower copy carries on into the upper copy, which is the wrap-around. Folding the two halves together gives a one-hot grant.

The search uses the lowest-set-bit trick from the priority encoder lesson, shifted to a start position: dbl & ~(dbl - base) keeps the lowest set bit at or above the one-hot base. Subtracting base borrows through the zeros below the first set bit and clears that bit, so the AND with the inverse keeps only it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// snippet: construction (b), full listing under Testbench
module rr_pick_dbl #(parameter int N = 4, localparam int W = (N > 1) ? $clog2(N) : 1) (
  input  logic [N-1:0] req,
  input  logic [W-1:0] last,
  output logic [W-1:0] idx,
  output logic         valid
);
  logic [2*N-1:0] dbl, base, first;
  logic [N-1:0]   grant;
  assign dbl   = {req, req};
  assign base  = (2*N)'(1) << (last + 1);   // one-hot start position, at most bit N
  assign first = dbl & ~(dbl - base);       // lowest set bit at or above base
  assign grant = first[N-1:0] | first[2*N-1:N];
  assign valid = |req;
  always_comb begin                         // one-hot to index
    idx = '0;
    for (int i = 0; i < N; i++) if (grant[i]) idx = i[W-1:0];
  end
endmodule

A variant rotates req right by last + 1, runs one priority encoder and adds last + 1 back to the index. It is the same idea with a barrel shifter instead of a subtractor.

The pointer register

Either picker becomes an arbiter with one register. The rule is short: load the winner, and only when there was one.

1
2
3
4

// snippet: from rr_arb, full listing under Testbench
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n)     last_q <= W'(N - 1);    // so requester 0 has first turn after reset
    else if (valid) last_q <= idx;          // move only when someone was granted

This lesson stops at the combinational search and its pointer. The arbitration lesson adds what a bus needs on top: a registered grant held until the transfer is accepted, and an interactive tool for comparing fixed priority with round robin.

What each costs

Both pickers were synthesised for N = 8 to generic gates, with the hierarchy flattened, and the longest path counted in gates:

Here the mask version is smaller and shallower. The doubled search turns into a 16-bit borrow chain, and generic gates build that as a ripple. A cell library with fast adders, or an FPGA carry chain, changes the picture, so measure on your own target before choosing. For wide N, both shapes are usually rebuilt as trees: encode each half with its valid flag and combine.

Common mistakes

Testbench

The bench compares both pickers with a reference that walks from last + 1 upwards and wraps. It covers every request pattern and every last value for N = 4 and N = 8 (64 + 2048 cases), plus 4000 random N = 8 cases. Then it runs two N = 4 arbiters, one per construction, for 5000 cycles of random requests that stay up until granted. It checks that their grants agree and that no waiting requester sees more than N - 1 = 3 grants go to others.

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
64
65
66
67
68
69
70
71
72
73
74
75

module prio_enc #(parameter int N = 8) (   // N must be at least 1
  input  logic [N-1:0]          req,
  output logic [(N > 1 ? $clog2(N) : 1)-1:0] idx,
  output logic                  valid
);
  localparam int SW = (N > 1) ? $clog2(N) : 1;
  always_comb begin
    idx   = '0;
    valid = 1'b0;
    for (int i = N-1; i >= 0; i--) begin       // scan from the HIGH end so the LOWEST index wins last
      if (req[i]) begin
        idx   = i[SW-1:0];
        valid = 1'b1;
      end
    end
  end
endmodule

// (a) Mask and two priority encoders. last = index of the previous grant.
module rr_pick_mask #(parameter int N = 4, localparam int W = (N > 1) ? $clog2(N) : 1) (
  input  logic [N-1:0] req,
  input  logic [W-1:0] last,
  output logic [W-1:0] idx,
  output logic         valid
);
  logic [N-1:0] mask, req_m;
  logic [W-1:0] idx_m, idx_u;
  logic         valid_m, valid_u;
  assign mask  = {N{1'b1}} << (last + 1);   // 1 strictly above last; all 0 when last = N-1
  assign req_m = req & mask;
  prio_enc #(.N(N)) pe_masked   (.req(req_m), .idx(idx_m), .valid(valid_m));
  prio_enc #(.N(N)) pe_unmasked (.req(req),   .idx(idx_u), .valid(valid_u));
  assign idx   = valid_m ? idx_m : idx_u;   // someone above last asks: they go first
  assign valid = valid_u;
endmodule

// (b) Double width: search {req, req} from bit last+1, then fold the halves.
module rr_pick_dbl #(parameter int N = 4, localparam int W = (N > 1) ? $clog2(N) : 1) (
  input  logic [N-1:0] req,
  input  logic [W-1:0] last,
  output logic [W-1:0] idx,
  output logic         valid
);
  logic [2*N-1:0] dbl, base, first;
  logic [N-1:0]   grant;
  assign dbl   = {req, req};
  assign base  = (2*N)'(1) << (last + 1);   // one-hot start position, at most bit N
  assign first = dbl & ~(dbl - base);       // lowest set bit at or above base
  assign grant = first[N-1:0] | first[2*N-1:N];
  assign valid = |req;
  always_comb begin                         // one-hot to index
    idx = '0;
    for (int i = 0; i < N; i++) if (grant[i]) idx = i[W-1:0];
  end
endmodule

// The pointer register that makes either picker round robin.
module rr_arb #(parameter int N = 4, parameter bit DBL = 0, localparam int W = (N > 1) ? $clog2(N) : 1) (
  input  logic         clk, rst_n,
  input  logic [N-1:0] req,
  output logic [N-1:0] grant,
  output logic [W-1:0] last_q
);
  logic [W-1:0] idx;
  logic         valid;
  if (DBL) begin : g_dbl
    rr_pick_dbl  #(.N(N)) pick (.req, .last(last_q), .idx, .valid);
  end else begin : g_mask
    rr_pick_mask #(.N(N)) pick (.req, .last(last_q), .idx, .valid);
  end
  assign grant = valid ? (N'(1) << idx) : '0;
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n)     last_q <= W'(N - 1);    // so requester 0 has first turn after reset
    else if (valid) last_q <= idx;          // move only when someone was granted
endmodule

$ iverilog -g2012 -s tb_rr -o r rr.sv && vvp r
cycle 1: last=3 mask=0000 req&mask=0000 grant=0001
cycle 2: last=0 mask=1110 req&mask=1100 grant=0100
cycle 3: last=2 mask=1000 req&mask=1000 grant=1000
cycle 4: last=3 mask=0000 req&mask=0000 grant=0001
cycle 5: last=0 mask=1110 req&mask=1100 grant=0100
cases=6112 worst wait=3 grants
PASS: both pickers match the reference for every request and pointer (N=4, N=8); no requester waits more than N-1 grants

Related topics

• Bus arbitration

• Priority encoder