Fix two arbiter checkers that run side by side: one loses count of reset owners, one forgets a broken premise.
Hardware context: Round-robin arbiter with accepted-grant priority updates. Expose starvation, priority wrap and illegitimate grants across requester counts.
A regression runs two checkers on the same arbiter. On a correct arbiter both should stay silent, and their counts should balance. They do not. Each checker has one bug.
grant_retention_checker checks every offer, receipt and lock against the arbiter rules. Its counts must balance: every retained client ends exactly once. service_fairness_checker checks that waiting clients are served in time. Its edge deadline holds only while transfers keep coming.
The tests call both checkers on every edge of the same arbiter. They use N = 1, 2, 3, 5 and 8, a correct arbiter, and many faulty ones. They check the fairness report after every edge, and both final reports.
Find the two bugs, one in each class, and fix them. The full rules are in the specification. Grant Retention Under Backpressure and Bounded Service Fairness explain each checker on its own.
Signals in the Timeline
| Signal | Width | Role |
|---|---|---|
clients | 4 | input of each check |
maximum_interval | 3 | input of each check |
hardware_fault | 4 | input of each check |
Full specification
| Checker | Its rules |
|---|---|
| grant_retention_checker | The first part below: the arbiter rules, the 12 compared fields and the report. |
| service_fairness_checker | The second part below: waits, ages, the progress premise and the report. |
class grant_retention_checker;
function new(input int clients, initial_priority);
function void sample(input int cycle, input bit reset, ready, input bit [7:0] requests,
input int pre_pointer, input bit pre_locked, input bit [7:0] pre_owner,
input bit valid, input bit [7:0] grant, winner,
input bit accepted, input bit [7:0] accepted_client, input bit canceled,
input int post_pointer, input bit post_locked, input bit [7:0] post_owner);
function string report();
endclass
| Rule | What the arbiter does |
|---|---|
| Clients | N is the number of clients. Clients are 0 to N - 1. Request bits at N and above are ignored. |
| Fresh choice | With no retained client, scan the clients in circular order, starting at priority_state. The first one that requests is offered. |
| Offer | valid = 1, winner = the client and grant = its one-hot bit. With no offer, valid = 0, winner = 0xff and grant = 0. |
| Transfer | A transfer happens at an edge with reset = 0, valid = 1 and ready = 1. priority_state then becomes winner + 1, wrapping to 0 after N - 1. |
| Stall | At an edge with valid = 1 and ready = 0, the offered client becomes the retained client. priority_state does not move. |
| Retained offer | While the retained client keeps requesting, it stays offered. Requests from other clients cannot take its place. |
| Withdrawal | If the retained client drops its request, the offer is idle for that whole cycle. This holds even when others request and ready = 1. |
| After a withdrawal | At that edge canceled = 1 and the retained client is released. priority_state does not move. A fresh choice starts in the next cycle. |
| Reset | reset is synchronous and active high. While it is 1 the offer is idle. Its edge accepts nothing, sets priority_state to 0 and releases the retained client. |
| Receipts | accepted and accepted_client describe the transfer at the last edge. accepted_client is 0xff when there was none. Reset clears both, and canceled stays 0. |
| Lock registers | locked and locked_client show the retained client. With none, locked = 0 and locked_client = 0xff. |
Each sample() call describes one edge. Check the old state against your model first. Then predict the edge, check the offer and receipts, and update your model. Check the new state last.
| Bit | Field | Compares |
|---|---|---|
| 0 | PREP | priority_state before the edge |
| 1 | PRELOCK | locked before the edge |
| 2 | PREOWNER | locked_client before the edge |
| 3 | VALID | valid of the offer |
| 4 | GRANT | the whole grant bitmap |
| 5 | WINNER | winner of the offer |
| 6 | ACCEPT | accepted after the edge |
| 7 | CLIENT | accepted_client after the edge |
| 8 | CANCEL | canceled after the edge |
| 9 | POSTP | priority_state after the edge |
| 10 | POSTLOCK | locked after the edge |
| 11 | POSTOWNER | locked_client after the edge |
Your model follows the rules, never the hardware. It must not copy the pointer or the lock from the pins, even after a mismatch. Keep checking after errors and through resets.
| Report item | Meaning |
|---|---|
| FIRST | The first mismatch, as FIELD@cycle:expected>actual with both values in 8 hex digits. Within one edge, the lowest bit wins. OK when there is none. |
| MASK | All field bits that ever failed, in 3 hex digits. |
| BAD | The number of edges with at least one mismatch. |
| A | Transfers your model predicts. |
| SEEN | Edges where the accepted pin was 1. |
| MATCH | Predicted transfers where the pin was 1 and accepted_client was right. |
| OPEN | Retained clients started: the first stalled edge of a fresh offer. A transfer with no stall opens nothing. |
| RET | Retained clients that ended in a transfer. |
| WITHDRAW | Retained clients that ended by withdrawal. |
| RESET_CANCEL | Retained clients that ended by reset. |
| RESETS | Reset edges. |
| P | Your predicted priority_state after the last edge. |
| OWNER | Your predicted retained client in 2 hex digits, or ff. |
The report joins the items with |, as FIRST=OK|MASK=000|... in the order above. Every retained client ends exactly once, so OPEN = RET + WITHDRAW + RESET_CANCEL, plus 1 if one is still retained.
| Faulty arbiter | What is wrong |
|---|---|
| 1 | It makes a fresh choice even while a client is retained. |
| 2 | The pointer moves on a stalled offer. |
| 3 | It keeps offering a retained client that has withdrawn. |
| 4 | It never retains a stalled offer. |
| 5 | The pointer wraps to 1 instead of 0, so client 0 is skipped. With N = 1 it behaves correctly. |
| 6 | The retained client survives reset. |
| 7 | grant also has a bit for every other client that asks. |
| 8 | The old receipt survives reset. |
class service_fairness_checker;
function new(input int clients, maximum_interval);
function void sample(input int cycle, input bit reset, input bit [7:0] requests,
input bit accepted, input bit [7:0] client);
function string report();
endclass
N is 1, 2, 3, 5 or 8, and G = maximum_interval is 1 to 4. sample() gets the requests and the receipts read 1 ns after each edge. client is the accepted client.
| Rule | Meaning |
|---|---|
| Wait | A client below N that asks has an open wait. The wait ends when it is served or stops asking. Reset ends every wait. |
| grant_age | Transfers to other clients during the wait. Only edges with accepted = 1 count. Stalls do not. |
| cycle_age | Edges in the wait, including the current one. On the first edge of a wait it is 1. |
| Own service | When the client itself transfers, both ages clear before any check. Service on the last allowed edge is on time. |
| GRANT error | grant_age reaches N. Report it once per wait. |
| GAP | Non-reset edges in a row where some client asks and nothing transfers. An edge with no requests, or with a transfer, sets GAP to 0. |
| ENV error | GAP reaches G = maximum_interval. Report ENV and set QUAL to 0. Only reset sets QUAL back to 1. |
| CYCLE error | While QUAL = 1, cycle_age reaches N × G. Report it once per wait. |
| Order in one edge | Update GAP and check ENV first. Then count the transfer. Then go through clients 0 to N - 1, with GRANT before CYCLE. |
| Reset | Clears all ages, the once-per-wait flags and GAP, and sets QUAL to 1. FIRST, MASK, BAD, the error counts and SERVICE stay. |
Why N × G: a round robin serves a waiting client within N transfers. If a transfer comes at least every G edges, the client waits at most N × G edges. Without that premise, a wall-clock deadline proves nothing.
| Report item | Meaning |
|---|---|
| FIRST | The first error, as ENV@cycle, GRANT@cycle:client or CYCLE@cycle:client. OK when there is none. |
| MASK | ENV adds 1, GRANT adds 2 and CYCLE adds 4, in decimal. |
| BAD | Edges with at least one new error. |
| QUAL | 1 while the progress premise holds, 0 after an ENV error. |
| GAP | The current GAP. |
| A | Edges where the accepted pin was 1. |
| ENV, GRANT, CYCLE | How many of each error were reported. |
| WAIT | grant_age/cycle_age for clients 0 to N - 1, separated by commas. |
| SERVICE | Transfers each client received over the whole run, separated by commas. |
The report joins the items with |, as FIRST=OK|MASK=0|... in the order above.
| Faulty arbiter | What is wrong |
|---|---|
| 5 | The pointer wraps to 1 instead of 0, so client 0 is skipped. With N = 1 it behaves correctly. |
| 9 | The pointer returns to 0 after every transfer, so it acts as a fixed-priority arbiter. |
Inputs are steady 1 ns before each rising edge. The tests read the offer and the old state just before the edge. They read the receipts and the new state 1 ns after it.
PREFIX=<edges where a fairness report was wrong>|<final fairness report>|TRACE=<the arbiter trace>|SAFETY=<final retention report>
The traces mix both families: steady traffic with stalls, and random traffic with withdrawals and resets. Each checker must keep working when the other one reports an error.
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
Both Checkers Clean on the Deadline- Input
N = 3, G = 2, priority 1, correct arbiter. All clients ask for 8 edges, with ready = 1 on odd edges.
- Output
your_line_length = 1712, expected_line_length = 1712, lines_match = yes
Client 0 is served on edge 5, exactly N × G edges into its wait, so there is no fairness error. Each of the 4 transfers follows a stall, so OPEN=4 and RET=4.
Example 2
Starvation with Steady Progress- Input
The same traffic with faulty arbiter 5, which skips client 0
- Output
your_line_length = 1743, expected_line_length = 1743, lines_match = yes
The fairness report shows GRANT@5:0 first, with QUAL still 1. The retention report also fails, first at POSTP@3, because the pointer wraps to 1 instead of 0.
Example 3
A Stalled Receiver Breaks the Premise- Input
N = 3, G = 2, correct arbiter. All clients ask for 8 edges with ready = 0, then nobody asks.
- Output
your_line_length = 1715, expected_line_length = 1715, lines_match = yes
ENV is reported on edge 1, and QUAL stays 0. The retention report is clean: one retained client opens and later ends by withdrawal, so OPEN=1 and WITHDRAW=1.
Constraints and Contract
- Predict from your own models. Use the pins only for comparison.
- A clean run on 32 edges shows no violation in that run. It is not a proof of fairness.
- Keep both class names, the method names and the argument types.
Hints
Hint 1
Run the ledger check by hand on a trace with a reset during a stall. Does OPEN equal RET + WITHDRAW + RESET_CANCEL?
Hint 2
In the fairness checker, find every place that sets QUAL. Which events may set it back to 1?
Hint 3
One bug is in the reset branch of grant_retention_checker.sample(): it forgets to count the cancelled owner. The other sets qualified = 1 on a transfer.
What the grader checks: Both checkers watch the same real arbiters, one correct and many with distinct faults. Every fairness report after every edge and the final retention report are compared. A finite run is not a proof of fairness.
111 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