H3.4 Bounded Service Fairness

HardFixVerilator · serverReview the topic

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

SignalWidthRole
clients4input of each check
maximum_interval3input of each check
hardware_fault4input of each check
Full specification
The class (keep these names and types)
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.

RuleMeaning
WaitA client below N that asks has an open wait. The wait ends when it is served or stops asking. Reset ends every wait.
grant_ageTransfers to other clients during the wait. Only edges with accepted = 1 count. Stalls do not.
cycle_ageEdges in the wait, including the current one. On the first edge of a wait it is 1.
Own serviceWhen the client itself transfers, both ages clear before any check. Service on the last allowed edge is on time.
GRANT errorgrant_age reaches N. Report it once per wait.
GAPNon-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 errorGAP reaches G = maximum_interval. Report ENV and set QUAL to 0. Only reset sets QUAL back to 1.
CYCLE errorWhile QUAL = 1, cycle_age reaches N × G. Report it once per wait.
Order in one edgeUpdate GAP and check ENV first. Then count the transfer. Then go through clients 0 to N - 1, with GRANT before CYCLE.
ResetClears 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 itemMeaning
FIRSTThe first error, as ENV@cycle, GRANT@cycle:client or CYCLE@cycle:client. OK when there is none.
MASKENV adds 1, GRANT adds 2 and CYCLE adds 4, in decimal.
BADEdges with at least one new error.
QUAL1 while the progress premise holds, 0 after an ENV error.
GAPThe current GAP.
AEdges where the accepted pin was 1.
ENV, GRANT, CYCLEHow many of each error were reported.
WAITgrant_age/cycle_age for clients 0 to N - 1, separated by commas.
SERVICETransfers 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 arbiterWhat is wrong
5The pointer wraps to 1 instead of 0, so client 0 is skipped. With N = 1 it behaves correctly.
9The 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.

The line the tests compare
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

Report a problem with this page

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

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.
Expected 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.

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

Verilator · server