Difficulty: Medium · Puzzle 4 of 6 · Topic: FIFO, Arbitration and Credit Puzzles
A 3-requester arbiter grants one requester per cycle. The request vectors (bit order {req2, req1, req0}) over 9 cycles are 111, 111, 111, 101, 101, 010, 111, 111, 000, each held for just that cycle. The round-robin arbiter starts with the pointer on requester 2 (so requester 0 has first priority), searches from the requester after the last one granted, and moves the pointer only on a grant. Give the grant sequence for round-robin and for a fixed-priority (0 > 1 > 2) arbiter.
`timescale 1ns/1ns
module arb #(parameter bit RR = 1, parameter string NAME = "?", parameter int N = 9) (input bit clk, input bit [2:0] req);
int last = 2; // requester served last: the search starts after it
int g, c, cyc = 0;
string s = "";
always @(posedge clk) begin
g = -1;
for (int k = 1; k <= 3; k++) begin
c = RR ? (last + k) % 3 : (k - 1);
if (g < 0 && req[c]) g = c;
end
if (g >= 0) last = g; // the pointer moves only when somebody is granted
s = {s, (g < 0) ? "- " : $sformatf("%0d ", g)};
if (cyc == N-1) $display("%s grants: %s", NAME, s);
cyc++;
end
endmodule
module tb;
localparam int N = 9;
// cycle: 012345678
localparam bit [2:0] REQ [N] = '{3'b111, 3'b111, 3'b111, 3'b101, 3'b101, 3'b010, 3'b111, 3'b111, 3'b000};
bit clk = 0;
int cyc = 0;
always #5 clk = ~clk;
always @(posedge clk) cyc <= cyc + 1;
wire [2:0] req = REQ[cyc];
arb #(1, "round-robin") rr(clk, req);
arb #(0, "fixed-prio ") fx(clk, req);
initial #(10*N) $finish;
endmoduleFor round-robin the search order after 'last = L' is L+1, L+2, L (mod 3). For cycle 4 the last grant is 0, so requester 1 is checked first.
1) Round-robin: cycle 0 -> 0 (last=0); cycle 1 -> 1; cycle 2 -> 2; cycle 3 (101, last=2) -> 0.
2) Cycle 4 (101, last=0): the search order is 1, 2, 0, requester 1 is idle, so grant 2. Cycle 5 (010) -> 1. Cycle 6 (111, last=1) -> 2. Cycle 7 (111, last=2) -> 0. Cycle 8: no request, no grant, the pointer stays.
3) Fixed priority always picks the lowest request: 0 0 0 0 0 1 0 0 -.
4) Requester 2 requests in 7 of the 9 cycles but is granted 0 times with fixed priority, and 3 times with round-robin.Answer: Round-robin: 0 1 2 0 2 1 2 0 - . Fixed priority: 0 0 0 0 0 1 0 0 - , so requester 2 starves under fixed priority.
Checked by running the code in Verilator 5; the printed output supports the answer above. The same request stream through both arbiters: round-robin serves requester 2 three times, fixed priority never.
Cycle 4 is the trap: after granting 0 the search must go to 1 (idle) and then 2, so 2 wins; a design that restarts from 0 or only skips to the next INDEX without checking its request gets it wrong. The pointer must follow the last GRANTED requester. A second trap is moving the pointer in the no-request cycle 8, which would bias the next grant.
What is the worst-case wait for a requester that holds its request in an N-requester round-robin arbiter that grants one per cycle? Model answer: N-1 grants of other requesters, i.e. at most N-1 cycles before its own grant (so at most 2 here). That bound is the fairness property a checker should assert.