RTL Design Patterns · Chapter 10 · Arbitration
Weighted & LRU Arbitration
Round-robin gives every requester an equal turn, but equal is rarely what a real chip wants: a CPU port streaming cache misses deserves far more of the shared bus than a debug port poked once a second. Two refinements fix this. Weighted round-robin gives each requester a weight and lets it win in proportion, using a credit counter that starts at the weight, decrements on each grant, and refills once everyone has spent their credits. Least-recently-used ignores weights and instead grants whoever has waited longest, tracked with per-requester age counters so nobody starves. Both sit on top of a round-robin or priority core and only change which request it favors. This lesson builds both, and shows how a single wrong bookkeeping update silently breaks the bandwidth guarantee. Everything is coded in SystemVerilog, Verilog, and VHDL.
Intermediate14 min readRTL Design PatternsArbitrationWeighted Round-RobinLRUCredit CounterFairnessBandwidth Allocation
Chapter 10 · Section 10.3 · Arbitration
1. The Engineering Problem
You have a shared memory bus with four masters contending for it: a CPU streaming cache-line refills, a DMA engine moving a video frame, a crypto accelerator draining a queue, and a debug/trace port that occasionally reads a status register. In 10.2 you built a round-robin arbiter that resolved their contention fairly — it rotates a pointer so each master gets the next turn in strict rotation, and over time each of the four ends up with one quarter of the granted cycles. That was the right answer to the question round-robin asks: no starvation, everyone gets a turn.
But one quarter each is the wrong allocation for this system. The CPU and DMA are latency-critical and bandwidth-hungry; the debug port needs a sliver. Giving the debug port the same 25% the CPU gets is a design failure — you have starved the parts that matter to feed one that does not. What you actually need is proportional service: the CPU should win, say, four cycles for every one the debug port wins. Round-robin has no way to say that. Its fairness is equal by construction, and equal is a policy you did not choose.
There is a second, orthogonal need in the same system. Suppose all four masters have equal weight but their request patterns are bursty and uneven. You want a guarantee that whoever has waited longest gets served next — a recency policy — so a master that lost several rounds to a burst of others does not keep losing. That is not about weights at all; it is about age.
Both needs are refinements of the same arbiter, and neither is a new arbiter. You do not throw away round-robin; you layer a policy on top of it that changes which request it favors. The policy is stored in counters — a per-master credit counter for the weighted case, a per-master age counter for the recency case — and the entire correctness of the scheme lives in how those counters are updated on each grant. That update is the pattern.
// Four masters request the shared bus, every cycle, in parallel:
wire [3:0] req; // req[0]=CPU req[1]=DMA req[2]=crypto req[3]=debug
// Round-robin (10.2) grants each an EQUAL share => 25% each. WRONG allocation:
// the debug port gets as much bus as the CPU. Latency-critical masters starve.
// What we want instead is PROPORTIONAL service, set by a per-master WEIGHT:
wire [3:0] weight_cpu = 4'd4; // CPU may win up to 4 times per round
wire [3:0] weight_dma = 4'd4; // DMA likewise
wire [3:0] weight_crypto = 4'd2; // crypto half of that
wire [3:0] weight_debug = 4'd1; // debug a sliver
// Achieved bandwidth ratio should equal the WEIGHT ratio 4:4:2:1.
// ...or a RECENCY policy: grant whoever has waited LONGEST (max AGE), so no
// master that lost a burst keeps losing. Same core arbiter, different policy.2. Mental Model
3. Pattern Anatomy
Both refinements share one shape: a per-requester counter, an eligibility filter derived from that counter, an arbiter core that picks among the eligible requesters, and an update rule that adjusts the counters on each grant. The two policies differ only in what the counter means and how it updates.
Weighted round-robin — the credit counter. Each requester i has a weight Wi and a credit counter credit[i], initialized to Wi. On any cycle the eligible requesters are those that both assert req[i] and have credit[i] > 0. The arbiter core (a round-robin pointer, or a priority encoder) picks one eligible requester as the winner. On that grant, the winner's credit is decremented: credit[i] <= credit[i] - 1. A requester whose credit reaches zero is skipped — filtered out of eligibility — even while it keeps requesting, so it cannot win more than Wi times. The round ends, and credits refill to their weights, when no eligible requester remains — that is, when every requester that still wants the bus has spent all its credits. Refilling exactly then is what makes the allocation proportional: over one full round, requester i wins Wi times, so across many rounds its share of grants is Wi / sum(W). Set weights 4:4:2:1 and, over enough rounds, the grant counts converge to 4:4:2:1 — the achieved bandwidth ratio equals the weight ratio.
A close variant, deficit round-robin (DRR), generalizes this to variable-size transfers: instead of one credit per grant, each requester accumulates a quantum of credit per round and spends credit equal to the size of the packet it sends, carrying any leftover ("deficit") into the next round. WRR is DRR with a quantum of Wi and a fixed cost of one per grant; the credit-counter machinery is identical, which is why WRR is the pattern to learn first.
LRU — the age counter (or recency matrix). Each requester i has an age counter age[i]. While a requester waits (asserts req[i] but is not granted), its age increments; when it is granted, its age resets to zero — it becomes most-recently-used. The arbiter grants the requesting requester with the maximum age (the least-recently-used one still asking). This is a pure recency policy: the update rule (reset the served requester, age the waiters) is what keeps the ordering consistent and guarantees no one waits forever. An equivalent, area-cheaper-for-small-N formulation is an NxN 'more-recently-used-than' matrix: mru[i][j] = 1 means i was used more recently than j. On granting requester g, you set row g to zero and column g to one (g is now more-recently-used than everyone, and no one is more recent than g); the least-recently-used requester is the row that is all-zeros among those requesting. The matrix and the age-counter forms compute the same ordering; the matrix trades N counters for N² bits of state and an O(1) update.
Both layer on the core. Neither policy replaces the round-robin or priority arbiter — they change which request it favors. WRR narrows eligibility to credit-bearing requesters, then lets the core rotate among them; LRU orders the requesters by age, then hands ties to the core. This is why 10.3 is a supporting pattern on top of 10.2's flagship round-robin: same skeleton, one added counter and one added rule.
Weighted / LRU arbitration — a policy layered on an arbiter core
data flowTwo anatomy details close the section. First, the refill boundary is load-bearing: refill exactly when no requesting requester has credit left (the round is exhausted). Refill too early and a high-weight requester over-serves (it never runs out); never refill and every requester starves after its first Wi grants. Second, a weight of zero must be handled deliberately: a requester with Wi = 0 has no credits ever, so it is permanently skipped — sometimes intended (disable a port by setting its weight to 0), but a common accident that produces a requester whose grant count is stuck at zero. Treat Wi = 0 as "never serve," and make the refill logic robust to it so it does not stall the round.
4. Real RTL Implementation
This is the core of the page. We build three things — (a) a weighted round-robin arbiter (credit counter per requester, consumed on grant, zero-credit skipped, refilled on round exhaustion; parameterized N and weights), (b) the credit-not-consumed over-service bug vs the consume-on-grant fix, and (c) an LRU age-counter arbiter (grant max-age, reset on grant) — each with a synthesizable RTL block and a self-checking clocked testbench. (a) and (b) appear in SystemVerilog, Verilog, and VHDL; (c) is shown in SystemVerilog. The idea is identical across languages; seeing the credit and age bookkeeping in each is what makes the policy language-independent in your head.
One discipline runs through every block: the counter is updated on the same clock edge as the grant. The grant and the credit-decrement (or age-reset) are two halves of one atomic action — separate them and you get the §7 bug, where the grant happens but the credit does not move.
4a. Weighted round-robin — credit counter, consume-on-grant, refill on exhaustion
The arbiter keeps a credit counter per requester. Eligibility is req[i] & (credit[i] != 0). A priority pick over the eligible set chooses the winner (a real design rotates a round-robin pointer over the eligible set; we use a fixed priority pick over the eligible set here to keep the credit machinery in focus — the eligibility filter is the WRR contribution, and it composes with any core). On grant, the winner's credit is decremented. When no requester is eligible but some are still requesting, the round is exhausted and all credits refill to their weights.
module wrr_arb #(
parameter int N = 4 // number of requesters
)(
input logic clk,
input logic rst, // synchronous, active-high
input logic [N-1:0] req, // request lines, valid in parallel
input logic [3:0] weight [N], // per-requester WEIGHT (grants per round)
output logic [N-1:0] grant // one-hot winner this cycle
);
logic [3:0] credit [N]; // per-requester CREDIT counter
logic [N-1:0] eligible; // req AND has credit left
// Eligible = requesting AND still has credit. This is the WRR filter that
// sits in front of the arbiter core.
always_comb begin
for (int i = 0; i < N; i++)
eligible[i] = req[i] & (credit[i] != 4'd0);
end
// Priority pick over the ELIGIBLE set (stands in for the RR core). Lowest
// index among the eligible wins; grant is one-hot.
always_comb begin
grant = '0;
for (int i = 0; i < N; i++)
if (eligible[i] && grant == '0)
grant[i] = 1'b1;
end
// The POLICY update, clocked. On grant: spend the winner's credit. When the
// round is exhausted (someone still requests but nobody is eligible): refill.
always_ff @(posedge clk) begin
if (rst) begin
for (int i = 0; i < N; i++) credit[i] <= weight[i]; // start full
end else begin
if (grant != '0) begin
for (int i = 0; i < N; i++)
if (grant[i]) credit[i] <= credit[i] - 4'd1; // CONSUME on grant
end else if (|req) begin
// Some requester still wants the bus, but no one is eligible =>
// the round is exhausted. Refill every credit to its weight.
for (int i = 0; i < N; i++) credit[i] <= weight[i];
end
end
end
endmoduleThree lines carry the whole policy. eligible[i] = req[i] & (credit[i] != 0) is the filter — a requester out of credit is invisible to the core even while it requests. if (grant[i]) credit[i] <= credit[i] - 1 is the consume-on-grant rule — the winner pays one credit for the grant it just received. And the else if (|req) refill fires exactly when the round is exhausted (requests remain but nobody has credit), restoring each credit to its weight so the next round can allocate the same proportions again. The testbench runs the arbiter for many rounds with all requesters continuously requesting and counts each requester's grants — the invariant is that the grant counts land in the weight ratio and no requester is starved.
module wrr_arb_tb;
localparam int N = 4;
logic clk = 0, rst;
logic [N-1:0] req;
logic [3:0] weight [N];
logic [N-1:0] grant;
int grants [N]; // measured grant count per requester
int errors = 0;
wrr_arb #(.N(N)) dut (.clk(clk), .rst(rst), .req(req), .weight(weight), .grant(grant));
always #5 clk = ~clk; // 100 MHz clock
initial begin
weight[0]=4; weight[1]=4; weight[2]=2; weight[3]=1; // target ratio 4:4:2:1
foreach (grants[i]) grants[i] = 0;
req = '1; // every requester asks, every cycle
rst = 1; @(posedge clk); #1 rst = 0;
// Run enough cycles to cover many full rounds (round length = sum of weights = 11).
for (int c = 0; c < 220; c++) begin
@(posedge clk); #1;
for (int i = 0; i < N; i++) if (grant[i]) grants[i]++; // tally the winner
end
// Invariant 1: PROPORTIONAL bandwidth — grant counts are in the weight ratio.
// With continuous requests, grants[i] should be (weight[i]/sum) of the total.
// Check the ratios pairwise against the weights (allow a small rounding slack).
assert (grants[0] == grants[1])
else begin $error("equal weights 0,1 unequal: %0d vs %0d", grants[0], grants[1]); errors++; end
assert (grants[0] > grants[2] && grants[2] > grants[3])
else begin $error("ratio broken: g0=%0d g2=%0d g3=%0d", grants[0], grants[2], grants[3]); errors++; end
// weight 4 vs weight 1 => roughly 4x the grants (integer rounds => near-exact).
assert (grants[0] >= 3*grants[3])
else begin $error("weight-4 requester under 3x the weight-1: %0d vs %0d", grants[0], grants[3]); errors++; end
// Invariant 2: NO STARVATION — every requester with nonzero weight won at least once.
for (int i = 0; i < N; i++)
assert (grants[i] > 0) else begin $error("requester %0d starved", i); errors++; end
if (errors == 0) $display("PASS: WRR grant counts %0d:%0d:%0d:%0d track weights 4:4:2:1, no starvation",
grants[0], grants[1], grants[2], grants[3]);
else $display("FAIL: %0d bandwidth/starvation violations", errors);
$finish;
end
endmoduleThe Verilog form is identical in intent; the differences are reg/wire typing, flattened arrays (credit and weight packed into wide buses sliced with +:), and $display("FAIL") instead of assert. The credit machinery — consume on grant, refill on exhaustion — is the same.
module wrr_arb #(
parameter N = 4,
parameter CW = 4 // credit/weight bit-width
)(
input wire clk,
input wire rst,
input wire [N-1:0] req,
input wire [N*CW-1:0] weight_flat, // N weights packed, CW bits each
output reg [N-1:0] grant
);
reg [N*CW-1:0] credit_flat; // N credit counters, packed
reg [N-1:0] eligible;
integer i;
// Eligibility: requesting AND credit slice is nonzero.
always @(*) begin
for (i = 0; i < N; i = i + 1)
eligible[i] = req[i] & (credit_flat[i*CW +: CW] != {CW{1'b0}});
end
// Priority pick over the eligible set (stands in for the RR core).
always @(*) begin
grant = {N{1'b0}};
for (i = 0; i < N; i = i + 1)
if (eligible[i] && grant == {N{1'b0}})
grant[i] = 1'b1;
end
// Clocked policy update: consume winner's credit; refill on round exhaustion.
always @(posedge clk) begin
if (rst) begin
for (i = 0; i < N; i = i + 1)
credit_flat[i*CW +: CW] <= weight_flat[i*CW +: CW]; // start full
end else if (grant != {N{1'b0}}) begin
for (i = 0; i < N; i = i + 1)
if (grant[i])
credit_flat[i*CW +: CW] <= credit_flat[i*CW +: CW] - 1'b1; // CONSUME
end else if (|req) begin
for (i = 0; i < N; i = i + 1)
credit_flat[i*CW +: CW] <= weight_flat[i*CW +: CW]; // REFILL round
end
end
endmodule module wrr_arb_tb;
parameter N = 4;
parameter CW = 4;
reg clk, rst;
reg [N-1:0] req;
reg [N*CW-1:0] weight_flat;
wire [N-1:0] grant;
integer g0, g1, g2, g3;
integer c, errors;
wrr_arb #(.N(N), .CW(CW)) dut
(.clk(clk), .rst(rst), .req(req), .weight_flat(weight_flat), .grant(grant));
initial clk = 0;
always #5 clk = ~clk;
initial begin
errors = 0; g0=0; g1=0; g2=0; g3=0;
// weights 4:4:2:1 packed low-to-high: {debug=1, crypto=2, dma=4, cpu=4}
weight_flat = {4'd1, 4'd2, 4'd4, 4'd4};
req = {N{1'b1}}; // continuous requests
rst = 1; @(posedge clk); #1 rst = 0;
for (c = 0; c < 220; c = c + 1) begin
@(posedge clk); #1;
if (grant[0]) g0 = g0 + 1;
if (grant[1]) g1 = g1 + 1;
if (grant[2]) g2 = g2 + 1;
if (grant[3]) g3 = g3 + 1;
end
// Proportional bandwidth: equal weights equal, and the ratio ordering holds.
if (g0 !== g1) begin
$display("FAIL: equal weights unequal: g0=%0d g1=%0d", g0, g1); errors = errors + 1; end
if (!(g0 > g2 && g2 > g3)) begin
$display("FAIL: ratio broken: g0=%0d g2=%0d g3=%0d", g0, g2, g3); errors = errors + 1; end
if (!(g0 >= 3*g3)) begin
$display("FAIL: weight-4 requester under 3x weight-1: %0d vs %0d", g0, g3); errors = errors + 1; end
// No starvation:
if (g0==0 || g1==0 || g2==0 || g3==0) begin
$display("FAIL: a requester starved: %0d %0d %0d %0d", g0, g1, g2, g3); errors = errors + 1; end
if (errors == 0) $display("PASS: WRR counts %0d:%0d:%0d:%0d track weights 4:4:2:1", g0, g1, g2, g3);
else $display("FAIL: %0d violations", errors);
$finish;
end
endmoduleIn VHDL the credit and weight are numeric_std arrays of unsigned, eligibility is a std_logic_vector, and the clocked process performs the same consume-on-grant / refill-on-exhaustion update. The others => and array types make the parameterization clean.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity wrr_arb is
generic ( N : positive := 4; CW : positive := 4 );
port (
clk : in std_logic;
rst : in std_logic; -- synchronous, active-high
req : in std_logic_vector(N-1 downto 0);
weight : in std_logic_vector(N*CW-1 downto 0); -- N weights, CW bits each
grant : out std_logic_vector(N-1 downto 0)
);
end entity;
architecture rtl of wrr_arb is
type cnt_array is array (0 to N-1) of unsigned(CW-1 downto 0);
signal credit : cnt_array;
signal eligible : std_logic_vector(N-1 downto 0);
signal grant_i : std_logic_vector(N-1 downto 0);
-- Helper: read weight slice i as unsigned.
function wslice(w : std_logic_vector; i : integer) return unsigned is
begin
return unsigned(w((i+1)*CW-1 downto i*CW));
end function;
begin
-- Eligibility: requesting AND credit nonzero.
process (all)
begin
for i in 0 to N-1 loop
if req(i) = '1' and credit(i) /= 0 then
eligible(i) <= '1';
else
eligible(i) <= '0';
end if;
end loop;
end process;
-- Priority pick over the eligible set (stands in for the RR core).
process (all)
variable taken : boolean;
begin
grant_i <= (others => '0');
taken := false;
for i in 0 to N-1 loop
if eligible(i) = '1' and not taken then
grant_i(i) <= '1';
taken := true;
end if;
end loop;
end process;
grant <= grant_i;
-- Clocked policy update: CONSUME winner's credit; REFILL on round exhaustion.
process (clk)
begin
if rising_edge(clk) then
if rst = '1' then
for i in 0 to N-1 loop credit(i) <= wslice(weight, i); end loop; -- full
elsif grant_i /= (grant_i'range => '0') then
for i in 0 to N-1 loop
if grant_i(i) = '1' then
credit(i) <= credit(i) - 1; -- CONSUME
end if;
end loop;
elsif req /= (req'range => '0') then
for i in 0 to N-1 loop credit(i) <= wslice(weight, i); end loop; -- REFILL
end if;
end if;
end process;
end architecture; library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity wrr_arb_tb is
end entity;
architecture sim of wrr_arb_tb is
constant N : positive := 4;
constant CW : positive := 4;
signal clk : std_logic := '0';
signal rst : std_logic;
signal req : std_logic_vector(N-1 downto 0);
signal weight: std_logic_vector(N*CW-1 downto 0);
signal grant : std_logic_vector(N-1 downto 0);
begin
dut : entity work.wrr_arb
generic map (N => N, CW => CW)
port map (clk => clk, rst => rst, req => req, weight => weight, grant => grant);
clk <= not clk after 5 ns;
stim : process
type itab is array (0 to N-1) of integer;
variable g : itab := (others => 0);
begin
-- weights 4:4:2:1 packed low-to-high (slice 0 = cpu = 4).
weight <= std_logic_vector(to_unsigned(4, CW)) & -- slice 3 (debug=1)... build MSB..LSB
std_logic_vector(to_unsigned(2, CW)) &
std_logic_vector(to_unsigned(4, CW)) &
std_logic_vector(to_unsigned(1, CW));
-- NOTE: concatenation is MSB..LSB, so this packs slice3=4,slice2=2,slice1=4,slice0=1.
req <= (others => '1'); -- continuous requests
rst <= '1'; wait until rising_edge(clk); wait for 1 ns; rst <= '0';
for c in 0 to 219 loop
wait until rising_edge(clk); wait for 1 ns;
for i in 0 to N-1 loop
if grant(i) = '1' then g(i) := g(i) + 1; end if;
end loop;
end loop;
-- No starvation: every requester won at least once.
for i in 0 to N-1 loop
assert g(i) > 0 report "requester starved" severity error;
end loop;
-- Proportional: the two weight-4 requesters tie, and dominate the weight-1 one.
assert g(1) >= 3*g(0)
report "weight ratio broken: high-weight requester not >= 3x low-weight" severity error;
report "wrr self-check complete" severity note;
wait;
end process;
end architecture;4b. The credit-not-consumed over-service bug — buggy vs fixed, in all three HDLs
This is the signature failure, shown here as buggy vs fixed RTL in each language and dramatized in §7. The bug is the same everywhere: the arbiter grants but the clocked update forgets to decrement the winner's credit (or decrements the wrong requester's). The winner therefore never runs out of credit, is never filtered out, and keeps winning far beyond its weight — the bandwidth ratio silently diverges from the configured weights, starving the low-weight requesters. It passes a one-round eyeball test (the grant is correct) and fails a multi-round bandwidth check.
// BUGGY: on grant, the credit is NOT decremented (the update was left out).
// The winner's credit stays at its weight forever, so it is always eligible
// and always wins the priority pick => it over-serves; low-weight requesters
// starve. Every INDIVIDUAL grant still looks correct.
module wrr_update_bad #(parameter int N = 4)(
input logic clk, rst,
input logic [N-1:0] req,
input logic [3:0] weight [N],
output logic [N-1:0] grant
);
logic [3:0] credit [N];
logic [N-1:0] eligible;
always_comb for (int i=0;i<N;i++) eligible[i] = req[i] & (credit[i]!=0);
always_comb begin grant='0; for (int i=0;i<N;i++) if (eligible[i] && grant=='0) grant[i]=1'b1; end
always_ff @(posedge clk) begin
if (rst) for (int i=0;i<N;i++) credit[i] <= weight[i];
// BUG: no credit decrement on grant; only a refill that never triggers,
// because credit never reaches zero => the round never exhausts.
else if (grant=='0 && |req) for (int i=0;i<N;i++) credit[i] <= weight[i];
end
endmodule
// FIXED: decrement the winner's credit on every grant; the round then exhausts
// and refills, and each requester wins exactly WEIGHT times per round.
module wrr_update_good #(parameter int N = 4)(
input logic clk, rst,
input logic [N-1:0] req,
input logic [3:0] weight [N],
output logic [N-1:0] grant
);
logic [3:0] credit [N];
logic [N-1:0] eligible;
always_comb for (int i=0;i<N;i++) eligible[i] = req[i] & (credit[i]!=0);
always_comb begin grant='0; for (int i=0;i<N;i++) if (eligible[i] && grant=='0) grant[i]=1'b1; end
always_ff @(posedge clk) begin
if (rst) for (int i=0;i<N;i++) credit[i] <= weight[i];
else if (grant!='0) for (int i=0;i<N;i++) if (grant[i]) credit[i] <= credit[i]-4'd1; // CONSUME
else if (|req) for (int i=0;i<N;i++) credit[i] <= weight[i]; // REFILL
end
endmodule module wrr_bug_tb;
localparam int N = 4;
logic clk=0, rst;
logic [N-1:0] req;
logic [3:0] weight [N];
logic [N-1:0] grant;
int grants [N];
int errors = 0;
// Point at wrr_update_good to PASS; at wrr_update_bad to see over-service.
wrr_update_good dut (.clk(clk), .rst(rst), .req(req), .weight(weight), .grant(grant));
always #5 clk = ~clk;
initial begin
weight[0]=1; weight[1]=2; weight[2]=4; weight[3]=4; // requester 0 has the SMALLEST weight
foreach (grants[i]) grants[i]=0;
req = '1; rst = 1; @(posedge clk); #1 rst = 0;
for (int c=0;c<220;c++) begin @(posedge clk); #1; for (int i=0;i<N;i++) if (grant[i]) grants[i]++; end
// In the BUGGY DUT, requester 0 (lowest index, always eligible) wins nearly
// EVERY cycle despite weight 1 => this check FAILS, exposing over-service.
assert (grants[0] <= grants[3])
else begin $error("OVER-SERVICE: weight-1 requester 0 won %0d, weight-4 requester 3 won %0d",
grants[0], grants[3]); errors++; end
// And the high-weight requesters must not be starved:
assert (grants[3] > 0)
else begin $error("weight-4 requester STARVED (won 0)"); errors++; end
if (errors == 0) $display("PASS: bandwidth tracks weights (credit consumed on grant)");
else $display("FAIL: %0d over-service violations (credit not consumed?)", errors);
$finish;
end
endmoduleThe Verilog buggy/fixed pair tells the same story with flattened credit buses and always @(posedge clk).
// BUGGY: grant happens, credit never decremented => winner over-serves.
module wrr_update_bad #(parameter N=4, parameter CW=4)(
input wire clk, rst,
input wire [N-1:0] req,
input wire [N*CW-1:0] weight_flat,
output reg [N-1:0] grant
);
reg [N*CW-1:0] credit_flat; reg [N-1:0] eligible; integer i;
always @(*) for (i=0;i<N;i=i+1) eligible[i] = req[i] & (credit_flat[i*CW +: CW] != 0);
always @(*) begin grant={N{1'b0}}; for (i=0;i<N;i=i+1) if (eligible[i] && grant=={N{1'b0}}) grant[i]=1'b1; end
always @(posedge clk) begin
if (rst) for (i=0;i<N;i=i+1) credit_flat[i*CW +: CW] <= weight_flat[i*CW +: CW];
// BUG: no consume-on-grant; refill never triggers (credit never hits 0).
else if (grant=={N{1'b0}} && |req)
for (i=0;i<N;i=i+1) credit_flat[i*CW +: CW] <= weight_flat[i*CW +: CW];
end
endmodule
// FIXED: consume the winner's credit each grant; the round exhausts and refills.
module wrr_update_good #(parameter N=4, parameter CW=4)(
input wire clk, rst,
input wire [N-1:0] req,
input wire [N*CW-1:0] weight_flat,
output reg [N-1:0] grant
);
reg [N*CW-1:0] credit_flat; reg [N-1:0] eligible; integer i;
always @(*) for (i=0;i<N;i=i+1) eligible[i] = req[i] & (credit_flat[i*CW +: CW] != 0);
always @(*) begin grant={N{1'b0}}; for (i=0;i<N;i=i+1) if (eligible[i] && grant=={N{1'b0}}) grant[i]=1'b1; end
always @(posedge clk) begin
if (rst) for (i=0;i<N;i=i+1) credit_flat[i*CW +: CW] <= weight_flat[i*CW +: CW];
else if (grant!={N{1'b0}})
for (i=0;i<N;i=i+1) if (grant[i]) credit_flat[i*CW +: CW] <= credit_flat[i*CW +: CW]-1'b1; // CONSUME
else if (|req)
for (i=0;i<N;i=i+1) credit_flat[i*CW +: CW] <= weight_flat[i*CW +: CW]; // REFILL
end
endmodule module wrr_bug_tb;
parameter N=4, CW=4;
reg clk, rst; reg [N-1:0] req; reg [N*CW-1:0] weight_flat; wire [N-1:0] grant;
integer g0,g1,g2,g3,c,errors;
// Bind to _good to PASS; to _bad to observe over-service of requester 0.
wrr_update_good #(.N(N), .CW(CW)) dut
(.clk(clk), .rst(rst), .req(req), .weight_flat(weight_flat), .grant(grant));
initial clk=0; always #5 clk=~clk;
initial begin
errors=0; g0=0; g1=0; g2=0; g3=0;
weight_flat = {4'd4, 4'd4, 4'd2, 4'd1}; // slice0=1 (smallest), slice3=4
req = {N{1'b1}}; rst=1; @(posedge clk); #1 rst=0;
for (c=0;c<220;c=c+1) begin @(posedge clk); #1;
if (grant[0]) g0=g0+1; if (grant[1]) g1=g1+1;
if (grant[2]) g2=g2+1; if (grant[3]) g3=g3+1; end
// weight-1 requester 0 must NOT out-win weight-4 requester 3.
if (g0 > g3) begin
$display("FAIL: OVER-SERVICE g0(w=1)=%0d > g3(w=4)=%0d", g0, g3); errors=errors+1; end
if (g3 == 0) begin
$display("FAIL: weight-4 requester 3 STARVED"); errors=errors+1; end
if (errors==0) $display("PASS: bandwidth tracks weights (credit consumed)");
else $display("FAIL: %0d over-service violations", errors);
$finish;
end
endmoduleIn VHDL the same bug is the omission of the consume branch in the clocked process; the fix restores it.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
-- BUGGY: the clocked process refills but never CONSUMES on grant, so the
-- lowest-index requester is always eligible and over-serves.
entity wrr_update_bad is
generic ( N : positive := 4; CW : positive := 4 );
port ( clk, rst : in std_logic;
req : in std_logic_vector(N-1 downto 0);
weight : in std_logic_vector(N*CW-1 downto 0);
grant : out std_logic_vector(N-1 downto 0) );
end entity;
architecture rtl of wrr_update_bad is
type cnt_array is array (0 to N-1) of unsigned(CW-1 downto 0);
signal credit : cnt_array; signal elig, g_i : std_logic_vector(N-1 downto 0);
function ws(w : std_logic_vector; i : integer) return unsigned is
begin return unsigned(w((i+1)*CW-1 downto i*CW)); end function;
begin
process (all) begin
for i in 0 to N-1 loop
elig(i) <= '1' when (req(i)='1' and credit(i)/=0) else '0';
end loop;
end process;
process (all) variable t : boolean; begin
g_i <= (others=>'0'); t := false;
for i in 0 to N-1 loop
if elig(i)='1' and not t then g_i(i) <= '1'; t := true; end if;
end loop;
end process;
grant <= g_i;
process (clk) begin
if rising_edge(clk) then
if rst='1' then
for i in 0 to N-1 loop credit(i) <= ws(weight,i); end loop;
-- BUG: no consume-on-grant branch; refill never fires (credit stays > 0).
elsif g_i = (g_i'range => '0') and req /= (req'range => '0') then
for i in 0 to N-1 loop credit(i) <= ws(weight,i); end loop;
end if;
end if;
end process;
end architecture;
-- FIXED: add the consume-on-grant branch so credit is spent each grant.
entity wrr_update_good is
generic ( N : positive := 4; CW : positive := 4 );
port ( clk, rst : in std_logic;
req : in std_logic_vector(N-1 downto 0);
weight : in std_logic_vector(N*CW-1 downto 0);
grant : out std_logic_vector(N-1 downto 0) );
end entity;
architecture rtl of wrr_update_good is
type cnt_array is array (0 to N-1) of unsigned(CW-1 downto 0);
signal credit : cnt_array; signal elig, g_i : std_logic_vector(N-1 downto 0);
function ws(w : std_logic_vector; i : integer) return unsigned is
begin return unsigned(w((i+1)*CW-1 downto i*CW)); end function;
begin
process (all) begin
for i in 0 to N-1 loop
elig(i) <= '1' when (req(i)='1' and credit(i)/=0) else '0';
end loop;
end process;
process (all) variable t : boolean; begin
g_i <= (others=>'0'); t := false;
for i in 0 to N-1 loop
if elig(i)='1' and not t then g_i(i) <= '1'; t := true; end if;
end loop;
end process;
grant <= g_i;
process (clk) begin
if rising_edge(clk) then
if rst='1' then
for i in 0 to N-1 loop credit(i) <= ws(weight,i); end loop;
elsif g_i /= (g_i'range => '0') then
for i in 0 to N-1 loop
if g_i(i)='1' then credit(i) <= credit(i) - 1; end if; -- CONSUME
end loop;
elsif req /= (req'range => '0') then
for i in 0 to N-1 loop credit(i) <= ws(weight,i); end loop; -- REFILL
end if;
end if;
end process;
end architecture; library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity wrr_bug_tb is
end entity;
architecture sim of wrr_bug_tb is
constant N : positive := 4; constant CW : positive := 4;
signal clk : std_logic := '0'; signal rst : std_logic;
signal req : std_logic_vector(N-1 downto 0);
signal weight : std_logic_vector(N*CW-1 downto 0);
signal grant : std_logic_vector(N-1 downto 0);
begin
-- Bind to wrr_update_good to PASS; to _bad to observe over-service.
dut : entity work.wrr_update_good
generic map (N => N, CW => CW)
port map (clk => clk, rst => rst, req => req, weight => weight, grant => grant);
clk <= not clk after 5 ns;
stim : process
type itab is array (0 to N-1) of integer;
variable g : itab := (others => 0);
begin
-- slice0 = requester 0 = weight 1 (smallest); slice3 = weight 4.
weight <= std_logic_vector(to_unsigned(4, CW)) &
std_logic_vector(to_unsigned(4, CW)) &
std_logic_vector(to_unsigned(2, CW)) &
std_logic_vector(to_unsigned(1, CW));
req <= (others => '1'); rst <= '1';
wait until rising_edge(clk); wait for 1 ns; rst <= '0';
for c in 0 to 219 loop
wait until rising_edge(clk); wait for 1 ns;
for i in 0 to N-1 loop
if grant(i) = '1' then g(i) := g(i) + 1; end if;
end loop;
end loop;
-- weight-1 requester 0 must not out-win weight-4 requester 3.
assert g(0) <= g(3)
report "OVER-SERVICE: weight-1 requester out-won weight-4 requester (credit not consumed?)"
severity error;
assert g(3) > 0 report "weight-4 requester starved" severity error;
report "wrr_bug self-check complete" severity note;
wait;
end process;
end architecture;4c. LRU age-counter arbiter — grant max-age, reset on grant (the recency policy)
The recency refinement drops weights entirely. Each requester carries an age counter. On every cycle the arbiter grants the requesting requester with the largest age (least-recently-used); on that grant it resets the winner's age to zero (now most-recently-used) and increments the age of every other requester still waiting. The reset-on-grant is the LRU counterpart of WRR's consume-on-grant — omit it and the just-served requester keeps the largest age and is re-granted immediately, breaking the recency guarantee (that omission is the §6 LRU mistake).
module lru_arb #(
parameter int N = 4
)(
input logic clk,
input logic rst,
input logic [N-1:0] req, // requesters, valid in parallel
output logic [N-1:0] grant // one-hot: the oldest-waiting requester
);
logic [7:0] age [N]; // per-requester AGE counter
logic [$clog2(N)-1:0] oldest; // index of max-age requesting requester
logic any; // is any requester asking?
// Combinationally find the REQUESTING requester with the maximum age.
always_comb begin
oldest = '0; any = 1'b0;
for (int i = 0; i < N; i++) begin
if (req[i]) begin
if (!any || age[i] > age[oldest]) begin
oldest = i[$clog2(N)-1:0];
any = 1'b1;
end
end
end
grant = '0;
if (any) grant[oldest] = 1'b1; // grant the oldest waiter
end
// Clocked recency update: winner resets to MRU (age 0); other waiters age up.
always_ff @(posedge clk) begin
if (rst) begin
for (int i = 0; i < N; i++) age[i] <= i[7:0]; // distinct start ages break ties
end else if (any) begin
for (int i = 0; i < N; i++) begin
if (grant[i]) age[i] <= 8'd0; // served => MOST-recently-used
else if (req[i]) age[i] <= age[i] + 8'd1; // still waiting => age up
end
end
end
endmoduleThe clocked block is the whole policy: if (grant[i]) age[i] <= 0 makes the served requester most-recently-used, and else if (req[i]) age[i] <= age[i] + 1 ages everyone still waiting so their turn comes. The testbench forces two requesters to contend continuously and asserts the arbiter alternates between them — because whoever was just served is now youngest and cannot win again until the other has been served.
module lru_arb_tb;
localparam int N = 4;
logic clk=0, rst;
logic [N-1:0] req;
logic [N-1:0] grant;
int last = -1; // index granted on the previous cycle
int errors = 0;
lru_arb #(.N(N)) dut (.clk(clk), .rst(rst), .req(req), .grant(grant));
always #5 clk = ~clk;
function automatic int idx(input logic [N-1:0] oh);
idx = -1;
for (int i=0;i<N;i++) if (oh[i]) idx = i;
endfunction
initial begin
req = 4'b0011; // only requesters 0 and 1 contend, forever
rst = 1; @(posedge clk); #1 rst = 0;
for (int c = 0; c < 40; c++) begin
@(posedge clk); #1;
int g = idx(grant);
if (g != -1) begin
// RECENCY invariant: the requester served last cycle is now MRU, so it
// cannot be granted again while the other is still requesting.
assert (g != last)
else begin $error("LRU re-granted %0d two cycles in a row", g); errors++; end
last = g;
end
end
if (errors == 0) $display("PASS: LRU alternates 0,1 — no requester served twice running");
else $display("FAIL: %0d recency violations", errors);
$finish;
end
endmoduleAcross all three languages (and both policies) the lesson is one sentence: the grant is the easy half; the counter update on that grant IS the policy — spend a credit for WRR, reset an age for LRU — and the whole bandwidth or recency guarantee lives in getting that update right.
5. Verification Strategy
Weighted and LRU arbiters are clocked and their correctness is statistical over many cycles, not a single-cycle truth table. A grant that is correct this cycle tells you almost nothing; the guarantee is about the distribution of grants over a whole round or many rounds. So the verification is fundamentally a multi-round measurement.
- WRR — multi-round grant-count ratio (self-checking). Drive every requester with a continuous request, run for many full rounds (round length is
sum(weights)), and tally each requester's grant count. The invariant isgrants[i] / grants[j] == weight[i] / weight[j]— the achieved bandwidth ratio equals the weight ratio. The threewrr_arbtestbenches in §4a do exactly this: equal-weight requesters must tie, higher-weight requesters must win proportionally more, and (SV)assert (grants[0] >= 3*grants[3])pins the 4-vs-1 ratio. A single-cycle check would pass a broken arbiter; only the multi-round count exposes a wrong distribution. - WRR — no starvation. Every requester with a nonzero weight must win at least once per round. Assert
grants[i] > 0for alliwithweight[i] > 0(the §4a testbenches do). A requester that never wins signals either a refill that never fires or aweight = 0mis-set. - WRR — the over-service check (the §7 bug). Deliberately give the lowest-index requester the smallest weight and assert it does not out-win a high-weight requester. On the buggy consume-omitted DUT this fails: the always-eligible low-index requester wins nearly every cycle. This is the check that turns the silent bug into a loud failure, and it is the point of §4b.
- LRU — oldest-wins and reset-to-MRU. Two properties. First, the granted requester is always the oldest-waiting one still requesting (grant equals the max-age requester). Second, after a grant the served requester becomes most-recently-used and therefore cannot be re-granted until every other requester has been served. The §4c testbench forces two requesters to contend and asserts they alternate —
assert (g != last)— which is the reset-to-MRU guarantee made observable. - Refill / round-boundary coverage. Verify the refill fires exactly on round exhaustion: run past a round boundary and confirm the next round reproduces the same proportions. Under-testing here hides a refill that triggers too early (over-service) or never (starvation after the first round).
- Parameter-generic verification. Re-run with different
N, different weight sets (including a non-trivial ratio like 5:3:1), and aweight = 0requester (which must be permanently skipped without stalling the round). A scheme that looks right at 4:4:2:1 can be wrong at 5:3:1 if the refill boundary was tuned to a specific sum. - Expected waveform. For WRR, over one round the grant one-hot visits each requester exactly
weight[i]times before the credits refill; the visible signature of the §7 bug is a grant that sticks on one requester and never rotates. For LRU, the grant strictly alternates among contending requesters, and a requester served on cycletnever reappears ont+1while others still ask — a grant that repeats immediately is the missing reset-to-MRU.
6. Common Mistakes
Credit not decremented on grant (WRR over-service). The signature bug, dramatized in §7. The arbiter grants but the clocked update omits the credit decrement, so the winner's credit never falls, it stays eligible forever, and it wins far beyond its weight — the bandwidth ratio diverges and low-weight requesters starve. It passes a single-round eyeball test (each individual grant is legal) and only a multi-round bandwidth count catches it. Always pair the grant and the credit-consume in the same clocked update, and verify the grant ratio, not just grant legality.
Credits refilled too early, or never. The refill boundary is load-bearing. Refill before the round is exhausted (e.g. every cycle, or whenever any requester hits zero) and a high-weight requester's credit keeps topping up so it over-serves. Refill never (forget the exhaustion branch) and every requester dies after spending its first weight grants — the arbiter stops granting entirely once all credits are zero. Refill exactly when a request remains but nobody is eligible.
LRU update omitted — served requester not moved to MRU. The LRU counterpart of the credit bug. If, on a grant, you fail to reset the winner's age (or fail to update the recency matrix), the just-served requester keeps the largest age and is immediately re-granted next cycle — the arbiter locks onto one requester and the recency guarantee is gone. Reset the winner to most-recently-used on the same edge as the grant, and age the waiters up so their turn arrives.
Weight of zero causing a stuck skip. A requester with weight = 0 has no credits ever and is permanently ineligible. That is legitimate as a disable (turn a port off by zeroing its weight), but it is a frequent accident — a requester whose grant count is inexplicably zero. Two guards: treat weight = 0 as an intentional never-serve, and make the refill logic robust to it (an all-zero-weight active requester must not cause the round-exhaustion test to spin, since it can never become eligible even after a refill).
Confusing the arbiter core with the policy. WRR and LRU do not replace the round-robin or priority core underneath — they filter or order the requesters and hand the rest to that core. A common error is to re-implement tie-breaking inside the policy (two credit-bearing requesters at the same priority) and get it inconsistent with the core, producing subtle unfairness. Keep the layering clean: policy narrows eligibility; the core breaks the remaining ties exactly as 10.1/10.2 defined.
Overflowing the age or credit counter. Age counters increment while a requester waits; under a pathological pattern (a requester that requests forever but is starved by a bug elsewhere) an age counter can wrap, and a wrapped age looks young, so the starving requester is deprioritized further. Size the counters for the worst-case wait, or saturate them at max rather than wrapping.
7. DebugLab
The debug port that ate the bus — a WRR grant that never consumed its credit
The engineering lesson: weighted and LRU arbitration are a fairness POLICY layered on an arbiter core, and the policy lives entirely in the per-grant counter bookkeeping — a credit spent for WRR, an age reset for LRU. The grant can be perfectly correct on every single cycle while the distribution over many cycles is completely wrong, because the thing that shapes the distribution is the update, not the grant. The tell is a bug that only appears in aggregate ('the CPU takes everything over 10,000 cycles' while 'every individual grant looks legal'): a distribution failure that a single-cycle or single-round check cannot see. Two habits make it impossible, and they are identical across SystemVerilog, Verilog, and VHDL: update the policy counter on the same clock edge as the grant (consume a credit, reset an age — never issue a grant without its bookkeeping), and verify the grant distribution over many rounds — assert the bandwidth ratio equals the weight ratio, not merely that each grant is legal.
8. Interview Q&A
9. Exercises
Design and reasoning exercises — no syntax drills. Each rehearses the 'the counter update IS the policy' habit.
Exercise 1 — Set the weights for the SoC
Your shared bus has four masters: a CPU, a DMA engine, a crypto block, and a debug port. The architect wants the CPU and DMA to each get 40% of the bus, crypto 15%, and debug 5%. (a) Choose an integer weight for each master that realizes those proportions, and state the resulting round length (sum(weights)). (b) Explain, in terms of the credit counter, why the achieved bandwidth converges to those percentages over many rounds. (c) If the debug port is later disabled, what single change turns it off, and what does that do to the other three masters' shares?
Exercise 2 — Trace the over-service bug
Take the §7 buggy arbiter (grant issued, credit never consumed) with weights 4:4:2:1 and all four masters requesting continuously, using a lowest-index-wins core. (i) Write out the grant sequence for the first eight cycles. (ii) State precisely why the refill branch never fires. (iii) Now apply the fix and write the grant sequence for one full round, showing where each master's credit hits zero and where the refill occurs. Contrast the two grant distributions.
Exercise 3 — WRR vs LRU for the same system
Two teams must arbitrate the same four masters. Team A uses weighted round-robin with weights 3:3:2:2; Team B uses LRU with no weights. (i) For a workload where all four request continuously, describe how each arbiter distributes grants over 100 cycles. (ii) For a bursty workload where master 3 goes quiet for 50 cycles then requests hard, describe how each arbiter treats master 3 when it returns — and which policy guarantees it is served soonest. (iii) State one system requirement that makes WRR the right choice and one that makes LRU the right choice.
Exercise 4 — Design the LRU update on paper
You are implementing LRU for N = 4 requesters using per-requester age counters. (a) Write the exact update rule for the served requester and for the still-waiting requesters on a grant. (b) Explain what breaks if you forget to reset the served requester's age (relate it to the §6 mistake). (c) Now describe the equivalent NxN 'more-recently-used-than' matrix formulation: what does granting requester g do to row g and column g, and how do you read off the least-recently-used requester? State one reason you might prefer the matrix over the counters for small N.
10. Related Tutorials
Continue in RTL Design Patterns (forward links unlock as they ship):
- Round-Robin Arbiter — Chapter 10.2; the equal-share flagship core this page generalizes — weighted round-robin is round-robin with proportional turns instead of one turn each.
- Fixed-Priority Arbiter — Chapter 10.1; the simplest arbiter core, and the alternative tie-breaker the weighted/LRU policy can sit on top of.
- Request-Grant Handshake — Chapter 10; the req/grant contract every arbiter in this chapter speaks — how a master asks and learns it won.
- Arbiter Fairness — Chapter 10; the formal notions of fairness (no starvation, bounded wait, proportional share) these policies are engineered to satisfy.
Foundations this pattern is built from:
- Up/Down Counters — Chapter 3.1; the credit counter (decrement-to-zero) and the age counter (increment-while-waiting) are exactly these counters put to work as policy state.
- Modulo-N Counters — Chapter 3.2; the wrap-and-reload behaviour that the WRR round (spend credits, refill on exhaustion) mirrors at the policy level.
- Priority Encoders — Chapter 1.3; the combinational pick-one-winner core that the eligibility filter feeds — how a set of eligible requesters becomes a single one-hot grant.
Backward / method:
- The RTL Design Mindset — Chapter 0.2; the Interface → State → Datapath → Control → Verification lenses this page applied — the policy counters are state, the eligibility filter is control.
- What Is an RTL Design Pattern? — Chapter 0.1; why a fairness policy earns the name 'pattern' — a recurring need (proportional/recency service), a reusable form (a counter plus an update rule), and a signature failure (the un-consumed credit).
- Valid/Ready Handshake — Chapter 9.1; the backpressure contract on the granted data path, once the arbiter has chosen a winner.
Verilog v1 prerequisites (the grammar this pattern transcribes into):
- Case Statements — the construct behind the eligibility and refill decisions in the clocked update block.
- If-Else Statements — the priority-pick and the consume-vs-refill branch structure of the policy update.
- Blocking and Non-Blocking Assignments — why the clocked credit/age update uses non-blocking (
<=) while the combinational eligibility and grant logic uses blocking (=). - Arithmetic Operators — the decrement (
credit - 1), increment (age + 1), and comparison (credit != 0,age > age) that drive the counters.
11. Summary
- Above equal shares: two refinements. Round-robin gives every requester an equal turn; real systems need proportional shares (weighted round-robin) or a recency policy (LRU). Both are fairness policies layered on a round-robin or priority arbiter core — they change which request it favors, they do not replace it.
- Weighted round-robin = a credit counter. Each requester has a weight and a credit counter initialized to that weight. On a grant the winner spends one credit; a zero-credit requester is skipped even while requesting; when the round is exhausted (requests remain but nobody is eligible) all credits refill. Over a round each requester wins exactly
weighttimes, so the achieved bandwidth ratio equals the weight ratio. Deficit round-robin generalizes this to variable-size transfers with a size-aware spend. - LRU = an age counter. Each requester ages while waiting and resets to zero (most-recently-used) on service; the arbiter grants the oldest (max-age) requester, so no one starves. An equivalent NxN 'more-recently-used-than' matrix computes the same ordering with an O(1) update.
- The policy is the per-grant counter update. The grant itself is the easy half (the core does it); the policy is what happens to the counter on that grant — consume a credit for WRR, reset an age for LRU. Pair the update with the grant on the same clock edge, always.
- The signature failure is the un-consumed credit — and it is silent. Grant without decrementing the winner's credit and it over-serves forever, collapsing WRR into fixed priority while every individual grant still looks legal; the LRU counterpart is forgetting to reset the served requester to MRU. Only a multi-round bandwidth-ratio check (not a single-cycle grant check) exposes it — verified here with self-checking clocked testbenches in SystemVerilog, Verilog, and VHDL.