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
| Signal | Width | Role |
|---|---|---|
offered_edges | 6 | input of each check |
reset_edges | 6 | input of each check |
Full specification
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
| Rule | What the arbiter does |
|---|---|
| Groups | Group 0 holds clients 0 and 1. Group 1 holds clients 2 and 3. Leaf 0 or 1 is the position inside a group. |
| Pointers | group_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 choice | Try the preferred group, then the other. Inside a group, try its preferred leaf, then the other. The first client that asks is offered. |
| Offer | grant is the one-hot bit of the offered client, or 0 for no offer. |
| Transfer | At an edge with an offer and ready = 1: accepted = 1, accepted_leaf = grant, and accepted_group has the winning group bit. |
| Pointer update | On 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. |
| Stall | An offer with ready = 0 makes the client the retained owner. No pointer moves. |
| Retained owner | While 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. |
| Reset | Synchronous and active high. No offer while it is 1. Its edge sets all pointers to 0 and releases the owner. |
| Receipts | accepted, accepted_leaf, accepted_group and canceled are 0 after any edge where their event did not happen. owner = 4 means no owner. |
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