RTL Design Patterns · Chapter 10 · Arbitration
Round-Robin Arbiters
A fixed-priority arbiter always serves the same top requester first, so a busy high-priority master can hold a shared resource forever and starve everyone below it. A round-robin arbiter fixes this with one idea: rotate who holds top priority. After a requester wins, it drops to the bottom of the order and the next in line rises to the top, so grants sweep around the ring and every requester is served within N cycles. This lesson treats round-robin as fixed priority made fair, the same priority encoder wrapped in a rotating pointer. It builds the canonical two-encoder implementation, masking off requests below the pointer, running a priority encoder on the rest, falling back to an unmasked encoder on wrap-around, then advancing the pointer just past the winner. It also covers the most-shipped bug, a pointer that stops one short and collapses back into starvation, verified in SystemVerilog, Verilog, and VHDL.
Advanced16 min readRTL Design PatternsRound-Robin ArbiterArbitrationFairnessPriority EncoderStarvation
Chapter 10 · Section 10.2 · Arbitration
1. The Engineering Problem
You have four bus masters — a CPU fetch unit, a DMA engine, a display controller, and a debug port — and one shared memory port. Only one master can drive the port each cycle, and in 10.1 you built a fixed-priority arbiter to pick the winner: a priority encoder that always grants the lowest-indexed requester that is asserting. It is one line of logic, combinational, fast, and correct in the narrow sense that it always grants exactly one requester when any is asking.
It is also unfair to the point of being broken. Give the CPU fetch unit index 0 and let it stream requests back-to-back — a tight loop that misses cache every cycle — and it wins every arbitration. The DMA engine at index 1 never advances while the CPU is busy; the display controller and debug port at indices 2 and 3 are shut out entirely. This is starvation: a requester that keeps asking can be denied forever because a higher-priority requester keeps asking too. It is not a timing bug or a coding slip — it is exactly what fixed priority means. The fixed order is a permanent hierarchy, and anyone below a busy neighbour waits without bound.
Real systems cannot ship this. A DMA engine that never gets the bus stalls a transfer; a display controller that never gets the bus drops frames; a debug port that never gets the bus makes the chip un-debuggable. What these masters need is not "who is most important" but "whose turn is it" — a policy where the resource is shared fairly, where waiting is bounded, where a requester is guaranteed to be served within a known number of cycles regardless of how greedy its neighbours are. That policy is round-robin arbitration, and it is Chapter 10.2 because fairness — bounding the worst-case wait — is the property nearly every real arbiter must provide, and round-robin is the workhorse that provides it.
// Fixed-priority arbiter (10.1): grant the lowest-index requester.
// grant[i] = req[i] & ~(any lower-index req).
wire [3:0] req; // four masters ask in parallel
wire [3:0] grant; // one-hot: at most one winner
// If req[0] (the CPU) asserts EVERY cycle, grant is ALWAYS 4'b0001.
// req[1], req[2], req[3] are NEVER served -> STARVATION, by design.
//
// The fix is NOT a different encoder. It is the SAME priority encoder with a
// ROTATING starting point: after granting i, start the NEXT search just past i,
// so the winner drops to the bottom of the order and everyone gets a turn.
// (the pattern this page builds — a rotating priority pointer)2. Mental Model
3. Pattern Anatomy
The structure is a priority encoder you already know (1.4), a small pointer register (a counter, 3.1), and one clever trick to make the encoder start at the pointer instead of at index 0: masking.
The priority pointer. A register ptr, log2(N) bits wide, holds the index the search should start from — the seat with top priority this round. At reset it is 0 (so the very first arbitration behaves like a fixed-priority arbiter starting at index 0). After every grant it updates to winner + 1 modulo N. It is exactly a loadable counter: not a free-running counter that ticks every cycle, but one that loads winner + 1 on each grant. That distinction matters — the pointer advances by the arbitration result, not by the clock.
Masking — how you make a fixed encoder start at the pointer. A plain priority encoder always resolves from index 0. To make it resolve from ptr, you first mask off every request below the pointer, so the encoder only sees requests at index ptr or higher. The mask is a vector with 1s from ptr up to N-1 and 0s below: mask[i] = (i >= ptr). Then req_masked = req & mask contains only the requests at or after the pointer, and a priority encoder on req_masked grants the first request at or after the pointer — exactly the clockwise sweep the model describes.
The unmasked fallback — the wrap-around. There is one case the masked encoder cannot handle: when every active request is below the pointer. Then req_masked is all zeros — the masked encoder finds nothing — but there are requesters asking, and one of them must be served (denying them would be a lost grant and a hang). This is the wrap: the sweep ran off the top of the ring and must continue from seat 0. The fix is a second priority encoder on the UNMASKED requests (req directly, resolving from index 0). The arbiter uses the masked winner when the masked set is non-empty, and falls back to the unmasked winner when it is empty. Two encoders, one selector between them — this is the canonical round-robin structure, and the two-encoder cost is the trade-off discussed in §4 and §6.
One-hot grant and the pointer update. The winner from whichever encoder fired is a one-hot vector grant (exactly one bit set when any request is active, all-zero when none is). The winning index then feeds the pointer update: ptr <= winner_index + 1 (modulo N), committed on the clock edge together with the grant. That single update — past the winner — is what guarantees rotation and bounded wait.
The rotating priority pointer — the winner drops to the back of the ring
data flowThe second visual is the one that makes the two-encoder resolution tangible: how the masked encoder handles the common case and the unmasked encoder handles the wrap-around, and how the selector chooses between them.
Masked + unmasked priority — the search that starts at the pointer and wraps
data flowAn equivalent formulation is worth naming because you will meet it: instead of two encoders, rotate the request vector right by ptr, run a single fixed-priority encoder from index 0, then rotate the resulting grant left by ptr. Rotating by the pointer is the wrap — index ptr becomes bit 0 of the rotated vector, so the fixed encoder naturally resolves from the pointer and wraps around for free, and rotating the grant back re-aligns it. It uses one encoder and two barrel rotators instead of two encoders and a selector; which is cheaper depends on N and your synthesis target (§6). The masked/unmasked form is the one to internalize because it reads directly as 'first request at-or-after the pointer, else wrap' and needs no barrel shifter.
4. Real RTL Implementation
This is the core of the page. We build two things — (a) an N-requester round-robin arbiter (parameterized N, masked-priority + unmasked-priority fallback, rotating pointer updated to winner + 1, one-hot grant) with a self-checking clocked testbench that asserts one-hot grant, fairness (rotation order and bounded wait under all-requesters-active), and the lone-persistent-requester case; and (b) the signature pointer-not-advanced starvation bug beside its fix — and each is shown in SystemVerilog, Verilog, and VHDL with an RTL block and a self-checking clocked testbench. The reasoning is identical in all three; only the syntax differs.
One discipline runs through every RTL block, inherited from the register pattern and 10.1: the pointer is a registered state element updated with non-blocking assignment on the clock, reset is explicit (synchronous, active-high rst here), and the grant is a combinational function of the current request vector and the current registered pointer — so the grant this cycle reflects the pointer set by the previous grant, and there is no combinational loop.
4a. The N-requester round-robin arbiter — masked + unmasked, three ways
The arbiter takes an N-bit req, produces an N-bit one-hot grant, and holds a log2(N)-bit ptr. The grant is combinational (mask, two priority encoders, select); the pointer is clocked (ptr <= winner + 1 on a grant).
module rr_arbiter #(
parameter int N = 4 // number of requesters
)(
input logic clk,
input logic rst, // synchronous, active-high
input logic [N-1:0] req, // N requests, valid in parallel
output logic [N-1:0] grant // one-hot winner (all-zero if idle)
);
localparam int PW = (N > 1) ? $clog2(N) : 1; // pointer width
logic [PW-1:0] ptr; // search origin = top priority seat
logic [N-1:0] mask; // 1s from ptr..N-1 (at-or-after ptr)
logic [N-1:0] req_masked; // requests at-or-after the pointer
logic [N-1:0] grant_masked, grant_unmasked; // one-hot winners of each encoder
logic masked_hit; // any request at-or-after the pointer?
// MASK: keep only requests at index ptr or higher. This is what makes a fixed
// priority encoder resolve FROM THE POINTER instead of from index 0.
always_comb begin
for (int i = 0; i < N; i++)
mask[i] = (i >= ptr); // 1 at-or-after ptr, 0 below it
req_masked = req & mask; // requests in the "this round" window
end
// Two priority encoders (lowest set bit wins). The masked one grants the first
// request at-or-after ptr (common case); the unmasked one grants the first
// request from 0 (the WRAP-AROUND, used only when the masked set is empty).
function automatic logic [N-1:0] lowest_onehot(input logic [N-1:0] v);
// isolate the lowest set bit: v & (~v + 1). One-hot, or 0 if v==0.
return v & (~v + 1'b1);
endfunction
always_comb begin
grant_masked = lowest_onehot(req_masked);
grant_unmasked = lowest_onehot(req);
masked_hit = |req_masked; // is there a hit at-or-after ptr?
// FALLBACK: masked winner if the masked set is non-empty, else wrap to the
// unmasked winner. Omitting this branch => no grant when only sub-ptr
// requests are active => a hang (see the DebugLab).
grant = masked_hit ? grant_masked : grant_unmasked;
end
// Encode the one-hot winner back to an index, then advance the pointer PAST it.
function automatic logic [PW-1:0] onehot_to_idx(input logic [N-1:0] oh);
logic [PW-1:0] idx;
idx = '0;
for (int i = 0; i < N; i++)
if (oh[i]) idx = i[PW-1:0];
return idx;
endfunction
always_ff @(posedge clk) begin
if (rst)
ptr <= '0; // reset: behave like fixed-priority from 0
else if (|grant) // only advance ON a grant
// ptr = winner + 1 (mod N). PAST the winner: the winner drops to the
// LOWEST priority next round -> rotation, bounded wait, no starvation.
ptr <= (onehot_to_idx(grant) == N-1) ? '0
: onehot_to_idx(grant) + 1'b1;
end
endmoduleThe clocked testbench does the thing the flagship stands or falls on: it drives all requesters always active and checks the grant sequence is a strict rotation 0,1,...,N-1,0,... with every requester served within N cycles (bounded wait), checks the grant is one-hot every cycle, and checks a lone persistent requester is still served every time.
module rr_arbiter_tb;
localparam int N = 4;
logic clk = 1'b0, rst;
logic [N-1:0] req, grant;
int errors = 0;
int served_count [N]; // how many grants each requester got
rr_arbiter #(.N(N)) dut (.clk(clk), .rst(rst), .req(req), .grant(grant));
always #5 clk = ~clk;
// helper: population count of a one-hot check (0 or 1 bits set is legal)
function automatic int popcount(input logic [N-1:0] v);
int c = 0;
for (int i = 0; i < N; i++) c += v[i];
return c;
endfunction
initial begin
foreach (served_count[i]) served_count[i] = 0;
rst = 1'b1; req = '0;
@(posedge clk); #1; rst = 1'b0;
// ---- FAIRNESS: all requesters always active -> perfect rotation ----
req = '1; // every requester asserts, forever
for (int c = 0; c < N; c++) begin // watch N consecutive grants
@(posedge clk); #1;
// one-hot: exactly one grant when any request is active
assert (popcount(grant) == 1)
else begin $error("not one-hot: grant=%b", grant); errors++; end
for (int i = 0; i < N; i++) if (grant[i]) served_count[i]++;
end
// bounded wait / rotation: after N grants under all-active, EVERY requester
// was served exactly once (a strict rotation, worst-case wait N-1).
for (int i = 0; i < N; i++)
assert (served_count[i] == 1)
else begin $error("fairness: req %0d served %0d times in N cycles (starvation?)",
i, served_count[i]); errors++; end
// ---- LONE PERSISTENT REQUESTER: only req[2] asks, must win every cycle ----
req = '0; req[2] = 1'b1;
repeat (3) begin
@(posedge clk); #1;
assert (grant == (1 << 2))
else begin $error("lone requester 2 not served: grant=%b", grant); errors++; end
end
// ---- IDLE: no requests -> no grant (all-zero, still 'one-hot-or-zero') ----
req = '0; @(posedge clk); #1;
assert (grant == '0)
else begin $error("grant asserted with no request: grant=%b", grant); errors++; end
if (errors == 0) $display("PASS: one-hot, fair rotation (wait <= N-1), lone requester served");
else $display("FAIL: %0d errors", errors);
$finish;
end
endmoduleThe Verilog form is identical in intent; the differences are wire/reg typing, $display("FAIL") instead of assert, and spelling the priority encoders as explicit loops. The mask, the two encoders, the fallback select, and the ptr <= winner + 1 update are the same structure.
module rr_arbiter #(
parameter N = 4,
parameter PW = 2 // = clog2(N); set by instantiator
)(
input wire clk,
input wire rst, // synchronous, active-high
input wire [N-1:0] req,
output reg [N-1:0] grant // one-hot (all-zero if idle)
);
reg [PW-1:0] ptr; // search origin
reg [N-1:0] mask, req_masked;
reg [N-1:0] grant_masked, grant_unmasked;
reg [PW-1:0] win_idx;
integer i;
// Combinational grant: mask, two lowest-set-bit encoders, fall back on wrap.
always @(*) begin
for (i = 0; i < N; i = i + 1)
mask[i] = (i >= ptr); // keep requests at-or-after ptr
req_masked = req & mask;
grant_masked = req_masked & (~req_masked + 1'b1); // lowest set bit, or 0
grant_unmasked = req & (~req + 1'b1); // wrap-around encoder
// FALLBACK: masked winner if any masked request, else the unmasked winner.
grant = (|req_masked) ? grant_masked : grant_unmasked;
end
// one-hot grant -> winning index (for the pointer update)
always @(*) begin
win_idx = {PW{1'b0}};
for (i = 0; i < N; i = i + 1)
if (grant[i]) win_idx = i[PW-1:0];
end
// Clocked pointer: advance to just PAST the winner (winner + 1, mod N).
always @(posedge clk) begin
if (rst)
ptr <= {PW{1'b0}}; // reset: fixed-priority from index 0
else if (|grant)
ptr <= (win_idx == N-1) ? {PW{1'b0}} : win_idx + 1'b1;
end
endmodule module rr_arbiter_tb;
parameter N = 4;
parameter PW = 2;
reg clk, rst;
reg [N-1:0] req;
wire [N-1:0] grant;
integer served [0:N-1];
integer i, c, cnt, errors;
rr_arbiter #(.N(N), .PW(PW)) dut (.clk(clk), .rst(rst), .req(req), .grant(grant));
initial clk = 1'b0;
always #5 clk = ~clk;
initial begin
errors = 0;
for (i = 0; i < N; i = i + 1) served[i] = 0;
rst = 1'b1; req = {N{1'b0}};
@(posedge clk); #1; rst = 1'b0;
// FAIRNESS: all requesters active -> perfect rotation over N grants.
req = {N{1'b1}};
for (c = 0; c < N; c = c + 1) begin
@(posedge clk); #1;
cnt = 0;
for (i = 0; i < N; i = i + 1) cnt = cnt + grant[i];
if (cnt !== 1) begin
$display("FAIL: not one-hot at cycle %0d grant=%b", c, grant);
errors = errors + 1;
end
for (i = 0; i < N; i = i + 1) if (grant[i]) served[i] = served[i] + 1;
end
for (i = 0; i < N; i = i + 1)
if (served[i] !== 1) begin
$display("FAIL: fairness - req %0d served %0d times in N cycles", i, served[i]);
errors = errors + 1;
end
// LONE PERSISTENT REQUESTER: only req[2] asks -> must win every cycle.
req = {N{1'b0}}; req[2] = 1'b1;
for (c = 0; c < 3; c = c + 1) begin
@(posedge clk); #1;
if (grant !== (1 << 2)) begin
$display("FAIL: lone requester 2 not served grant=%b", grant);
errors = errors + 1;
end
end
// IDLE: no request -> no grant.
req = {N{1'b0}}; @(posedge clk); #1;
if (grant !== {N{1'b0}}) begin
$display("FAIL: grant asserted with no request grant=%b", grant);
errors = errors + 1;
end
if (errors == 0) $display("PASS: one-hot, fair rotation (wait <= N-1), lone requester served");
else $display("FAIL: %0d errors", errors);
$finish;
end
endmoduleIn VHDL the same arbiter uses numeric_std: the pointer is an unsigned, the mask is built in a loop, and the two priority encoders are written as loops that find the first set bit at-or-after the pointer and from index 0. to_integer(unsigned(...)) and to_unsigned(...) convert between the pointer and the index.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity rr_arbiter is
generic ( N : positive := 4 );
port (
clk : in std_logic;
rst : in std_logic; -- synchronous, active-high
req : in std_logic_vector(N-1 downto 0);
grant : out std_logic_vector(N-1 downto 0) -- one-hot (all-zero if idle)
);
end entity;
architecture rtl of rr_arbiter is
signal ptr : integer range 0 to N-1 := 0; -- search origin
begin
-- Combinational grant: sweep from ptr for the first request; if none at-or-after
-- ptr, wrap and sweep from 0. Two priority searches, fall back on the wrap.
process (all)
variable g : std_logic_vector(N-1 downto 0);
variable masked_hit : boolean;
begin
g := (others => '0');
masked_hit := false;
-- MASKED search: first request at index >= ptr (the common case).
for i in 0 to N-1 loop
if (i >= ptr) and (req(i) = '1') and (not masked_hit) then
g(i) := '1';
masked_hit := true;
end if;
end loop;
-- UNMASKED fallback: only if nothing at-or-after ptr -> wrap from index 0.
if not masked_hit then
for i in 0 to N-1 loop
if (req(i) = '1') and (g = (g'range => '0')) then
g(i) := '1'; -- first set bit from 0
end if;
end loop;
end if;
grant <= g;
end process;
-- Clocked pointer: advance to just PAST the winner (winner + 1, mod N).
process (clk)
variable win : integer range 0 to N-1;
variable any : boolean;
begin
if rising_edge(clk) then
if rst = '1' then
ptr <= 0; -- reset: fixed-priority from 0
else
any := false;
win := 0;
for i in 0 to N-1 loop
if grant(i) = '1' then win := i; any := true; end if;
end loop;
if any then
if win = N-1 then ptr <= 0; else ptr <= win + 1; end if;
end if;
end if;
end if;
end process;
end architecture;The VHDL testbench uses assert ... report ... severity error as its self-check — driving all requesters active and confirming a strict rotation over N grants, then the lone-requester case.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity rr_arbiter_tb is
end entity;
architecture sim of rr_arbiter_tb is
constant N : positive := 4;
signal clk : std_logic := '0';
signal rst : std_logic;
signal req : std_logic_vector(N-1 downto 0);
signal grant : std_logic_vector(N-1 downto 0);
function popcount(v : std_logic_vector) return integer is
variable c : integer := 0;
begin
for i in v'range loop
if v(i) = '1' then c := c + 1; end if;
end loop;
return c;
end function;
begin
dut : entity work.rr_arbiter
generic map (N => N)
port map (clk => clk, rst => rst, req => req, grant => grant);
clk <= not clk after 5 ns;
stim : process
type int_arr is array (0 to N-1) of integer;
variable served : int_arr := (others => 0);
begin
rst <= '1'; req <= (others => '0');
wait until rising_edge(clk); wait for 1 ns; rst <= '0';
-- FAIRNESS: all requesters active -> strict rotation over N grants.
req <= (others => '1');
for c in 0 to N-1 loop
wait until rising_edge(clk); wait for 1 ns;
assert popcount(grant) = 1
report "not one-hot under all-active" severity error;
for i in 0 to N-1 loop
if grant(i) = '1' then served(i) := served(i) + 1; end if;
end loop;
end loop;
for i in 0 to N-1 loop
assert served(i) = 1
report "fairness: a requester was not served exactly once in N cycles" severity error;
end loop;
-- LONE PERSISTENT REQUESTER: only req(2) asks -> must win every cycle.
req <= (others => '0'); req(2) <= '1';
for c in 0 to 2 loop
wait until rising_edge(clk); wait for 1 ns;
assert grant(2) = '1' and popcount(grant) = 1
report "lone requester 2 not served" severity error;
end loop;
-- IDLE: no request -> no grant.
req <= (others => '0');
wait until rising_edge(clk); wait for 1 ns;
assert popcount(grant) = 0
report "grant asserted with no request" severity error;
report "rr_arbiter self-check complete" severity note;
wait;
end process;
end architecture;4b. The pointer-not-advanced starvation bug — buggy vs fixed, in all three HDLs
The signature failure is the pointer that lands on the winner instead of past it. Here it is as buggy-vs-fixed RTL in each language, then dramatized narratively in §7. The bug is the same everywhere: ptr <= winner (not winner + 1) leaves the winner at the top of the priority order, so under a sustained request it wins every cycle and round-robin collapses into fixed priority — the other requesters starve.
// BUGGY: pointer loaded with the WINNER's own index. The winner stays at the top
// of the priority order, so a persistent requester wins EVERY cycle ->
// round-robin silently degrades into fixed priority -> starvation.
module rr_ptr_bad #( parameter int N = 4, localparam int PW = $clog2(N) )(
input logic clk, rst, input logic [N-1:0] grant_in, output logic [PW-1:0] ptr
);
function automatic logic [PW-1:0] idx(input logic [N-1:0] oh);
logic [PW-1:0] r; r = '0;
for (int i = 0; i < N; i++) if (oh[i]) r = i[PW-1:0];
return r;
endfunction
always_ff @(posedge clk)
if (rst) ptr <= '0;
else if (|grant_in) ptr <= idx(grant_in); // BUG: ON the winner, not past
endmodule
// FIXED: pointer loaded with winner + 1 (mod N). The winner drops to the BOTTOM
// of the priority order -> rotation, bounded wait, no starvation.
module rr_ptr_good #( parameter int N = 4, localparam int PW = $clog2(N) )(
input logic clk, rst, input logic [N-1:0] grant_in, output logic [PW-1:0] ptr
);
function automatic logic [PW-1:0] idx(input logic [N-1:0] oh);
logic [PW-1:0] r; r = '0;
for (int i = 0; i < N; i++) if (oh[i]) r = i[PW-1:0];
return r;
endfunction
always_ff @(posedge clk)
if (rst) ptr <= '0;
else if (|grant_in) ptr <= (idx(grant_in) == N-1) ? '0 : idx(grant_in) + 1'b1;
endmodule module rr_bug_tb;
localparam int N = 4;
logic clk = 1'b0, rst;
logic [N-1:0] req, grant;
int served [N];
int errors = 0;
// Instantiate the WHOLE arbiter but wired so the pointer-update module under
// test drives ptr. Simplest form: bind rr_arbiter (which uses winner+1) to
// PASS, and a starving variant to observe the bug. Here we drive the fixed
// arbiter and assert fairness; swapping in the buggy pointer makes it FAIL.
rr_arbiter #(.N(N)) dut (.clk(clk), .rst(rst), .req(req), .grant(grant));
always #5 clk = ~clk;
initial begin
foreach (served[i]) served[i] = 0;
rst = 1'b1; req = '0; @(posedge clk); #1; rst = 1'b0;
req = '1; // sustained: every requester asks
for (int c = 0; c < 4*N; c++) begin // watch many rounds
@(posedge clk); #1;
for (int i = 0; i < N; i++) if (grant[i]) served[i]++;
end
// The correct arbiter serves each requester ~equally (fairness).
// The BUGGY pointer would show served[0]=4*N and all others 0 (starvation).
for (int i = 0; i < N; i++)
assert (served[i] >= 1)
else begin $error("STARVATION: requester %0d never served in %0d cycles", i, 4*N); errors++; end
if (errors == 0) $display("PASS: every requester served under sustained load (no starvation)");
else $display("FAIL: %0d requesters starved (pointer not advanced past winner?)", errors);
$finish;
end
endmoduleThe Verilog buggy/fixed pair is the same story with reg outputs. The whole bug is the single missing + 1'b1 on the pointer load.
// BUGGY: pointer parked ON the winner -> persistent requester wins forever.
module rr_ptr_bad #( parameter N = 4, parameter PW = 2 )(
input wire clk, rst, input wire [N-1:0] grant_in, output reg [PW-1:0] ptr
);
integer i; reg [PW-1:0] win;
always @(*) begin win = {PW{1'b0}};
for (i = 0; i < N; i = i + 1) if (grant_in[i]) win = i[PW-1:0]; end
always @(posedge clk)
if (rst) ptr <= {PW{1'b0}};
else if (|grant_in) ptr <= win; // BUG: not win + 1
endmodule
// FIXED: pointer parked PAST the winner -> the winner drops to lowest priority.
module rr_ptr_good #( parameter N = 4, parameter PW = 2 )(
input wire clk, rst, input wire [N-1:0] grant_in, output reg [PW-1:0] ptr
);
integer i; reg [PW-1:0] win;
always @(*) begin win = {PW{1'b0}};
for (i = 0; i < N; i = i + 1) if (grant_in[i]) win = i[PW-1:0]; end
always @(posedge clk)
if (rst) ptr <= {PW{1'b0}};
else if (|grant_in) ptr <= (win == N-1) ? {PW{1'b0}} : win + 1'b1;
endmodule module rr_bug_tb;
parameter N = 4; parameter PW = 2;
reg clk, rst;
reg [N-1:0] req;
wire [N-1:0] grant;
integer served [0:N-1];
integer i, c, errors;
// Bind to the fixed arbiter to PASS; a buggy-pointer build would starve others.
rr_arbiter #(.N(N), .PW(PW)) dut (.clk(clk), .rst(rst), .req(req), .grant(grant));
initial clk = 1'b0;
always #5 clk = ~clk;
initial begin
errors = 0;
for (i = 0; i < N; i = i + 1) served[i] = 0;
rst = 1'b1; req = {N{1'b0}}; @(posedge clk); #1; rst = 1'b0;
req = {N{1'b1}}; // sustained: everyone asks
for (c = 0; c < 4*N; c = c + 1) begin
@(posedge clk); #1;
for (i = 0; i < N; i = i + 1) if (grant[i]) served[i] = served[i] + 1;
end
for (i = 0; i < N; i = i + 1)
if (served[i] < 1) begin
$display("FAIL: STARVATION - requester %0d never served in %0d cycles", i, 4*N);
errors = errors + 1;
end
if (errors == 0) $display("PASS: no starvation under sustained load");
else $display("FAIL: %0d starved (pointer not advanced past winner?)", errors);
$finish;
end
endmoduleIn VHDL the same bug appears as ptr <= win; in place of the wrap-and-increment. The others => on the reset and the modulo increment are the discipline that keeps the fix correct.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
-- BUGGY: pointer loaded with the winner's own index -> winner stays top priority
-- -> a persistent requester wins every cycle -> starvation.
entity rr_ptr_bad is
generic ( N : positive := 4 );
port ( clk, rst : in std_logic;
grant_in : in std_logic_vector(N-1 downto 0);
ptr : out integer range 0 to N-1 );
end entity;
architecture rtl of rr_ptr_bad is
begin
process (clk)
variable win : integer range 0 to N-1; variable any : boolean;
begin
if rising_edge(clk) then
if rst = '1' then ptr <= 0;
else
win := 0; any := false;
for i in 0 to N-1 loop
if grant_in(i) = '1' then win := i; any := true; end if;
end loop;
if any then ptr <= win; end if; -- BUG: not win + 1
end if;
end if;
end process;
end architecture;
-- FIXED: pointer loaded with win + 1 (mod N) -> winner drops to lowest priority.
entity rr_ptr_good is
generic ( N : positive := 4 );
port ( clk, rst : in std_logic;
grant_in : in std_logic_vector(N-1 downto 0);
ptr : out integer range 0 to N-1 );
end entity;
architecture rtl of rr_ptr_good is
begin
process (clk)
variable win : integer range 0 to N-1; variable any : boolean;
begin
if rising_edge(clk) then
if rst = '1' then ptr <= 0;
else
win := 0; any := false;
for i in 0 to N-1 loop
if grant_in(i) = '1' then win := i; any := true; end if;
end loop;
if any then
if win = N-1 then ptr <= 0; else ptr <= win + 1; end if;
end if;
end if;
end if;
end process;
end architecture; library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity rr_bug_tb is
end entity;
architecture sim of rr_bug_tb is
constant N : positive := 4;
signal clk : std_logic := '0';
signal rst : std_logic;
signal req : std_logic_vector(N-1 downto 0);
signal grant : std_logic_vector(N-1 downto 0);
begin
-- Bind to the fixed arbiter to PASS; a buggy-pointer build would starve others.
dut : entity work.rr_arbiter
generic map (N => N)
port map (clk => clk, rst => rst, req => req, grant => grant);
clk <= not clk after 5 ns;
stim : process
type int_arr is array (0 to N-1) of integer;
variable served : int_arr := (others => 0);
begin
rst <= '1'; req <= (others => '0');
wait until rising_edge(clk); wait for 1 ns; rst <= '0';
req <= (others => '1'); -- sustained: everyone asks
for c in 0 to 4*N-1 loop
wait until rising_edge(clk); wait for 1 ns;
for i in 0 to N-1 loop
if grant(i) = '1' then served(i) := served(i) + 1; end if;
end loop;
end loop;
for i in 0 to N-1 loop
assert served(i) >= 1
report "STARVATION: a requester was never served under sustained load" severity error;
end loop;
report "rr_bug self-check complete (no starvation)" severity note;
wait;
end process;
end architecture;Across all three languages the lesson is one sentence: advance the pointer to winner + 1, not winner — parking it on the winner leaves that requester at top priority and round-robin silently collapses into the fixed-priority starvation it was built to cure.
5. Verification Strategy
A round-robin arbiter's correctness is not a truth table — it is a fairness property that only shows up over time, so its verification lives in a clocked testbench that watches the grant sequence across many cycles. The single invariant that captures a correct round-robin arbiter is:
Under all requesters continuously active, the grant sequence is a strict rotation
0, 1, ..., N-1, 0, ..., exactly one grant is asserted each cycle (one-hot), and every requester is served withinNcycles — a bounded wait ofN - 1grants, so no requester ever starves.
Everything below makes that invariant checkable and maps onto the testbenches in §4. This is the flagship verification checklist — an explicit, enumerated set of properties a learner must confirm, beyond the prose.
- One-hot-or-zero grant, every cycle. Assert on every clock that
granthas at most one bit set — exactly one when any request is active, all-zero when none is. Two grant bits set means two masters drive the resource (contention); zero bits with an active request means a lost grant (hang). The §4 testbenches check this with a population count (popcount(grant) <= 1, and== 1wheneverreq != 0). - Fairness / rotation under all-active (the core self-check). Drive
reqall-ones and record which requester each grant went to overNconsecutive grants. The invariant: each of the N requesters is served exactly once in any window of N grants, and they arrive in strict rotation order from the pointer. This is the direct starvation detector — a buggy pointer that parks on the winner shows one requester served every cycle and the rest served zero times, which this check flags immediately. The §4 fairness loop does exactly this. - Bounded-wait assertion. State it as a property that must always hold: a continuously-asserting requester is granted within
N - 1cycles of first asking. In the testbench, hold one requester high and count cycles to its grant; assert the count never exceedsN - 1. This is the property fixed priority cannot satisfy and the one that most distinguishes round-robin. - Lone persistent requester still served. Drive exactly one requester (and no others) and confirm it wins every cycle — the pointer must not skip a sole asker. This catches an over-eager pointer or a masking error that advances past the only requester and produces no grant. The §4 testbenches drive
req[2]alone and assertgrant == (1 << 2). - Random request vectors, pointer-always-advances-past-winner. Drive random
reqvectors for many cycles and, on every grant, check that the pointer on the next cycle equals(winner + 1) mod N. This is the invariant that the whole fairness argument rests on; verifying it directly (rather than only its downstream effect) localizes the §7 bug to the pointer update. Also confirm the unmasked fallback fires: drive a vector whose only active requests are below the current pointer and check a grant is still produced (the wrap-around), not a stall. - Small-N exhaustive where feasible. For small
N(sayN = 4), the state is(ptr, req)—Npointer values times2^Nrequest vectors — which is small enough to sweep exhaustively: for every(ptr, req)pair, check the grant is the first active request at-or-afterptr(wrapping), the grant is one-hot-or-zero, and the next pointer is(winner + 1) mod N. Exhaustive coverage atN = 4gives high confidence the masking, fallback, and pointer update are all correct before trusting the parameterized form at largerN. - Expected waveform. On a correct run with all requesters active,
grantsteps0001 → 0010 → 0100 → 1000 → 0001 → ...— one bit walking around the ring, one position per cycle — andptrsteps1 → 2 → 3 → 0 → 1 → ..., always one ahead of the current winner. The visual signature of the §7 bug isgrantstuck on one bit (0001forever) while other requesters ask — the walking bit stops walking, which is starvation on a waveform.
6. Common Mistakes
Pointer parked ON the winner instead of PAST it. The signature failure. Loading ptr <= winner instead of ptr <= winner + 1 leaves the just-served requester at the top of the priority order, so under a sustained request it wins again next cycle, and again, forever — round-robin silently degrades into the fixed-priority starvation it was meant to cure. It passes a single-grant test (the pointer looks like it moved) and fails only under sustained multi-requester load, which is why it ships. Always advance past the winner. (Full post-mortem in §7.)
Missing the unmasked fallback. The masked priority encoder finds the first request at or after the pointer — but when every active request is below the pointer, the masked set is empty and the masked encoder produces nothing. Without a fallback the arbiter emits no grant even though requesters are asking: a lost grant and, if the requester holds, a hang. The fix is the second (unmasked) priority encoder that resolves from index 0 whenever the masked set is empty — the wrap-around. Omitting it is the second failure in §7.
Pointer updated even when no grant is issued. If the arbiter is idle (no request) and you still advance the pointer every cycle, the pointer drifts — it rotates while no one is asking, so when a request finally arrives the 'turn' has moved arbitrarily and fairness is no longer relative to the actual request history. The pointer must update only on a grant (else if (|grant)), not every clock. This is why the pointer is a loadable counter driven by the grant, not a free-running counter driven by the clock.
A bad mask producing a non-one-hot grant. If the mask is built wrong — off-by-one on the i >= ptr comparison, or the two encoders are OR-ed together instead of selected between — the grant can end up with two bits set (masked winner and unmasked winner both surviving). Two grant bits is two masters on the shared resource: contention, exactly the failure the arbiter exists to prevent. The masked and unmasked winners must be mutually exclusive by selection (masked_hit ? masked : unmasked), never combined, and the result asserted one-hot-or-zero every cycle.
Deriving the grant from the next pointer (combinational loop). The grant this cycle must be a function of the current registered pointer (set by the previous grant), not of the pointer value you are about to compute. If you feed the freshly-computed winner + 1 back into the same-cycle mask, grant depends on ptr and ptr depends on grant in the same cycle — a combinational loop. Keep the grant a function of the registered ptr; let the update land on the clock edge.
Choosing the wrong implementation for the size. The masked + unmasked form uses two priority encoders and a selector; the rotate-based form uses one encoder and two barrel rotators (rotate req right by ptr, encode from 0, rotate the grant left by ptr). For small N the two-encoder form is usually smaller and reads more clearly; for large N the barrel rotators can be cheaper than a second wide encoder, or the reverse depending on your target — but both are combinational and both put the encoder(s) on the grant path. The mistake is not choosing at all: dropping in a textbook form without checking which is smaller/faster for your N and target. And whichever you pick, remember the real synthesis cost of round-robin over fixed priority is one extra encoder (or the rotators) plus the pointer register and its update — the price of fairness. Fixed priority is a single encoder and no state; round-robin buys bounded wait with that extra logic and one pipeline-safe register.
7. DebugLab
The arbiter that quietly went unfair — a pointer that stopped one short
The engineering lesson: round-robin is fixed priority made fair by two things working together — a pointer that advances PAST the winner (so the winner drops to the back of the line) and a search that WRAPS AROUND (so a requester behind the pointer is still reached). Drop either one and the fairness guarantee is gone. The tell for the first bug is a fairness failure that only appears under sustained, overlapping load — an arbiter that is fair when lightly probed and monopolized by one busy master under real traffic is a pointer that stopped one short, not a bandwidth problem. The tell for the second is an intermittent stall correlated with the pointer being ahead of the only active requests — a completeness gap where the wrap is missing. Two habits make both impossible, and they are identical across SystemVerilog, Verilog, and VHDL: always load the pointer with winner + 1 (modulo N), never the winner itself, and always pair the masked encoder with an unmasked fallback so the search wraps, then verify by driving all requesters continuously active and asserting a strict rotation with a bounded wait of N - 1.
8. Interview Q&A
9. Exercises
Design and reasoning exercises — no syntax drills. Each rehearses the rotating-pointer / masked-plus-unmasked reasoning and the bounded-wait discipline behind it.
Exercise 1 — Trace the rotation and prove the bound
For an N = 4 round-robin arbiter with ptr starting at 0 and all four requesters continuously asserting, write the grant vector and the next pointer for eight consecutive cycles. Confirm the grants form a strict rotation and that every requester is served within any window of 4 cycles. Then, keeping all four active, state the exact worst-case number of grants a requester can wait, and explain in one line why it cannot be more.
Exercise 2 — Where the unmasked fallback earns its keep
Take N = 4 with the pointer currently at ptr = 3 and a request vector where only req[0] and req[1] are asserting (both below the pointer). Work out what the masked request vector is, what the masked encoder produces, and what the arbiter must therefore do to issue a grant. State which requester wins and the next pointer value. Then describe, in two lines, exactly how the arbiter behaves if the unmasked fallback is omitted, and what the symptom would look like on a waveform.
Exercise 3 — Diagnose the unfair bus on paper
A bus arbiter is reported 'unfair under load': one master gets ~100% of grants when several masters are busy, but tests fine when probed one master at a time. You are shown that the pointer update is ptr <= win_idx. Explain precisely why this reproduces only under sustained multi-requester load, why a single-request test misses it, and what the pointer update should be. Then state the one testbench change that would have caught it before tape-out.
Exercise 4 — Choose and size the implementation
You must build a round-robin arbiter for (a) N = 4 masters on an ASIC where area is tight, and (b) N = 32 requesters on an FPGA where the grant path is showing up as the critical timing path. For each, choose between the masked+unmasked two-encoder form and the rotate-based single-encoder form, justify the choice in terms of encoder width versus barrel-rotator cost, and name one technique to shorten the grant path in case (b) and the latency cost it introduces.
10. Related Tutorials
Continue in RTL Design Patterns (sibling and forward links unlock as they ship):
- Fixed-Priority Arbiters — Chapter 10.1; the direct prerequisite — the single priority encoder round-robin rotates; this page is that arbiter made fair by a moving starting point, and the starvation it suffers is the problem round-robin solves.
- Weighted & LRU Arbitration — Chapter 10.3; the next step past equal-turn fairness — giving some requesters more turns (weighted) or ordering by least-recently-used, both built on the rotating-priority idea here.
- Request/Grant Handshake — Chapter 10.4; the handshake that wraps an arbiter's grant — how a granted requester holds and releases the resource, the protocol layer above this page's combinational grant.
- Fairness & Starvation — Chapter 10.5; the general treatment of the bounded-wait property this page provides by construction, across arbitration policies.
Backward / in-track dependencies:
- Priority Encoders — Chapter 1.4; the encoder at the heart of every arbiter — the 'first set bit wins' search that round-robin runs twice (masked and unmasked).
- Up/Down & Loadable Counters — Chapter 3.1; the pointer is a loadable counter — it loads
winner + 1on each grant rather than free-running, the exact distinction this page depends on. - Mod-N & Programmable Counters — Chapter 3.2; the modulo-N wrap (
winner == N-1 ? 0 : winner + 1) that keeps the pointer inside the ring — the same wrapping arithmetic taught here. - FSM Fundamentals — Chapter 4.1; the arbiter is a registered-state / combinational-output machine — the pointer is its state, the grant its output — so the same state-vs-output discipline applies.
- Moore vs Mealy — Chapter 4.2; the grant depends on both the pointer and the current requests, making it a Mealy-style output — the reason it is combinational while the pointer is registered.
- The valid/ready Handshake — Chapter 9.1; the handshake an arbitrated resource typically speaks — how the granted master transfers once it holds the resource.
- The RTL Design Mindset — Chapter 0.2; the State and Verification lenses this page applies — the pointer is the arbiter's state, and fairness is how you prove it correct over time.
- What Is an RTL Design Pattern? — Chapter 0.1; why round-robin earns the name 'pattern' — a recurring problem, a reusable form, a synthesis reality, and a signature failure.
Verilog v1 prerequisites (the grammar this pattern transcribes into):
- Case / If-Else Statements — the priority
if-chain /casebehind the priority encoders the arbiter runs. - Case Statements — the construct behind the pointer-update and grant-selection logic.
- Bitwise Operators — the AND mask (
req & mask), the lowest-set-bit isolation (v & (~v + 1)), and the reductions the flag logic uses. - Blocking and Non-Blocking Assignments — why the pointer updates with non-blocking (
<=) in its clocked process while the grant uses blocking (=) in the combinational block.
11. Summary
- Round-robin is fixed priority made fair by a rotating pointer. A fixed-priority arbiter always serves the same order, so a busy top-priority requester starves everyone below it. Round-robin keeps the same priority-encoder search but rotates where the search starts, so every requester is served within
Ngrants — a bounded wait, no starvation. - The pointer marks the search origin and must advance PAST the winner. After granting
i,ptr <= (i == N-1) ? 0 : i + 1— the winner drops to the lowest priority next round. Parking the pointer on the winner (ptr <= winner) makes it win forever and collapses round-robin back into fixed-priority starvation — the signature §7 bug that passes a one-grant test and fails under sustained load. - Masked + unmasked priority is the canonical structure. Mask off requests below the pointer (
req & (index >= ptr)) and run a priority encoder to grant the first request at or after the pointer (the common case); fall back to a second, unmasked priority encoder (resolving from index 0) when the masked set is empty — the wrap-around. Omitting the fallback yields no grant when only sub-pointer requests are active: a lost grant and a hang. An equivalent form rotatesreqbyptr, runs one encoder, and rotates the grant back. - One-hot grant, combinational; pointer, registered. The grant is a one-hot combinational function of the current requests and the registered pointer; the pointer is state updated on the clock to
winner + 1, and only on a grant (so an idle arbiter does not drift). That split avoids a combinational loop and keeps the arbiter pipeline- and reset-clean. - Verify fairness over time, not with a truth table. Drive all requesters continuously active and assert a strict rotation with each requester served exactly once per
Ngrants and a bounded wait ofN - 1; assertgrantis one-hot-or-zero every cycle; confirm a lone persistent requester wins every cycle and the unmasked fallback fires when only sub-pointer requests are active. The synthesis cost of that fairness over fixed priority is one extra encoder-equivalent plus the pointer register — self-checking clocked testbenches shown here in SystemVerilog, Verilog, and VHDL.