Arbiters
Share one resource between requesters: fixed priority, why it starves, and a round-robin arbiter whose state is the last winner.
You Will Be Able To
- Build a fixed-priority arbiter and show how it starves a requester.
- Build a round-robin arbiter as a state machine whose state is the last winner.
- State the properties every arbiter must keep: one grant, no grant without a request.
- Test fairness as a bound on how long a waiting requester can be passed over.
- Lesson
- G7.8
- Time
- 30 min
- Runs on
- Your browser
- Check
- 5 questions
A DMA engine and a CPU shared one memory bus through a fixed-priority arbiter. The DMA engine asked in every cycle. The CPU waited for ever. Here are both arbiters on one request stream.
- Cycle 1
From cycle 1 both requesters ask. Fixed priority gives 01 every time: requester 1 never wins.
- Cycle 2
Round robin gave 10 in cycle 1, so requester 1 won last. Now requester 0 wins.
- Cycle 9
Over ten cycles fixed priority grants 10 to 0 and none to 1. Round robin grants 6 and 4.
Measured: the lab below, on Icarus Verilog 12.
Fixed Priority and Starvation
An arbiter takes requests for a shared resource and gives at most one grant per cycle. A fixed-priority arbiter ranks the requesters once: the highest-ranked requester that asks wins.
Fixed priority is simple and fast. But a high-ranked requester that asks all the time locks the others out. That is starvation.
| Arbiter | Grants to 0 | Grants to 1 | Cycles with two grants |
|---|---|---|---|
| Fixed priority | 10 | 0 | 0 |
| Round robin | 6 | 4 | 0 |
Measured: the lab below, ten cycles. Requester 1 asked in 8 of them.
Round Robin: The State Is the Last Winner
A round-robin arbiter changes the order every time it grants. Its state remembers the last winner. The search for the next winner starts just after it, and wraps from the highest requester back to 0.
So the last winner is searched last. With two requesters, "after the last winner" is simply the other one.
- I/O
- Control / FSM
- Storage
- Control
- Search
The grant logic starts after the last winner and takes the first requester that asks.
- Grant
The grant is combinational: it is for this cycle. That makes the arbiter a Mealy machine.
- Remember
At the edge, the register loads the winner. With no grant it keeps its value.
Read the diagram as text
- Requests: one bit per requester
- Grant logic: search after the last winner
- Last winner: the state register
- Grant: at most one bit
- Requests → Grant logic
- Last winner → Grant logic: where to start
- Grant logic → Grant
- Grant logic → Last winner: winner, if any
A fixed-priority arbiter is the grant logic alone, with no register: its search always starts at 0.
Properties to Test
An arbiter is checked with properties, not single values. Each one is a check the bench can run in every cycle.
| Property | Check in every cycle | In the lab |
|---|---|---|
| One grant at a time | $onehot0(gnt) | no cycle with two grants |
| No grant without a request | (gnt & ~req) == 0 | holds by construction |
| No idle bus while someone asks | req != 0 implies gnt != 0 | holds by construction |
| Fairness | a requester that keeps asking is passed over at most N - 1 times | fixed priority fails it; round robin keeps it |
N is the number of requesters. The fairness bound for two requesters is 1.
Round robin keeps the bound because each grant moves the start of the search past the winner. A waiting requester gets closer to the front with every grant to someone else.
Asked in interviews
Fixed priority or round robin?
Fixed priority is cheapest and lets an urgent requester always win, but it can starve the rest. Round robin bounds the wait of every requester at N - 1 grants, at the cost of a little state.
How would you verify an arbiter?
With properties checked every cycle. At most one grant; no grant without a request; no idle cycle while someone asks. Add a bound on how long a waiting requester is passed over. Then drive streams where several requesters ask for long stretches.
What is the state of a round-robin arbiter?
The last winner, or a pointer to the requester after it. The grant logic searches from there and wraps around. The state changes only in cycles with a grant.
Try It
Each line is read mid-cycle: the requests and both grants for that cycle. The last line counts grants and cycles with two grants.
Round robin alternates while both ask. In cycle 5 only requester 0 asks, so it wins; in cycle 6 requester 1 is first again.
Change ask1 to all 1s and predict the round-robin counts. Then reset last to 0 and see who wins cycle 1.
Synthesize the design to measure its cells and inspect the mapped gates.
cycle 0 req=01 fixed=01 rr=01 cycle 1 req=11 fixed=01 rr=10 cycle 2 req=11 fixed=01 rr=01 cycle 3 req=11 fixed=01 rr=10 cycle 4 req=11 fixed=01 rr=01 cycle 5 req=01 fixed=01 rr=01 cycle 6 req=11 fixed=01 rr=10 cycle 7 req=11 fixed=01 rr=01 cycle 8 req=11 fixed=01 rr=10 cycle 9 req=11 fixed=01 rr=01 fixed: r0=10 r1=0 round robin: r0=6 r1=4 two grants at once: 0Original design · 7 cells · 1 flip-flops · 0 latches · 2 logic levels. Synthesis uses Yosys; counts depend on the toolchain.
Read included file: tb.sv
// tb.sv: the bench (read-only). Requester 0 asks in every cycle; requester 1 in most.
module tb;
logic clk = 0, rst = 1;
logic [1:0] req, gf, gr;
fixed2 f (.req(req), .gnt(gf));
rr2 r (.clk(clk), .rst(rst), .req(req), .gnt(gr));
string ask1 = "0111101111"; // requester 1, one character per cycle
int nf0 = 0, nf1 = 0, nr0 = 0, nr1 = 0, two = 0;
initial begin
#1 clk = 1; #1 clk = 0; rst = 0;
for (int c = 0; c < ask1.len(); c++) begin
req = {ask1[c] == "1", 1'b1};
#1 $display("cycle %0d req=%b fixed=%b rr=%b", c, req, gf, gr);
nf0 += gf[0]; nf1 += gf[1]; nr0 += gr[0]; nr1 += gr[1];
if (!$onehot0(gf) || !$onehot0(gr)) two++;
#1 clk = 1; #1 clk = 0;
end
$display("fixed: r0=%0d r1=%0d round robin: r0=%0d r1=%0d two grants at once: %0d", nf0, nf1, nr0, nr1, two);
end
endmodule
Check Yourself
Common Mistakes
Wrong Use fixed priority where any requester can ask in every cycle.
The top requester can then win every time. In the lab, requester 1 asked in 8 cycles and got 0 grants.
Fix Use round robin, or prove that the top requester leaves gaps.
Wrong Start the round-robin search at the last winner.
The last winner is then searched first and wins again. The arbiter becomes fixed priority with a moving label.
Fix Start at the requester after the last winner, and wrap from the highest back to 0.
Wrong Move the pointer in every cycle, granted or not.
In an idle cycle there is no winner. A pointer that moves anyway skips requesters and breaks the fairness bound.
Fix Update the last-winner state only in a cycle with a grant.
Wrong Build the grant as req ANDed with a priority mask and forget to keep only one bit.
Two requesters inside the mask both get a grant, and two masters drive the bus.
Fix Pick the first requester in search order. Test that no cycle has two grants.
Remember
- An arbiter gives at most one grant per cycle, and only to a requester that asks.
- Fixed priority is simple but starves low-ranked requesters when a high one keeps asking.
- Round robin keeps the last winner as its state and searches from the next requester, wrapping around.
- Test arbiters with properties every cycle, including a bound of N - 1 on how long a requester is passed over.