Four masters share one memory port. In every cycle any of them may ask for it, and only one can have it. Something must choose, every cycle, in a way that never grants two at once, never grants to someone who did not ask, and, ideally, never leaves anyone waiting for ever. That something is an arbiter, and the rule it follows is its policy.

How does an arbiter choose, and what does each policy guarantee?

The obvious answer, and why it breaks

The obvious policy is fixed priority: number the requesters and always grant the lowest number asking. It is one line of logic and it gives urgent requesters exactly what they need. It also lets a busy high-priority requester take every cycle, so lower ones may wait for ever. A policy is a choice of who waits, and fixed priority makes the same requesters wait every time.

The idea: five policies

Every arbiter, whatever its policy, must satisfy two safety rules: at most one grant per resource per cycle, and grants only to requesters that ask. Fairness, bandwidth shares and latency are what the policy adds on top.

Build it: a 4-way round-robin arbiter

This is DCLink step 7: the arbiter that will share one link among several senders. It searches for the first requester asking, starting just after the last one granted. The checker enforces the two safety rules and a bounded wait: no requester that is asking waits for more than 3 grants 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

// DCLink step 7: a 4-way round-robin arbiter. Each cycle it grants one requester:
// the first one asking, searching from the requester after the last one granted.
// Requests change over time; the checker confirms one grant at most per cycle,
// grants only to requesters that ask, and that no asking requester waits more than
// 3 grants to others (bounded wait).
module tb;
  logic clk = 0;
  always #5 clk = ~clk;
  initial begin $dumpfile("wave.vcd"); $dumpvars(0, tb); end

  int cyc = 0;
  always @(posedge clk) cyc <= cyc + 1;
  logic [3:0] req;
  always_comb begin
    case (cyc)
      1, 2, 3, 4, 5, 6: req = 4'b1111;        // everyone asks
      7, 8:             req = 4'b0101;        // only 0 and 2
      9, 10, 11:        req = 4'b1001;        // only 0 and 3
      default:          req = 4'b0000;        // cycle 0: nobody yet
    endcase
  end

  logic [1:0] last = 3;                       // so requester 0 has priority first
  logic [3:0] gnt;
  always_comb begin
    gnt = 0;
    for (int k = 1; k <= 4; k++) begin
      if (gnt == 0 && req[(last + k) % 4]) gnt[(last + k) % 4] = 1;
    end
  end
  always @(posedge clk)
    for (int i = 0; i < 4; i++) if (gnt[i]) last <= 2'(i);
  // For the waveform: who is granted this cycle (valid when gnt_vld is high)
  wire       gnt_vld = (gnt != 0);
  wire [1:0] gnt_id  = gnt[1] ? 2'd1 : gnt[2] ? 2'd2 : gnt[3] ? 2'd3 : 2'd0;

  int waits [0:3];
  initial for (int i = 0; i < 4; i++) waits[i] = 0;
  int errors = 0, grants = 0;
  always @(posedge clk) begin
    if ($countones(gnt) > 1) errors++;
    if ((gnt & ~req) != 0) errors++;
    if (gnt != 0) grants++;
    for (int i = 0; i < 4; i++) begin
      if (gnt[i] || !req[i]) waits[i] <= 0;
      else begin waits[i] <= waits[i] + 1; if (waits[i] + 1 > 3) errors++; end
    end
  end
  initial begin
    #150;
    if (errors == 0 && grants == 11) $display("PASS: 11 grants, never more than one per cycle; no requester waited more than 3 grants");
    else $display("FAIL: errors %0d grants %0d", errors, grants);
    $finish;
  end
endmodule

The pointer last is the whole of round-robin's memory: moving the search start past the most recent winner is what gives everyone a turn.

Watch it run

How to read it, slot by slot (gnt_id is meaningful where gnt_vld is high):

• Slots 0 to 5: all four requesters ask (req = f). Grants rotate 0, 1, 2, 3, 0, 1: nobody waits more than three grants.

• Slots 6 and 7: only requesters 0 and 2 ask (req = 5). The search starts after 1, so 2 wins, then 0.

• Slots 8 to 10: only 0 and 3 ask (req = 9). Grants alternate 3, 0, 3: requesters that are not asking are skipped without costing anyone a cycle.

• Slot 11: nobody asks and nothing is granted.

Try it

How real systems chose

What breaks

A DMA engine (illustrative) was given fixed top priority on a shared memory port so that its transfers would finish quickly. During long transfers it asked every cycle, and a processor's cache misses, at lower priority, stalled for tens of microseconds. Switching to round-robin with a weight for the DMA engine kept its bandwidth high and bounded the processor's wait to a few cycles.

Key takeaways

• An arbiter's policy decides who waits: fixed priority, round-robin, weighted, least recently used or oldest first.

• Round-robin searches from just after the last winner, bounding every wait to N − 1 grants.

• Every arbiter must grant at most one requester, and only one that asks.

Related topics

• Part 8 overview: Sharing and Arbitration

• RTL course: Bus Integration