G7.8.1 Round-Robin Arbiter for Three

MediumImplementIcarus Verilog + Yosys · serverReview the topic

Build a three-requester round-robin arbiter whose state is the last winner, with exactly one grant whenever anyone asks.

Hardware context: Three engines sharing one memory port, where one of them asks in almost every cycle. Build a round-robin arbiter for three requesters whose state is the last winner.

Three engines share one memory port. The fixed-priority arbiter in the starter lets engine 0 lock the others out. The team wants round robin.

This is an Implement problem. Complete rr3: the grant is combinational from the requests and the state, and the state is the last winner. Both are ports.

The check resets the arbiter and drives request patterns for 16 cycles. In every cycle it records gnt and last. The design must synthesize with no latches.

Signals in the Timeline

SignalWidthRole
reqs48input of each check
Full specification
The module (keep the name and the ports)
module rr3 (
  input  logic       clk,
  input  logic       rst,    // synchronous reset, active high: last = 2
  input  logic [2:0] req,    // req[i] = 1: requester i asks in this cycle
  output logic [2:0] gnt,    // the grant for this cycle: at most one bit, combinational from req and last
  output logic [1:0] last    // the state: the requester that won the most recent grant (0, 1 or 2)
);
  ...
endmodule
RuleDetail
Search orderStart at the requester after last, and wrap from 2 back to 0. The first requester found that asks is granted.
GrantAt most one bit of gnt is 1, and only for a requester that asks. If anyone asks, someone is granted.
StateAt the edge that ends a cycle with a grant, last becomes the index of the winner. With no grant, last keeps its value.
Resetrst = 1 at an edge gives last = 2, so requester 0 is searched first.

Examples

Example 1

All Three Ask in Every Cycle
Input
req per cycle (bit 2 to bit 0): 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111
Output
gnt_cycle0 = 'b001, last_cycle0 = 2, gnt_cycle1 = 'b010, last_cycle1 = 0, gnt_cycle2 = 'b100, last_cycle2 = 1, gnt_cycle3 = 'b001, last_cycle3 = 2, gnt_cycle4 = 'b010, last_cycle4 = 0, gnt_cycle5 = 'b100, last_cycle5 = 1, gnt_cycle6 = 'b001, last_cycle6 = 2, gnt_cycle7 = 'b010, last_cycle7 = 0, gnt_cycle8 = 'b100, last_cycle8 = 1, gnt_cycle9 = 'b001, last_cycle9 = 2, gnt_cycle10 = 'b010, last_cycle10 = 0, gnt_cycle11 = 'b100, last_cycle11 = 1, gnt_cycle12 = 'b001, last_cycle12 = 2, gnt_cycle13 = 'b010, last_cycle13 = 0, gnt_cycle14 = 'b100, last_cycle14 = 1, gnt_cycle15 = 'b001, last_cycle15 = 2

Reset leaves last = 2, so requester 0 wins first. Then 1, then 2, and around again: each wins every third cycle.

Example 2

Requesters 0 and 2 Ask in Every Cycle
Input
req per cycle (bit 2 to bit 0): 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101
Output
gnt_cycle0 = 'b001, last_cycle0 = 2, gnt_cycle1 = 'b100, last_cycle1 = 0, gnt_cycle2 = 'b001, last_cycle2 = 2, gnt_cycle3 = 'b100, last_cycle3 = 0, gnt_cycle4 = 'b001, last_cycle4 = 2, gnt_cycle5 = 'b100, last_cycle5 = 0, gnt_cycle6 = 'b001, last_cycle6 = 2, gnt_cycle7 = 'b100, last_cycle7 = 0, gnt_cycle8 = 'b001, last_cycle8 = 2, gnt_cycle9 = 'b100, last_cycle9 = 0, gnt_cycle10 = 'b001, last_cycle10 = 2, gnt_cycle11 = 'b100, last_cycle11 = 0, gnt_cycle12 = 'b001, last_cycle12 = 2, gnt_cycle13 = 'b100, last_cycle13 = 0, gnt_cycle14 = 'b001, last_cycle14 = 2, gnt_cycle15 = 'b100, last_cycle15 = 0

After 0 wins, the search starts at 1, which is silent, so 2 wins. After 2 wins it wraps to 0. They alternate.

Example 3

One Requester at a Time
Input
req per cycle (bit 2 to bit 0): 001 010 100 000 100 010 001 001 010 010 000 000 000 000 000 000
Output
gnt_cycle0 = 'b001, last_cycle0 = 2, gnt_cycle1 = 'b010, last_cycle1 = 0, gnt_cycle2 = 'b100, last_cycle2 = 1, gnt_cycle3 = 'b000, last_cycle3 = 2, gnt_cycle4 = 'b100, last_cycle4 = 2, gnt_cycle5 = 'b010, last_cycle5 = 2, gnt_cycle6 = 'b001, last_cycle6 = 1, gnt_cycle7 = 'b001, last_cycle7 = 0, gnt_cycle8 = 'b010, last_cycle8 = 0, gnt_cycle9 = 'b010, last_cycle9 = 1, gnt_cycle10 = 'b000, last_cycle10 = 1, gnt_cycle11 = 'b000, last_cycle11 = 1, gnt_cycle12 = 'b000, last_cycle12 = 1, gnt_cycle13 = 'b000, last_cycle13 = 1, gnt_cycle14 = 'b000, last_cycle14 = 1, gnt_cycle15 = 'b000, last_cycle15 = 1

With a single request there is no contest: it wins at once. An idle cycle gives no grant and leaves last alone.

Constraints and Contract

  • req is a known 0/1 value and changes only between edges.
  • Keep the module name and the ports. last must be the arbiter's state register.

Hints

Hint 1

List the search order for each value of last: from 0 it is 1, 2, 0. Write the other two.

Hint 2

A case on last with an if-else chain in each arm gives one grant by construction.

Hint 3

Update last only when gnt is not zero, from the bit that is set.

What the grader checks: Eight directed and twelve seeded request streams of 16 cycles after a reset. In every cycle gnt and last are compared with a JavaScript model. Synthesis must report no latches.

The submitted design must synthesize with 0 latches and no combinational loop. Counts come from the pinned open-source synthesis flow. They are proxies for logic size and depth, not physical area or timing.

20 checks on Icarus Verilog + Yosys · 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 1 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 Three Ask in Every Cycle

Input
req per cycle (bit 2 to bit 0): 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111
Expected output
gnt_cycle0 = 'b001, last_cycle0 = 2, gnt_cycle1 = 'b010, last_cycle1 = 0, gnt_cycle2 = 'b100, last_cycle2 = 1, gnt_cycle3 = 'b001, last_cycle3 = 2, gnt_cycle4 = 'b010, last_cycle4 = 0, gnt_cycle5 = 'b100, last_cycle5 = 1, gnt_cycle6 = 'b001, last_cycle6 = 2, gnt_cycle7 = 'b010, last_cycle7 = 0, gnt_cycle8 = 'b100, last_cycle8 = 1, gnt_cycle9 = 'b001, last_cycle9 = 2, gnt_cycle10 = 'b010, last_cycle10 = 0, gnt_cycle11 = 'b100, last_cycle11 = 1, gnt_cycle12 = 'b001, last_cycle12 = 2, gnt_cycle13 = 'b010, last_cycle13 = 0, gnt_cycle14 = 'b100, last_cycle14 = 1, gnt_cycle15 = 'b001, last_cycle15 = 2

Reset leaves last = 2, so requester 0 wins first. Then 1, then 2, and around again: each wins every third cycle.

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

Icarus Verilog + Yosys · server