RTL Design Patterns · Chapter 10 · Arbitration
Fixed-Priority Arbiters
Sooner or later several blocks in your design want the same resource at once, and it can serve exactly one of them this cycle. Wiring them all together is contention, not sharing. You need an arbiter that looks at every request and picks one winner deterministically. The simplest one ranks the requesters by a fixed order and grants the highest-priority line that is actually asking, as a one-hot vector with exactly one bit set, or all zero when nobody asks. A fixed-priority arbiter is really a priority encoder over the request vector, its winner expressed as a one-hot grant instead of an index. This lesson covers the one-hot grant, the isolate-lowest-set-bit trick, held-grant versus per-cycle arbitration, and the double-grant mask bug that lets two masters drive a bus at once. It closes on the weakness fixed priority cannot escape, starvation, in SystemVerilog, Verilog, and VHDL.
Intermediate14 min readRTL Design PatternsArbiterFixed PriorityOne-Hot GrantStarvationBus Contention
Chapter 10 · Section 10.1 · Arbitration
1. The Engineering Problem
You are building a small SoC subsystem where four masters — a CPU, a DMA engine, a debug port, and a video refresh unit — all share a single write port into an on-chip SRAM. The SRAM has exactly one write port: one address, one data bus, one write-enable, and it can accept exactly one write per cycle. On a busy cycle the CPU wants to store a result, the DMA engine wants to drain its buffer, and the video unit wants to refresh a line — all in the same cycle. The port can serve one of them. Something has to choose.
This is the shape of almost every resource-sharing junction in a chip: several independent requesters, a resource that can serve exactly one per cycle, and a decision that must be made combinationally, every cycle, deterministically. A memory with one port. A bus with one set of address/data wires. A register file write port shared by two pipelines. A single floating-point unit shared by several issue slots. In every case the need is identical: look at who is requesting this cycle, pick exactly one winner, and tell the rest to wait.
You cannot just OR the requesters onto the port — driving one address bus from four masters at once is contention, not sharing; in real hardware two masters enabling the write at the same time is a short that resolves to X and corrupts the transfer. You need a structure that inspects the request vector (one bit per master, high when that master wants the port) and produces a grant that enables exactly one master — never two. The simplest such structure ranks the masters by a fixed order and always gives the port to the highest-ranked one that is asking. That is the fixed-priority arbiter, and it is the first arbitration pattern because it is nothing more than a priority encoder (Chapter 1.4) whose winner is expressed as a one-hot grant.
// Four masters can all request the SHARED SRAM write port in the SAME cycle:
wire [3:0] req; // req[0]=CPU req[1]=DMA req[2]=debug req[3]=video
// WRONG — OR every master onto the port: two writers = contention = X on the bus.
// assign wr_en = req[0] | req[1] | req[2] | req[3]; // multiple drivers!
// assign wr_addr = cpu_addr | dma_addr | dbg_addr | vid_addr; // corrupt
// RIGHT — an ARBITER: inspect req, emit a ONE-HOT grant that enables ONE master.
wire [3:0] grant; // exactly one bit set, or all-zero if req==0
// fixed priority: LOWEST index wins -> CPU (req[0]) beats DMA beats debug beats video
// grant = highest-priority ACTIVE request, expressed one-hot (this page builds it)2. Mental Model
3. Pattern Anatomy
A fixed-priority arbiter is built from two ports, one identity, three invariants, and one policy axis.
The two ports — request in, one-hot grant out. The input is an N-bit request vector req, one bit per requester, high on the cycles that requester wants the resource; many bits may be high at once. The output is an N-bit grant vector grant, in which exactly one bit is set (the winner) or no bit is set (nobody asked). grant[i] high means requester i owns the resource this cycle and its address/data/enable are steered onto the shared port (that steering is a one-hot mux, Chapter 1.1). There is no separate index output — the one-hot grant is the answer, and a decoder would turn a priority-encoder index into exactly this vector.
The isolate-lowest-set-bit identity. For LSB-priority (lowest index wins) there is a one-expression way to compute the one-hot grant directly from the request vector:
grant = req & (~req + 1) — equivalently grant = req & (-req) in two's complement.
Adding one to ~req propagates a carry up through the trailing zeros of req and stops at (and flips) its lowest set bit, so ~req + 1 agrees with req only from that lowest set bit upward — ANDing the two leaves only that one bit set. The result is a one-hot grant by construction: it is impossible for this expression to produce two bits, which is exactly the property an arbiter must guarantee. If req == 0 it yields 0 (no grant), which is the correct all-zero. This identity is the seed of the round-robin arbiter's masking logic, where you apply it to a rotated request vector.
The three invariants. A correct fixed-priority arbiter satisfies all three, every cycle, by construction:
- One-hot-or-zero.
granthas at most one bit set. Two bits is the signature failure (§7); zero bits is legal and means no request. - Granted-implies-requesting.
(grant & req) == grant— every granted line is also requesting. You never grant an idle master. - Highest-priority-active-wins. The granted bit is the highest-priority set bit of
reqin the documented direction — for LSB-priority, the lowest set bit; the winner matches a reference priority encoder (1.4) exactly.
The policy axis — combinational re-arbitration vs held grant. The same winner can be delivered two ways with very different behaviour:
- Combinational (per-cycle re-arbitration).
grantis a pure function ofreqthis cycle — recompute every cycle, no state. Simple and fast, and correct when a transfer completes in one cycle. But if a higher-priority master starts requesting mid-transfer, the grant switches away from the current winner immediately, which corrupts a multi-cycle burst. - Held grant (an FSM). For a multi-cycle transaction the arbiter must lock the grant to the winner until it releases the resource. That is a small state machine (Chapter 4.1): an IDLE state that arbitrates and a HELD state that keeps
grantfixed on the winner while it is busy, returning to IDLE (and re-arbitrating) only when the winner deasserts. This is where an arbiter stops being pure combinational logic and acquires state.
A fixed-priority arbiter — request in, one-hot grant out, two policies
data flowTwo facts close the anatomy. First, the one-hot invariant is not something you test for after the fact — it is something you build in. The isolate-lowest-set-bit expression (or a correct priority encoder) cannot emit two bits; a hand-rolled priority mask can, and that is the whole of §7. Choose a construction that is one-hot by definition and the invariant is free. Second, the winner index is a genuine don't-care when req == 0 — the all-zero grant is the correct output, and every consumer must gate its use of a master's address/data on that master's grant bit, never acting on stale data when its grant is low.
4. Real RTL Implementation
This is the core of the page. We build three patterns — (a) a parameterized N-requester fixed-priority arbiter (a one-hot grant via isolate-lowest-set-bit, with a clocked self-checking testbench that sweeps request patterns and asserts all three invariants), (b) the double-grant broken-mask bug (buggy vs fixed), and (c) a held-grant FSM variant that locks the grant across a multi-cycle transfer — and each is shown in SystemVerilog, Verilog, and VHDL, with both an RTL block and a self-checking testbench. The idea is identical in all three; the syntax differs, and seeing them side by side is what makes the pattern language-independent in your head.
One discipline runs through every RTL block: the grant is one-hot or zero by construction, and a granted line is always a requesting line. That is what keeps two masters off the bus, and it is exactly what pattern (b) violates.
4a. Parameterized N-requester fixed-priority arbiter — one-hot by construction
Start with the workhorse: an arbiter for any number of requesters, emitting a one-hot grant. We choose LSB-priority (lowest index wins) and document it, because it lets us compute the grant directly with the isolate-lowest-set-bit identity — one expression, provably one-hot, no loop or chain. The arbiter itself is combinational; the testbench is clocked so it exercises the invariants cycle by cycle under changing request patterns.
module fp_arb #(
parameter int N = 4 // number of requesters
)(
input logic [N-1:0] req, // multi-hot: any requesters may ask
output logic [N-1:0] grant // ONE-HOT: winner bit set, or all-zero
);
// LSB-PRIORITY: lowest index wins. Isolate the lowest set bit of req:
// ~req + 1 is the two's-complement negation -req; ANDing it with req leaves
// ONLY the lowest set bit -> a one-hot grant BY CONSTRUCTION (never two bits).
// req == 0 -> grant == 0 (no request, no grant) — the correct all-zero.
assign grant = req & (~req + 1'b1);
endmoduleThe single expression carries the whole engineering point. req & (~req + 1) is one-hot by construction — it is impossible for it to set two bits — so the arbiter's core invariant is not verified after the fact, it is guaranteed by the algebra. The testbench sweeps every request pattern (exhaustive, because a small N has only 2**N codes), on a clock, and every cycle asserts all three invariants against an independent reference model: grant is one-hot-or-zero, (grant & req) == grant, and the granted bit is the lowest set bit of req.
module fp_arb_tb;
localparam int N = 4;
logic clk = 0;
logic [N-1:0] req, grant;
int errors = 0;
always #5 clk = ~clk; // 100 MHz test clock
fp_arb #(.N(N)) dut (.req(req), .grant(grant));
// Independent reference: one-hot mask of the LOWEST set bit (LSB-priority).
function automatic logic [N-1:0] ref_grant(input logic [N-1:0] r);
for (int i = 0; i < N; i++) if (r[i]) return (1 << i); // lowest wins
return '0; // no request -> no grant
endfunction
initial begin
for (int code = 0; code < (1 << N); code++) begin // EXHAUSTIVE over req
@(negedge clk);
req = code[N-1:0];
@(posedge clk); #1; // sample after the edge settles
// Invariant 1: grant is one-hot OR zero — never two masters driving.
assert ($onehot0(grant))
else begin $error("req=%b grant=%b NOT one-hot-or-zero", req, grant); errors++; end
// Invariant 2: a granted line is always a requesting line.
assert ((grant & req) == grant)
else begin $error("req=%b grant=%b grants a non-requester", req, grant); errors++; end
// Invariant 3: the winner is the highest-priority (lowest-index) request.
assert (grant === ref_grant(req))
else begin $error("req=%b grant=%b exp=%b", req, grant, ref_grant(req)); errors++; end
end
if (errors == 0) $display("PASS: fp_arb one-hot + granted-implies-req + lowest-wins on all %0d codes", 1<<N);
else $display("FAIL: %0d mismatches", errors);
$finish;
end
endmoduleThe Verilog form is identical in intent; the differences are wire/reg typing and that Verilog has no $onehot0, so the testbench checks one-hot-or-zero with the classic (grant & (grant-1)) == 0 reduction (true for zero and for any single bit). The req & (~req + 1) expression is the same, so the grant is one-hot by construction in Verilog too.
module fp_arb #(
parameter N = 4
)(
input wire [N-1:0] req,
output wire [N-1:0] grant
);
// LSB-priority one-hot grant: req & -req isolates the lowest set bit.
// One-hot BY CONSTRUCTION; req==0 -> grant==0. No loop, no priority chain.
assign grant = req & (~req + 1'b1);
endmodule module fp_arb_tb;
parameter N = 4;
reg clk;
reg [N-1:0] req;
wire [N-1:0] grant;
reg [N-1:0] exp;
integer code, i, errors;
reg found;
fp_arb #(.N(N)) dut (.req(req), .grant(grant));
initial begin clk = 0; forever #5 clk = ~clk; end // test clock
initial begin
errors = 0;
for (code = 0; code < (1 << N); code = code + 1) begin // EXHAUSTIVE over req
@(negedge clk);
req = code[N-1:0];
@(posedge clk); #1;
// Independent reference: one-hot mask of the lowest set bit.
exp = {N{1'b0}};
found = 1'b0;
for (i = 0; i < N; i = i + 1)
if (req[i] && !found) begin exp = (1 << i); found = 1'b1; end
// Invariant 1: one-hot OR zero.
if ((grant & (grant - 1)) != 0)
begin $display("FAIL: req=%b grant=%b not one-hot-or-zero", req, grant); errors=errors+1; end
// Invariant 2: granted-implies-requesting.
if ((grant & req) !== grant)
begin $display("FAIL: req=%b grant=%b grants a non-requester", req, grant); errors=errors+1; end
// Invariant 3: lowest-index request wins.
if (grant !== exp)
begin $display("FAIL: req=%b grant=%b exp=%b", req, grant, exp); errors=errors+1; end
end
if (errors == 0) $display("PASS: fp_arb one-hot + granted-implies-req + lowest-wins on all codes");
else $display("FAIL: %0d mismatches", errors);
$finish;
end
endmoduleIn VHDL the same identity is req and std_logic_vector(unsigned(not req) + 1) — the numeric_std way to write ~req + 1 on a std_logic_vector. The grant is a concurrent assignment, one-hot by construction exactly as in the other languages; to_integer/to_unsigned and the numeric_std arithmetic are how VHDL expresses the two's-complement negation.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity fp_arb is
generic ( N : positive := 4 ); -- generic == Verilog parameter
port (
req : in std_logic_vector(N-1 downto 0); -- multi-hot allowed
grant : out std_logic_vector(N-1 downto 0) -- one-hot or all-zero
);
end entity;
architecture rtl of fp_arb is
begin
-- LSB-priority one-hot grant. unsigned(not req) + 1 is the two's-complement
-- negation -req; ANDing with req isolates the LOWEST set bit -> one-hot BY
-- CONSTRUCTION. req = 0 -> grant = 0 (no request, no grant).
grant <= req and std_logic_vector(unsigned(not req) + 1);
end architecture; library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity fp_arb_tb is
end entity;
architecture sim of fp_arb_tb is
constant N : positive := 4;
signal clk : std_logic := '0';
signal req : std_logic_vector(N-1 downto 0);
signal grant : std_logic_vector(N-1 downto 0);
-- Independent reference: one-hot mask of the lowest set bit (LSB-priority).
function ref_grant (r : std_logic_vector) return std_logic_vector is
variable g : std_logic_vector(r'range) := (others => '0');
begin
for i in r'low to r'high loop
if r(i) = '1' then g(i) := '1'; return g; end if; -- lowest wins
end loop;
return g; -- no request -> zero
end function;
-- Count set bits to check one-hot-or-zero (0 or 1 bits allowed).
function popcount (v : std_logic_vector) return natural is
variable c : natural := 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
clk <= not clk after 5 ns; -- test clock
dut : entity work.fp_arb generic map (N => N) port map (req => req, grant => grant);
stim : process
begin
for code in 0 to (2**N - 1) loop -- EXHAUSTIVE over req
wait until falling_edge(clk);
req <= std_logic_vector(to_unsigned(code, N));
wait until rising_edge(clk);
wait for 1 ns;
-- Invariant 1: one-hot or zero (at most one master driving).
assert popcount(grant) <= 1
report "grant not one-hot-or-zero (double grant!)" severity error;
-- Invariant 2: granted-implies-requesting.
assert (grant and req) = grant
report "arbiter granted a non-requester" severity error;
-- Invariant 3: lowest-index request wins.
assert grant = ref_grant(req)
report "arbiter did not grant the highest-priority requester" severity error;
end loop;
report "fp_arb self-check complete" severity note;
wait;
end process;
end architecture;4b. The double-grant broken-mask bug — buggy vs fixed, in all three HDLs
Pattern (b) is the signature failure, shown here as buggy vs fixed RTL in each language, then dramatized narratively in §7. The bug is the same everywhere: instead of a construction that is one-hot by definition, an engineer hand-builds a priority mask — the idea is "grant a line only if no higher-priority line is requesting" — but gets the mask wrong so that under some request patterns two grant bits assert at once. A common form is an off-by-one that only blocks the immediately higher line (grant[i] = req[i] & ~req[i-1]) instead of all higher lines, so two non-adjacent requesters can both win. Two grants means two masters drive the shared bus → contention.
// BUGGY: the mask only kills the ADJACENT lower-priority line, not ALL lower ones.
// grant[i] = req[i] & ~req[i-1] blocks i only when i-1 asks — so req=4'b0101
// grants BOTH bit 0 (nothing below it) AND bit 2 (bit 1 is idle) -> TWO grants.
module fp_arb_bad #(
parameter int N = 4
)(
input logic [N-1:0] req,
output logic [N-1:0] grant
);
always_comb begin
grant = '0;
for (int i = 0; i < N; i++) begin
if (i == 0) grant[i] = req[i]; // bit 0 always wins if asking
else grant[i] = req[i] & ~req[i-1]; // BUG: only blocks the ADJACENT line
end
end
endmodule
// FIXED: isolate the lowest set bit — one-hot BY CONSTRUCTION, cannot emit two bits.
module fp_arb_good #(
parameter int N = 4
)(
input logic [N-1:0] req,
output logic [N-1:0] grant
);
assign grant = req & (~req + 1'b1); // provably one-hot or zero
endmodule module fp_arb_bug_tb;
localparam int N = 4;
logic [N-1:0] req, grant;
int errors = 0;
// Bind to fp_arb_good to PASS; to fp_arb_bad to SEE the double grant fire.
fp_arb_good #(.N(N)) dut (.req(req), .grant(grant));
initial begin
// Single requests: even the buggy mask looks fine here (the unit-test trap).
for (int i = 0; i < N; i++) begin
req = (1 << i); #1;
assert ($onehot(grant) && grant == (1 << i))
else begin $error("single req %0d: grant=%b", i, grant); errors++; end
end
// The pattern that breaks the leaky mask: bits 0 and 2 set, bit 1 idle.
req = 4'b0101; #1; // CPU (0) and debug (2) both ask
assert ($onehot0(grant)) // MUST be one-hot-or-zero
else begin $error("req=0101 grant=%b DOUBLE GRANT -> bus contention", grant); errors++; end
assert (grant == 4'b0001) // LSB-priority: only bit 0 wins
else begin $error("req=0101 grant=%b exp=0001", grant); errors++; end
if (errors == 0) $display("PASS: grant stays one-hot even when two masters request");
else $display("FAIL: %0d mismatches (double grant on multi-request)", errors);
$finish;
end
endmoduleThe Verilog buggy/fixed pair is the same story with reg outputs and an always @(*) mask. The whole bug is that req[i] & ~req[i-1] only blocks the adjacent line, so 4'b0101 — two masters with an idle line between them — produces two grants; the fixed version's req & -req cannot.
// BUGGY: only blocks the adjacent lower line -> non-adjacent requesters double-grant.
module fp_arb_bad #(
parameter N = 4
)(
input wire [N-1:0] req,
output reg [N-1:0] grant
);
integer i;
always @(*) begin
grant = {N{1'b0}};
for (i = 0; i < N; i = i + 1) begin
if (i == 0) grant[i] = req[i];
else grant[i] = req[i] & ~req[i-1]; // BUG: adjacent-only kill
end
end
endmodule
// FIXED: one-hot by construction.
module fp_arb_good #(
parameter N = 4
)(
input wire [N-1:0] req,
output wire [N-1:0] grant
);
assign grant = req & (~req + 1'b1); // provably one-hot or zero
endmodule module fp_arb_bug_tb;
parameter N = 4;
reg [N-1:0] req;
wire [N-1:0] grant;
integer i, errors;
// Bind to fp_arb_good to PASS; to fp_arb_bad to observe the double grant.
fp_arb_good #(.N(N)) dut (.req(req), .grant(grant));
initial begin
errors = 0;
for (i = 0; i < N; i = i + 1) begin // single requests: buggy mask looks OK
req = (1 << i); #1;
if (grant !== (1 << i)) begin
$display("FAIL: single req %0d grant=%b", i, grant); errors = errors + 1;
end
end
req = 4'b0101; #1; // bits 0 and 2 set, bit 1 idle
// One-hot-or-zero check: (g & (g-1)) must be 0.
if ((grant & (grant - 1)) != 0) begin
$display("FAIL: req=0101 grant=%b DOUBLE GRANT -> bus contention", grant);
errors = errors + 1;
end
if (grant !== 4'b0001) begin // LSB-priority winner is bit 0 only
$display("FAIL: req=0101 grant=%b exp=0001", grant); errors = errors + 1;
end
if (errors == 0) $display("PASS: grant one-hot even when two masters request");
else $display("FAIL: %0d mismatches", errors);
$finish;
end
endmoduleIn VHDL the same bug is a for loop that ANDs each request with the negation of only its adjacent lower neighbour. The fixed version replaces the whole loop with the req and -req identity, which cannot produce two set bits.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
-- BUGGY: blocks only the adjacent lower line -> non-adjacent pairs double-grant.
entity fp_arb_bad is
generic ( N : positive := 4 );
port (
req : in std_logic_vector(N-1 downto 0);
grant : out std_logic_vector(N-1 downto 0)
);
end entity;
architecture rtl of fp_arb_bad is
begin
process (all)
variable g : std_logic_vector(N-1 downto 0);
begin
g := (others => '0');
for i in 0 to N-1 loop
if i = 0 then g(i) := req(i);
else g(i) := req(i) and not req(i-1); -- BUG: adjacent-only kill
end if;
end loop;
grant <= g;
end process;
end architecture;
-- FIXED: isolate the lowest set bit -> one-hot by construction.
entity fp_arb_good is
generic ( N : positive := 4 );
port (
req : in std_logic_vector(N-1 downto 0);
grant : out std_logic_vector(N-1 downto 0)
);
end entity;
architecture rtl of fp_arb_good is
begin
grant <= req and std_logic_vector(unsigned(not req) + 1); -- provably one-hot or zero
end architecture; library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity fp_arb_bug_tb is
end entity;
architecture sim of fp_arb_bug_tb is
constant N : positive := 4;
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 natural is
variable c : natural := 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
-- Bind to fp_arb_good to PASS; to fp_arb_bad to see popcount = 2 (double grant).
dut : entity work.fp_arb_good generic map (N => N) port map (req => req, grant => grant);
stim : process
begin
for i in 0 to N-1 loop -- single requests: buggy mask "OK"
req <= (others => '0');
req(i) <= '1';
wait for 1 ns;
assert popcount(grant) = 1
report "single request did not produce exactly one grant" severity error;
end loop;
req <= "0101"; -- bits 0 and 2, bit 1 idle
wait for 1 ns;
assert popcount(grant) <= 1
report "req=0101 DOUBLE GRANT -> two masters drive the bus" severity error;
assert grant = "0001" -- LSB-priority: only bit 0
report "req=0101 winner should be bit 0 (lowest index)" severity error;
report "fp_arb_bug self-check complete" severity note;
wait;
end process;
end architecture;4c. Held-grant FSM variant — locking the grant across a multi-cycle transfer
Combinational re-arbitration is correct only when a transaction finishes in one cycle. For a multi-cycle burst the arbiter must hold the grant on the winner until it releases the resource, or a higher-priority latecomer would steal the bus mid-transfer. That requires state — a two-state FSM (Chapter 4.1): IDLE arbitrates combinationally and captures the winner; HELD freezes grant on that winner while it stays busy and returns to IDLE (re-arbitrating) only when the winner deasserts its request. Reset is synchronous, active-high, and clears the grant.
module fp_arb_hold #(
parameter int N = 4
)(
input logic clk,
input logic rst, // synchronous, active-high
input logic [N-1:0] req,
output logic [N-1:0] grant // one-hot, HELD across the transfer
);
typedef enum logic {IDLE, HELD} state_t;
state_t state, next;
logic [N-1:0] pick, grant_q;
// Combinational fixed-priority pick (isolate lowest set bit) — same core as 4a.
assign pick = req & (~req + 1'b1);
always_comb begin
next = state;
unique case (state)
IDLE: if (|req) next = HELD; // someone asked -> lock a winner
HELD: if (!(grant_q & req)) next = IDLE; // winner dropped its req -> re-arbitrate
endcase
end
always_ff @(posedge clk) begin
if (rst) begin
state <= IDLE;
grant_q <= '0;
end else begin
state <= next;
// Latch the winner on entering HELD; hold it while busy; clear when idle.
if (state == IDLE && |req) grant_q <= pick; // capture this cycle's winner
else if (state == HELD && !(grant_q & req)) grant_q <= '0; // release
end
end
assign grant = grant_q; // grant is the HELD one-hot vector
endmoduleThe held grant is still one-hot: pick is one-hot by construction and grant_q only ever holds a captured pick or zero. The self-checking testbench drives a multi-cycle request from a low-priority master, then raises a higher-priority request mid-transfer, and asserts the grant does not switch away until the original winner releases — the property that a combinational arbiter would violate.
module fp_arb_hold_tb;
localparam int N = 4;
logic clk = 0, rst;
logic [N-1:0] req, grant;
int errors = 0;
always #5 clk = ~clk;
fp_arb_hold #(.N(N)) dut (.clk(clk), .rst(rst), .req(req), .grant(grant));
initial begin
rst = 1; req = '0; @(posedge clk); #1;
rst = 0;
// Low-priority master 2 starts a multi-cycle transfer (nobody else asking).
req = 4'b0100; @(posedge clk); #1;
assert (grant == 4'b0100) else begin $error("start: grant=%b exp=0100", grant); errors++; end
// Mid-transfer, higher-priority master 0 also requests — but master 2 is still busy.
req = 4'b0101; repeat (2) @(posedge clk); #1;
// HELD: the grant must STAY on master 2, not jump to the higher-priority master 0.
assert (grant == 4'b0100)
else begin $error("held grant stolen: grant=%b exp=0100", grant); errors++; end
// Master 2 finishes and drops its request; now master 0 may win.
req = 4'b0001; repeat (2) @(posedge clk); #1;
assert (grant == 4'b0001)
else begin $error("after release: grant=%b exp=0001", grant); errors++; end
if (errors == 0) $display("PASS: held grant survives a higher-priority latecomer");
else $display("FAIL: %0d mismatches", errors);
$finish;
end
endmoduleThe Verilog held-grant FSM uses an explicit state register and always @(posedge clk); the engineering content is identical — capture the one-hot pick on entering HELD, hold until the winner drops req.
module fp_arb_hold #(
parameter N = 4
)(
input wire clk,
input wire rst, // synchronous, active-high
input wire [N-1:0] req,
output wire [N-1:0] grant
);
localparam IDLE = 1'b0, HELD = 1'b1;
reg state;
reg [N-1:0] grant_q;
wire [N-1:0] pick = req & (~req + 1'b1); // combinational fixed-priority pick
always @(posedge clk) begin
if (rst) begin
state <= IDLE;
grant_q <= {N{1'b0}};
end else begin
case (state)
IDLE: if (|req) begin
grant_q <= pick; // capture this cycle's winner
state <= HELD;
end
HELD: if ((grant_q & req) == 0) begin // winner dropped its request
grant_q <= {N{1'b0}}; // release the bus
state <= IDLE;
end
endcase
end
end
assign grant = grant_q; // HELD one-hot grant
endmodule module fp_arb_hold_tb;
parameter N = 4;
reg clk, rst;
reg [N-1:0] req;
wire [N-1:0] grant;
integer errors;
fp_arb_hold #(.N(N)) dut (.clk(clk), .rst(rst), .req(req), .grant(grant));
initial begin clk = 0; forever #5 clk = ~clk; end
initial begin
errors = 0;
rst = 1; req = {N{1'b0}}; @(posedge clk); #1;
rst = 0;
req = 4'b0100; @(posedge clk); #1; // master 2 starts a burst
if (grant !== 4'b0100) begin $display("FAIL: start grant=%b", grant); errors=errors+1; end
req = 4'b0101; repeat (2) @(posedge clk); #1; // master 0 (higher) also asks
if (grant !== 4'b0100) begin // grant must NOT be stolen
$display("FAIL: held grant stolen grant=%b exp=0100", grant); errors=errors+1;
end
req = 4'b0001; repeat (2) @(posedge clk); #1; // master 2 releases
if (grant !== 4'b0001) begin
$display("FAIL: after release grant=%b exp=0001", grant); errors=errors+1;
end
if (errors == 0) $display("PASS: held grant survives a higher-priority latecomer");
else $display("FAIL: %0d mismatches", errors);
$finish;
end
endmoduleIn VHDL the held-grant FSM is a clocked process (clk) with a state_t enumeration; the capture-hold-release logic mirrors the other two languages exactly, and req = 0 / grant and req are the release conditions.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity fp_arb_hold 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)
);
end entity;
architecture rtl of fp_arb_hold is
type state_t is (IDLE, HELD);
signal state : state_t := IDLE;
signal grant_q : std_logic_vector(N-1 downto 0) := (others => '0');
signal pick : std_logic_vector(N-1 downto 0);
begin
-- Combinational fixed-priority pick: isolate the lowest set bit (one-hot).
pick <= req and std_logic_vector(unsigned(not req) + 1);
process (clk)
begin
if rising_edge(clk) then
if rst = '1' then
state <= IDLE;
grant_q <= (others => '0');
else
case state is
when IDLE =>
if unsigned(req) /= 0 then
grant_q <= pick; -- capture the winner
state <= HELD;
end if;
when HELD =>
if unsigned(grant_q and req) = 0 then -- winner released
grant_q <= (others => '0');
state <= IDLE;
end if;
end case;
end if;
end if;
end process;
grant <= grant_q; -- HELD one-hot grant
end architecture; library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity fp_arb_hold_tb is
end entity;
architecture sim of fp_arb_hold_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
clk <= not clk after 5 ns;
dut : entity work.fp_arb_hold generic map (N => N)
port map (clk => clk, rst => rst, req => req, grant => grant);
stim : process
begin
rst <= '1'; req <= (others => '0');
wait until rising_edge(clk); wait for 1 ns;
rst <= '0';
req <= "0100"; -- master 2 starts a burst
wait until rising_edge(clk); wait for 1 ns;
assert grant = "0100" report "start: grant /= 0100" severity error;
req <= "0101"; -- master 0 (higher) also requests
wait until rising_edge(clk); wait until rising_edge(clk); wait for 1 ns;
assert grant = "0100" -- must NOT be preempted
report "held grant stolen by higher-priority latecomer" severity error;
req <= "0001"; -- master 2 releases
wait until rising_edge(clk); wait until rising_edge(clk); wait for 1 ns;
assert grant = "0001" report "after release: grant /= 0001" severity error;
report "fp_arb_hold self-check complete" severity note;
wait;
end process;
end architecture;Across all three languages the lesson is one sentence: a fixed-priority arbiter's grant must be one-hot by construction — isolate the lowest set bit (or use a correct priority encoder), and hold it in an FSM when a transfer spans multiple cycles.
5. Verification Strategy
A combinational fixed-priority arbiter is a truth table over the request vector, and for a small N that table is small enough to check exhaustively — the held-grant variant adds temporal properties on top. Three invariants together capture a correct arbiter:
(1)
grantis one-hot or zero — at most one requester is granted, so at most one master ever drives the shared resource. (2)(grant & req) == grant— a granted line is always a requesting line. (3) The granted bit is the highest-priority set bit ofreqin the documented direction — for LSB-priority, the lowest set bit, matching a reference priority encoder.
Everything below is those three invariants, made checkable, and it maps directly onto the testbenches in §4.
- Exhaustive
reqsweep (self-checking, clocked). For anN-bit arbiter, drive every request pattern from0to2**N - 1and, for each, assert all three invariants against an independent reference model. The reference computes the one-hot mask of the highest-priority set bit separately from the DUT — never by reading the DUT's own output. Because there are only2**Ncodes, this is complete for a smallN, not sampled. The threefp_arbtestbenches in §4a do exactly this on a clock: SVassert ($onehot0(grant))plus the reference compare, Verilog(grant & (grant-1)) == 0plusif (grant !== exp) $display("FAIL…"), VHDLassert popcount(grant) <= 1andassert grant = ref_grant(req) report … severity error. - The one-hot-or-zero invariant, checked directly. State it as a property that holds every cycle:
granthas at most one bit set. Check it with$onehot0(SV), the(g & (g-1)) == 0reduction (Verilog), or a bit-count<= 1(VHDL) — computed fromgrantalone. This is the invariant the whole page turns on, and the only one the double-grant bug (§4b, §7) violates: a leaky mask passes every single-request test and fails the moment two requesters assert, so a directed two-requester vector (like4'b0101, non-adjacent bits) is the named case that catches it. - The granted-implies-requesting corner. Assert
(grant & req) == granton every vector, and specifically drivereq == 0and confirmgrant == 0— an arbiter must never grant an idle master, and the all-zero request is the corner where "grant nobody" must hold. A design that grants a phantom winner on an idle bus fails exactly here. - The priority-direction check (single-bit and adjacent-bit cases). Verify the ordering deliberately: drive each single-bit vector (
req = 1 << kfor everyk) and confirmgrant == 1 << k— this proves the arbiter is correct when only one master asks. Then drive adjacent and non-adjacent multi-request pairs and confirm the winner is the one the documented direction picks (the lowest index for LSB-priority). Multi-request pairs are where a wrong direction or a leaky mask shows up — the single-bit tests can't see either. - The held-grant temporal properties (clocked). For the FSM variant, the invariants become temporal: once granted, the grant must remain on the winner until it releases, and a higher-priority request arriving mid-transfer must not preempt it. The §4c testbenches drive a low-priority multi-cycle transfer, raise a higher-priority request in the middle, and assert the grant does not move until the original winner drops
req— the property a purely combinational arbiter would fail. Also check that after release the arbiter re-arbitrates and the higher-priority master then wins. - The starvation observation (a directed scenario, not a pass/fail). Fixed priority by design lets a high-priority master hold the resource indefinitely; verification should make that visible, not "fix" it. Drive a persistent high-priority request together with a low-priority one and observe that the low-priority
grantbit never asserts. This is not an assertion failure — it is the documented behaviour — but exercising it is how a learner sees the weakness that motivates round-robin (10.2). If the low-priority client is latency-sensitive, this scenario is the evidence that fixed priority is the wrong policy. - Expected waveform. For the combinational arbiter, "correct" is immediate: as
reqchanges, exactly onegrantbit (the lowest set bit for LSB-priority) tracks it combinationally, andgrantis all-zero only whenreqis all-zero — never two bits high at once. The visual signature of the double-grant bug is two grant bits high simultaneously on a multi-request cycle (the §7 failure). For the held-grant FSM, the signature of correctness is agrantbit that stays high across many cycles whilereqfor a higher-priority master pulses high underneath it without stealing the grant.
6. Common Mistakes
Non-one-hot grant → two masters drive the bus. The signature arbiter bug. A hand-built priority mask that, under some request pattern, asserts two grant bits means two masters enable their address/data/write onto the shared resource at once — contention that resolves to X and corrupts the transfer. The fix is structural: build the grant so it is one-hot by construction — isolate the lowest set bit (req & (~req + 1)) or use a correct priority encoder whose one winner you decode to one-hot — rather than hand-rolling a mask you then hope is one-hot. Verify it exhaustively for small N with a two-requester directed case. (Full post-mortem in §7; buggy-vs-fixed RTL for all three HDLs in §4b.)
Granting a line that is not requesting. A subtler correctness slip: an arbiter whose grant does not satisfy (grant & req) == grant — it asserts a grant bit for a master that is not asking (often a stale registered grant, or a default that grants master 0 on an idle bus). The consumer then steers an idle master's garbage address onto the port. The rule is that a granted line is always a requesting line; assert (grant & req) == grant every cycle, and drive req == 0 expecting grant == 0.
Using a granted line's data when its grant is low. The mirror mistake on the consumer side: reading a master's address/data unconditionally instead of gating it on that master's grant bit. When grant is low, a master's outputs are don't-cares (it does not own the bus this cycle); acting on them corrupts the transfer just as surely as a double grant. Every consumer must select the winner's signals through a one-hot mux keyed on grant — never OR all masters' data, never read a master whose grant bit is 0.
Re-arbitrating mid-transaction (a stolen burst). Using a purely combinational arbiter for a multi-cycle transfer: the instant a higher-priority master requests, the grant switches away from the current winner, aborting its burst half-finished and corrupting both transfers. Multi-cycle transactions need a held grant — a small FSM (Chapter 4.1) that locks the grant on the winner until it releases the resource (§4c). Use combinational re-arbitration only when every transaction completes in one cycle.
Ignoring starvation for a latency-sensitive low-priority client. The weakness fixed priority can never escape: a low-priority requester wins only when every higher-priority line is idle, so a continuously-busy high-priority master starves it forever. This is not a coding bug — it is what fixed priority means — but it is the wrong policy for any client that needs a bounded worst-case latency (a real-time video refresh, a watchdog, a slow peripheral that must not be locked out). When any requester has a latency requirement, fixed priority is disqualified and you reach for a fair arbiter (round-robin, 10.2, or weighted/LRU, 10.3). The tell is a low-priority client that works in isolation and hangs under load.
7. DebugLab
Two masters on one bus — a priority mask that leaked a second grant
The engineering lesson: an arbiter's grant must be one-hot by construction — at most one master may own the shared resource per cycle — and a mask that is merely "usually one-hot" will, on some request pattern, leak a second grant and put two drivers on the bus. The tell is memory or bus corruption that appears only under contention (two masters requesting together) and vanishes when you test one requester at a time: single-request tests can never see a double grant, because it takes two simultaneous requests to expose a mask that fails to kill all higher-priority lines. Two habits make it impossible, and they are identical across SystemVerilog, Verilog, and VHDL: build the grant so it is one-hot by definition — isolate the lowest set bit req & (~req + 1) or decode a correct priority encoder's single winner, never hand-roll a priority mask you hope is one-hot — and verify one-hotness exhaustively over all 2**N request patterns (or at least a directed multi-requester case), asserting $onehot0(grant) on every one. And remember the deeper limit even a correct fixed-priority arbiter carries: it is simple and fast, but it starves low-priority requesters whenever a higher line stays busy — which is exactly why fair arbiters exist.
8. Interview Q&A
9. Exercises
Design and reasoning exercises — no syntax drills. Each rehearses the "one token, fixed order, and it starves" habit.
Exercise 1 — Diagnose the double grant
A 4-master fixed-priority arbiter uses the mask grant[i] = req[i] & ~req[i-1] (with grant[0] = req[0]), and each master drives the shared bus when its grant bit is high. In one paragraph, explain (i) exactly what grant is for req = 4'b0101 and why two bits assert, (ii) what happens physically on the shared bus when two grants fire, (iii) why a block test that drives one request at a time never sees the bug, and (iv) the one-line fix that makes the grant one-hot by construction. Then state the single directed request vector that would have caught it.
Exercise 2 — Pick the arbitration policy
For each shared resource, state whether fixed priority is acceptable or whether you need a fair arbiter, and defend it in one line: (a) a bus where master 0 is a real-time interrupt controller that must always win when it asks; (b) a memory port shared by four identical DMA channels that each need bounded worst-case latency; (c) a debug port that outranks everything but is used only occasionally; (d) a shared multiplier where a low-priority background task must not be locked out for more than a few cycles. Then explain, for the case(s) where fixed priority fails, exactly which requester starves and under what traffic.
Exercise 3 — Combinational vs held grant
Two engineers build the same 4-master arbiter. Engineer A writes a purely combinational grant = req & (~req + 1). Engineer B wraps it in a two-state FSM that latches the grant and holds it until the winner drops req. Both grant the same winner on the first cycle. Describe (i) what each does when a higher-priority master requests during a lower-priority master's 8-cycle burst, (ii) which transactions corrupt in A's design and why, (iii) which design you'd choose for a single-cycle register-file write port and which for a burst DMA transfer, and (iv) why B's grant is still one-hot despite adding state.
Exercise 4 — Prove it correct on paper
You must verify a parameterized N-master fixed-priority arbiter with a self-checking testbench. State (i) the three invariants the testbench must assert every cycle and how the reference model computes the expected one-hot grant independently of the DUT, (ii) why a directed two-requester vector (non-adjacent bits set) must be a named case rather than relying only on single-bit sweeps, (iii) how you would exercise — and observe, without failing the test — the starvation behaviour, and (iv) what you switch to when N = 32 makes an exhaustive 2**N sweep infeasible, and what you check on each random request pattern.
10. Related Tutorials
Continue in RTL Design Patterns (sibling and forward links unlock as they ship):
- Priority Encoders — Chapter 1.4; the direct prerequisite — a fixed-priority arbiter is a priority encoder over the request vector, its winner expressed as a one-hot grant instead of an index. Read it first if the find-first scan is unfamiliar.
- Round-Robin Arbiter — Chapter 10.2; the next arbiter — the fair answer to the starvation this page ends on, built by rotating the priority origin and masking the request vector.
- Weighted / LRU Arbiter — Chapter 10.3; arbitration that bounds latency while still favouring some clients — the middle ground between fixed priority and pure round-robin.
- Request / Grant Handshake — the protocol on the arbiter's ports — how a requester asserts
req, waits forgrant, and releases, and how a held grant participates in it. (unlocks as it ships.) - Arbiter Fairness — the formal notion of fairness (bounded waiting, no starvation) that fixed priority fails and round-robin provides. (unlocks as it ships.)
Backward / method:
- FSM Fundamentals — Chapter 4.1; the two-state IDLE/HELD machine the held-grant arbiter (§4c) is built from — where an arbiter stops being pure combinational logic and acquires state.
- FSM Coding Styles — Chapter 4; the one-/two-/three-process styles the held-grant FSM follows, and the latch-free next-state discipline it depends on.
- Multiplexers (2:1, N:1, one-hot) — Chapter 1.1; the one-hot mux that steers the winner's address/data onto the shared port — the grant vector is the mux's one-hot select.
- Decoders — Chapter 1.2; index → one-hot — a decoder on a priority encoder's
grant_idxproduces exactly this arbiter's one-hot grant. - The valid/ready Handshake — Chapter 9.1; the flow-control cousin of request/grant, and where the "assert until acknowledged" discipline the arbiter's requesters follow is formalized.
Verilog v1 prerequisites (the grammar this pattern transcribes into):
- Bitwise Operators — the AND / NOT the isolate-lowest-set-bit identity
req & (~req + 1)is built from, and the reduction OR that detects any request. - Case Statements — the construct behind the held-grant FSM's state decode and the priority-mask forms.
- If-Else Statements — the conditional the priority mask and the FSM's capture/hold/release logic transcribe into.
- Blocking and Non-Blocking Assignments — why the combinational grant uses blocking (
=) while the held-grant FSM's state and registered grant use non-blocking (<=).
11. Summary
- An arbiter resolves contention for a shared resource; the fixed-priority arbiter is the simplest. Many requesters want one resource that serves one per cycle; the arbiter inspects the request vector and emits a grant that permits exactly one. Fixed priority ranks the requesters by a fixed order and grants the highest-priority active line — no state, no history, just a priority scan.
- A fixed-priority arbiter is a priority encoder (1.4), its winner expressed as a one-hot grant. For LSB-priority the grant is
req & (~req + 1)— the isolate-lowest-set-bit identity — which is one-hot by construction and yields all-zero when nobody asks. Same decision as a priority encoder; the winner is a one-hot bit instead of an index. - One-hot-or-zero is the invariant, and it must be built in, not tested after. At most one master may own the resource per cycle. A grant with two bits set puts two drivers on the bus — contention that corrupts the transfer — and is the signature failure (§7): a leaky hand-rolled priority mask that passes single-request tests and double-grants when two masters ask. Also hold
(grant & req) == grant(never grant an idle master) and gate every consumer on its grant bit. - Combinational re-arbitration for single-cycle transfers; a held-grant FSM (4.1) for multi-cycle bursts. Recomputing the grant every cycle is right when a transaction finishes in one cycle, but it lets a higher-priority latecomer steal a burst mid-transfer. A two-state IDLE/HELD FSM locks the one-hot grant on the winner until it releases — adding state without breaking one-hotness.
- Fixed priority is simple and fast — and it starves. A low-priority requester wins only when every higher line is idle, so a continuously-busy high-priority master starves it forever. That is what fixed priority means, not a bug — but it disqualifies fixed priority for any latency-sensitive client, which is the entire motivation for the fair arbiters ahead. Verify exhaustively for small
N(one-hot, granted-implies-requesting, lowest-wins) with self-checking clocked testbenches shown here in SystemVerilog, Verilog, and VHDL; the round-robin arbiter (10.2) is the next step.