H3.7 Arbiter Fairness Witness

MediumFixVerilator · serverReview the topic

Fix a test plan that should show client 0 starving, but stops one edge before the deadline.

Hardware context: Round-robin arbiter with accepted-grant priority updates. Construct a finite service-bound witness for a requester skipped at priority wrap.

An arbiter has a pointer bug: it wraps to client 1 instead of client 0. A good bug report shows client 0 waiting past its deadline. This plan builder stops one edge too early, so its report never shows the starvation.

The class fairness_witness builds a list of edges for an arbiter with N clients. Every client asks on every edge. The receiver stalls for H edges, then takes one transfer, and repeats. The plan also gives two bounds: grant_bound = N transfers and cycle_bound = N × (H + 1) edges.

The tests replay the plan on a correct arbiter and on the faulty one. A fairness checker watches both. On the correct arbiter, client 0 must be served on the very last edge. On the faulty one, the checker must flag client 0 on that edge.

Find the bug and fix it.

Signals in the Timeline

SignalWidthRole
clients4input of each check
maximum_hold2input of each check
Full specification
The classes (keep these names and types)
class arbitration_offer;   // given
  bit [7:0] requests;
  bit       ready, reset;
  function new(input bit [7:0] req = 0, input bit permit = 0, rst = 0);
endclass

class fairness_witness;    // yours
  arbitration_offer items[$];
  int cycle_bound, grant_bound;
  function new(input int clients, max_hold);
endclass
Plan ruleMeaning
ClientsN is 2, 3, 5 or 8. H = max_hold is 0 to 3.
RequestsEvery edge asks for all N clients: requests = (1 << N) - 1.
readyEdge c has ready = 1 when c mod (H + 1) = H. Otherwise ready = 0.
resetAlways 0.
LengthExactly cycle_bound edges, each a new object. No entry is null.
Boundsgrant_bound = N and cycle_bound = N × (H + 1).
RunWhat happens
StartBoth arbiters start with priority 1. They keep a stalled offer, so each ready edge transfers one client.
Correct arbiterIt serves 1, 2, up to N - 1, then 0. Client 0 transfers on edge cycle_bound - 1, counting from 0.
Faulty arbiterAfter N - 1 it wraps to 1, so client 0 is never served. On the last edge client 0 has seen N transfers to others.
CheckerIt flags GRANT when a waiting client sees N transfers to others. It flags CYCLE when it waits N × G edges. Here G = H + 1.
After the planThe remaining edges up to 32 are idle and not checked.
The line the tests compare
SIZE=<items>|CYCLE_BOUND=<n>|GRANT_BOUND=<n>|SHAPE=<bad entries>|GOOD_FIRST=<edge>|FAULT_FIRST=<edge>|GOOD{<checker report and trace>}|FAULT{<checker report and trace>}

SHAPE counts null and repeated entries, plus 1 for a plan over 32 edges. GOOD_FIRST and FAULT_FIRST give the first edge where client 0 is served, or 255 if never. A correct plan gives GOOD_FIRST = cycle_bound - 1 and FAULT_FIRST = 255.

The result compares this line with the expected text, character by character. It shows both lengths and whether the two lines match. On a mismatch the log prints your line.

Examples

Example 1

The Third Transfer Meets the Deadline
Input
N = 3, H = 1
Output
your_line_length = 859, expected_line_length = 859, lines_match = yes

The plan has 6 edges and ready is 0, 1, 0, 1, 0, 1. The correct arbiter serves 1, 2 and 0 on edges 1, 3 and 5. The faulty one serves 1, 2, 1, so the checker reports GRANT and CYCLE for client 0 on edge 5.

Example 2

Eight Clients, Three Stalls Each
Input
N = 8, H = 3
Output
your_line_length = 3369, expected_line_length = 3369, lines_match = yes

Eight transfers need 32 edges. The correct arbiter serves client 0 on edge 31. The faulty one serves client 1 again on that edge, and the checker flags client 0 there.

Example 3

No Stalls Still Need a Full Round
Input
N = 2, H = 0
Output
your_line_length = 479, expected_line_length = 479, lines_match = yes

ready is always 1. The correct arbiter serves 1, then 0, on edges 0 and 1. The faulty one serves 1 twice, so the second transfer shows client 0 starving.

Constraints and Contract

  • Allocate a new arbitration_offer for every edge.
  • N = 1 is not tested, because there is no other client to serve instead of client 0.
  • Keep the class names, the members and the constructor arguments.

Hints

Hint 1

Work out N = 3 and H = 1 by hand. Ready is 0, 1, 0, 1, 0, 1. On which edge does the correct arbiter serve client 0?

Hint 2

Edges count from 0. A plan that must include edge k needs k + 1 entries.

Hint 3

Look at cycle_bound. It should be N × (H + 1), with nothing taken away, so the last ready edge is in the plan.

What the grader checks: The plan runs on a real correct arbiter and a real one that skips client 0. A fairness checker watches both runs. This shows the bound for steady requests, stalls of at most H and no withdrawal. It does not cover unbounded stalls.

19 checks on Verilator · server. Run the examples first, then check the full regression. Full checks use the server judge. Downloads contain public samples only. A passing result establishes the tested cases, not a proof for all possible inputs.

See all 8 steps and the final capstone

Report a problem with this page

Your code SystemVerilogSaved locally
Ln 1, Col 1Tab indents · Ctrl/⌘ + Enter runs samples
Not run yet

The Third Transfer Meets the Deadline

Input
N = 3, H = 1
Expected output
your_line_length = 859, expected_line_length = 859, lines_match = yes

The plan has 6 edges and ready is 0, 1, 0, 1, 0, 1. The correct arbiter serves 1, 2 and 0 on edges 1, 3 and 5. The faulty one serves 1, 2, 1, so the checker reports GRANT and CYCLE for client 0 on edge 5.

Run samples executes all 3 public checks. Check all tests runs 19 checks on the server.

Verilator · server