Round Robin

Chapter 17.1 built a policy with no memory at all. The same eligibility vector always produces the same winner, forever.

How can selection remember who was served last?

1. What Has to Be Remembered, and What Does Not

Round robin needs one register. In this implementation it is last_q, the index of the requester that received the last committed grant, and the scan starts at last_q + 1 and wraps.

With three requesters that is enough to make the policy rotate. History 0 and everyone asking: scan 1, 2, 0 — choose 1. History 1: scan 2, 0, 1 — choose 2. History 2: scan 0, 1, 2 — choose 0.

What is not remembered is as important. There is no counter of how long anyone has waited, no record of how many times a requester has lost, no notion of urgency and no ageing. The policy knows one index and nothing else, which keeps it cheap and keeps its behaviour fully predictable from a single value you can print.

Rotating is not the policy. Rotating and then scanning for an eligible requester is. Section 4 measures a policy that does the first without the second, and it hands grants to requesters that are not asking.

2. RTL — Where the History Is Told It May Move

The policy module from Chapter 17.1 updates last_q on commit_i, and commit_i comes from somewhere else. This is that somewhere else — the ownership mechanism, with the policy plugged into it.

// ─────────────────────────────────────────────────────────────────────────
// wb_owner_arb3 — OWNERSHIP for three requesters, with the selection
// policy plugged in as a separate module.
//
// ── WHY THERE ARE THREE ─────────────────────────────────────────────────
// Chapter 17.1 measured a two-master system under sustained demand from
// both masters and found ZERO contested arbitration events. That is not an
// accident of the workload, it is a property of the structure:
//
//   an arbitration event fires when the current owner negates CYC_O, and
//   the master that caused the event is, by definition, no longer asking.
//
// With two requesters that leaves at most one eligible master at every
// release, so the policy has nothing to choose between and fixed priority
// and round robin produce identical service. A contested release needs a
// third requester. Chapter 17.2 publishes the measurement that says so.
//
//   requester 0 = CPU      requester 1 = DMA      requester 2 = IO
//
// ── THE THREE QUESTIONS, KEPT APART ─────────────────────────────────────
//   ELIGIBILITY  who is asking?          {io_cyc, dma_cyc, cpu_cyc}
//   SELECTION    who gets it next?       wb_arb_policy
//   RETENTION    how long do they hold?  the owner register below
//
// ELIGIBILITY IS A LOCAL ARCHITECTURE CHOICE. This system uses each
// master's own CYC_O, which the specification describes for this case -
// "In these cases, the [CYC_O] signal requests use of a common bus from an
// arbiter" - and which RECOMMENDATION 3.05 says arbitration logic "often"
// does. There is no REQ/GNT pair in B3.
//
// ── THE ARBITRATION EVENT ───────────────────────────────────────────────
// A decision happens on exactly two kinds of clock: nobody owns the path,
// or the current owner has negated CYC_O. On every other clock the owner
// is RETAINED and the policy's output is ignored. That guard is the whole
// difference between an arbiter and a preemption defect.
//
// LOCK_O is structurally redundant under this retention rule, because an
// owner is held for the whole of its CYC_O and that is exactly what
// LOCK_O's description asks of an INTERCON. Chapter 15.4 measured the
// policy in which the lock is load-bearing; this module does not rebuild
// it, and Chapter 17.5 says so rather than implying the lock does work
// here that it does not.
//
// ── THE DEFECT ──────────────────────────────────────────────────────────
//   PREEMPT   the arbitration event fires every clock, so the policy is
//             re-evaluated during a transfer nobody has answered. This is
//             Chapter 16.3's preemption defect wearing an arbitration
//             label, and it is what "fixed priority preempts" becomes when
//             somebody builds it.
// ─────────────────────────────────────────────────────────────────────────
module wb_owner_arb3 #(
  parameter int unsigned AW      = 12,
  parameter int unsigned DW      = 32,
  parameter int unsigned SW      = DW/8,
  parameter bit          POLICY  = 1'b0,    // 0 fixed priority, 1 round robin
  parameter bit          PREEMPT = 1'b0,
  parameter bit          PTR_ON_REQUEST     = 1'b0,
  parameter bit          IGNORE_ELIGIBILITY = 1'b0
) (
  input  logic          clk_i,
  input  logic          rst_i,
  // -- requester 0: CPU --
  input  logic          m0_cyc_i, m0_stb_i, m0_lock_i, m0_we_i,
  input  logic [AW-1:0] m0_adr_i,
  input  logic [DW-1:0] m0_dat_i,
  input  logic [SW-1:0] m0_sel_i,
  output logic [DW-1:0] m0_dat_o,
  output logic          m0_ack_o, m0_err_o, m0_rty_o,
  // -- requester 1: DMA --
  input  logic          m1_cyc_i, m1_stb_i, m1_lock_i, m1_we_i,
  input  logic [AW-1:0] m1_adr_i,
  input  logic [DW-1:0] m1_dat_i,
  input  logic [SW-1:0] m1_sel_i,
  output logic [DW-1:0] m1_dat_o,
  output logic          m1_ack_o, m1_err_o, m1_rty_o,
  // -- requester 2: IO --
  input  logic          m2_cyc_i, m2_stb_i, m2_lock_i, m2_we_i,
  input  logic [AW-1:0] m2_adr_i,
  input  logic [DW-1:0] m2_dat_i,
  input  logic [SW-1:0] m2_sel_i,
  output logic [DW-1:0] m2_dat_o,
  output logic          m2_ack_o, m2_err_o, m2_rty_o,
  // -- shared downstream Wishbone path --
  output logic          s_cyc_o, s_stb_o, s_lock_o, s_we_o,
  output logic [AW-1:0] s_adr_o,
  output logic [DW-1:0] s_dat_o,
  output logic [SW-1:0] s_sel_o,
  input  logic [DW-1:0] s_dat_i,
  input  logic          s_ack_i, s_err_i, s_rty_i,
  // -- observation --
  output logic [1:0]    owner_o,      // 0 = NONE, 1 = CPU, 2 = DMA, 3 = IO
  output logic [2:0]    elig_o,       // {io, dma, cpu}
  output logic          arb_event_o,
  output logic          commit_o,
  output logic [1:0]    grant_o,      // 0 = CPU, 1 = DMA, 2 = IO
  output logic [1:0]    hist_o
);
  localparam logic [1:0] OWN_NONE = 2'd0;

  logic [1:0] owner_q;
  logic own0, own1, own2;
  assign own0 = (owner_q == 2'd1);
  assign own1 = (owner_q == 2'd2);
  assign own2 = (owner_q == 2'd3);

  logic cur_cyc;
  assign cur_cyc = (own0 && m0_cyc_i) || (own1 && m1_cyc_i)
                || (own2 && m2_cyc_i);

  assign elig_o = {m2_cyc_i, m1_cyc_i, m0_cyc_i};

  logic arb_event;
  assign arb_event = PREEMPT ? 1'b1
                             : ((owner_q == OWN_NONE) || !cur_cyc);
  assign arb_event_o = arb_event;

  logic [1:0] psel, plast;
  logic       pvalid;
  wb_arb_policy #(
    .NREQ(3), .POLICY(POLICY),
    .PTR_ON_REQUEST(PTR_ON_REQUEST),
    .IGNORE_ELIGIBILITY(IGNORE_ELIGIBILITY)
  ) u_policy (
    .clk_i(clk_i), .rst_i(rst_i), .req_i(elig_o), .commit_i(arb_event),
    .sel_o(psel), .valid_o(pvalid), .last_o(plast));

  assign commit_o = arb_event && pvalid;
  assign grant_o  = psel;
  assign hist_o   = plast;

  logic [1:0] owner_n;
  always_comb begin
    owner_n = owner_q;
    if (arb_event) begin
      if (!pvalid)            owner_n = OWN_NONE;
      else if (psel == 2'd0)  owner_n = 2'd1;
      else if (psel == 2'd1)  owner_n = 2'd2;
      else                    owner_n = 2'd3;
    end
  end

  always_ff @(posedge clk_i) begin
    if (rst_i) owner_q <= OWN_NONE;
    else       owner_q <= owner_n;
  end
  assign owner_o = owner_q;

  // ── FORWARD ROUTING ──
  // Gated by ownership, so RULE 3.30 keeps every slave silent for a
  // non-owner; the payload fields are selected as ONE context because
  // RULE 3.60 names them as one set qualified together by STB_O.
  assign s_cyc_o  = (own0 && m0_cyc_i)  || (own1 && m1_cyc_i)
                 || (own2 && m2_cyc_i);
  assign s_stb_o  = (own0 && m0_stb_i)  || (own1 && m1_stb_i)
                 || (own2 && m2_stb_i);
  assign s_lock_o = (own0 && m0_lock_i) || (own1 && m1_lock_i)
                 || (own2 && m2_lock_i);

  always_comb begin
    if (own0) begin
      s_adr_o = m0_adr_i; s_we_o = m0_we_i;
      s_dat_o = m0_dat_i; s_sel_o = m0_sel_i;
    end else if (own1) begin
      s_adr_o = m1_adr_i; s_we_o = m1_we_i;
      s_dat_o = m1_dat_i; s_sel_o = m1_sel_i;
    end else if (own2) begin
      s_adr_o = m2_adr_i; s_we_o = m2_we_i;
      s_dat_o = m2_dat_i; s_sel_o = m2_sel_i;
    end else begin
      s_adr_o = '0; s_we_o = 1'b0; s_dat_o = '0; s_sel_o = '0;
    end
  end

  // ── RETURN ROUTING ──
  assign m0_ack_o = own0 && s_ack_i;
  assign m0_err_o = own0 && s_err_i;
  assign m0_rty_o = own0 && s_rty_i;
  assign m1_ack_o = own1 && s_ack_i;
  assign m1_err_o = own1 && s_err_i;
  assign m1_rty_o = own1 && s_rty_i;
  assign m2_ack_o = own2 && s_ack_i;
  assign m2_err_o = own2 && s_err_i;
  assign m2_rty_o = own2 && s_rty_i;
  assign m0_dat_o = s_dat_i;
  assign m1_dat_o = s_dat_i;
  assign m2_dat_o = s_dat_i;
endmodule

Reading it

Three signals define the whole interface between selection and ownership.

elig_o is the eligibility vector, {io_cyc, dma_cyc, cpu_cyc}. arb_event says a decision may be taken this clock. commit_o says one actually was.

  assign arb_event = PREEMPT ? 1'b1
                             : ((owner_q == OWN_NONE) || !cur_cyc);

and, a few lines further down, the signal the history listens to:

  assign commit_o = arb_event && pvalid;

commit_o is what the history listens to, and the distinction between arb_event and commit_o is not pedantry. An event on which nobody is eligible is still an event — the owner drops to NONE — but no grant was taken, so the preference must not move. A pointer that advanced on every event would rotate through idle clocks and arrive somewhere arbitrary the moment work appeared.

Now the history rule, stated once because it has to be:

last_q updates on every committed grant, contested or not.

That is a choice, and a different one is equally defensible. "Update only on contested grants" means a requester that has been served alone many times does not lose its turn when a competitor finally appears. Both conventions are used in real designs and they produce different service orders after a run of uncontested tenures. What is not defensible is leaving it unwritten, because the next person to read the RTL will derive a different one.

Everything else in this module is Chapter 16.3's interconnect, restated for three masters and otherwise unchanged. CYC_O and STB_O gated by ownership so RULE 3.30 silences every non-owner; the payload fields selected as one context because RULE 3.60 names them as one set; terminations routed to the owner and nobody else.

The history state machine is small enough to draw completely:

Every transition is labelled commit, and there is no transition for an event without one. That absence is the specification of the pointer, and Section 6 measures the module with it moved to the wrong event.

3. Simulation — SIM E: Requesters Arriving and Leaving

This experiment runs the selection policy on its own, with no bus underneath, driven by a scripted eligibility trace at one decision per clock. That is not a shortcut — wb_arb_policy is a separable module precisely so this question can be asked without a transfer in the way, and it makes "the same trace" exact rather than approximate.

Three requesters A, B and C, with B leaving and returning. The right-hand column is the same policy with IGNORE_ELIGIBILITY set — a rotation that does not scan.

  === SIM E - round robin with requesters coming and going ===
    three requesters A, B, C. One decision per clock. The
    history advances only on a grant that is taken.

    step  A B C   history  chosen   blind-rotation chosen
      0    1 1 1      B       C        C
      1    1 1 1      C       A        A
      2    1 1 1      A       B        B
      3    1 0 1      B       C        C
      4    1 0 1      C       A        A
      5    1 0 1      A       C        B
      6    1 1 1      C       A        C
      7    1 1 1      A       B        A
      8    1 0 0      B       A        B
      9    1 0 0      A       A        C
     10    0 0 1      A       C        A
     11    0 1 1      C       B        B
     12    0 1 1      B       C        C
     13    0 0 0      C       -        -
     14    1 1 0      C       A        A
     15    1 1 0      A       B        B

    grants to a requester that was not asking:
      round robin        0
      blind rotation     4
    -> rotating the position is not the policy. Rotating it
       and then SCANNING FOR AN ELIGIBLE REQUESTER is.

Reading it — four rows carry the chapter

Steps 0, 1, 2: history B → C → A, chosen C → A → B. All three asking, and the preference rotates. Both columns agree here, because when everyone is eligible, rotating and scanning give the same answer.

Step 5 is the first row where they differ, and it is the whole point. History is A. B is not asking. Round robin scans B, finds it absent, and takes C. Blind rotation hands the grant to B. A requester that never asked has just been given the shared path, and it will do nothing with it.

Step 9: history A, and only A is asking. Round robin scans B, C, A — and comes back to A. A requester with no competition keeps being served, which is correct and is worth stating because "round robin" invites the reading that somebody else must get a turn.

Step 13: nobody asking. Chosen -. valid_o is low, the owner drops to NONE, and — crucially — the history does not move. Compare the blind column, which also shows - here only because its valid_o is |req_i; its internal position is still being dragged forward by the rotation.

Grants to a requester that was not asking: round robin 0, blind rotation 4.

Four wasted tenures out of sixteen opportunities. On a real bus each one is an owner that asserts nothing, a slave that sees no cycle, and a requester that is genuinely waiting being told to wait longer. It is not a data corruption. It is a liveness defect, and no protocol checker will see it.

4. Why This Module Has Three Requesters

Here is a result that changed the shape of this module.

Run Module 16's two-master system under sustained demand from both masters — the CPU with permanent work, the DMA copying — and count the contested arbitration events.

  === SIM D - round robin under continuous demand ===
    control first: CPU and DMA only, 40 clocks of both asking.
      arbitration events 12   of which contested 0
      -> an event fires when the owner negates CYC_O, and that
         master is then not asking. With two requesters the
         other one is the only candidate, so the policy has
         nothing to decide.

    three requesters, all asking (C = CPU, D = DMA, I = IO)
      ICDICDICDICDICDICDICDICD

    arbitration events      53
    of which contested      23
    grants                  CPU 18   DMA 15   IO 8
    longest run of asking and not chosen
                            CPU 1   DMA 1   IO 1
    selection disagreed with the reference model  0
    a grant went to a requester not asking        0

Reading it

Twelve arbitration events. Zero contested.

And the reason is structural rather than accidental. An arbitration event fires when the current owner negates CYC_O. That master is, at that moment, not asking — its CYC_O is what just went away. With only two requesters, the only remaining candidate is the other one. The policy is handed a set of size one, every time.

So with two masters and this release rule, fixed priority and round robin produce byte-identical service. Not similar — identical. Any chapter that compared them on two masters would be comparing nothing, and the honest response is to say so and add a requester rather than to tune a workload until a difference appears.

With a third requester the picture changes immediately. ICDICDICDICDICDICDICDICD — a clean rotation, 23 contested events out of 53, and the longest run of any requester asking and not being chosen is 1.

Read that last number carefully, because Chapter 17.3 will make it precise. With three requesters the best a rotation can do is serve the other two before coming back, so at most two lost opportunities in a row is the structural bound. Measuring 1 here does not prove the bound; it is one trace. The bound comes from the policy, and it holds only under assumptions this chapter has not yet stated.

The two audit lines are clean: selection disagreed with the reference model 0 times, and no grant went to a requester that was not asking. The reference model is independent — it keeps its own history and recomputes the expected winner from the eligibility vector, so an arbiter that reaches the right answer with a broken pointer is still caught. Section 6 of Chapter 17.5 shows it catching exactly that.

5. Pointer Semantics: The Bugs Worth Naming

A round-robin pointer is one register and it has more failure modes than the rest of the arbiter combined. Each of these is a real design, and each produces a system that mostly works.

Three of those six are invisible to any bus-level check, and two of them produce a service distribution that looks reasonable in aggregate. The one instrument that finds them all is a reference model that recomputes the decision independently, which is why wb_arb_probe has one and why it is not wired to the arbiter's own pointer.

The discipline that prevents all six is the same one line: decide what event moves the history, write it down in the module, and test that exact event. PTR_ON_REQUEST in this module's RTL is the first row of that table, built so it can be measured — and in Chapter 17.5's gate it produces exactly one wrong choice in over a hundred events.

6. Common Mistakes

"Round robin means equal bandwidth."

Why it is wrong: it rotates ownership opportunities. Tenures differ in length, phases differ in count, and slaves differ in latency. Chapter 17.3 measures a run where equal grants produced unequal work done.

"Round robin is always fair."

Why it is incomplete: "fair" is not a property until you say which one. Chapter 17.3 defines the one this arbiter has, states four assumptions it needs, and checks it.

"A round-robin pointer should advance every clock."

Why it is wrong: the pointer is a record of who was served. Advancing it on clocks where nobody was served makes it a record of nothing. It must move on the event the design says it moves on, and that event is a grant.

"If a requester is alone, round robin should still move on."

Why it is wrong: step 9 of SIM E serves A twice in a row because A is the only requester. There is nobody to move on to. A policy that refused would be idling a bus on principle.

"Round robin is a more complex fixed priority."

Why it is wrong in a way that matters: it is fixed priority plus one register and a rotated starting point. The scan is the same scan. If you can write one you can write the other, and the interesting engineering is in when the register updates, not in the scan.

"Two masters is enough to test an arbitration policy."

Why it is wrong: Section 5. Twelve events, zero contested, both policies identical. Count contested events in your regression before believing it exercised the arbiter.

7. Interview Reasoning

"What state does round robin require that fixed priority does not?"

One register: the index of the last committed grant. Fixed priority is a pure function of the eligibility vector; round robin is a function of the vector and that register. Everything else — the scan, the eligibility gating, the grant output — is the same.

"When should a round-robin pointer update?"

On the event your design says it does, and that event must be written down. This design updates on every committed grant, contested or not. "Only on contested grants" is a different, equally valid convention with a different service order. The bug is not choosing one; the bug is not saying which.

"Your round-robin arbiter serves the same requester twice in a row. Is it broken?"

Not necessarily. If it was the only requester eligible at both events, that is correct behaviour. Look at the eligibility vector at those two events before looking at the pointer — and if the other requesters were asking, then look at when the pointer updates.

"How would you test an arbitration policy?"

Drive the eligibility vector directly and compare against an independent model, rather than driving masters and hoping they contend. Masters have duty cycles; a policy test should not depend on them. Then check the contested count — a policy test with no contested events has tested eligibility, not selection.

"You inherit an arbiter documented as round robin. What do you check first?"

That the pointer exists and that you can find the one line that writes it. Then which event that line is under. In three designs out of the six failure modes above, the pointer is written under the wrong condition and the code still reads like round robin.

8. Understanding Check

At step 5 of SIM E the history is A, and A and C are asking. Why is C chosen rather than A?

The scan starts one past the history. From A it checks B — absent — then C, which is eligible. A is only reached if neither of the others is asking, which is what happens at step 9.

In the two-master control, both policies produced identical service. Was one of them broken?

No. Neither was ever asked to decide. Every event had one eligible candidate, so both policies returned it. The measurement is about the system, not the arbiters.

Your pointer advances on every arbitration event rather than on every committed grant. When does this first hurt?

On a bus with idle periods. Events fire with nobody eligible, the pointer walks forward through them, and when work arrives the starting position is unrelated to who was last served. Under continuous demand it may never show at all — which is why it survives regressions.

A colleague argues that round robin makes fixed priority unnecessary. What do you say?

That they encode different system goals. Fixed priority states that one requester's deadline matters more than another's, and keeps stating it. Round robin states that no requester should be preferred twice in a row. A display engine that must not miss a scanline and a debug port that can wait are not the same requester, and a policy that treats them identically has thrown information away.

9. What's Next

Two policies now exist and they behave differently under contention. Describing that difference has so far needed the word "fair", and the word has been avoided.

What exactly does fairness mean here, and what does it require to be true?

Chapter 17.3 — Fairness replaces the adjective with a property, states the four assumptions it depends on, and measures both policies on one identical trace. The specification is no help at all: the word does not occur in B3.