Fix a fairness checker that counts stalled edges as turns given to other clients.
Hardware context: Round-robin arbiter with accepted-grant priority updates. Check service fairness in accepted grants with an explicit downstream-progress bound.
A fairness checker flagged a correct round-robin arbiter. The errors came only when the receiver stalled. The checker treated each stalled edge as a turn given to another client.
The class service_fairness_checker watches the transfers of one arbiter. For each waiting client it counts transfers to others and elapsed edges. A client must be served within N transfers to others. The edge deadline holds only while transfers keep coming.
The tests run it on a correct arbiter and on two faulty ones, with stalls, withdrawals and resets. It must stay silent on the correct one and catch each starving client. The tests check report() after every edge.
Find the bug and fix it. The full rules are in the specification.
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
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. |
The arbiter keeps a stalled offer, as in Grant Changes Under Stall. Its receipts are always one-hot and legal here.
PREFIX=<edges where report() was wrong>|<your final report>|TRACE=<the arbiter trace>
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
Service on the Deadline Is on Time- 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 = 1601, expected_line_length = 1601, lines_match = yes
Clients 1, 2 and 0 transfer on edges 1, 3 and 5. Client 0 is served on edge 5, its sixth edge, which is exactly N × G. Its service clears its ages first, so there is no error.
Example 2
Transfers Keep Coming While One Client Starves- Input
The same traffic with faulty arbiter 5, which skips client 0
- Output
your_line_length = 1608, expected_line_length = 1608, lines_match = yes
A transfer comes every two edges, so QUAL stays 1. On edge 5 client 0 has seen three transfers to others and waited six edges. GRANT and CYCLE both fail, and FIRST is GRANT@5:0.
Example 3
No Transfers Break the Premise- Input
N = 3, G = 2, correct arbiter. All clients ask for 8 edges with ready = 0.
- Output
your_line_length = 1604, expected_line_length = 1604, lines_match = yes
GAP reaches 2 on edge 1, so ENV is reported there and QUAL becomes 0. No transfer happens, so no GRANT error. CYCLE is not claimed, because the receiver, not the arbiter, stopped progress.
Constraints and Contract
- Use the accepted pin and its client, not the offer after the edge.
- A clean run on 32 edges shows no violation in that run. It is not a proof of fairness.
- Keep the class name, the method names and the argument types.
Hints
Hint 1
There are two clocks in this checker: transfers and edges. Which age counts which?
Hint 2
Trace three clients that all ask while ready is 0. No one transfers. What should grant_age be after two edges?
Hint 3
Look at the line that increments grant_age. It runs on every edge, but it should run only when accepted = 1.
What the grader checks: The checker watches real arbiters: a correct one, one that skips client 0, and one with fixed priority. N is 1, 2, 3, 5 and 8, and G is 1 to 4. Every report after every edge is compared. A finite run is not a proof of fairness.
123 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