See it move
The idea
When several requesters want one resource, like a bus, memory port or multiplier, an arbiter decides who gets it. Its output is a grant: at most one requester wins per cycle.
Fixed priority
The lowest-numbered active request always wins. It's small and fast, and there is a neat trick for it:
assign grant = req & (~req + 1'b1);This isolates the lowest set bit. For req = 01100, ~req + 1 = 10100, and the AND gives 00100.
The drawback is starvation: a busy high-priority requester can lock out everyone else forever.
Round robin
After granting a requester, give it the lowest priority for the next round. Everyone gets a turn, and no one waits for more than N-1 others.
module rr_arb #(parameter N = 4) (
input clk, rst_n,
input [N-1:0] req,
output [N-1:0] grant
);
reg [N-1:0] mask;
wire [N-1:0] masked = req & mask;
wire [N-1:0] use_req = (|masked) ? masked : req;
assign grant = use_req & (~use_req + 1'b1);
always_ff @(posedge clk or negedge rst_n)
if (!rst_n) mask <= '1;
else if (|grant) mask <= ~(grant | (grant - 1'b1));
endmodulemask removes the winner and everything below it for the next round. If no masked request remains, then the design wraps round to the full set.
Other schemes
- Weighted round robin gives some requesters more turns, while still guaranteeing service.
- Least recently granted is fairer in odd traffic, but needs more state.
- Matrix arbiters remember pairwise priorities and can be fast at small sizes.
Design points
A multi-cycle transaction may need to keep its grant until it finishes. Add a busy hold, so that the arbiter doesn't move mid-burst. Think too about paths: a combinational request-to-grant path can become critical, so consider registering outputs.
Common mistake
Choosing round robin without measuring the traffic. If one source must meet a hard deadline, like a display refresh, then it needs priority. Fairness isn't always what you want. Run the animation above: with all requests on, fixed priority serves R0 only, whereas round robin gives each an equal share.
Key ideas
- Fixed priority is simple but can starve requesters.
- Round-robin rotates priority after each grant.
- Grants should be one-hot.
Your exercise
Find the bug
This code has one deliberate bug. Read the symptom, then click the line you think is wrong.
The fix
else if (|grant) mask <= ~(grant | (grant - 1'b1));
Why it failed
~grant removes only the last winner, so lower requesters are still eligible, and the lowest one wins again. R0 and R1 just take turns. The mask has to remove the winner and everything below it, leaving only higher requesters for the next round.
Interview questions
coreIsolating lowest set bit?
req & (~req + 1), or req & -req, is a neat trick for fixed priority.
basicUsing grant = req & (~req + 1), what is the grant for req = 8'b1011_0000?
~req is 0100_1111. Adding 1 turns the low ones to zero as the carry runs through them, giving 0101_0000. ANDing with req leaves only the bit that both share: 0001_0000. That is bit 4, the lowest set bit of req, so requester 4 wins.
basicWhat is starvation in a fixed-priority arbiter?
In fixed priority, the lowest-numbered active requester always wins. If a high-priority requester asks on every cycle, it wins every cycle, and lower-priority requesters never get a grant. The arbiter still obeys the rules, one-hot and only to requesters that ask, but service is not guaranteed. Round robin fixes this by rotating priority after each grant.
coreIn the round-robin arbiter, the mask is updated to ~(grant | (grant - 1)). If requester 2 of 4 was just granted and all four ask next cycle, what is the mask and who wins?
grant is 0100, grant - 1 is 0011, and OR gives 0111, the winner and everything below it. Inverting gives a mask of 1000. Masked requests are 1111 & 1000 = 1000, so requester 3 wins. On the cycle after that, the mask is 0000, no masked request remains, and the arbiter falls back to the full set, so requester 0 wins.
coreThis round-robin arbiter updates its mask with ~grant instead. With all four requesting, what is the grant pattern?
always @(posedge clk or negedge rst_n)
if (!rst_n) mask <= {N{1'b1}};
else if (|grant) mask <= ~grant;After requester 1 wins, the mask is 1101, which still includes requester 0. The picker always chooses the lowest set bit, so requester 0 wins next, then requester 1, and so on. Over 40 cycles, requesters 0 and 1 get 20 grants each, and 2 and 3 get none. The mask must remove the winner and everything below it, so only higher requesters are eligible next.
coreAn 8-way round-robin arbiter grants a resource that each winner holds for 4 cycles. How long can a requester wait, at worst?
Round robin guarantees that a waiting requester is served after at most the other N - 1 requesters. Each of the 7 others can hold the resource for 4 cycles, so the wait is up to about 7 x 4 = 28 cycles, plus any arbitration latency. That bound is what you compare with the requester's deadline. Fixed priority has no such bound.
coreA winner needs the shared bus for a multi-cycle burst. How do you stop the arbiter from moving the grant in the middle?
Add a busy or lock state: once a grant is given, hold it until the requester signals the end of its transaction, for example with a last flag. While busy, the arbiter ignores other requests and does not update its mask. When the burst ends, it arbitrates again with the mask set by that winner. Without this, grants could switch mid-burst and data from different requesters could be interleaved.
advancedFor a 32-way arbiter at a high clock rate, the request-to-grant path fails timing. What would you consider?
The lowest-set-bit trick is effectively a carry chain across all 32 bits, and the masked and unmasked paths add muxing on top. Options include registering the grant so the path ends at a flop, at the cost of a cycle of latency. You can also build the arbiter as a tree of smaller arbiters, or compute the masked and unmasked picks in parallel and select at the end. Synthesis may use a faster adder structure for the +1, but it is better to plan the structure than to rely on that.
advancedWhat happens if the round-robin mask is updated every cycle, even when no grant is given?
always @(posedge clk or negedge rst_n)
if (!rst_n) mask <= {N{1'b1}};
else mask <= ~(grant | (grant - 1'b1));With grant = 0, grant - 1 is all ones, so the new mask becomes ~(0 | 1111) = 0000. On the next request, the masked set is empty, so the arbiter falls back to the full set and requester 0 wins. Any idle cycle therefore resets the rotation to requester 0, which weakens fairness after quiet periods. Updating the mask only when |grant is true keeps the rotation position across idle cycles.