H3.8 Hierarchical Arbitration Accounting

MediumFixIcarus · browser samples / server checksReview the topic

Fix a two-level arbiter whose group pointer never moves, so one group starves the other.

Hardware context: Round-robin arbiter with accepted-grant priority updates. Account for one global hardware transfer across local and downstream arbiters.

A two-level arbiter serves four clients in two groups. With all four asking, clients 2 and 3 were never served. Clients 0 and 1 took turns, and group 1 waited forever.

The module hierarchical_arbiter picks a group first and then a client, or leaf, inside it. Each level has its own round-robin pointer. A transfer happens only when the shared output takes the offer, with ready = 1. Only a transfer may move the pointers.

The tests drive 32 edges of requests, stalls and resets. After each edge they record the offer, the receipts, the pointers and the retained client. The whole record is compared.

Find the bug and fix it.

Signals in the Timeline

SignalWidthRole
offered_edges6input of each check
reset_edges6input of each check
Full specification
The ports (keep them)
module hierarchical_arbiter (
  input  logic       clk, reset, ready,
  input  logic [3:0] requests,
  output logic [3:0] grant, accepted_leaf,
  output logic [1:0] accepted_group,
  output logic       accepted, canceled,
  output logic       group_priority,
  output logic [1:0] leaf_priority,
  output logic [2:0] owner);
  // your arbiter
endmodule
RuleWhat the arbiter does
GroupsGroup 0 holds clients 0 and 1. Group 1 holds clients 2 and 3. Leaf 0 or 1 is the position inside a group.
Pointersgroup_priority is the group tried first. Bit g of leaf_priority is the leaf tried first in group g. All are 0 after reset.
Fresh choiceTry the preferred group, then the other. Inside a group, try its preferred leaf, then the other. The first client that asks is offered.
Offergrant is the one-hot bit of the offered client, or 0 for no offer.
TransferAt an edge with an offer and ready = 1: accepted = 1, accepted_leaf = grant, and accepted_group has the winning group bit.
Pointer updateOn a transfer, group_priority moves to the other group. The winning group's leaf bit moves to the sibling. The other group's leaf bit stays.
StallAn offer with ready = 0 makes the client the retained owner. No pointer moves.
Retained ownerWhile the owner asks, it stays offered, whatever else arrives. If it withdraws, there is no offer that cycle, canceled = 1 after the edge, and the owner is released.
ResetSynchronous and active high. No offer while it is 1. Its edge sets all pointers to 0 and releases the owner.
Receiptsaccepted, accepted_leaf, accepted_group and canceled are 0 after any edge where their event did not happen. owner = 4 means no owner.
The line the tests compare (one record per edge)
record: <grant hex>:<accepted><accepted_leaf hex><accepted_group hex><canceled>:<group_priority><leaf_priority hex><owner>;

grant is read 1 ns before each edge. The other fields are read 1 ns after it. A reset edge comes first, before edge 0.

The result compares the whole record, all 32 edges, 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

All Four Clients Ask
Input
Edges 0 to 7: requests 0xf, ready = 1. Then idle.
Output
your_line_length = 352, expected_line_length = 352, lines_match = yes

The service order is 0, 2, 1, 3, then it repeats. Each transfer moves the group pointer to the other group and the winner's leaf bit to its sibling.

Example 2

A Stalled Client Keeps the Offer
Input
Edge 0: client 0 asks, stalled. Edge 1: all ask, stalled. Edges 2 and 3: all ask, ready = 1. Then idle.
Output
your_line_length = 352, expected_line_length = 352, lines_match = yes

Client 0 is retained and stays offered when the others arrive. It transfers on edge 2, and client 2 on edge 3. No pointer moves on edges 0 and 1.

Example 3

Withdrawal and Reset
Input
Edge 0: client 1 asks, stalled. Edges 1 and 2: clients 0, 2 and 3 ask, ready = 1. Edge 3: all ask, stalled. Edge 4: reset. Edge 5: all ask, ready = 1.
Output
your_line_length = 352, expected_line_length = 352, lines_match = yes

Client 1 withdraws on edge 1, giving an idle cycle with canceled = 1. Its leaf bit must not move. Client 0 transfers on edge 2. Client 2 stalls on edge 3. The reset on edge 4 releases it, and canceled stays 0.

Constraints and Contract

  • One transfer gives exactly one group bit and one leaf bit.
  • All inputs are known 0 or 1 values. There is no x or z.
  • Keep the module name and the ports.

Hints

Hint 1

A group that wins the local choice has not been served yet. Only the shared ready says a transfer happened.

Hint 2

Trace the first example. After client 0 transfers, which group should the arbiter offer next?

Hint 3

Look at the transfer branch of the clocked block. It moves the leaf pointer, but it sets group_priority to 0. It must point at the other group.

What the grader checks: The module runs 43 traces of 32 edges, with random requests, stalls and resets. Every record is compared with an independent model. Finite traces show safety and service order, not a proof of fairness.

43 checks on Icarus · browser samples / server checks. 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

All Four Clients Ask

Input
Edges 0 to 7: requests 0xf, ready = 1. Then idle.
Expected output
your_line_length = 352, expected_line_length = 352, lines_match = yes

The service order is 0, 2, 1, 3, then it repeats. Each transfer moves the group pointer to the other group and the winner's leaf bit to its sibling.

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

Icarus · browser samples / server checks