ASIC Point Explore

← RTL Design Interviews

Interview Question · Code Writing

Writing a Round-Robin Arbiter

L1 JuniorL2 Mid-Levelarbitersround robin
  • Likely at AMD
  • Likely at Intel

The interviewer asks

Write a 4-requester round-robin arbiter. After a requester wins, it should have the lowest priority next time.

Reveal the Model Answer

Keep a mask of the requesters above the last winner. First look for the lowest requester inside the mask. If there is none, wrap around and take the lowest requester overall. After each grant, set the mask to the bits above the winner. The pointer moves only on a grant, so an idle cycle changes nothing.

One Round-Robin GrantArrows carry values inside one clock cycle, except the pointer update, which happens at the edge.
One round-robin grantArrows carry values inside one clock cycle, except the pointer update, which happens at the edge. input req[3:0] who is asking flop ptr_q first in line (flop) logic Chain 1 requests at or afterptr logic Chain 2 all requests, from 0 logic Pick chain 1 if it foundone output grant[3:0] one-hot req & maskmaskreqfirstfirstgrantwinner + 1 at atransfer
  1. Mask

    With ptr_q = 2 and all four asking, the mask 1100 keeps requests 2 and 3 for chain 1.

  2. Two chains

    Chain 1 finds request 2. Chain 2 would find request 0, but it is used only when chain 1 finds nothing.

  3. Grant

    The grant is 0100. When ready is 1, the transfer happens at the edge.

    Follow the calls, values and waits
    1. data grant 0100: Pick → grant[3:0]
  4. Move the pointer

    At that edge the pointer becomes 3, the requester after the winner. Next time chain 1 starts at requester 3, then chain 2 wraps to 0.

    Follow the calls, values and waits
    1. data ptr = 3: grant[3:0] → ptr_q
Read the diagram as text
  • req[3:0]: who is asking
  • ptr_q: first in line (flop)
  • Chain 1: requests at or after ptr
  • Chain 2: all requests, from 0
  • Pick: chain 1 if it found one
  • grant[3:0]: one-hot
  • req[3:0] → Chain 1: req & mask
  • ptr_q → Chain 1: mask
  • req[3:0] → Chain 2: req
  • Chain 1 → Pick: first
  • Chain 2 → Pick: first
  • Pick → grant[3:0]: grant
  • grant[3:0] → ptr_q: winner + 1 at a transfer

Chain 2 is the wrap-around: it serves the requesters below the pointer when nobody at or above it asks.

The mask arbiter with all four requesting, then with requesters 0, 1 and 3.

RUNIcarus Verilog · in your browser
Edit the code, then run it

        
Expected: all four: grants r0=25 r1=25 r2=25 r3=25 r0, r1, r3: grants r0=34 r1=33 r2=0 r3=33

        
        
      

          
Self-Check
Tick each key point you covered in your answer.


What Interviewers Listen For (Junior)
A good junior answer writes the mask, the two searches for the lowest set bit, and the wrap-around. It also tests the case where only one requester is active.


        

      

    

    
  

    

    

    
Cross-Questions

    
Where the interviewer goes next. Open a node to practise that follow-up.

    
WhyWhat IfProve ItCompareScale It

    
    
      
  1. Writing a Round-Robin Arbiter
    2. 
      
  2. 
    
    WhyWhy Priority Moves Only on a GrantL1 Junior
      
    
      
    Why must the round-robin pointer move only when a grant is given?
    
      
    
    
    
    
      
      
    Reveal the Model Answer
        
    Round robin promises that the winner goes to the back of the queue. Suppose the pointer moves on cycles with no grant, or past idle requesters. Then some requester ends up first more often than the others. Tying the update to the winner keeps the promise for any request pattern.
    
          
    Self-Check
    Tick each key point you covered in your answer.
    


        
    
      
    
    
    
    
  
    
      
    
    
    Misconception
    
    
    "Moving every cycle is fairer, because everyone gets a turn at the top."
    
    
    Being at the top is useless if you are not asking then. Fairness is about grants to active requesters, not positions.
    
    
    Source Measured: the twin on this question, Icarus Verilog 12
    
  
    
    
    3. 

  3. 
    
    What IfHolding the Grant for a Whole TransferL2 Mid-Level
      
    
      
    What if a grant must be held for a multi-cycle transfer?
    
      
    
    
    
    
      
      
    Reveal the Model Answer
        
    Lock the grant until the transfer ends, for example on a last signal. Update the mask only when the lock is released. Otherwise the arbiter may switch owners in the middle of a burst. The lock also means the worst-case wait now depends on the longest transfer.
    
    
    A Newcomer During a StallPart 2 of the lab bench, cycles e18 to e24. grant (hold) is the round robin above; grant (no hold) lacks the line that keeps a stalled winner first.
    

    
    
    
  0123456clkreq00001000110001000000readygrant (hold)0000100001000000grant (no hold)00001000010010000000
    1. Cycle 1
      Cycle e19: only requester 3 asks. Both versions grant it, and ready is 0.
    2. Cycle 2
      Cycle e20: requester 2 arrives. With the hold, the pointer sits on 3 and the grant stays. Without it, chain 1 starts at 0 and finds 2 first.
    3. Cycle 3
      Cycle e21: ready is 1. The held version takes requester 3, whose data waited two cycles. The other takes requester 2 and abandons requester 3's offer.
    
    
    Measured. The bench's last line, "grant moved during a stall", reads 0 with the hold and 1 without it. Fixed priority also reads 1.
    
    
  
    
          
    Self-Check
    Tick each key point you covered in your answer.
    


        
    
      
    
    
    
    
  
    
      
    
    
    Missed Corner
    
    
    "The requester can just keep its request high."
    
    
    The other requesters are high too. Without a lock, the arbiter rotates to them and cuts the burst.
    
    
    Source Problem R5.6.1 brief (a merger that must not split packets)
    
  
    
    
    4. 

  4. 
    
    CompareMask Arbiter Versus Rotate-and-EncodeL2 Mid-Level
      
    
      
    Compare the mask arbiter with an arbiter that rotates the request vector, uses a fixed-priority encoder, and rotates the grant back.
    
      
    
    
    
    
      
      
    Reveal the Model Answer
        
    Both give the same grants. The rotate form needs two barrel shifters, which grow with N times log N and add depth. The mask form uses two fixed-priority searches and a mux, which map well to fast carry-style logic. For small N either is fine; for large N the mask form is usually smaller and faster.
    
          
    Self-Check
    Tick each key point you covered in your answer.
    


        
    
      
    
    
    
    
  
    
      
    
    
    Misconception
    
    
    "Rotation is free; it is only wiring."
    
    
    A fixed rotation is only wiring. Rotating by a variable amount needs a barrel shifter, which is real logic on the critical path.
    
    
    Source Sutherland, RTL Modeling with SystemVerilog (2017) ch. 5.10 Shift operators
    
  
    
    
    5. 

  5. 
    
    Prove ItSolve R5.4.1: A Round Robin for Any NSimulator-graded
      
    Show it, don't just say it: this Silicon Lab problem is graded by the simulator.
    Open Problem R5.4.1
    
    
    6. 

  6. 
    
    Scale ItRound Robin for Many RequestersL2 Mid-LevelL3 Senior
      
    
      
    The arbiter must now serve 64 requesters at a high clock. What changes?
    
      
    
    
    
    
      
      
    Reveal the Model Answer
        
    The lowest-bit search across 64 bits becomes the critical path. One option is a tree of small arbiters: eight groups of eight, with a round robin over the groups. Another is a pipelined arbiter that grants one cycle later. The tree changes fairness slightly, because each group gets an equal share regardless of how many requesters it has.
    
          
    Self-Check
    Tick each key point you covered in your answer.
    


        
    
      
    
    
    
    
  
    
      
    
    
    Half-Truth
    
    
    "A tree of round-robin arbiters is exactly as fair as one big one."
    
    
    Each group gets an equal share. A lone requester in one group gets far more than one in a full group.
    
  
    
    
    7. 

  7. 
    
    Prove ItSolve R5.4.1: A Round Robin for Any NSimulator-graded
      
    Show it, don't just say it: this Silicon Lab problem is graded by the simulator.
    Open Problem R5.4.1
    
    
    8. 
    

  

    
What People Get Wrong
Common wrong answers and why they fail. Run It shows the wrong belief failing on a real simulator.

    
Misconception

    
"Just rotate the priority pointer every cycle."

    
Then priority moves even when nobody was served. With two requesters the shares become uneven, as the twin shows: 75 against 25.

    
Run It
      
Requesters 0 and 1 always asking: a pointer that turns every cycle, then the mask arbiter.

        
RUNIcarus Verilog · in your browser

        
Edit the code, then run it

          

          

          

        
Expected: pointer every cycle, r0 and r1: grants r0=75 r1=25 r2=0 r3=0 FAIL: a pointer that turns every cycle gave requester 0 three times the grants of requester 1

        
        
      

      
See the Fix
// Round robin with a mask: after a grant, only requesters above the winner may win next.
module rr4 (input logic clk, rst_n, input logic [3:0] req, output logic [3:0] gnt);
  logic [3:0] mask, masked;
  assign masked = req & mask;
  always_comb
    if (masked != 0) gnt = masked & (~masked + 4'd1);   // lowest requester above the last winner
    else             gnt = req & (~req + 4'd1);         // nobody above: wrap to the lowest requester
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n)        mask <= 4'b1111;
    else if (gnt != 0) mask <= ~((gnt << 1) - 4'd1);    // bits above the winner only
endmodule
module tb;
  logic clk = 0, rst_n = 0;
  logic [3:0] req = 0, gnt;
  int n0, n1, n2, n3;
  always #5 clk = ~clk;
  rr4 dut (.clk(clk), .rst_n(rst_n), .req(req), .gnt(gnt));
  task automatic run(input string name, input int which);
    n0 = 0; n1 = 0; n2 = 0; n3 = 0;
    for (int c = 0; c < 100; c++) begin
      @(negedge clk);
      if (which == 0) req = 4'b0011;
      #1 n0 += gnt[0]; n1 += gnt[1]; n2 += gnt[2]; n3 += gnt[3];
    end
    $display("%s: grants r0=%0d r1=%0d r2=%0d r3=%0d", name, n0, n1, n2, n3);
  endtask
  initial begin
    #12 rst_n = 1;
    run("mask round robin, r0 and r1", 0);
    if (n0 == n1) $display("PASS: moving priority only on a grant gave equal turns");
    $finish;
  end
endmodule

Prints: mask round robin, r0 and r1: grants r0=50 r1=50 r2=0 r3=0 PASS: moving priority only on a grant gave equal turns

    

  

    
Missed Corner

    
Forgets the wrap case when no requester sits above the last winner.

    
The masked search finds nothing, so nobody is granted. The mask only changes on a grant, so the arbiter stays stuck.

    
Run It
      
Requesters 0 and 1 always asking, on a mask arbiter with no wrap case.

        
RUNIcarus Verilog · in your browser

        
Edit the code, then run it

          

          

          

        
Expected: no wrap, r0 and r1: grants r0=1 r1=1 r2=0 r3=0 FAIL: without the wrap case the arbiter stopped granting after requester 1 won

        
        
      

      
See the Fix
// Round robin with a mask: after a grant, only requesters above the winner may win next.
module rr4 (input logic clk, rst_n, input logic [3:0] req, output logic [3:0] gnt);
  logic [3:0] mask, masked;
  assign masked = req & mask;
  always_comb
    if (masked != 0) gnt = masked & (~masked + 4'd1);   // lowest requester above the last winner
    else             gnt = req & (~req + 4'd1);         // nobody above: wrap to the lowest requester
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n)        mask <= 4'b1111;
    else if (gnt != 0) mask <= ~((gnt << 1) - 4'd1);    // bits above the winner only
endmodule
module tb;
  logic clk = 0, rst_n = 0;
  logic [3:0] req = 0, gnt;
  int n0, n1, n2, n3;
  always #5 clk = ~clk;
  rr4 dut (.clk(clk), .rst_n(rst_n), .req(req), .gnt(gnt));
  task automatic run(input string name, input int which);
    n0 = 0; n1 = 0; n2 = 0; n3 = 0;
    for (int c = 0; c < 100; c++) begin
      @(negedge clk);
      if (which == 0) req = 4'b0011;
      #1 n0 += gnt[0]; n1 += gnt[1]; n2 += gnt[2]; n3 += gnt[3];
    end
    $display("%s: grants r0=%0d r1=%0d r2=%0d r3=%0d", name, n0, n1, n2, n3);
  endtask
  initial begin
    #12 rst_n = 1;
    run("with wrap, r0 and r1", 0);
    if (n0 + n1 == 100) $display("PASS: with the wrap case some requester is granted every cycle");
    $finish;
  end
endmodule

Prints: with wrap, r0 and r1: grants r0=50 r1=50 r2=0 r3=0 PASS: with the wrap case some requester is granted every cycle

    

  

    
Delivery

    
Starts writing code before asking whether a grant lasts one cycle or a whole transfer.

    
The answer changes when the pointer may move. Clarify it first; it is part of the spec.

  

    
Learn It, Then Prove It