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.

Requester 1 Under Two ArbitersOne column per cycle, from the lab run. Requester 0 asks in every cycle.
0123456789clkreq01110111fixed gnt01rr gnt011001100110011001both askonly 0 asks
Scroll horizontally ↔
  1. Cycle 1

    From cycle 1 both requesters ask. Fixed priority gives 01 every time: requester 1 never wins.

  2. Cycle 2

    Round robin gave 10 in cycle 1, so requester 1 won last. Now requester 0 wins.

  3. 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.

ArbiterGrants to 0Grants to 1Cycles with two grants
Fixed priority1000
Round robin640

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.

A Round-Robin Arbiter as BlocksThe requests and the last-winner register feed the grant logic. The grant goes out and also updates the register at the edge.
  • I/O
  • Control / FSM
  • Storage
  • Control
A round-robin arbiter as blocksThe requests and the last-winner register feed the grant logic. The grant goes out and also updates the register at the edge. io Requests one bit per requester control Grant logic search after the lastwinner storage Last winner the state register io Grant at most one bit where to startwinner, if any
  1. io Requestsone bit per requester
    • Grant logic
  2. storage Last winnerthe state register
    • where to start → Grant logic
  3. control Grant logicsearch after the last winner
    • Grant
    • winner, if any → Last winner
  4. io Grantat most one bit
  1. Search

    The grant logic starts after the last winner and takes the first requester that asks.

  2. Grant

    The grant is combinational: it is for this cycle. That makes the arbiter a Mealy machine.

  3. 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.

Round Robin for Two, as a State Machine
Round Robin for Two, as a State Machine00/0001/0110/1011/0100/0001/0110/1011/10L11 won lastL00 won last
  1. 1 won last · L1
    • ↓00 → L1 / 00
    • ↓01 → L0 / 01
    • ↓10 → L1 / 10
    • ↓11 → L0 / 01
  2. 0 won last · L0
    • ↓00 → L0 / 00
    • ↓01 → L0 / 01
    • ↓10 → L1 / 10
    • ↓11 → L1 / 10
StateInputNextOutput
L100L100
L101L001
L110L110
L111L001
L000L000
L001L001
L010L110
L011L110

Current state: L0 · Output: 01

Sampled input, state and output waveformStepState0L11L02L13L04L15L06L07L18L09L110L0r1—0111101111r0—1111111111g1—0101001010g0—1010110101
Scroll horizontally ↔
Sampled waveform: Moore output after each edge; Mealy output on the taken arc.
Step012345678910
Input—01111111110111111111
StateL1L0L1L0L1L0L0L1L0L1L0
Output—01100110010110011001

  1. Step 1. Reset is L1, as if requester 1 had just won. Only r0 asks, so it wins and the state becomes L0.
  2. Step 2. Both ask (11) in L0. Requester 0 won last, so requester 1 wins, and the state becomes L1.
  3. Step 5. With both asking, the grant alternates 10, 01, 10. The state is the last winner, so it alternates too.
  4. Step 6. Only r0 asks: no contest. It wins whatever the state is.

The stream is the lab's requests (r1 r0). A grant goes on the arc, so this is a Mealy machine: the grant is for this cycle.

Properties to Test

An arbiter is checked with properties, not single values. Each one is a check the bench can run in every cycle.

PropertyCheck in every cycleIn the lab
One grant at a time$onehot0(gnt)no cycle with two grants
No grant without a request(gnt & ~req) == 0holds by construction
No idle bus while someone asksreq != 0 implies gnt != 0holds by construction
Fairnessa requester that keeps asking is passed over at most N - 1 timesfixed 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
  1. 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.

  2. 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.

  3. 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.

RTLIcarus Verilog · in your browser · Lint: Verilator service · Synthesize: Yosys service
Edit the design, then Run, Lint or Synthesize
Expected: 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: 0

Original 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

ConceptWhat is starvation in an arbiter?
ConceptRequesters 0 to 3 share a round-robin arbiter. Requester 1 won last. Requesters 0 and 3 ask. Who wins?
ConceptIn a cycle with no request, what should a round-robin arbiter do with its last-winner state?
Predict the outputThe program checks the property "at most one grant" on four grant words. It counts the words that break it. Predict the exact line.
module tb;
  logic [2:0] g [0:3];
  int bad = 0;
  initial begin
    g[0] = 3'b000; g[1] = 3'b010; g[2] = 3'b110; g[3] = 3'b100;
    for (int i = 0; i < 4; i++)
      if (!$onehot0(g[i])) bad++;
    $display("%0d", bad);
  end
endmodule
ConceptWhy does a round-robin arbiter keep its fairness bound?

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.

Practice

Report a problem with this page