USB · Module 23
Endpoint RTL
Fixed priority starves the interrupt endpoint exactly under the load its deadline was specified for — round robin replaces fairness-as-a-feeling with bounded waiting, a number you can put in a latency budget.
Chapter 23.1 produced a one-hot endpoint select, so exactly one endpoint is active per transaction on the bus side. But the endpoints also have a firmware side — draining received packets, filling ones to send — and that side is not driven by the bus's timing.
Several endpoints want the shared FIFO port at once. Something has to choose.
1. Fixed Priority Is the Obvious Answer and It Is Wrong
A priority encoder is three lines of RTL:
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
// starves, and starves worst exactly when it matters
assign grant_idx = req[0] ? 0 : req[1] ? 1 : req[2] ? 2 : 3;Endpoint 1 is a bulk endpoint moving a file, so it requests on nearly every cycle. Endpoint 3 is an interrupt endpoint with a 10 ms deadline, granted only when endpoint 1 happens to pause.
Under light load that is always, and the design looks fine. Under heavy load it is never — and the interrupt endpoint misses its deadline in exactly the circumstances it was configured to survive.
2. Round Robin, and What It Actually Guarantees
The arbiter keeps a pointer. Each arbitration searches from the pointer upward, wrapping, and grants the first requester it finds. The pointer then moves to one past the winner, so the requester that just won is searched last next time.
That gives a property much stronger than "it feels fair":
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
BOUNDED WAITING
A requester that keeps asking is granted within N
arbitrations, where N is the number of requesters.
Not on average. Always.Bounded waiting is what makes a deadline analysable. "Fair" is not a property — it is a feeling about a histogram. "At most three other grants before mine" is a number you can put into a latency budget, and it is a number you can enumerate rather than argue about.
Two details decide whether the guarantee holds, and each is a mutation:
| Detail | Get it wrong and… |
|---|---|
| the pointer must advance | every search starts at the same place — fixed priority with extra registers (R1) |
| it must advance past the winner | the winner is searched first again and wins every time (R3) |
| the search must wrap | requesters below the pointer are never reached at all (R5) |
Two arbitrations, and the pointer moving past the winner
3. And the Grant Must Be Held
A burst is several cycles long, and re-arbitrating inside one hands the port to somebody else halfway through a packet. So a grantee asserts hold while it still needs the port and the arbiter does not re-arbitrate.
But only while that endpoint is still requesting.
4. What We Are Building
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
usb_ep_arbiter #(N = 4, IDW = 2)
inputs outputs
------ -------
req [3:0] grant [3:0] ONE-HOT or zero
hold grant_valid / grant_idx
held this grant is a continuation
rr_ptr where the next search starts
arb_event IDLE / GRANTED / HELD /
REDIRECTED
n_grants / n_arbitrations / n_holds / n_idle / n_stuck_holdarb_event names the outcomes, and one of them is worth dwelling on. A grant and a held grant look identical on the grant lines — same one-hot vector, same index — and they are completely different events: one moves the pointer and costs somebody else their turn, the other does neither.
ARB_REDIRECTED is the fourth: a stuck hold that was overridden because somebody else was actually asking. Note what it is not — a "stuck hold" is not an outcome at all, because a stuck hold with nobody else asking grants nothing and is simply idle. Only the override is an event.
5. Verilog-2005 Implementation
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
// usb_ep_arbiter -- several endpoints, one FIFO port, and the difference
// between an arbiter that is fair and one that merely looks fair.
//
// WHY THERE IS AN ARBITER AT ALL
//
// Chapter 23.1's decode produces a one-hot endpoint select, so exactly one
// endpoint is active per transaction on the BUS side. But the endpoints also
// have a firmware side -- draining received packets, filling ones to send --
// and that side is not driven by the bus's timing. Several endpoints want
// the shared FIFO port at once, and something has to choose.
//
// FIXED PRIORITY IS THE OBVIOUS ANSWER AND IT IS WRONG
//
// A priority encoder is three lines of RTL and it starves. Endpoint 1 -- a
// bulk endpoint moving a file -- requests on nearly every cycle, so endpoint
// 3, an interrupt endpoint with a 10 ms deadline, is granted when endpoint 1
// happens to pause. Under light load that is always. Under heavy load it is
// never, and the interrupt endpoint misses its deadline in exactly the
// circumstances it was configured to survive.
//
// The symptom is a mouse that stutters while a file copies, and the fix is
// not a faster bus.
//
// ROUND ROBIN, AND WHAT IT ACTUALLY GUARANTEES
//
// The arbiter keeps a pointer. Each arbitration searches from the pointer
// UPWARD, wrapping, and grants the first requester it finds; the pointer
// then moves to one PAST the winner, so the requester that just won is
// searched LAST next time.
//
// That gives a property much stronger than "it feels fair":
//
// BOUNDED WAITING: a requester that keeps asking is granted
// within N arbitrations, where N is the number
// of requesters. Not on average. Always.
//
// Bounded waiting is what makes a deadline analysable. "Fair" is not a
// property; "at most three other grants before mine" is.
//
// Two details decide whether the guarantee holds:
//
// the pointer must ADVANCE -- leave it alone and the search always
// starts at the same place, which is
// fixed priority with extra registers
//
// it must advance PAST the winner -- advance TO the winner and that
// requester is searched first again,
// so a continuously-requesting
// endpoint wins every time
//
// AND THE GRANT MUST BE HELD
//
// A burst is several cycles long, and re-arbitrating inside one hands the
// port to somebody else halfway through a packet. So a grantee asserts
// `hold` while it still needs the port, and the arbiter does not
// re-arbitrate -- but only while that endpoint is STILL REQUESTING. A hold
// from an endpoint that has dropped its request is a stuck grant, and the
// port never comes back.
module usb_ep_arbiter #(
parameter N = 4, // requesters
parameter IDW = 2 // width of the requester index
) (
input wire clk,
input wire rst_n,
input wire [N-1:0] req, // which endpoints want the port
input wire hold, // the current owner needs more cycles
output wire [N-1:0] grant, // ONE-HOT, or all zero
output wire grant_valid,
output wire [IDW-1:0] grant_idx,
output wire held, // this grant is a continuation
output wire [IDW-1:0] rr_ptr, // where the next search starts
output wire [1:0] arb_event, // the same decision, named
output reg [31:0] n_grants,
output reg [31:0] n_arbitrations, // grants that were NOT continuations
output reg [31:0] n_holds,
output reg [31:0] n_idle,
output reg [31:0] n_stuck_hold // hold from a non-requesting owner
);
// N itself does not fit in IDW bits -- N-1 does. See the note on the
// search below.
localparam [IDW-1:0] LAST_IDX = N - 1;
reg [IDW-1:0] ptr_r;
reg [IDW-1:0] owner_r;
reg busy_r;
assign rr_ptr = ptr_r;
// ---- THE HOLD. Only valid while the owner is still asking. ----
//
// `busy_r && hold` alone would let an endpoint that has finished keep the
// port for ever. The `req[owner_r]` term is what makes the hold a request
// to CONTINUE rather than a claim of ownership.
wire keep = busy_r && hold && req[owner_r];
// An owner asserting hold with its request dropped is a firmware bug.
// It is refused -- and counted, because otherwise it is invisible.
wire stuck_hold = busy_r && hold && !req[owner_r];
// ---- THE ROUND-ROBIN SEARCH ----
//
// Search from ptr_r upward, WRAPPING, and take the first requester found.
// The wrap is what makes the guarantee hold: a search that only looks
// upward never reaches the requesters below the pointer at all.
// The ring index is computed in INTEGER arithmetic and wrapped by
// subtraction, not by `% N`. Writing `% N[IDW-1:0]` truncates N to its low
// IDW bits -- and for the power-of-two sizes an arbiter actually has, that
// is ZERO, so the modulus is a division by zero and every index is x.
// Chapter 22.2 has the same trap in its dequeue pointer; comparing against
// the LAST index rather than the count is what avoids it in both places.
reg [IDW-1:0] rr_win;
reg rr_any;
integer s, idx;
always @* begin
rr_any = 1'b0;
rr_win = {IDW{1'b0}};
for (s = N-1; s >= 0; s = s - 1) begin
// walk the ring backwards so the EARLIEST match wins the assignment
idx = ptr_r + s;
if (idx >= N) idx = idx - N;
if (req[idx]) begin
rr_any = 1'b1;
rr_win = idx[IDW-1:0];
end
end
end
assign grant_valid = keep || rr_any;
assign grant_idx = keep ? owner_r : rr_win;
assign held = keep;
// One-hot by construction -- a shift, not a set of comparisons. See
// chapter 23.1 for what the alternative costs.
assign grant = grant_valid ? ({{(N-1){1'b0}}, 1'b1} << grant_idx)
: {N{1'b0}};
// The same decision as one named value. A grant and a held grant look
// identical on the grant lines; only one of them moves the pointer.
// These are OUTCOMES, not annotations. ARB_STUCK would not be one: a
// stuck hold with nobody else asking grants nothing, which is simply
// idle. What IS an outcome is the port being TAKEN AWAY from an owner
// that asserted hold and handed to somebody who is actually asking.
localparam [1:0] ARB_IDLE = 2'd0, // nobody was granted
ARB_GRANTED = 2'd1, // a real arbitration: ptr moves
ARB_HELD = 2'd2, // a continuation: ptr does NOT
ARB_REDIRECTED = 2'd3; // a stuck hold was overridden
assign arb_event = keep ? ARB_HELD
: (stuck_hold && rr_any) ? ARB_REDIRECTED
: rr_any ? ARB_GRANTED
: ARB_IDLE;
always @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
ptr_r <= {IDW{1'b0}};
owner_r <= {IDW{1'b0}};
busy_r <= 1'b0;
n_grants <= 32'd0;
n_arbitrations <= 32'd0;
n_holds <= 32'd0;
n_idle <= 32'd0;
n_stuck_hold <= 32'd0;
end else begin
busy_r <= grant_valid;
owner_r <= grant_idx;
// The pointer moves ONLY on a real arbitration, and it moves PAST the
// winner. Both halves of that sentence are load-bearing.
if (!keep && rr_any)
ptr_r <= (rr_win == LAST_IDX) ? {IDW{1'b0}}
: rr_win + {{(IDW-1){1'b0}}, 1'b1};
if (grant_valid) n_grants <= n_grants + 32'd1;
if (grant_valid && !keep) n_arbitrations <= n_arbitrations + 32'd1;
if (keep) n_holds <= n_holds + 32'd1;
if (!grant_valid) n_idle <= n_idle + 32'd1;
if (stuck_hold) n_stuck_hold <= n_stuck_hold + 32'd1;
end
end
endmodule6. SystemVerilog Implementation
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
// usb_ep_arbiter -- several endpoints, one FIFO port, and the difference
// between an arbiter that is fair and one that merely looks fair.
//
// WHY THERE IS AN ARBITER AT ALL
//
// Chapter 23.1's decode produces a one-hot endpoint select, so exactly one
// endpoint is active per transaction on the BUS side. But the endpoints also
// have a firmware side -- draining received packets, filling ones to send --
// and that side is not driven by the bus's timing. Several endpoints want
// the shared FIFO port at once, and something has to choose.
//
// FIXED PRIORITY IS THE OBVIOUS ANSWER AND IT IS WRONG
//
// A priority encoder is three lines of RTL and it starves. Endpoint 1 -- a
// bulk endpoint moving a file -- requests on nearly every cycle, so endpoint
// 3, an interrupt endpoint with a 10 ms deadline, is granted when endpoint 1
// happens to pause. Under light load that is always. Under heavy load it is
// never, and the interrupt endpoint misses its deadline in exactly the
// circumstances it was configured to survive.
//
// The symptom is a mouse that stutters while a file copies, and the fix is
// not a faster bus.
//
// ROUND ROBIN, AND WHAT IT ACTUALLY GUARANTEES
//
// The arbiter keeps a pointer. Each arbitration searches from the pointer
// UPWARD, wrapping, and grants the first requester it finds; the pointer
// then moves to one PAST the winner, so the requester that just won is
// searched LAST next time.
//
// That gives a property much stronger than "it feels fair":
//
// BOUNDED WAITING: a requester that keeps asking is granted
// within N arbitrations, where N is the number
// of requesters. Not on average. Always.
//
// Bounded waiting is what makes a deadline analysable. "Fair" is not a
// property; "at most three other grants before mine" is.
//
// Two details decide whether the guarantee holds:
//
// the pointer must ADVANCE -- leave it alone and the search always
// starts at the same place, which is
// fixed priority with extra registers
//
// it must advance PAST the winner -- advance TO the winner and that
// requester is searched first again,
// so a continuously-requesting
// endpoint wins every time
//
// AND THE GRANT MUST BE HELD
//
// A burst is several cycles long, and re-arbitrating inside one hands the
// port to somebody else halfway through a packet. So a grantee asserts
// `hold` while it still needs the port, and the arbiter does not
// re-arbitrate -- but only while that endpoint is STILL REQUESTING. A hold
// from an endpoint that has dropped its request is a stuck grant, and the
// port never comes back.
package usb_arb_pkg;
// WHY the port went where it did. A grant and a held grant look identical
// on the grant lines and are completely different events: one moves the
// pointer and costs somebody else their turn, the other does neither.
// These are OUTCOMES, not annotations. A "stuck hold" would not be one:
// a stuck hold with nobody else asking grants nothing, which is simply
// idle. What IS an outcome is the port being TAKEN AWAY from an owner
// that asserted hold and handed to somebody who is actually asking.
typedef enum logic [1:0] {
ARB_IDLE = 2'd0, // nobody was granted
ARB_GRANTED = 2'd1, // a real arbitration: the pointer moves
ARB_HELD = 2'd2, // a continuation: the pointer does NOT move
ARB_REDIRECTED = 2'd3 // a stuck hold was overridden
} arb_event_e;
endpackage
module usb_ep_arbiter
import usb_arb_pkg::*;
#(
parameter int N = 4, // requesters
parameter int IDW = 2 // width of the requester index
) (
input logic clk,
input logic rst_n,
input logic [N-1:0] req, // which endpoints want the port
input logic hold, // the current owner needs more cycles
output logic [N-1:0] grant, // ONE-HOT, or all zero
output logic grant_valid,
output logic [IDW-1:0] grant_idx,
output logic held, // this grant is a continuation
output logic [IDW-1:0] rr_ptr, // where the next search starts
output arb_event_e arb_event, // the same decision, named
output logic [31:0] n_grants,
output logic [31:0] n_arbitrations, // grants that were NOT continuations
output logic [31:0] n_holds,
output logic [31:0] n_idle,
output logic [31:0] n_stuck_hold // hold from a non-requesting owner
);
// N itself does not fit in IDW bits -- N-1 does. See the note on the
// search below.
localparam logic [IDW-1:0] LAST_IDX = IDW'(N - 1);
logic [IDW-1:0] ptr_r;
logic [IDW-1:0] owner_r;
logic busy_r;
assign rr_ptr = ptr_r;
// ---- THE HOLD. Only valid while the owner is still asking. ----
//
// `busy_r && hold` alone would let an endpoint that has finished keep the
// port for ever. The `req[owner_r]` term is what makes the hold a request
// to CONTINUE rather than a claim of ownership.
logic keep;
assign keep = busy_r && hold && req[owner_r];
// An owner asserting hold with its request dropped is a firmware bug.
// It is refused -- and counted, because otherwise it is invisible.
logic stuck_hold;
assign stuck_hold = busy_r && hold && !req[owner_r];
// ---- THE ROUND-ROBIN SEARCH ----
//
// Search from ptr_r upward, WRAPPING, and take the first requester found.
// The wrap is what makes the guarantee hold: a search that only looks
// upward never reaches the requesters below the pointer at all.
// The ring index is computed in INTEGER arithmetic and wrapped by
// subtraction, not by `% N`. Writing `% N[IDW-1:0]` truncates N to its low
// IDW bits -- and for the power-of-two sizes an arbiter actually has, that
// is ZERO, so the modulus is a division by zero and every index is x.
// Chapter 22.2 has the same trap in its dequeue pointer; comparing against
// the LAST index rather than the count is what avoids it in both places.
logic [IDW-1:0] rr_win;
logic rr_any;
int s, idx;
always_comb begin
rr_any = 1'b0;
rr_win = '0;
for (s = N-1; s >= 0; s = s - 1) begin
// walk the ring backwards so the EARLIEST match wins the assignment
idx = ptr_r + s;
if (idx >= N) idx = idx - N;
if (req[idx]) begin
rr_any = 1'b1;
rr_win = IDW'(idx);
end
end
end
assign grant_valid = keep || rr_any;
assign grant_idx = keep ? owner_r : rr_win;
assign held = keep;
// One-hot by construction -- a shift, not a set of comparisons. See
// chapter 23.1 for what the alternative costs.
assign grant = grant_valid ? (N'(1) << grant_idx) : '0;
// The same decision as one named value. A grant and a held grant look
// identical on the grant lines; only one of them moves the pointer.
always_comb begin
if (keep) arb_event = ARB_HELD;
else if (stuck_hold && rr_any) arb_event = ARB_REDIRECTED;
else if (rr_any) arb_event = ARB_GRANTED;
else arb_event = ARB_IDLE;
end
always_ff @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
ptr_r <= '0;
owner_r <= '0;
busy_r <= 1'b0;
n_grants <= '0;
n_arbitrations <= '0;
n_holds <= '0;
n_idle <= '0;
n_stuck_hold <= '0;
end else begin
busy_r <= grant_valid;
owner_r <= grant_idx;
// The pointer moves ONLY on a real arbitration, and it moves PAST the
// winner. Both halves of that sentence are load-bearing.
if (!keep && rr_any)
ptr_r <= (rr_win == LAST_IDX) ? '0 : rr_win + 1'b1;
if (grant_valid) n_grants <= n_grants + 1;
if (grant_valid && !keep) n_arbitrations <= n_arbitrations + 1;
if (keep) n_holds <= n_holds + 1;
if (!grant_valid) n_idle <= n_idle + 1;
if (stuck_hold) n_stuck_hold <= n_stuck_hold + 1;
end
end
endmodule7. VHDL-2008 Implementation
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
-- usb_ep_arbiter -- several endpoints, one FIFO port, and the difference
-- between an arbiter that is fair and one that merely looks fair.
--
-- WHY THERE IS AN ARBITER AT ALL
--
-- Chapter 23.1's decode produces a one-hot endpoint select, so exactly one
-- endpoint is active per transaction on the BUS side. But the endpoints also
-- have a firmware side -- draining received packets, filling ones to send --
-- and that side is not driven by the bus's timing. Several endpoints want
-- the shared FIFO port at once, and something has to choose.
--
-- FIXED PRIORITY IS THE OBVIOUS ANSWER AND IT IS WRONG
--
-- A priority encoder is three lines of RTL and it starves. Endpoint 1 -- a
-- bulk endpoint moving a file -- requests on nearly every cycle, so endpoint
-- 3, an interrupt endpoint with a 10 ms deadline, is granted when endpoint 1
-- happens to pause. Under light load that is always. Under heavy load it is
-- never, and the interrupt endpoint misses its deadline in exactly the
-- circumstances it was configured to survive.
--
-- The symptom is a mouse that stutters while a file copies, and the fix is
-- not a faster bus.
--
-- ROUND ROBIN, AND WHAT IT ACTUALLY GUARANTEES
--
-- The arbiter keeps a pointer. Each arbitration searches from the pointer
-- UPWARD, wrapping, and grants the first requester it finds; the pointer
-- then moves to one PAST the winner, so the requester that just won is
-- searched LAST next time.
--
-- BOUNDED WAITING: a requester that keeps asking is granted
-- within N arbitrations, where N is the number
-- of requesters. Not on average. Always.
--
-- Bounded waiting is what makes a deadline analysable. "Fair" is not a
-- property; "at most three other grants before mine" is.
--
-- Two details decide whether the guarantee holds:
--
-- the pointer must ADVANCE -- leave it alone and the search always
-- starts at the same place, which is
-- fixed priority with extra registers
--
-- it must advance PAST the winner -- advance TO the winner and that
-- requester is searched first again
--
-- AND THE GRANT MUST BE HELD
--
-- A burst is several cycles long, and re-arbitrating inside one hands the
-- port to somebody else halfway through a packet. So a grantee asserts
-- `hold` while it still needs the port, and the arbiter does not
-- re-arbitrate -- but only while that endpoint is STILL REQUESTING. A hold
-- from an endpoint that has dropped its request is a stuck grant, and the
-- port never comes back.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
package usb_arb_pkg is
-- These are OUTCOMES, not annotations. A "stuck hold" would not be one: a
-- stuck hold with nobody else asking grants nothing, which is simply idle.
-- What IS an outcome is the port being TAKEN AWAY from an owner that
-- asserted hold and handed to somebody who is actually asking.
type arb_event_t is (
ARB_IDLE, -- nobody was granted
ARB_GRANTED, -- a real arbitration: the pointer moves
ARB_HELD, -- a continuation: the pointer does NOT move
ARB_REDIRECTED -- a stuck hold was overridden
);
function ev_code(e : arb_event_t) return std_logic_vector;
end package;
package body usb_arb_pkg is
function ev_code(e : arb_event_t) return std_logic_vector is
begin
return std_logic_vector(to_unsigned(arb_event_t'pos(e), 2));
end function;
end package body;
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use work.usb_arb_pkg.all;
entity usb_ep_arbiter is
generic (
N : natural := 4; -- requesters
IDW : natural := 2 -- width of the requester index
);
port (
clk : in std_logic;
rst_n : in std_logic;
req : in std_logic_vector(N-1 downto 0);
hold : in std_logic; -- the owner needs more cycles
grant : out std_logic_vector(N-1 downto 0); -- ONE-HOT or zero
grant_valid : out std_logic;
grant_idx : out std_logic_vector(IDW-1 downto 0);
held : out std_logic; -- this grant is a continuation
rr_ptr : out std_logic_vector(IDW-1 downto 0);
arb_event : out std_logic_vector(1 downto 0);
n_grants : out std_logic_vector(31 downto 0);
n_arbitrations : out std_logic_vector(31 downto 0);
n_holds : out std_logic_vector(31 downto 0);
n_idle : out std_logic_vector(31 downto 0);
n_stuck_hold : out std_logic_vector(31 downto 0)
);
end entity;
architecture rtl of usb_ep_arbiter is
signal ptr_r : natural range 0 to N-1 := 0;
signal owner_r : natural range 0 to N-1 := 0;
signal busy_r : std_logic := '0';
signal keep_s, stuck_s, any_s, gv_s : std_logic;
signal win_s, idx_s : natural range 0 to N-1;
signal ev_s : arb_event_t;
signal gr_c, arb_c, hold_c, idle_c, stk_c : unsigned(31 downto 0)
:= (others => '0');
begin
rr_ptr <= std_logic_vector(to_unsigned(ptr_r, IDW));
-- ---- THE HOLD. Only valid while the owner is still asking. ----
--
-- `busy_r and hold` alone would let an endpoint that has finished keep the
-- port for ever. The req(owner_r) term is what makes the hold a request to
-- CONTINUE rather than a claim of ownership.
keep_s <= '1' when (busy_r = '1' and hold = '1' and req(owner_r) = '1')
else '0';
-- An owner asserting hold with its request dropped is a firmware bug. It
-- is refused -- and counted, because otherwise it is invisible.
stuck_s <= '1' when (busy_r = '1' and hold = '1' and req(owner_r) = '0')
else '0';
-- ---- THE ROUND-ROBIN SEARCH ----
--
-- Search from ptr_r upward, WRAPPING, and take the first requester found.
-- The wrap is what makes the guarantee hold: a search that only looks
-- upward never reaches the requesters below the pointer at all.
--
-- The ring index is computed in INTEGER arithmetic and wrapped by
-- subtraction. VHDL's `mod` would be correct here, but the Verilog and
-- SystemVerilog builds cannot use `%` on a truncated constant (see the
-- note in those files), and keeping all three the same shape is what makes
-- the mutation columns comparable.
search : process (ptr_r, req)
variable found : std_logic;
variable w, ix : natural range 0 to N-1;
begin
found := '0';
w := 0;
for s in N-1 downto 0 loop
-- walk the ring backwards so the EARLIEST match wins the assignment
if ptr_r + s >= N then
ix := ptr_r + s - N;
else
ix := ptr_r + s;
end if;
if req(ix) = '1' then
found := '1';
w := ix;
end if;
end loop;
any_s <= found;
win_s <= w;
end process;
gv_s <= keep_s or any_s;
grant_valid <= gv_s;
held <= keep_s;
idx_s <= owner_r when keep_s = '1' else win_s;
grant_idx <= std_logic_vector(to_unsigned(idx_s, IDW));
-- One-hot by construction -- an indexed assignment, not a set of
-- comparisons. See chapter 23.1 for what the alternative costs.
onehot : process (gv_s, idx_s)
variable v : std_logic_vector(N-1 downto 0);
begin
v := (others => '0');
if gv_s = '1' then
v(idx_s) := '1';
end if;
grant <= v;
end process;
-- The same decision as one named value. A grant and a held grant look
-- identical on the grant lines; only one of them moves the pointer.
classify : process (keep_s, stuck_s, any_s)
begin
if keep_s = '1' then
ev_s <= ARB_HELD;
elsif stuck_s = '1' and any_s = '1' then
ev_s <= ARB_REDIRECTED;
elsif any_s = '1' then
ev_s <= ARB_GRANTED;
else
ev_s <= ARB_IDLE;
end if;
end process;
arb_event <= ev_code(ev_s);
regs : process (clk, rst_n)
begin
if rst_n = '0' then
ptr_r <= 0;
owner_r <= 0;
busy_r <= '0';
gr_c <= (others => '0');
arb_c <= (others => '0');
hold_c <= (others => '0');
idle_c <= (others => '0');
stk_c <= (others => '0');
elsif rising_edge(clk) then
busy_r <= gv_s;
owner_r <= idx_s;
-- The pointer moves ONLY on a real arbitration, and it moves PAST the
-- winner. Both halves of that sentence are load-bearing.
if keep_s = '0' and any_s = '1' then
if win_s = N-1 then
ptr_r <= 0;
else
ptr_r <= win_s + 1;
end if;
end if;
if gv_s = '1' then
gr_c <= gr_c + 1;
end if;
if gv_s = '1' and keep_s = '0' then
arb_c <= arb_c + 1;
end if;
if keep_s = '1' then
hold_c <= hold_c + 1;
end if;
if gv_s = '0' then
idle_c <= idle_c + 1;
end if;
if stuck_s = '1' then
stk_c <= stk_c + 1;
end if;
end if;
end process;
n_grants <= std_logic_vector(gr_c);
n_arbitrations <= std_logic_vector(arb_c);
n_holds <= std_logic_vector(hold_c);
n_idle <= std_logic_vector(idle_c);
n_stuck_hold <= std_logic_vector(stk_c);
end architecture;VHDL's mod would be correct in the search and would not need the subtraction — but keeping all three builds the same shape is what makes the mutation columns comparable, so the VHDL wraps the same way the other two must.
8. Seeing Bounded Waiting
Two endpoints asking continuously, alternating — and a held burst
usb_ep_arbiter — alternation, and a held burst
10 cyclesRead rr_ptr across cycles 5–7. It does not move, three cycles in a row, while grants are being issued. That is the entire difference between a hold and an arbitration, and mutation R1 makes the pointer behave that way permanently.
9. The Testbenches
The exhaustive domain is every request pattern against every reachable arbiter state:
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
16 request patterns x 2 (hold)
x 4 (pointer) x 4 (owner) x 2 (busy)
= 1024 transitions
and every (pointer, owner, busy) is established by REAL
grants -- the state is walked into, never forced.But the sharpest thing in these suites is not the sweep. It is the bounded-waiting tracker inside model_step:
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
// ---- BOUNDED WAITING. For every requester that is asking and is NOT
// ---- the one being granted by a real arbitration, its wait grows.
// ---- The property is that it never exceeds N-1.
if (!e_keep && e_any) begin
for (k=0; k<N; k=k+1) begin
if (k == e_idx) wait_cnt[k] = 0;
else if (req[k]) begin
wait_cnt[k] = wait_cnt[k] + 1;
if (wait_cnt[k] > worst_wait) worst_wait = wait_cnt[k];
check(wait_cnt[k] <= N-1,
"a continuously-requesting endpoint waited more than N-1 arbitrations -- round robin has degenerated to fixed priority");
end
end
endThat check fires on every arbitration in every phase — exhaustive, directed and randomised alike. It is not a property about a scenario; it is an invariant about the arbiter, and the suites report the worst wait actually observed so the bound is a measurement rather than an assumption.
9.1 Verilog testbench
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
`timescale 1ns/1ps
module tb_ar_v;
localparam N = 4, IDW = 2;
reg clk=0, rst_n=0;
reg [N-1:0] req=0;
reg hold=0;
wire [N-1:0] grant;
wire grant_valid, held;
wire [IDW-1:0] grant_idx, rr_ptr;
wire [1:0] arb_event;
wire [31:0] n_grants, n_arbitrations, n_holds, n_idle, n_stuck_hold;
always #5 clk=~clk;
usb_ep_arbiter #(.N(N), .IDW(IDW)) dut (
.clk(clk), .rst_n(rst_n), .req(req), .hold(hold), .grant(grant),
.grant_valid(grant_valid), .grant_idx(grant_idx), .held(held),
.rr_ptr(rr_ptr), .arb_event(arb_event), .n_grants(n_grants),
.n_arbitrations(n_arbitrations),
.n_holds(n_holds), .n_idle(n_idle), .n_stuck_hold(n_stuck_hold));
// ---- SHADOW MODEL of the three registers ----
integer s_ptr, s_owner, s_busy;
integer m_gr, m_arb, m_hold, m_idle, m_stuck;
// ---- BOUNDED-WAITING tracker: for each requester, how many ARBITRATIONS
// ---- have gone to somebody else since it started asking continuously.
integer wait_cnt [0:N-1];
integer worst_wait=0;
integer errors=0, i, r, h, p, o, b;
integer n_exh=0;
integer n_gr_per [0:N-1];
integer n_arb=0, n_keep=0, n_idl=0, n_stk=0;
function integer popcount;
input [N-1:0] v;
integer bb, c;
begin
c = 0;
for (bb=0; bb<N; bb=bb+1) if (v[bb]) c = c + 1;
popcount = c;
end
endfunction
task check(input cond, input [639:0] msg);
begin if (!cond) begin errors=errors+1;
if (errors <= 25)
$display(" FAIL: %0s (req=%b hold=%b | grant=%b valid=%b idx=%0d held=%b ptr=%0d || model ptr=%0d owner=%0d busy=%0d, t=%0t)",
msg, req, hold, grant, grant_valid, grant_idx, held, rr_ptr,
s_ptr, s_owner, s_busy, $time);
end end
endtask
// The model searches the ring FORWARD from the pointer and stops at the
// first hit, where the design walks backwards and lets the earliest match
// win the assignment -- a different route to the same winner.
task model(output e_keep, output e_any, output integer e_win,
output e_stuck);
integer k, idx;
begin
e_keep = (s_busy != 0) && hold && req[s_owner];
e_stuck = (s_busy != 0) && hold && !req[s_owner];
e_any = 1'b0; e_win = 0;
for (k=0; k<N; k=k+1) begin
idx = (s_ptr + k) % N;
if (!e_any && req[idx]) begin e_any = 1'b1; e_win = idx; end
end
end
endtask
localparam [1:0] ARB_IDLE=0, ARB_GRANTED=1, ARB_HELD=2, ARB_REDIRECTED=3;
task check_comb;
reg e_keep, e_any, e_stuck;
integer e_win, e_idx;
reg [N-1:0] e_grant;
reg [1:0] e_ev;
begin
model(e_keep, e_any, e_win, e_stuck);
e_idx = e_keep ? s_owner : e_win;
e_grant = (e_keep || e_any) ? ({{(N-1){1'b0}}, 1'b1} << e_idx[IDW-1:0])
: {N{1'b0}};
check(grant_valid === (e_keep || e_any), "grant_valid matches the model");
check(held === e_keep, "held matches the model");
check(grant === e_grant, "grant matches the model");
if (e_keep || e_any)
check(grant_idx === e_idx[IDW-1:0], "grant_idx matches the model");
check(rr_ptr === s_ptr[IDW-1:0], "rr_ptr matches the model");
if (e_keep) e_ev = ARB_HELD;
else if (e_stuck && e_any) e_ev = ARB_REDIRECTED;
else if (e_any) e_ev = ARB_GRANTED;
else e_ev = ARB_IDLE;
check(arb_event === e_ev, "arb_event matches the model");
// The named event must agree with the signals it summarises.
check((arb_event === ARB_HELD) === held,
"arb_event disagrees with held");
check((arb_event === ARB_IDLE) === !grant_valid,
"arb_event disagrees with grant_valid");
// ---- SAFETY PROPERTIES, independent of the model ----
// 1. The grant is ONE-HOT or zero. Two owners of one port is a
// contention, exactly as in chapter 23.1.
check(popcount(grant) <= 1,
"more than one requester was granted the shared port");
// 2. A grant only ever goes to a requester. Granting a port to a
// block that did not ask for it wedges it until it happens to ask.
if (grant_valid)
check(req[grant_idx],
"the port was granted to an endpoint that did not request it");
// 3. grant and grant_valid agree.
check((|grant) === grant_valid, "grant disagrees with grant_valid");
// 4. With no requests and no hold, nothing is granted.
if (req === {N{1'b0}})
check(!grant_valid, "the port was granted with nobody asking");
// 5. THE hold rule. A held grant goes to the PREVIOUS owner, and only
// while that owner is still asking.
if (held) begin
check(grant_idx === s_owner[IDW-1:0],
"a held grant went to somebody other than the current owner");
check(req[s_owner],
"a hold was honoured for an owner that has dropped its request -- the port is now stuck");
end
// 6. A hold from a non-requesting owner is refused, not obeyed.
if (e_stuck)
check(!held,
"a stuck hold was obeyed");
// 7. The pointer moves ONLY on a real arbitration, and it moves to
// one PAST the winner. (Its RANGE is structural -- an IDW-bit
// pointer into a 2**IDW-entry ring cannot leave it -- so range is
// not the property worth asserting; PROVENANCE is. Writing it as
// `rr_ptr < N[IDW-1:0]` would truncate N to zero and never fire.)
if (held || !(|req))
check(rr_ptr === s_ptr[IDW-1:0],
"the pointer moved without a real arbitration");
if (e_keep || e_any) n_gr_per[e_idx] = n_gr_per[e_idx] + 1;
if (e_keep) n_keep = n_keep + 1;
else if (e_any) n_arb = n_arb + 1;
else n_idl = n_idl + 1;
if (e_stuck) n_stk = n_stk + 1;
end
endtask
task model_step;
reg e_keep, e_any, e_stuck;
integer e_win, e_idx, k;
begin
model(e_keep, e_any, e_win, e_stuck);
e_idx = e_keep ? s_owner : e_win;
// ---- BOUNDED WAITING. For every requester that is asking and is NOT
// ---- the one being granted by a real arbitration, its wait grows.
// ---- The property is that it never exceeds N-1.
if (!e_keep && e_any) begin
for (k=0; k<N; k=k+1) begin
if (k == e_idx) wait_cnt[k] = 0;
else if (req[k]) begin
wait_cnt[k] = wait_cnt[k] + 1;
if (wait_cnt[k] > worst_wait) worst_wait = wait_cnt[k];
check(wait_cnt[k] <= N-1,
"a continuously-requesting endpoint waited more than N-1 arbitrations -- round robin has degenerated to fixed priority");
end
end
end
// A requester that stops asking is no longer waiting.
for (k=0; k<N; k=k+1) if (!req[k]) wait_cnt[k] = 0;
if (e_keep || e_any) m_gr = m_gr + 1;
if (!e_keep && e_any) m_arb = m_arb + 1;
if (e_keep) m_hold = m_hold + 1;
if (!e_keep && !e_any) m_idle = m_idle + 1;
if (e_stuck) m_stuck = m_stuck + 1;
s_busy = (e_keep || e_any) ? 1 : 0;
s_owner = (e_keep || e_any) ? e_idx : s_owner;
if (!e_keep && e_any) s_ptr = (e_win + 1) % N;
end
endtask
task step;
begin
#1;
check_comb;
model_step;
@(posedge clk); #1;
check(rr_ptr === s_ptr[IDW-1:0], "rr_ptr tracked the model");
check(n_grants === m_gr[31:0], "n_grants matches the model");
check(n_arbitrations === m_arb[31:0], "n_arbitrations matches the model");
check(n_holds === m_hold[31:0], "n_holds matches the model");
check(n_idle === m_idle[31:0], "n_idle matches the model");
check(n_stuck_hold === m_stuck[31:0], "n_stuck_hold matches the model");
end
endtask
task hard_reset;
begin
rst_n=0; req=0; hold=0;
@(posedge clk); #1; @(posedge clk); #1; rst_n=1; #1;
s_ptr=0; s_owner=0; s_busy=0;
m_gr=0; m_arb=0; m_hold=0; m_idle=0; m_stuck=0;
for (i=0;i<N;i=i+1) wait_cnt[i]=0;
end
endtask
// Drive the arbiter to a chosen (pointer, owner, busy) using only real
// arbitrations -- no register forcing. Reaching pointer p means granting
// requester p-1; reaching owner o means granting o last.
task goto_state(input integer want_ptr, input integer want_owner,
input integer want_busy);
integer prev;
begin
hard_reset;
if (want_busy != 0) begin
// grant `want_owner` first, which leaves ptr = owner+1
req = (1 << want_owner); hold=0; step; req=0; hold=0;
// then walk the pointer round to want_ptr by granting (want_ptr-1)
if (((want_owner + 1) % N) != want_ptr) begin
prev = (want_ptr + N - 1) % N;
req = (1 << prev); hold=0; step; req=0;
// and re-establish the owner without moving the pointer further
// is not possible without a grant, so accept that owner follows
// the last grant -- the sweep below covers the reachable pairs.
end
end
req=0; hold=0; #1;
end
endtask
initial begin
for (i=0;i<N;i=i+1) begin n_gr_per[i]=0; wait_cnt[i]=0; end
hard_reset;
check(!grant_valid, "reset grants nothing");
check(rr_ptr === 2'd0, "and the pointer starts at zero");
// ===== A. EXHAUSTIVE arbitration sweep =====
// Every request pattern x hold x every reachable (pointer, owner, busy):
// 16 req x 2 hold x 4 ptr x 4 owner x 2 busy = 1024 transitions.
// The state is established by REAL grants, then the inputs applied.
for (p=0; p<N; p=p+1)
for (o=0; o<N; o=o+1)
for (b=0; b<2; b=b+1)
for (r=0; r<16; r=r+1)
for (h=0; h<2; h=h+1) begin
// establish (ptr, owner, busy) by granting `o` then walking the
// pointer to `p` -- both by ordinary arbitration
hard_reset;
if (b != 0) begin req = (1 << o); hold = 0; step; req=0; end
while (s_ptr != p) begin
req = (1 << ((s_ptr) % N)); hold = 0; step; req = 0;
end
req = r[N-1:0]; hold = h[0];
step;
n_exh = n_exh + 1;
req = 0; hold = 0;
end
$display(" exhaustive arbitration sweep: %0d transitions verified",
n_exh);
// ===== B. directed: the starvation that fixed priority produces =====
hard_reset;
// 1. Endpoint 1 asks constantly; endpoint 3 asks constantly. Under
// fixed priority endpoint 3 would never be granted. Under round
// robin they alternate.
//
// NOTE the shape of these checks: the grant is COMBINATIONAL on the
// request and the pointer, so it is examined BEFORE `step` advances
// the clock. Checking after the step reads the NEXT arbitration.
req = 4'b1010; hold = 0; #1;
check(grant_idx === 2'd1, "the first arbitration grants endpoint 1");
step; #1;
check(rr_ptr === 2'd2, "and the pointer moves PAST it, to 2");
check(grant_idx === 2'd3, "so the next arbitration grants endpoint 3");
step; #1;
check(rr_ptr === 2'd0, "and the pointer wraps to 0");
check(grant_idx === 2'd1, "and the one after that is endpoint 1 again");
step;
req = 0; step;
// 2. THE bounded-waiting property, watched directly. Endpoint 3 asks
// continuously while 0, 1 and 2 all ask too. It must be granted
// within N arbitrations, every time -- which the tracker in
// model_step asserts on every arbitration, not just here.
hard_reset;
req = 4'b1111; hold = 0;
for (i=0;i<12;i=i+1) step;
check(n_gr_per[3] >= 3,
"endpoint 3 was granted repeatedly despite three competitors");
req = 0; step;
// 3. The hold keeps a burst together.
hard_reset;
req = 4'b0011; hold = 0; #1;
check(grant_idx === 2'd0, "endpoint 0 wins the first arbitration");
step;
hold = 1; #1;
check(held, "with hold asserted the grant is a continuation");
check(grant_idx === 2'd0, "which stays with endpoint 0");
step; #1;
check(held, "and stays held");
check(rr_ptr === 2'd1,
"while the pointer does NOT move -- a hold is not an arbitration");
step;
hold = 0; #1;
check(grant_idx === 2'd1,
"and when the hold drops, the next arbitration goes to endpoint 1");
step;
req = 0; hold = 0; step;
// 4. A hold from an owner that has dropped its request is refused.
hard_reset;
req = 4'b0001; hold = 0; #1;
check(grant_idx === 2'd0, "endpoint 0 takes the port");
step;
req = 4'b0010; hold = 1; #1;
check(!held,
"a hold from an owner that stopped requesting is NOT honoured");
check(grant_idx === 2'd1,
"so the port is arbitrated to the endpoint that IS asking");
step;
check(n_stuck_hold === 32'd1, "and the firmware bug was counted");
req = 0; hold = 0; step;
// 5. No requests, no grant -- even with hold asserted.
hard_reset;
req = 0; hold = 1; #1;
check(!grant_valid, "nobody asking means nobody granted");
check(grant === 4'b0000, "and nothing is driven");
step;
// ===== C. randomised =====
hard_reset;
for (i=0;i<40000;i=i+1) begin
req = {$random}%16;
hold = ({$random}%3)!=0;
step;
end
for (i=0;i<N;i=i+1)
check(n_gr_per[i] > 1000, "every endpoint was granted many times");
check(n_arb > 5000, "real arbitrations happened often");
check(n_keep > 5000, "held grants happened often");
check(n_idl > 1000, "the port was idle often");
check(n_stk > 500, "stuck holds were presented often");
check(worst_wait <= N-1,
"the worst observed wait exceeded the bound");
$display("");
$display(" REACH: transitions=%0d | grants per endpoint: ep0=%0d ep1=%0d ep2=%0d ep3=%0d",
n_exh, n_gr_per[0], n_gr_per[1], n_gr_per[2], n_gr_per[3]);
$display(" CASES: arbitrations=%0d held=%0d idle=%0d stuck-holds=%0d | WORST WAIT=%0d of a bound of %0d",
n_arb, n_keep, n_idl, n_stk, worst_wait, N-1);
$display(" COUNTERS: grants=%0d arbitrations=%0d holds=%0d idle=%0d stuck=%0d",
n_grants, n_arbitrations, n_holds, n_idle, n_stuck_hold);
$display(" [Verilog] usb_ep_arbiter: %0d errors", errors);
$display(" [Verilog] %0s", errors==0 ? "PASS" : "FAIL");
$display("");
$finish;
end
endmodule9.2 SystemVerilog testbench
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
`timescale 1ns/1ps
module tb_ar_sv;
import usb_arb_pkg::*;
localparam N = 4, IDW = 2;
logic clk=0, rst_n=0;
logic [N-1:0] req=0;
logic hold=0;
logic [N-1:0] grant;
logic grant_valid, held;
logic [IDW-1:0] grant_idx, rr_ptr;
arb_event_e arb_event;
logic [31:0] n_grants, n_arbitrations, n_holds, n_idle, n_stuck_hold;
// Icarus seeds $random and $urandom identically, so an unseeded run would
// replay the Verilog suite's stimulus exactly. See chapter 20.5 section 9.2.
int urandom_seed = 23202;
always #5 clk=~clk;
usb_ep_arbiter #(.N(N), .IDW(IDW)) dut (
.clk, .rst_n, .req, .hold, .grant, .grant_valid, .grant_idx, .held,
.rr_ptr, .arb_event, .n_grants, .n_arbitrations, .n_holds, .n_idle,
.n_stuck_hold);
// ---- SHADOW MODEL of the three registers ----
int s_ptr, s_owner, s_busy;
int m_gr, m_arb, m_hold, m_idle, m_stuck;
// ---- BOUNDED-WAITING tracker: for each requester, how many ARBITRATIONS
// ---- have gone to somebody else since it started asking continuously.
int wait_cnt [N];
int worst_wait=0;
int errors=0, i, r, h, p, o, b;
int n_exh=0;
int n_gr_per [N];
int n_arb=0, n_keep=0, n_idl=0, n_stk=0;
function automatic int popcount(input logic [N-1:0] vec);
int c = 0;
for (int bb = 0; bb < N; bb++) if (vec[bb]) c++;
return c;
endfunction
task automatic check(input bit cond, input string msg);
// Icarus will not call .name() on a net, so the enum output is copied
// into a variable of the same type before being printed.
arb_event_e ev_v;
if (!cond) begin
errors++;
ev_v = arb_event;
if (errors <= 25)
$display(" FAIL: %0s (req=%b hold=%b | grant=%b idx=%0d ev=%s ptr=%0d || model ptr=%0d owner=%0d busy=%0d, t=%0t)",
msg, req, hold, grant, grant_idx, ev_v.name(), rr_ptr,
s_ptr, s_owner, s_busy, $time);
end
endtask
// The model searches the ring FORWARD from the pointer and stops at the
// first hit, where the design walks backwards and lets the earliest match
// win the assignment -- a different route to the same winner.
task automatic model(output bit e_keep, output bit e_any,
output int e_win, output bit e_stuck);
int k, idx;
begin
e_keep = (s_busy != 0) && hold && req[s_owner];
e_stuck = (s_busy != 0) && hold && !req[s_owner];
e_any = 1'b0; e_win = 0;
for (k=0; k<N; k=k+1) begin
idx = (s_ptr + k) % N;
if (!e_any && req[idx]) begin e_any = 1'b1; e_win = idx; end
end
end
endtask
task automatic check_comb;
bit e_keep, e_any, e_stuck;
int e_win, e_idx;
logic [N-1:0] e_grant;
arb_event_e e_ev;
begin
model(e_keep, e_any, e_win, e_stuck);
e_idx = e_keep ? s_owner : e_win;
e_grant = (e_keep || e_any) ? (N'(1) << IDW'(e_idx)) : '0;
check(grant_valid === (e_keep || e_any), "grant_valid matches the model");
check(held === e_keep, "held matches the model");
check(grant === e_grant, "grant matches the model");
if (e_keep || e_any)
check(grant_idx === IDW'(e_idx), "grant_idx matches the model");
check(rr_ptr === IDW'(s_ptr), "rr_ptr matches the model");
if (e_keep) e_ev = ARB_HELD;
else if (e_stuck && e_any) e_ev = ARB_REDIRECTED;
else if (e_any) e_ev = ARB_GRANTED;
else e_ev = ARB_IDLE;
check(arb_event === e_ev, "arb_event matches the model");
// The named event must agree with the signals it summarises.
check((arb_event === ARB_HELD) === held,
"arb_event disagrees with held");
check((arb_event === ARB_IDLE) === !grant_valid,
"arb_event disagrees with grant_valid");
// ---- SAFETY PROPERTIES, independent of the model ----
// 1. The grant is ONE-HOT or zero. Two owners of one port is a
// contention, exactly as in chapter 23.1.
check(popcount(grant) <= 1,
"more than one requester was granted the shared port");
// 2. A grant only ever goes to a requester. Granting a port to a
// block that did not ask for it wedges it until it happens to ask.
if (grant_valid)
check(req[grant_idx],
"the port was granted to an endpoint that did not request it");
// 3. grant and grant_valid agree.
check((|grant) === grant_valid, "grant disagrees with grant_valid");
// 4. With no requests and no hold, nothing is granted.
if (req === '0)
check(!grant_valid, "the port was granted with nobody asking");
// 5. THE hold rule. A held grant goes to the PREVIOUS owner, and only
// while that owner is still asking.
if (held) begin
check(grant_idx === IDW'(s_owner),
"a held grant went to somebody other than the current owner");
check(req[s_owner],
"a hold was honoured for an owner that has dropped its request -- the port is now stuck");
end
// 6. A hold from a non-requesting owner is refused, not obeyed.
if (e_stuck)
check(!held,
"a stuck hold was obeyed");
// 7. The pointer moves ONLY on a real arbitration, and it moves to
// one PAST the winner. (Its RANGE is structural -- an IDW-bit
// pointer into a 2**IDW-entry ring cannot leave it -- so range is
// not the property worth asserting; PROVENANCE is. Writing it as
// `rr_ptr < N[IDW-1:0]` would truncate N to zero and never fire.)
if (held || !(|req))
check(rr_ptr === IDW'(s_ptr),
"the pointer moved without a real arbitration");
if (e_keep || e_any) n_gr_per[e_idx] = n_gr_per[e_idx] + 1;
if (e_keep) n_keep = n_keep + 1;
else if (e_any) n_arb = n_arb + 1;
else n_idl = n_idl + 1;
if (e_stuck) n_stk = n_stk + 1;
end
endtask
task automatic model_step;
bit e_keep, e_any, e_stuck;
int e_win, e_idx, k;
begin
model(e_keep, e_any, e_win, e_stuck);
e_idx = e_keep ? s_owner : e_win;
// ---- BOUNDED WAITING. For every requester that is asking and is NOT
// ---- the one being granted by a real arbitration, its wait grows.
// ---- The property is that it never exceeds N-1.
if (!e_keep && e_any) begin
for (k=0; k<N; k=k+1) begin
if (k == e_idx) wait_cnt[k] = 0;
else if (req[k]) begin
wait_cnt[k] = wait_cnt[k] + 1;
if (wait_cnt[k] > worst_wait) worst_wait = wait_cnt[k];
check(wait_cnt[k] <= N-1,
"a continuously-requesting endpoint waited more than N-1 arbitrations -- round robin has degenerated to fixed priority");
end
end
end
// A requester that stops asking is no longer waiting.
for (k=0; k<N; k=k+1) if (!req[k]) wait_cnt[k] = 0;
if (e_keep || e_any) m_gr = m_gr + 1;
if (!e_keep && e_any) m_arb = m_arb + 1;
if (e_keep) m_hold = m_hold + 1;
if (!e_keep && !e_any) m_idle = m_idle + 1;
if (e_stuck) m_stuck = m_stuck + 1;
s_busy = (e_keep || e_any) ? 1 : 0;
s_owner = (e_keep || e_any) ? e_idx : s_owner;
if (!e_keep && e_any) s_ptr = (e_win + 1) % N;
end
endtask
task automatic step;
begin
#1;
check_comb;
model_step;
@(posedge clk); #1;
check(rr_ptr === IDW'(s_ptr), "rr_ptr tracked the model");
check(n_grants === 32'(m_gr), "n_grants matches the model");
check(n_arbitrations === 32'(m_arb), "n_arbitrations matches the model");
check(n_holds === 32'(m_hold), "n_holds matches the model");
check(n_idle === 32'(m_idle), "n_idle matches the model");
check(n_stuck_hold === 32'(m_stuck), "n_stuck_hold matches the model");
end
endtask
task automatic hard_reset;
begin
rst_n=0; req=0; hold=0;
@(posedge clk); #1; @(posedge clk); #1; rst_n=1; #1;
s_ptr=0; s_owner=0; s_busy=0;
m_gr=0; m_arb=0; m_hold=0; m_idle=0; m_stuck=0;
for (i=0;i<N;i=i+1) wait_cnt[i]=0;
end
endtask
// Drive the arbiter to a chosen (pointer, owner, busy) using only real
// arbitrations -- no register forcing. Reaching pointer p means granting
// requester p-1; reaching owner o means granting o last.
task automatic goto_state(input int want_ptr, input int want_owner,
input int want_busy);
int prev;
begin
hard_reset;
if (want_busy != 0) begin
// grant `want_owner` first, which leaves ptr = owner+1
req = N'(1 << want_owner); hold=0; step; req='0; hold=0;
// then walk the pointer round to want_ptr by granting (want_ptr-1)
if (((want_owner + 1) % N) != want_ptr) begin
prev = (want_ptr + N - 1) % N;
req = N'(1 << prev); hold=0; step; req='0;
// and re-establish the owner without moving the pointer further
// is not possible without a grant, so accept that owner follows
// the last grant -- the sweep below covers the reachable pairs.
end
end
req=0; hold=0; #1;
end
endtask
initial begin
void'($urandom(urandom_seed));
foreach (n_gr_per[i]) begin n_gr_per[i]=0; wait_cnt[i]=0; end
hard_reset;
check(!grant_valid, "reset grants nothing");
check(rr_ptr === 2'd0, "and the pointer starts at zero");
// ===== A. EXHAUSTIVE arbitration sweep =====
// Every request pattern x hold x every reachable (pointer, owner, busy):
// 16 req x 2 hold x 4 ptr x 4 owner x 2 busy = 1024 transitions.
// The state is established by REAL grants, then the inputs applied.
for (p=0; p<N; p=p+1)
for (o=0; o<N; o=o+1)
for (b=0; b<2; b=b+1)
for (r=0; r<16; r=r+1)
for (h=0; h<2; h=h+1) begin
// establish (ptr, owner, busy) by granting `o` then walking the
// pointer to `p` -- both by ordinary arbitration
hard_reset;
if (b != 0) begin req = N'(1 << o); hold = 0; step; req='0; end
while (s_ptr != p) begin
req = N'(1 << (s_ptr % N)); hold = 0; step; req = '0;
end
req = N'(r); hold = 1'(h);
step;
n_exh = n_exh + 1;
req = 0; hold = 0;
end
$display(" exhaustive arbitration sweep: %0d transitions verified",
n_exh);
// ===== B. directed: the starvation that fixed priority produces =====
hard_reset;
// 1. Endpoint 1 asks constantly; endpoint 3 asks constantly. Under
// fixed priority endpoint 3 would never be granted. Under round
// robin they alternate.
//
// NOTE the shape of these checks: the grant is COMBINATIONAL on the
// request and the pointer, so it is examined BEFORE `step` advances
// the clock. Checking after the step reads the NEXT arbitration.
req = 4'b1010; hold = 0; #1;
check(grant_idx === 2'd1, "the first arbitration grants endpoint 1");
step; #1;
check(rr_ptr === 2'd2, "and the pointer moves PAST it, to 2");
check(grant_idx === 2'd3, "so the next arbitration grants endpoint 3");
step; #1;
check(rr_ptr === 2'd0, "and the pointer wraps to 0");
check(grant_idx === 2'd1, "and the one after that is endpoint 1 again");
step;
req = 0; step;
// 2. THE bounded-waiting property, watched directly. Endpoint 3 asks
// continuously while 0, 1 and 2 all ask too. It must be granted
// within N arbitrations, every time -- which the tracker in
// model_step asserts on every arbitration, not just here.
hard_reset;
req = 4'b1111; hold = 0;
for (i=0;i<12;i=i+1) step;
check(n_gr_per[3] >= 3,
"endpoint 3 was granted repeatedly despite three competitors");
req = 0; step;
// 3. The hold keeps a burst together.
hard_reset;
req = 4'b0011; hold = 0; #1;
check(grant_idx === 2'd0, "endpoint 0 wins the first arbitration");
step;
hold = 1; #1;
check(held, "with hold asserted the grant is a continuation");
check(grant_idx === 2'd0, "which stays with endpoint 0");
step; #1;
check(held, "and stays held");
check(rr_ptr === 2'd1,
"while the pointer does NOT move -- a hold is not an arbitration");
step;
hold = 0; #1;
check(grant_idx === 2'd1,
"and when the hold drops, the next arbitration goes to endpoint 1");
step;
req = 0; hold = 0; step;
// 4. A hold from an owner that has dropped its request is refused.
hard_reset;
req = 4'b0001; hold = 0; #1;
check(grant_idx === 2'd0, "endpoint 0 takes the port");
step;
req = 4'b0010; hold = 1; #1;
check(!held,
"a hold from an owner that stopped requesting is NOT honoured");
check(grant_idx === 2'd1,
"so the port is arbitrated to the endpoint that IS asking");
step;
check(n_stuck_hold === 32'd1, "and the firmware bug was counted");
req = 0; hold = 0; step;
// 5. No requests, no grant -- even with hold asserted.
hard_reset;
req = 0; hold = 1; #1;
check(!grant_valid, "nobody asking means nobody granted");
check(grant === '0, "and nothing is driven");
step;
// ===== C. randomised =====
hard_reset;
for (i=0;i<40000;i=i+1) begin
req = N'($urandom%16);
hold = ($urandom%3)!=0;
step;
end
foreach (n_gr_per[i])
check(n_gr_per[i] > 1000, "every endpoint was granted many times");
check(n_arb > 5000, "real arbitrations happened often");
check(n_keep > 5000, "held grants happened often");
check(n_idl > 1000, "the port was idle often");
check(n_stk > 500, "stuck holds were presented often");
check(worst_wait <= N-1,
"the worst observed wait exceeded the bound");
$display("");
$display(" REACH: transitions=%0d | grants per endpoint: ep0=%0d ep1=%0d ep2=%0d ep3=%0d",
n_exh, n_gr_per[0], n_gr_per[1], n_gr_per[2], n_gr_per[3]);
$display(" CASES: arbitrations=%0d held=%0d idle=%0d stuck-holds=%0d | WORST WAIT=%0d of a bound of %0d",
n_arb, n_keep, n_idl, n_stk, worst_wait, N-1);
$display(" COUNTERS: grants=%0d arbitrations=%0d holds=%0d idle=%0d stuck=%0d",
n_grants, n_arbitrations, n_holds, n_idle, n_stuck_hold);
$display(" [SystemVerilog] usb_ep_arbiter: %0d errors", errors);
$display(" [SystemVerilog] %0s", errors==0 ? "PASS" : "FAIL");
$display("");
$finish;
end
endmodule9.3 VHDL testbench
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use ieee.math_real.all;
use work.usb_arb_pkg.all;
entity tb_ar_vhdl is
end entity;
architecture sim of tb_ar_vhdl is
constant N : natural := 4;
constant IDW : natural := 2;
signal clk : std_logic := '0';
signal rst_n : std_logic := '0';
signal req : std_logic_vector(N-1 downto 0) := (others => '0');
signal hold : std_logic := '0';
signal grant : std_logic_vector(N-1 downto 0);
signal grant_valid, held : std_logic;
signal grant_idx, rr_ptr : std_logic_vector(IDW-1 downto 0);
signal arb_event : std_logic_vector(1 downto 0);
signal n_grants, n_arbitrations, n_holds, n_idle, n_stuck_hold
: std_logic_vector(31 downto 0);
signal running : boolean := true;
type cntn_t is array (0 to N-1) of integer;
begin
clk <= not clk after 5 ns when running else '0';
dut : entity work.usb_ep_arbiter
generic map (N => N, IDW => IDW)
port map (clk => clk, rst_n => rst_n, req => req, hold => hold,
grant => grant, grant_valid => grant_valid,
grant_idx => grant_idx, held => held, rr_ptr => rr_ptr,
arb_event => arb_event, n_grants => n_grants,
n_arbitrations => n_arbitrations, n_holds => n_holds,
n_idle => n_idle, n_stuck_hold => n_stuck_hold);
stim : process
variable seed1 : positive := 1237;
variable seed2 : positive := 6491;
variable r1 : real;
-- VHDL-2008 requires a shared variable to have a protected type, so the
-- bookkeeping lives inside the single stimulus process instead.
variable errors : integer := 0;
-- SHADOW MODEL of the three registers.
variable s_ptr, s_owner, s_busy : integer := 0;
variable m_gr, m_arb, m_hold, m_idle, m_stuck : integer := 0;
-- BOUNDED-WAITING tracker: for each requester, how many ARBITRATIONS
-- have gone to somebody else since it started asking continuously.
variable wait_cnt : cntn_t := (others => 0);
variable worst_wait : integer := 0;
variable n_exh : integer := 0;
variable n_gr_per : cntn_t := (others => 0);
variable n_arb, n_keep, n_idl, n_stk : integer := 0;
function popcount(v : std_logic_vector) return integer is
variable c : integer := 0;
begin
for b in v'range loop
if v(b) = '1' then c := c + 1; end if;
end loop;
return c;
end function;
procedure check(cond : boolean; msg : string) is
begin
if not cond then
errors := errors + 1;
if errors <= 25 then
report " FAIL: " & msg
& " (req=" & integer'image(to_integer(unsigned(req)))
& " hold=" & std_logic'image(hold)(2)
& " | grant=" & integer'image(to_integer(unsigned(grant)))
& " idx=" & integer'image(to_integer(unsigned(grant_idx)))
& " ev=" & integer'image(to_integer(unsigned(arb_event)))
& " ptr=" & integer'image(to_integer(unsigned(rr_ptr)))
& " || model ptr=" & integer'image(s_ptr)
& " owner=" & integer'image(s_owner)
& " busy=" & integer'image(s_busy)
& ")" severity note;
end if;
end if;
end procedure;
procedure rnd(variable v : out integer; m : integer) is
begin
uniform(seed1, seed2, r1);
v := integer(floor(r1 * real(m)));
end procedure;
-- The model searches the ring FORWARD from the pointer and stops at the
-- first hit, where the design walks backwards and lets the earliest
-- match win the assignment -- a different route to the same winner.
procedure model(variable e_keep, e_any, e_stuck : out boolean;
variable e_win : out integer) is
variable idx : integer;
variable found : boolean := false;
variable w : integer := 0;
begin
e_keep := s_busy /= 0 and hold = '1' and req(s_owner) = '1';
e_stuck := s_busy /= 0 and hold = '1' and req(s_owner) = '0';
found := false; w := 0;
for k in 0 to N-1 loop
idx := (s_ptr + k) mod N;
if not found and req(idx) = '1' then
found := true; w := idx;
end if;
end loop;
e_any := found;
e_win := w;
end procedure;
procedure check_comb is
variable e_keep, e_any, e_stuck : boolean;
variable e_win, e_idx : integer;
variable e_grant : std_logic_vector(N-1 downto 0);
variable e_ev : arb_event_t;
begin
model(e_keep, e_any, e_stuck, e_win);
if e_keep then e_idx := s_owner; else e_idx := e_win; end if;
e_grant := (others => '0');
if e_keep or e_any then e_grant(e_idx) := '1'; end if;
check((grant_valid = '1') = (e_keep or e_any),
"grant_valid matches the model");
check((held = '1') = e_keep, "held matches the model");
check(grant = e_grant, "grant matches the model");
if e_keep or e_any then
check(to_integer(unsigned(grant_idx)) = e_idx,
"grant_idx matches the model");
end if;
check(to_integer(unsigned(rr_ptr)) = s_ptr, "rr_ptr matches the model");
if e_keep then e_ev := ARB_HELD;
elsif e_stuck and e_any then e_ev := ARB_REDIRECTED;
elsif e_any then e_ev := ARB_GRANTED;
else e_ev := ARB_IDLE;
end if;
check(arb_event = ev_code(e_ev), "arb_event matches the model");
-- The named event must agree with the signals it summarises.
check((arb_event = ev_code(ARB_HELD)) = (held = '1'),
"arb_event disagrees with held");
check((arb_event = ev_code(ARB_IDLE)) = (grant_valid = '0'),
"arb_event disagrees with grant_valid");
-- ---- SAFETY PROPERTIES, independent of the model ----
-- 1. The grant is ONE-HOT or zero.
check(popcount(grant) <= 1,
"more than one requester was granted the shared port");
-- 2. A grant only ever goes to a requester.
if grant_valid = '1' then
check(req(to_integer(unsigned(grant_idx))) = '1',
"the port was granted to an endpoint that did not request it");
end if;
-- 3. grant and grant_valid agree.
check((grant /= (grant'range => '0')) = (grant_valid = '1'),
"grant disagrees with grant_valid");
-- 4. With no requests and no hold, nothing is granted.
if req = (req'range => '0') then
check(grant_valid = '0', "the port was granted with nobody asking");
end if;
-- 5. THE hold rule.
if held = '1' then
check(to_integer(unsigned(grant_idx)) = s_owner,
"a held grant went to somebody other than the current owner");
check(req(s_owner) = '1',
"a hold was honoured for an owner that has dropped its request -- the port is now stuck");
end if;
-- 6. A hold from a non-requesting owner is refused, not obeyed.
if e_stuck then
check(held = '0', "a stuck hold was obeyed");
end if;
-- 7. The pointer moves ONLY on a real arbitration. (Its RANGE is
-- structural; PROVENANCE is the property worth asserting.)
if held = '1' or req = (req'range => '0') then
check(to_integer(unsigned(rr_ptr)) = s_ptr,
"the pointer moved without a real arbitration");
end if;
if e_keep or e_any then n_gr_per(e_idx) := n_gr_per(e_idx) + 1; end if;
if e_keep then n_keep := n_keep + 1;
elsif e_any then n_arb := n_arb + 1;
else n_idl := n_idl + 1; end if;
if e_stuck then n_stk := n_stk + 1; end if;
end procedure;
procedure model_step is
variable e_keep, e_any, e_stuck : boolean;
variable e_win, e_idx : integer;
begin
model(e_keep, e_any, e_stuck, e_win);
if e_keep then e_idx := s_owner; else e_idx := e_win; end if;
-- ---- BOUNDED WAITING. For every requester that is asking and is NOT
-- ---- the one being granted by a real arbitration, its wait grows.
-- ---- The property is that it never exceeds N-1.
if not e_keep and e_any then
for k in 0 to N-1 loop
if k = e_idx then
wait_cnt(k) := 0;
elsif req(k) = '1' then
wait_cnt(k) := wait_cnt(k) + 1;
if wait_cnt(k) > worst_wait then worst_wait := wait_cnt(k); end if;
check(wait_cnt(k) <= N-1,
"a continuously-requesting endpoint waited more than N-1 arbitrations -- round robin has degenerated to fixed priority");
end if;
end loop;
end if;
-- A requester that stops asking is no longer waiting.
for k in 0 to N-1 loop
if req(k) = '0' then wait_cnt(k) := 0; end if;
end loop;
if e_keep or e_any then m_gr := m_gr + 1; end if;
if not e_keep and e_any then m_arb := m_arb + 1; end if;
if e_keep then m_hold := m_hold + 1; end if;
if not e_keep and not e_any then m_idle := m_idle + 1; end if;
if e_stuck then m_stuck := m_stuck + 1; end if;
if e_keep or e_any then s_busy := 1; else s_busy := 0; end if;
if e_keep or e_any then s_owner := e_idx; end if;
if not e_keep and e_any then s_ptr := (e_win + 1) mod N; end if;
end procedure;
procedure step is
begin
wait for 1 ns;
check_comb;
model_step;
wait until rising_edge(clk);
wait for 1 ns;
check(to_integer(unsigned(rr_ptr)) = s_ptr, "rr_ptr tracked the model");
check(n_grants = std_logic_vector(to_unsigned(m_gr, 32)),
"n_grants matches the model");
check(n_arbitrations = std_logic_vector(to_unsigned(m_arb, 32)),
"n_arbitrations matches the model");
check(n_holds = std_logic_vector(to_unsigned(m_hold, 32)),
"n_holds matches the model");
check(n_idle = std_logic_vector(to_unsigned(m_idle, 32)),
"n_idle matches the model");
check(n_stuck_hold = std_logic_vector(to_unsigned(m_stuck, 32)),
"n_stuck_hold matches the model");
end procedure;
procedure hard_reset is
begin
rst_n <= '0'; req <= (others => '0'); hold <= '0';
wait until rising_edge(clk); wait for 1 ns;
wait until rising_edge(clk); wait for 1 ns;
rst_n <= '1'; wait for 1 ns;
s_ptr := 0; s_owner := 0; s_busy := 0;
m_gr := 0; m_arb := 0; m_hold := 0; m_idle := 0; m_stuck := 0;
wait_cnt := (others => 0);
end procedure;
procedure setreq(v : integer) is
begin
req <= std_logic_vector(to_unsigned(v, N));
end procedure;
variable iv : integer;
begin
hard_reset;
check(grant_valid = '0', "reset grants nothing");
check(to_integer(unsigned(rr_ptr)) = 0, "and the pointer starts at zero");
-- ===== A. EXHAUSTIVE arbitration sweep =====
-- Every request pattern x hold x every reachable (pointer, owner, busy):
-- 16 req x 2 hold x 4 ptr x 4 owner x 2 busy = 1024 transitions.
-- The state is established by REAL grants, then the inputs applied.
for p in 0 to N-1 loop
for o in 0 to N-1 loop
for b in 0 to 1 loop
for r in 0 to 15 loop
for h in 0 to 1 loop
hard_reset;
if b /= 0 then
setreq(2**o); hold <= '0'; step; setreq(0);
end if;
while s_ptr /= p loop
setreq(2**(s_ptr mod N)); hold <= '0'; step; setreq(0);
end loop;
setreq(r);
if h = 1 then hold <= '1'; else hold <= '0'; end if;
step;
n_exh := n_exh + 1;
setreq(0); hold <= '0';
end loop;
end loop;
end loop;
end loop;
end loop;
report " exhaustive arbitration sweep: " & integer'image(n_exh)
& " transitions verified" severity note;
-- ===== B. directed: the starvation that fixed priority produces =====
hard_reset;
-- 1. Endpoints 1 and 3 ask constantly. Under fixed priority endpoint 3
-- would never be granted; under round robin they alternate.
--
-- NOTE the shape: the grant is COMBINATIONAL on the request and the
-- pointer, so it is examined BEFORE `step` advances the clock.
setreq(2#1010#); hold <= '0'; wait for 1 ns;
check(to_integer(unsigned(grant_idx)) = 1,
"the first arbitration grants endpoint 1");
step; wait for 1 ns;
check(to_integer(unsigned(rr_ptr)) = 2,
"and the pointer moves PAST it, to 2");
check(to_integer(unsigned(grant_idx)) = 3,
"so the next arbitration grants endpoint 3");
step; wait for 1 ns;
check(to_integer(unsigned(rr_ptr)) = 0, "and the pointer wraps to 0");
check(to_integer(unsigned(grant_idx)) = 1,
"and the one after that is endpoint 1 again");
step;
setreq(0); step;
-- 2. THE bounded-waiting property, watched directly.
hard_reset;
setreq(2#1111#); hold <= '0';
for i in 0 to 11 loop step; end loop;
check(n_gr_per(3) >= 3,
"endpoint 3 was granted repeatedly despite three competitors");
setreq(0); step;
-- 3. The hold keeps a burst together.
hard_reset;
setreq(2#0011#); hold <= '0'; wait for 1 ns;
check(to_integer(unsigned(grant_idx)) = 0,
"endpoint 0 wins the first arbitration");
step;
hold <= '1'; wait for 1 ns;
check(held = '1', "with hold asserted the grant is a continuation");
check(to_integer(unsigned(grant_idx)) = 0,
"which stays with endpoint 0");
step; wait for 1 ns;
check(held = '1', "and stays held");
check(to_integer(unsigned(rr_ptr)) = 1,
"while the pointer does NOT move -- a hold is not an arbitration");
step;
hold <= '0'; wait for 1 ns;
check(to_integer(unsigned(grant_idx)) = 1,
"and when the hold drops, the next arbitration goes to endpoint 1");
step;
setreq(0); hold <= '0'; step;
-- 4. A hold from an owner that has dropped its request is refused.
hard_reset;
setreq(2#0001#); hold <= '0'; wait for 1 ns;
check(to_integer(unsigned(grant_idx)) = 0, "endpoint 0 takes the port");
step;
setreq(2#0010#); hold <= '1'; wait for 1 ns;
check(held = '0',
"a hold from an owner that stopped requesting is NOT honoured");
check(to_integer(unsigned(grant_idx)) = 1,
"so the port is arbitrated to the endpoint that IS asking");
step;
check(n_stuck_hold = std_logic_vector(to_unsigned(1, 32)),
"and the firmware bug was counted");
setreq(0); hold <= '0'; step;
-- 5. No requests, no grant -- even with hold asserted.
hard_reset;
setreq(0); hold <= '1'; wait for 1 ns;
check(grant_valid = '0', "nobody asking means nobody granted");
check(grant = (grant'range => '0'), "and nothing is driven");
step;
-- ===== C. randomised =====
-- ieee.math_real.uniform is a genuinely different generator from either
-- Verilog builtin, which is what makes this column independent evidence.
hard_reset;
for i in 0 to 39999 loop
rnd(iv, 16); setreq(iv);
rnd(iv, 3); if iv /= 0 then hold <= '1'; else hold <= '0'; end if;
step;
end loop;
for i in 0 to N-1 loop
check(n_gr_per(i) > 1000, "every endpoint was granted many times");
end loop;
check(n_arb > 5000, "real arbitrations happened often");
check(n_keep > 5000, "held grants happened often");
check(n_idl > 1000, "the port was idle often");
check(n_stk > 500, "stuck holds were presented often");
check(worst_wait <= N-1, "the worst observed wait exceeded the bound");
report " REACH: transitions=" & integer'image(n_exh)
& " | grants per endpoint: ep0=" & integer'image(n_gr_per(0))
& " ep1=" & integer'image(n_gr_per(1))
& " ep2=" & integer'image(n_gr_per(2))
& " ep3=" & integer'image(n_gr_per(3)) severity note;
report " CASES: arbitrations=" & integer'image(n_arb)
& " held=" & integer'image(n_keep)
& " idle=" & integer'image(n_idl)
& " stuck-holds=" & integer'image(n_stk)
& " | WORST WAIT=" & integer'image(worst_wait)
& " of a bound of " & integer'image(N-1) severity note;
report " COUNTERS: grants="
& integer'image(to_integer(unsigned(n_grants)))
& " arbitrations=" & integer'image(to_integer(unsigned(n_arbitrations)))
& " holds=" & integer'image(to_integer(unsigned(n_holds)))
& " idle=" & integer'image(to_integer(unsigned(n_idle)))
& " stuck=" & integer'image(to_integer(unsigned(n_stuck_hold)))
severity note;
report " [VHDL] usb_ep_arbiter: " & integer'image(errors) & " errors"
severity note;
if errors = 0 then
report " [VHDL] PASS" severity note;
else
report " [VHDL] FAIL" severity failure;
end if;
running <= false;
wait;
end process;
end architecture;10. Exhaustive Verification
| Measure | Verilog | SystemVerilog | VHDL |
|---|---|---|---|
| Exhaustive transitions | 1024 | 1024 | 1024 |
| grants to endpoint 0 | 10402 | 10424 | 10166 |
| grants to endpoint 1 | 10184 | 10170 | 10252 |
| grants to endpoint 2 | 10089 | 10180 | 10179 |
| grants to endpoint 3 | 9853 | 9783 | 9913 |
| real arbitrations | 27890 | 27943 | 27694 |
| held grants | 12638 | 12614 | 12816 |
| idle cycles | 2570 | 2541 | 2588 |
| stuck holds refused | 12870 | 12807 | 12766 |
| worst observed wait | 3 of 3 | 3 of 3 | 3 of 3 |
| Result | PASS | PASS | PASS |
The grants-per-endpoint row is the fairness claim as a measurement: 10 402 / 10 184 / 10 089 / 9853 across four endpoints under random load, a spread of 5%. A fixed-priority arbiter under the same stimulus would read roughly 20 000 / 10 000 / 5 000 / 2 500.
And worst observed wait = 3, against a bound of 3. The bound is not merely respected; it is reached, which means the sweep drove the arbiter into the corner the guarantee is about rather than staying comfortably inside it.
11. Mutation Testing
| # | Mutation | Verilog | SysVer | VHDL |
|---|---|---|---|---|
| R1 | the pointer never advances — fixed priority | 231423 | 231844 | 231331 |
| R2 | the hold is ignored; bursts are broken | 202314 | 202257 | 203253 |
| R3 | the pointer advances to the winner, not past | 244460 | 244076 | 245747 |
| R4 | a grant is issued with nobody asking | 223963 | 223609 | 223856 |
| R5 | the ring search clamps instead of wrapping | 258033 | 258131 | 256126 |
| R6 | a hold from a non-requesting owner is honoured | 387914 | 385748 | 386035 |
| R7 | the grant is not one-hot — endpoint 0 always set | 60252 | 60266 | 60688 |
| — | unmutated baseline | 0 | 0 | 0 |
All seven die, all counts distinct, columns within 1%.
R1, R3 and R5 are the three ways to break bounded waiting, and all three are caught by the tracker as well as by the model. R5 is the largest of the three (~258 000) because clamping the search means the requesters below the pointer are never reached, which is worse than the pointer not moving: R1 at least still serves whoever the fixed priority favours.
R6 is the largest in the table at ~387 000 — honouring a hold from an owner that has stopped requesting. Note why it is so large: every subsequent cycle is wrong, because the port is stuck with an endpoint that will never release it. It is the only mutation here that does not recover, and that is exactly the property that makes a stuck grant so much worse than an unfair one.
R7 is the smallest at ~60 000, and it is the one-hot violation. It is worth comparing against 23.1's Q4, the same bug in the decode: both assert an extra bit, both are caught by a popcount property, and both are an order of magnitude smaller than the mutations that change which endpoint is served. A contention is rarer than a wrong answer and considerably harder to debug, which is the argument for asserting one-hotness rather than inferring it.
12. Debugging Walkthrough: The Mouse That Stutters During a File Copy
The report. A composite USB device — a keyboard, a mouse and a mass-storage partition in one enclosure — has a mouse pointer that becomes visibly jerky whenever a large file is written to it. The keyboard is fine. The file copy is fast.
Step 1 — is it bandwidth? Measure. The mouse's interrupt endpoint is 8 bytes every 10 ms; the bus is high speed. The reservation is a rounding error, and the host's periodic budget (Chapter 22.3) is nowhere near full. There is bandwidth to spare.
Step 2 — is the host scheduling it? Trace the bus. The host issues the interrupt IN token every microframe as expected. The device NAKs most of them.
Step 3 — why would it NAK? A NAK on an interrupt IN means the endpoint has no data ready. Firmware is producing mouse reports on time, so the data exists — it has not reached the endpoint FIFO.
Step 4 — what is between firmware and the FIFO? The shared port and its arbiter. Instrument n_grants per endpoint. The bulk endpoint has 98% of the grants; the interrupt endpoint has 0.4%.
Step 5 — why. The arbiter's pointer was not advancing: every search started at 0, found the bulk endpoint requesting, and granted it. Mutation R1, in production — fixed priority wearing a round-robin pointer that never moves.
Step 6 — why the keyboard is fine. A keyboard produces data only when a key is pressed, so its endpoint requests rarely and gets served whenever the bulk endpoint happens to pause. The mouse produces a report every 10 ms regardless, so it is the one that notices.
13. UVM and Assertions
13.1 The sequences
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
class usb_arb_item extends uvm_sequence_item;
`uvm_object_utils(usb_arb_item)
rand bit [3:0] req;
rand bit hold;
// A real device has a bulk endpoint that asks nearly always and
// interrupt endpoints that ask periodically.
constraint c_realistic { req[1] dist {1 := 9, 0 := 1}; }
constraint c_hold_common { hold dist {1 := 2, 0 := 1}; }
function new(string name = "usb_arb_item"); super.new(name); endfunction
endclass
// THE sequence for this chapter. One endpoint asks CONTINUOUSLY while the
// others also ask -- the population in which bounded waiting either holds or
// does not. Random traffic produces continuous requests only by accident,
// and starvation is invisible unless a requester asks for long enough to be
// starved.
class continuous_requester_seq extends uvm_sequence #(usb_arb_item);
`uvm_object_utils(continuous_requester_seq)
function new(string name = "continuous_requester_seq"); super.new(name); endfunction
task body();
repeat (400) begin
usb_arb_item it = usb_arb_item::type_id::create("it");
start_item(it);
it.c_realistic.constraint_mode(0);
it.c_hold_common.constraint_mode(0);
// everybody asks, nobody holds -- pure arbitration
if (!it.randomize() with { req == 4'b1111; hold == 0; })
`uvm_error("RAND", "continuous randomize failed")
finish_item(it);
end
endtask
endclass
// The bulk-versus-interrupt pattern from the debugging walkthrough: endpoint
// 1 asks on every cycle, endpoint 3 asks in bursts. Under fixed priority
// endpoint 3 is granted 0.4% of the time; under round robin, half.
class bulk_vs_interrupt_seq extends uvm_sequence #(usb_arb_item);
`uvm_object_utils(bulk_vs_interrupt_seq)
function new(string name = "bulk_vs_interrupt_seq"); super.new(name); endfunction
task body();
repeat (100) begin
usb_arb_item it;
// ten cycles of bulk alone
repeat (10) begin
it = usb_arb_item::type_id::create("it");
start_item(it);
it.c_realistic.constraint_mode(0);
it.c_hold_common.constraint_mode(0);
if (!it.randomize() with { req == 4'b0010; hold == 0; })
`uvm_error("RAND", "bulk randomize failed")
finish_item(it);
end
// then the interrupt endpoint joins, and must be served promptly
repeat (4) begin
it = usb_arb_item::type_id::create("it");
start_item(it);
it.c_realistic.constraint_mode(0);
it.c_hold_common.constraint_mode(0);
if (!it.randomize() with { req == 4'b1010; hold == 0; })
`uvm_error("RAND", "mixed randomize failed")
finish_item(it);
end
end
endtask
endclass
// A burst: one endpoint takes the port and holds it, while others queue up.
// The property under test is that the hold is honoured while the owner still
// asks and refused the instant it stops.
class burst_and_release_seq extends uvm_sequence #(usb_arb_item);
`uvm_object_utils(burst_and_release_seq)
function new(string name = "burst_and_release_seq"); super.new(name); endfunction
task body();
repeat (300) begin
usb_arb_item it;
int unsigned len = $urandom_range(2, 6);
// take the port
it = usb_arb_item::type_id::create("it");
start_item(it);
it.c_realistic.constraint_mode(0);
it.c_hold_common.constraint_mode(0);
if (!it.randomize() with { req == 4'b1001; hold == 0; })
`uvm_error("RAND", "take randomize failed")
finish_item(it);
// hold it for a burst
repeat (len) begin
it = usb_arb_item::type_id::create("it");
start_item(it);
it.c_realistic.constraint_mode(0);
it.c_hold_common.constraint_mode(0);
if (!it.randomize() with { req == 4'b1001; hold == 1; })
`uvm_error("RAND", "burst randomize failed")
finish_item(it);
end
// ...and then STOP asking while still asserting hold. The arbiter must
// refuse it and give the port to somebody who is asking.
it = usb_arb_item::type_id::create("it");
start_item(it);
it.c_realistic.constraint_mode(0);
it.c_hold_common.constraint_mode(0);
if (!it.randomize() with { req == 4'b1000; hold == 1; })
`uvm_error("RAND", "stuck randomize failed")
finish_item(it);
end
endtask
endclass13.2 The scoreboard, with the bounded-waiting tracker
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
class usb_arb_scoreboard extends uvm_scoreboard;
`uvm_component_utils(usb_arb_scoreboard)
uvm_analysis_imp #(usb_arb_mon_item, usb_arb_scoreboard) ap;
localparam int N = 4;
int unsigned sb_ptr;
int unsigned wait_cnt[N]; // arbitrations lost while requesting
int unsigned worst_wait;
int unsigned n_grants[N];
int unsigned n_arb, n_held, n_stuck;
function new(string name, uvm_component parent);
super.new(name, parent);
ap = new("ap", this);
endfunction
function automatic int popcount(bit [N-1:0] v);
int c = 0;
foreach (v[i]) if (v[i]) c++;
return c;
endfunction
function void write(usb_arb_mon_item t);
// ---- The grant is ONE-HOT or zero ----
if (popcount(t.grant) > 1)
`uvm_error("CONTENTION",
$sformatf("grant=%b has %0d bits set -- two endpoints are driving the shared port",
t.grant, popcount(t.grant)))
// ---- A grant only ever goes to a requester ----
if (t.grant_valid && !t.req[t.grant_idx])
`uvm_error("PHANTOM",
"the port was granted to an endpoint that did not request it")
// ---- A held grant belongs to the previous owner, and only while that
// ---- owner is STILL asking. A hold that outlives its request is a
// ---- stuck port with no timeout to rescue it.
if (t.held && !t.req[t.grant_idx])
`uvm_error("STUCK",
"a hold was honoured for an owner that has dropped its request -- the port will never come back")
// ---- THE property. BOUNDED WAITING. ----
if (t.grant_valid && !t.held) begin
foreach (wait_cnt[k]) begin
if (k == t.grant_idx) wait_cnt[k] = 0;
else if (t.req[k]) begin
wait_cnt[k]++;
if (wait_cnt[k] > worst_wait) worst_wait = wait_cnt[k];
if (wait_cnt[k] > N-1)
`uvm_error("STARVATION",
$sformatf("endpoint %0d has now lost %0d consecutive arbitrations while requesting -- the bound is %0d, and round robin has degenerated to fixed priority",
k, wait_cnt[k], N-1))
end
end
// the pointer must move PAST the winner
sb_ptr = (t.grant_idx + 1) % N;
if (t.rr_ptr_after !== sb_ptr)
`uvm_error("POINTER",
$sformatf("rr_ptr=%0d after granting %0d, expected %0d -- the pointer must advance PAST the winner or that endpoint wins again immediately",
t.rr_ptr_after, t.grant_idx, sb_ptr))
n_arb++;
n_grants[t.grant_idx]++;
end else if (t.held) begin
// a hold is NOT an arbitration: the pointer must not move
if (t.rr_ptr_after !== t.rr_ptr_before)
`uvm_error("POINTER",
"the pointer moved on a held grant -- a hold is not an arbitration")
n_held++;
n_grants[t.grant_idx]++;
end
foreach (wait_cnt[k]) if (!t.req[k]) wait_cnt[k] = 0;
endfunction
function void report_phase(uvm_phase phase);
`uvm_info("SB", $sformatf("grants=%p arbitrations=%0d held=%0d worst wait=%0d of %0d",
n_grants, n_arb, n_held, worst_wait, N-1), UVM_LOW)
// Every endpoint must have been granted, and the bound must have been
// APPROACHED -- a run whose worst wait is 0 never put the arbiter under
// any contention at all.
foreach (n_grants[i])
if (n_grants[i] == 0)
`uvm_error("COVERAGE",
$sformatf("endpoint %0d was never granted", i))
if (worst_wait < N-1)
`uvm_error("COVERAGE",
$sformatf("the worst observed wait was %0d of a bound of %0d -- the arbiter was never driven into the corner the guarantee is about",
worst_wait, N-1))
if (n_held == 0) `uvm_error("COVERAGE", "no burst was ever held")
endfunction
endclassThe last report_phase check is the one that is easy to leave out and worth keeping. A run whose worst observed wait is 0 or 1 has not tested bounded waiting — it has demonstrated that the arbiter works when nothing is competing. Requiring the bound to be reached turns the guarantee from a claim into a measurement, and it is why the suites report WORST WAIT=3 of a bound of 3 rather than simply passing.
13.3 Assertions
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
module usb_ep_arbiter_sva
import usb_arb_pkg::*;
#(
parameter int N = 4,
parameter int IDW = 2
) (
input logic clk,
input logic rst_n,
input logic [N-1:0] req,
input logic hold,
input logic [N-1:0] grant,
input logic grant_valid,
input logic [IDW-1:0] grant_idx,
input logic held,
input logic [IDW-1:0] rr_ptr,
input arb_event_e arb_event
);
default clocking cb @(posedge clk); endclocking
default disable iff (!rst_n);
// ---- 1. The grant is ONE-HOT or zero. ----
property p_grant_onehot0;
$onehot0(grant);
endproperty
a_grant_onehot0 : assert property (p_grant_onehot0)
else $error("grant=%b -- two endpoints are driving the shared port", grant);
// ---- 2. A grant only ever goes to a requester. ----
property p_grant_to_a_requester;
grant_valid |-> req[grant_idx];
endproperty
a_grant_to_a_requester : assert property (p_grant_to_a_requester)
else $error("the port was granted to an endpoint that did not ask");
// ---- 3. Nobody asking, nobody granted. ----
property p_no_request_no_grant;
(req == '0) |-> !grant_valid;
endproperty
a_no_request_no_grant : assert property (p_no_request_no_grant);
// ---- 4. THE hold rule. A hold is honoured only while the owner asks. ----
property p_hold_needs_a_request;
held |-> req[grant_idx];
endproperty
a_hold_needs_a_request : assert property (p_hold_needs_a_request)
else $error("a hold outlived its request -- the port is stuck with no timeout to rescue it");
// ---- 5. A hold does NOT move the pointer. ----
property p_hold_is_not_an_arbitration;
held |=> $stable(rr_ptr);
endproperty
a_hold_is_not_an_arbitration :
assert property (p_hold_is_not_an_arbitration)
else $error("the pointer moved on a held grant");
// ---- 6. THE round-robin rule. A real arbitration moves the pointer to
// ---- one PAST the winner -- not to it, and not nowhere.
property p_pointer_advances_past_winner;
(grant_valid && !held)
|=> (rr_ptr == ((IDW'($past(grant_idx)) == IDW'(N-1))
? '0 : $past(grant_idx) + 1'b1));
endproperty
a_pointer_advances_past_winner :
assert property (p_pointer_advances_past_winner)
else $error("the pointer did not advance past the winner -- round robin has degenerated");
// ---- 7. The pointer moves ONLY on a real arbitration. ----
property p_pointer_moves_only_on_arbitration;
(!$stable(rr_ptr)) |-> $past(grant_valid && !held);
endproperty
a_pointer_moves_only_on_arbitration :
assert property (p_pointer_moves_only_on_arbitration);
// ---- 8. BOUNDED WAITING, as a bounded-liveness property. A requester
// ---- that asks continuously is granted within N arbitrations.
//
// Written with a bounded range rather than an eventually operator:
// `s_eventually` is unbounded and therefore not what the design
// guarantees. The guarantee is a NUMBER.
property p_bounded_waiting;
@(posedge clk) disable iff (!rst_n)
(req[0] throughout (grant_valid && !held)[->N])
|-> (grant_idx == 0) or ##0 1'b1;
endproperty
// (stated for requester 0; the parameterised form is generated for each)
// ---- 9. The named event agrees with the signals it summarises. ----
property p_event_agrees;
((arb_event == ARB_HELD) == held)
&& ((arb_event == ARB_IDLE) == !grant_valid);
endproperty
a_event_agrees : assert property (p_event_agrees);
// ---- Cover: contention, bursts, and a stuck hold being overridden. ----
c_all_requesting : cover property ((req == '4'b1111));
c_burst : cover property ((held ##1 held ##1 held));
c_redirected : cover property ((arb_event == ARB_REDIRECTED));
c_wrap : cover property ((grant_valid && !held
&& (grant_idx == IDW'(N-1))));
endmodule
bind usb_ep_arbiter usb_ep_arbiter_sva #(.N(N), .IDW(IDW)) u_sva (.*);14. Common Misconceptions
"Fixed priority is fine if the high-priority endpoint is bursty." It is fine until it is not, and the load that makes it fail is exactly the load the deadline was specified for.
"Round robin is fair, so deadlines are met." Round robin gives bounded waiting, which is a number. "Fair" is not a property you can put in a latency budget.
"The pointer should move to the winner." It must move past the winner, or that requester is searched first again and wins every time.
"A search that does not wrap is nearly as good." It never reaches the requesters below the pointer at all — mutation R5, the largest of the three starvation bugs.
"busy && hold is enough to hold a grant." It lets an endpoint that has finished own the port for ever. There is no timeout to rescue it.
"A refused hold is a corner case not worth counting." It is a firmware bug, and an uncounted one is invisible. n_stuck_hold is a handful of flops.
"Throughput proves the arbiter is fair." Aggregate throughput is exactly what a starving arbiter delivers. Grants per requester is the measurement.
15. Exercises
1. Stop the pointer advancing (mutation R1) and predict which fires first: the model check, safety property 7, or the bounded-waiting tracker. Then run it and explain why R5 scores higher than R1.
2. The bound is N−1. Prove it from the search rule, then find the stimulus that reaches it — and check that the suites' worst_wait does reach it.
3. Add a weighted round robin in which endpoint 1 gets two consecutive turns. What does the bound become, and which of the nine SVA properties needs changing?
4. R7 asserts an extra grant bit and scores ~60 000 — an order of magnitude below the mutations that change which endpoint is served. Argue from that number whether $onehot0 is worth asserting, and compare with Chapter 23.1's Q4.
5. Property 8 is sketched rather than complete. Write it properly for a parameterised N, then argue whether you would ship it or keep the scoreboard counter.
6. N[IDW-1:0] truncates to zero for every power-of-two N. Write the lint rule that would have caught it in both this chapter and 22.2, and say why a testbench cannot.
16. Summary
| Idea | Why it matters |
|---|---|
| Fixed priority starves | and worst exactly under the load the deadline assumed |
| Round robin gives bounded waiting | a number, not a feeling |
| The pointer must advance | or it is fixed priority with extra registers |
| ...and advance past the winner | or that requester wins again immediately |
| The search must wrap | or half the ring is never reached |
| A hold needs a live request | busy && hold alone is a permanently stuck port |
| A refused hold is counted | an uncounted firmware bug is invisible |
| A grant and a held grant look identical | only one of them moves the pointer |
N[IDW-1:0] truncates to zero | the same trap as Chapter 22.2, made twice |
| Grants per requester is the diagnostic | throughput is what a starving arbiter delivers |
| 1024 transitions, every state walked into | plus a bounded-waiting tracker on every arbitration |
| 7 mutations, all killed in 3 languages | and the worst wait measured at exactly the bound |
Tooling
| Step | Command |
|---|---|
| Verilog-2005 | iverilog -g2005 -o ar_v.out ar_v.v ar_v_tb.v && ./ar_v.out |
| SystemVerilog | iverilog -g2012 -o ar_sv.out ar_sv.sv ar_sv_tb.sv && ./ar_sv.out |
| VHDL-2008 analyse | nvc --std=2008 -a ar_vhdl.vhd ar_vhdl_tb.vhd |
| VHDL-2008 elaborate | nvc --std=2008 -e tb_ar_vhdl |
| VHDL-2008 run | nvc --std=2008 -r tb_ar_vhdl |
| One mutation | iverilog -g2005 -DMUT_R1 -o mm ar_v_mut.v ar_v_tb.v && ./mm |
All three implementations pass with 0 errors: 1024 exhaustive transitions, 40 000 randomised cycles, every endpoint granted, and the worst observed wait exactly at the bound of N−1.
Chapter 23.3 — FIFO Design is about a number that is almost always chosen wrong: the almost-full watermark. Backpressure takes time to arrive, and writes already in flight land after it. A watermark set at "full" overflows by exactly the pipeline depth — every time, silently, and only under sustained load.
Continue learning
Related tutorials
- Related topic
Host Scheduling Algorithm
Pending, eligible and granted are three different things. An arbiter verified exhaustively over 262144 points — and the reference-model coupling that made four invariant mutations die by a single check each.
- Related topic
USB on FPGA Development Boards
The connector on the board does not reach the FPGA — it reaches a bridge chip, and what arrives on the pins is a byte FIFO with two active-low flags and a bus turnaround. Built as a synchronous FIFO bus master, where the bug that matters starves one direction forever and corrupts nothing.
- Related topic
Endpoint Logic
A lost ACK and a lost data packet look identical to the host, so it resends the same bytes — and the data toggle is the only thing that tells a device a retransmission from new data.
- Related topic
The Scheduling Question
Periodic traffic is placed first because that is how admission control's promise is kept — and bulk is round-robin because a rotating pointer is the only fairness mechanism in the entire schedule.
Standards & specifications
- Governing standard
- USB-IF (Universal Serial Bus Specification)(opens USB Implementers Forum (USB-IF) in a new tab)
Defines the USB bus — its electrical signalling, connectors, packet and transaction model, device framework and the descriptors a device must expose — together with the device-class specifications layered on it. It does not define host-controller register interfaces (xHCI and EHCI are separate documents) nor any operating system's driver architecture.
This page also covers RTL structure, verification approach and debugging technique. Those are engineering practice built on the standard, not requirements the standard itself imposes.
Where this fits
Part of the USB curriculum.