H3.1 Priority Winner

EasyFixVerilator · serverReview the topic

Fix a reference function for a rotating-priority selector that always starts its search at client 0.

Hardware context: Round-robin arbiter with accepted-grant priority updates. Choose the requesting client nearest the current rotating priority.

A rotating-priority selector gives each client a turn at being first in line. Its reference model disagreed with the hardware whenever the priority was not 0. The model always picked the lowest-numbered client that was asking.

The function next_request(clients, requests, priority_index) returns the client that the selector should pick. It looks at the clients in circular order, starting at priority_index. It returns the first one whose request bit is 1, or 0xff when none is asking.

The tests drive each request pattern into real selector hardware. They try every starting priority and compare your answer with the hardware winner and grant. They also compare every answer with an independent model.

Find the bug and fix it.

Signals in the Timeline

SignalWidthRole
clients4input of each check
requests8input of each check
priority_index4input of each check
Full specification
The function (keep its signature)
function automatic bit [7:0] next_request(input int clients, input bit [7:0] requests, input int priority_index);
RuleMeaning
Clientsclients is 1, 2, 3, 5 or 8. The clients are 0 to clients - 1.
Unused bitsRequest bits at clients and above are not connected. Ignore them, even when they are 1.
Search orderpriority_index, priority_index + 1, up to clients - 1, then 0 up to priority_index - 1. Each client is looked at once.
AnswerThe first client in that order whose request bit is 1.
Nobody asksReturn 0xff. It is a marker, not a client number.
Rangepriority_index is always 0 to clients - 1.

For each test the selector starts at first_priority. It then steps the priority by 1, wrapping at clients, until every priority is tried. It waits 1 ns after each step.

Result fieldHolds
choice_jYour answer for priority (first_priority + j) mod clients. Bytes at j = clients and above are 0xff.
valid_maskBit j is the valid pin of the hardware for step j. Unused bits are 0.
errorsBit j is 1 when the hardware winner or one-hot grant disagrees with your answer for step j.

Agreeing with the hardware is not enough. Every choice byte is also compared with the expected answer.

Examples

Example 1

A Gap in the Requests
Input
clients = 3, requests = 0x05 (clients 0 and 2), first_priority = 1
Output
errors = {}, valid_mask = {0, 1, 2}, choice_7 = 0xff, choice_6 = 0xff, choice_5 = 0xff, choice_4 = 0xff, choice_3 = 0xff, choice_2 = 0x0, choice_1 = 0x2, choice_0 = 0x2

From priority 1 the order is 1, 2, 0. Client 1 is not asking, so client 2 wins. From priority 2, client 2 wins again. From priority 0, client 0 wins.

Example 2

Wrap at the Client Count
Input
clients = 5, requests = 0x02 (client 1 only), first_priority = 4
Output
errors = {}, valid_mask = {0, 1, 2, 3, 4}, choice_7 = 0xff, choice_6 = 0xff, choice_5 = 0xff, choice_4 = 0x1, choice_3 = 0x1, choice_2 = 0x1, choice_1 = 0x1, choice_0 = 0x1

From priority 4 the order is 4, 0, 1, so client 1 wins. The search wraps after client 4, not after bit 7. With one client asking, every priority picks client 1.

Example 3

Unused Request Bits
Input
clients = 1, requests = 0xfe, first_priority = 0
Output
errors = {}, valid_mask = {}, choice_7 = 0xff, choice_6 = 0xff, choice_5 = 0xff, choice_4 = 0xff, choice_3 = 0xff, choice_2 = 0xff, choice_1 = 0xff, choice_0 = 0xff

Only client 0 exists, and it is not asking. Bits 1 to 7 are not connected. The answer is 0xff, and the hardware shows valid = 0 and grant = 0.

Constraints and Contract

  • All inputs are known 0 or 1 values. There is no x or z.
  • The tests cover every request pattern for every client count, and every priority for some patterns.
  • Keep the function name, the arguments and the 8-bit return value.

Hints

Hint 1

Try clients = 3, requests = 0b101 and priority_index = 1 by hand. The search order is 1, 2, 0. Which client wins?

Hint 2

The loop counts the distance from priority_index, from 0 up to clients - 1. Each distance names one client.

Hint 3

Look at how the loop turns a distance into a client number. It should add priority_index and wrap with % clients.

What the grader checks: Every answer is compared with real selector hardware and with an independent model. The tests cover every request pattern for 1, 2, 3, 5 and 8 clients. This problem checks the choice only, not a priority that moves over time.

338 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

A Gap in the Requests

Input
clients = 3, requests = 0x05 (clients 0 and 2), first_priority = 1
Expected output
errors = {}, valid_mask = {0, 1, 2}, choice_7 = 0xff, choice_6 = 0xff, choice_5 = 0xff, choice_4 = 0xff, choice_3 = 0xff, choice_2 = 0x0, choice_1 = 0x2, choice_0 = 0x2

From priority 1 the order is 1, 2, 0. Client 1 is not asking, so client 2 wins. From priority 2, client 2 wins again. From priority 0, client 0 wins.

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

Verilator · server