USB · Module 22
Host-Side Scheduling
A USB transaction cannot be stopped once its token goes out, so the scheduler must ask whether it will finish before it starts — and the periodic reserve exists to protect bulk traffic, not to limit isochronous.
22.1 and 22.2 were about how a host controller finds work. This chapter is about the other half of its job: deciding what actually runs this frame — and it turns on a constraint most schedulers do not have.
1. The Frame Is a Hard Boundary
The bus is divided into frames — 1 ms on full speed, 125 µs microframes on high speed — and each one begins with a Start-of-Frame packet that every device on the bus can see. Devices time their isochronous and interrupt endpoints against it.
So the boundary is not a scheduling convenience or a bookkeeping period. It is a thing devices observe, and a transaction still on the wire when the next SOF is due does not merely finish late: it collides with the SOF, and every device on the bus loses its timing reference for that frame.
2. You Cannot Start a Transaction You Cannot Finish
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
There is no mechanism to stop a USB transaction once the
token has gone out.
The device WILL reply. The data WILL flow. The handshake
WILL come back -- all at the bus's pace, and none of it
abortable by the host.So the only moment at which the controller has a choice is before the token. Admission is therefore a question about the future — "will this fit in the time that remains?" — asked before anything is committed.
And the boundary condition within the boundary condition: a transaction that exactly fills the remaining budget fits. <=, not <. Getting that wrong wastes the last slot of every frame — a permanent few-percent bandwidth loss that never shows up as an error (mutation N5).
3. Periodic Traffic Is Reserved, Not Prioritised
Isochronous and interrupt endpoints get a bandwidth reservation, and the reservation is made at configuration time — when the host works out whether the bandwidth exists at all and refuses the configuration if it does not.
By the time this scheduler runs, that question is already settled. The frame budget is held for periodic traffic whether it is used or not.
4. And Within the Frame, Periodic Goes First
A pending periodic request outranks an asynchronous one absolutely. Periodic traffic has a deadline this frame; bulk traffic does not have a deadline at all.
An async transaction admitted ahead of a periodic one can push it past its slot, and the reservation it was promised at configuration time is gone — for that frame, permanently, with no retry.
One frame, and the three ways a request is refused
5. What We Are Building
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
usb_frame_scheduler #(FRAME_UNITS = 16, PERIODIC_CAP = 12, TW = 5)
inputs outputs
------ -------
frame_start (SOF) grant
req_valid reason NONE / GRANT / NO_TIME /
req_is_periodic OVER_CAP / PREEMPTED
req_len [2:0] time_used / time_left
periodic_pending periodic_used / periodic_left
n_frames / n_granted / n_no_time / n_over_cap / n_preemptedgrant is derived from reason, not computed alongside it. The decision is made once, and grant is a view of it. Computing the two independently lets them disagree — and a scheduler that grants a transaction while reporting a refusal is worse than one that simply refuses, because nothing downstream will ever notice.
6. Verilog-2005 Implementation
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
// usb_frame_scheduler -- deciding what runs this frame, and the rule that
// makes a USB scheduler different from every other scheduler.
//
// THE FRAME IS A HARD BOUNDARY
//
// The bus is divided into frames -- 1 ms on full speed, 125 us microframes on
// high speed -- and each one begins with a Start-of-Frame packet that every
// device on the bus can see. Devices time their isochronous and interrupt
// endpoints against it.
//
// So the boundary is not a scheduling convenience. It is a thing devices
// observe, and a transaction that is still on the wire when the next SOF is
// due does not merely finish late: it collides with the SOF, and every
// device on the bus loses its timing reference for that frame.
//
// THE RULE THAT FOLLOWS
//
// YOU CANNOT START A TRANSACTION YOU CANNOT FINISH.
//
// Not "prefer not to". There is no mechanism to stop a transaction once the
// token has gone out -- the device will reply, the data will flow, and the
// handshake will come back, all at the bus's pace and none of it abortable.
// The only moment at which the controller has a choice is BEFORE the token.
//
// So admission is a question about the FUTURE -- "will this fit in the time
// that remains?" -- asked before anything is committed. A scheduler that
// checks "is there time left?" instead of "is there enough time left?" is
// right almost always and catastrophically wrong at the end of a frame.
//
// PERIODIC TRAFFIC IS RESERVED, NOT PRIORITISED
//
// Isochronous and interrupt endpoints are admitted at CONFIGURATION time,
// when the host works out whether the bandwidth exists. By the time the
// scheduler runs, the answer is already yes -- the reservation was made when
// the endpoint was configured, and the frame budget is held for it whether it
// is used or not.
//
// That is why the cap exists. Periodic traffic may use at most
// PERIODIC_CAP of the frame; the rest is for bulk and control, which have no
// reservation and no guarantee and take what is left. The cap protects the
// ASYNCHRONOUS traffic: without it, periodic endpoints could fill every frame
// and bulk transfers would never make progress at all.
//
// Real values are 90% of a full-speed frame and 80% of a high-speed
// microframe. The numbers here are scaled down so the entire state space can
// be enumerated -- the arithmetic is identical.
//
// AND PERIODIC GOES FIRST
//
// Within a frame, a pending periodic request outranks an asynchronous one
// absolutely. Periodic traffic has a deadline this frame; bulk does not have
// a deadline at all. An async transaction admitted ahead of a periodic one
// can push it past its slot, and the reservation it was promised is gone.
module usb_frame_scheduler #(
parameter FRAME_UNITS = 16, // total time in a frame
parameter PERIODIC_CAP = 12, // reserved for periodic (75% here)
parameter TW = 5 // width: must hold 0 .. FRAME_UNITS
) (
input wire clk,
input wire rst_n,
input wire frame_start, // SOF: the budget resets
input wire req_valid,
input wire req_is_periodic,
input wire [2:0] req_len, // how long this transaction takes
input wire periodic_pending, // a periodic request is waiting
output wire grant,
output wire [2:0] reason,
output wire [TW-1:0] time_used,
output wire [TW-1:0] periodic_used,
output wire [TW-1:0] time_left,
output wire [TW-1:0] periodic_left,
output reg [31:0] n_frames,
output reg [31:0] n_granted,
output reg [31:0] n_no_time,
output reg [31:0] n_over_cap,
output reg [31:0] n_preempted
);
localparam [2:0] R_NONE = 3'd0, // nothing was requested
R_GRANT = 3'd1,
R_NO_TIME = 3'd2, // will not fit before the next SOF
R_OVER_CAP = 3'd3, // would exceed the periodic reserve
R_PREEMPTED = 3'd4; // async waiting for a pending periodic
reg [TW-1:0] used_r;
reg [TW-1:0] pused_r;
assign time_used = used_r;
assign periodic_used = pused_r;
assign time_left = FRAME_UNITS[TW-1:0] - used_r;
assign periodic_left = PERIODIC_CAP[TW-1:0] - pused_r;
// The sum is computed one bit wider than either operand. A transaction at
// the end of a frame is exactly the case where the addition overflows, and
// an overflowed comparison says "it fits" about a transaction that does
// not -- which is the bug this whole block exists to avoid, arriving
// through the arithmetic instead of through the logic.
wire [TW:0] used_after = {1'b0, used_r} + {{(TW-2){1'b0}}, req_len};
wire [TW:0] pused_after = {1'b0, pused_r} + {{(TW-2){1'b0}}, req_len};
// ---- THE ADMISSION TEST. "Enough time", not "some time". ----
//
// <= and not <: a transaction that exactly fills the remaining budget FITS.
// Refusing it wastes the last slot of every frame.
wire fits_frame = (used_after <= {1'b0, FRAME_UNITS[TW-1:0]});
wire fits_cap = (pused_after <= {1'b0, PERIODIC_CAP[TW-1:0]});
// A periodic transaction must satisfy BOTH its own reserve and the frame.
// The cap is smaller than the frame, so the frame test looks redundant --
// it is not, because the frame also holds asynchronous traffic admitted
// earlier, and the periodic reserve says nothing about that.
// Periodic outranks asynchronous absolutely: an async request waits while
// a periodic one is pending, because the periodic one has a deadline this
// frame and the async one has no deadline at all.
wire async_blocked = periodic_pending && !req_is_periodic;
// WHY, when it was refused. Three different refusals that all look like
// "not now" from the requester's side, and need three different responses
// from whoever is tuning the system.
//
// The decision is made ONCE, here, and `grant` is a view of it. Computing
// the two independently lets them disagree -- and a scheduler that grants
// while reporting a refusal is worse than one that simply refuses.
assign reason = !req_valid ? R_NONE
: async_blocked ? R_PREEMPTED
: req_is_periodic
? (!fits_cap ? R_OVER_CAP
: !fits_frame ? R_NO_TIME
: R_GRANT)
: (!fits_frame ? R_NO_TIME
: R_GRANT);
assign grant = (reason == R_GRANT);
always @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
used_r <= {TW{1'b0}};
pused_r <= {TW{1'b0}};
n_frames <= 32'd0;
n_granted <= 32'd0;
n_no_time <= 32'd0;
n_over_cap <= 32'd0;
n_preempted <= 32'd0;
end else if (frame_start) begin
// A new frame: both budgets reset. Nothing carries over -- an
// unspent reservation is not credit, it is gone.
used_r <= {TW{1'b0}};
pused_r <= {TW{1'b0}};
n_frames <= n_frames + 32'd1;
end else begin
if (grant) begin
used_r <= used_after[TW-1:0];
// Only a periodic grant consumes the periodic reserve. Charging
// async traffic to it would make the cap bind on traffic it was
// never meant to limit.
if (req_is_periodic) pused_r <= pused_after[TW-1:0];
n_granted <= n_granted + 32'd1;
end
if (reason == R_NO_TIME) n_no_time <= n_no_time + 32'd1;
if (reason == R_OVER_CAP) n_over_cap <= n_over_cap + 32'd1;
if (reason == R_PREEMPTED) n_preempted <= n_preempted + 32'd1;
end
end
endmodule7. SystemVerilog Implementation
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
// usb_frame_scheduler -- deciding what runs this frame, and the rule that
// makes a USB scheduler different from every other scheduler.
//
// THE FRAME IS A HARD BOUNDARY
//
// The bus is divided into frames -- 1 ms on full speed, 125 us microframes on
// high speed -- and each one begins with a Start-of-Frame packet that every
// device on the bus can see. Devices time their isochronous and interrupt
// endpoints against it.
//
// So the boundary is not a scheduling convenience. It is a thing devices
// observe, and a transaction that is still on the wire when the next SOF is
// due does not merely finish late: it collides with the SOF, and every
// device on the bus loses its timing reference for that frame.
//
// THE RULE THAT FOLLOWS
//
// YOU CANNOT START A TRANSACTION YOU CANNOT FINISH.
//
// Not "prefer not to". There is no mechanism to stop a transaction once the
// token has gone out -- the device will reply, the data will flow, and the
// handshake will come back, all at the bus's pace and none of it abortable.
// The only moment at which the controller has a choice is BEFORE the token.
//
// So admission is a question about the FUTURE -- "will this fit in the time
// that remains?" -- asked before anything is committed. A scheduler that
// checks "is there time left?" instead of "is there enough time left?" is
// right almost always and catastrophically wrong at the end of a frame.
//
// PERIODIC TRAFFIC IS RESERVED, NOT PRIORITISED
//
// Isochronous and interrupt endpoints are admitted at CONFIGURATION time,
// when the host works out whether the bandwidth exists. By the time the
// scheduler runs, the answer is already yes -- the reservation was made when
// the endpoint was configured, and the frame budget is held for it whether it
// is used or not.
//
// That is why the cap exists. Periodic traffic may use at most
// PERIODIC_CAP of the frame; the rest is for bulk and control, which have no
// reservation and no guarantee and take what is left. The cap protects the
// ASYNCHRONOUS traffic: without it, periodic endpoints could fill every frame
// and bulk transfers would never make progress at all.
//
// Real values are 90% of a full-speed frame and 80% of a high-speed
// microframe. The numbers here are scaled down so the entire state space can
// be enumerated -- the arithmetic is identical.
//
// AND PERIODIC GOES FIRST
//
// Within a frame, a pending periodic request outranks an asynchronous one
// absolutely. Periodic traffic has a deadline this frame; bulk does not have
// a deadline at all. An async transaction admitted ahead of a periodic one
// can push it past its slot, and the reservation it was promised is gone.
package usb_sched_pkg;
// WHY a request was refused. Three different refusals that all look like
// "not now" from the requester's side and need three different responses
// from whoever is tuning the system: NO_TIME means the frame is full,
// OVER_CAP means the periodic RESERVE is full while the frame is not, and
// PREEMPTED means nothing is full at all and something else goes first.
typedef enum logic [2:0] {
R_NONE = 3'd0, // nothing was requested
R_GRANT = 3'd1,
R_NO_TIME = 3'd2, // will not fit before the next SOF
R_OVER_CAP = 3'd3, // would exceed the periodic reserve
R_PREEMPTED = 3'd4 // async waiting for a pending periodic
} sched_reason_e;
endpackage
module usb_frame_scheduler
import usb_sched_pkg::*;
#(
parameter int FRAME_UNITS = 16, // total time in a frame
parameter int PERIODIC_CAP = 12, // reserved for periodic (75% here)
parameter int TW = 5 // width: must hold 0 .. FRAME_UNITS
) (
input logic clk,
input logic rst_n,
input logic frame_start, // SOF: the budget resets
input logic req_valid,
input logic req_is_periodic,
input logic [2:0] req_len, // how long this transaction takes
input logic periodic_pending, // a periodic request is waiting
output logic grant,
output sched_reason_e reason,
output logic [TW-1:0] time_used,
output logic [TW-1:0] periodic_used,
output logic [TW-1:0] time_left,
output logic [TW-1:0] periodic_left,
output logic [31:0] n_frames,
output logic [31:0] n_granted,
output logic [31:0] n_no_time,
output logic [31:0] n_over_cap,
output logic [31:0] n_preempted
);
logic [TW-1:0] used_r;
logic [TW-1:0] pused_r;
assign time_used = used_r;
assign periodic_used = pused_r;
assign time_left = TW'(FRAME_UNITS) - used_r;
assign periodic_left = TW'(PERIODIC_CAP) - pused_r;
// The sum is computed one bit wider than either operand. A transaction at
// the end of a frame is exactly the case where the addition overflows, and
// an overflowed comparison says "it fits" about a transaction that does
// not -- which is the bug this whole block exists to avoid, arriving
// through the arithmetic instead of through the logic.
logic [TW:0] used_after, pused_after;
assign used_after = {1'b0, used_r} + (TW+1)'(req_len);
assign pused_after = {1'b0, pused_r} + (TW+1)'(req_len);
// ---- THE ADMISSION TEST. "Enough time", not "some time". ----
//
// <= and not <: a transaction that exactly fills the remaining budget FITS.
// Refusing it wastes the last slot of every frame.
logic fits_frame, fits_cap;
assign fits_frame = (used_after <= (TW+1)'(FRAME_UNITS));
assign fits_cap = (pused_after <= (TW+1)'(PERIODIC_CAP));
// A periodic transaction must satisfy BOTH: its own reserve and the frame.
// The cap is smaller than the frame, so the frame test looks redundant --
// it is not, because the frame also holds asynchronous traffic admitted
// earlier, and the periodic reserve says nothing about that.
// Periodic outranks asynchronous absolutely: an async request waits while
// a periodic one is pending, because the periodic one has a deadline this
// frame and the async one has no deadline at all.
logic async_blocked;
assign async_blocked = periodic_pending && !req_is_periodic;
// WHY, when it was refused. Three different refusals that all look like
// "not now" from the requester's side, and need three different responses
// from whoever is tuning the system.
// Written as an if-chain rather than nested ternaries: an enum-valued
// ternary needs an explicit cast in Icarus, and the cast would obscure
// which refusal is which.
//
// The decision is made ONCE, here, and `grant` is a view of it. Computing
// the two independently lets them disagree -- and a scheduler that grants
// while reporting a refusal is worse than one that simply refuses.
always_comb begin
if (!req_valid) reason = R_NONE;
else if (async_blocked) reason = R_PREEMPTED;
else if (req_is_periodic) begin
if (!fits_cap) reason = R_OVER_CAP;
else if (!fits_frame) reason = R_NO_TIME;
else reason = R_GRANT;
end else begin
if (!fits_frame) reason = R_NO_TIME;
else reason = R_GRANT;
end
end
assign grant = (reason == R_GRANT);
always_ff @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
used_r <= '0;
pused_r <= '0;
n_frames <= '0;
n_granted <= '0;
n_no_time <= '0;
n_over_cap <= '0;
n_preempted <= '0;
end else if (frame_start) begin
// A new frame: both budgets reset. Nothing carries over -- an
// unspent reservation is not credit, it is gone.
used_r <= '0;
pused_r <= '0;
n_frames <= n_frames + 1;
end else begin
if (grant) begin
used_r <= used_after[TW-1:0];
// Only a periodic grant consumes the periodic reserve. Charging
// async traffic to it would make the cap bind on traffic it was
// never meant to limit.
if (req_is_periodic) pused_r <= pused_after[TW-1:0];
n_granted <= n_granted + 1;
end
if (reason == R_NO_TIME) n_no_time <= n_no_time + 1;
if (reason == R_OVER_CAP) n_over_cap <= n_over_cap + 1;
if (reason == R_PREEMPTED) n_preempted <= n_preempted + 1;
end
end
endmodule8. VHDL-2008 Implementation
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
-- usb_frame_scheduler -- deciding what runs this frame, and the rule that
-- makes a USB scheduler different from every other scheduler.
--
-- THE FRAME IS A HARD BOUNDARY
--
-- The bus is divided into frames -- 1 ms on full speed, 125 us microframes on
-- high speed -- and each one begins with a Start-of-Frame packet that every
-- device on the bus can see. Devices time their isochronous and interrupt
-- endpoints against it.
--
-- So the boundary is not a scheduling convenience. It is a thing devices
-- observe, and a transaction still on the wire when the next SOF is due does
-- not merely finish late: it collides with the SOF, and every device on the
-- bus loses its timing reference for that frame.
--
-- THE RULE THAT FOLLOWS
--
-- YOU CANNOT START A TRANSACTION YOU CANNOT FINISH.
--
-- There is no mechanism to stop a transaction once the token has gone out --
-- the device will reply, the data will flow, and the handshake will come
-- back, all at the bus's pace and none of it abortable. The only moment at
-- which the controller has a choice is BEFORE the token.
--
-- So admission is a question about the FUTURE -- "will this fit in the time
-- that remains?" -- asked before anything is committed. A scheduler that
-- checks "is there time left?" instead of "is there ENOUGH time left?" is
-- right almost always and catastrophically wrong at the end of a frame.
--
-- PERIODIC TRAFFIC IS RESERVED, NOT PRIORITISED
--
-- Isochronous and interrupt endpoints are admitted at CONFIGURATION time,
-- when the host works out whether the bandwidth exists. By the time this
-- scheduler runs the answer is already yes, and the frame budget is held for
-- them whether they use it or not.
--
-- That is why the cap exists. Periodic traffic may use at most PERIODIC_CAP
-- of the frame; the rest is for bulk and control, which have no reservation
-- and take what is left. The cap protects the ASYNCHRONOUS traffic: without
-- it, periodic endpoints could fill every frame and bulk transfers would
-- never make progress at all.
--
-- Real values are 90% of a full-speed frame and 80% of a high-speed
-- microframe. The numbers here are scaled down so the entire state space can
-- be enumerated -- the arithmetic is identical.
--
-- AND PERIODIC GOES FIRST
--
-- Within a frame, a pending periodic request outranks an asynchronous one
-- absolutely. Periodic traffic has a deadline this frame; bulk does not have
-- a deadline at all.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
package usb_sched_pkg is
-- WHY a request was refused. Three different refusals that all look like
-- "not now" from the requester's side and need three different responses
-- from whoever is tuning the system: R_NO_TIME means the frame is full,
-- R_OVER_CAP means the periodic RESERVE is full while the frame is not,
-- and R_PREEMPTED means nothing is full at all.
type sched_reason_t is (
R_NONE, -- nothing was requested
R_GRANT,
R_NO_TIME, -- will not fit before the next SOF
R_OVER_CAP, -- would exceed the periodic reserve
R_PREEMPTED -- async waiting for a pending periodic
);
function reason_code(r : sched_reason_t) return std_logic_vector;
end package;
package body usb_sched_pkg is
function reason_code(r : sched_reason_t) return std_logic_vector is
begin
return std_logic_vector(to_unsigned(sched_reason_t'pos(r), 3));
end function;
end package body;
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use work.usb_sched_pkg.all;
entity usb_frame_scheduler is
generic (
FRAME_UNITS : natural := 16; -- total time in a frame
PERIODIC_CAP : natural := 12; -- reserved for periodic (75% here)
TW : natural := 5 -- width: must hold 0 .. FRAME_UNITS
);
port (
clk : in std_logic;
rst_n : in std_logic;
frame_start : in std_logic; -- SOF: the budget resets
req_valid : in std_logic;
req_is_periodic : in std_logic;
req_len : in std_logic_vector(2 downto 0);
periodic_pending : in std_logic; -- a periodic request is waiting
grant : out std_logic;
reason : out std_logic_vector(2 downto 0);
time_used : out std_logic_vector(TW-1 downto 0);
periodic_used : out std_logic_vector(TW-1 downto 0);
time_left : out std_logic_vector(TW-1 downto 0);
periodic_left : out std_logic_vector(TW-1 downto 0);
n_frames : out std_logic_vector(31 downto 0);
n_granted : out std_logic_vector(31 downto 0);
n_no_time : out std_logic_vector(31 downto 0);
n_over_cap : out std_logic_vector(31 downto 0);
n_preempted : out std_logic_vector(31 downto 0)
);
end entity;
architecture rtl of usb_frame_scheduler is
-- The accumulators are UNSIGNED VECTORS rather than range-constrained
-- integers, and deliberately so. A constrained integer aborts the
-- simulation the instant a value leaves its range, which sounds like a
-- safety net and is the wrong behaviour here: it turns "this design
-- admitted a transaction that does not fit" into a crash rather than into
-- an observable wrong answer, and a crash is not something a testbench can
-- compare against a model. Vectors truncate exactly as the Verilog and
-- SystemVerilog builds do, so all three are comparable.
signal used_r : unsigned(TW-1 downto 0) := (others => '0');
signal pused_r : unsigned(TW-1 downto 0) := (others => '0');
-- The sums are computed ONE BIT WIDER than either operand. The end of a
-- frame is exactly where a fixed-width addition overflows, and an
-- overflowed comparison says "it fits" about a transaction that does not --
-- which is the bug this whole block exists to avoid, arriving through the
-- arithmetic instead of through the logic.
signal len_i : unsigned(TW downto 0);
signal used_after : unsigned(TW downto 0);
signal pused_after : unsigned(TW downto 0);
signal fits_frame, fits_cap, async_blocked, grant_s : std_logic;
signal reason_s : sched_reason_t;
signal fr_c, gr_c, nt_c, oc_c, pe_c : unsigned(31 downto 0)
:= (others => '0');
begin
len_i <= resize(unsigned(req_len), TW + 1);
time_used <= std_logic_vector(used_r);
periodic_used <= std_logic_vector(pused_r);
time_left <= std_logic_vector(to_unsigned(FRAME_UNITS, TW) - used_r);
periodic_left <= std_logic_vector(to_unsigned(PERIODIC_CAP, TW) - pused_r);
used_after <= ('0' & used_r) + len_i;
pused_after <= ('0' & pused_r) + len_i;
-- ---- THE ADMISSION TEST. "Enough time", not "some time". ----
--
-- <= and not <: a transaction that exactly fills the remaining budget FITS.
-- Refusing it wastes the last slot of every frame.
fits_frame <= '1' when used_after <= to_unsigned(FRAME_UNITS, TW+1)
else '0';
fits_cap <= '1' when pused_after <= to_unsigned(PERIODIC_CAP, TW+1)
else '0';
-- Periodic outranks asynchronous absolutely: an async request waits while a
-- periodic one is pending, because the periodic one has a deadline this
-- frame and the async one has no deadline at all.
async_blocked <= periodic_pending and (not req_is_periodic);
-- A periodic transaction must satisfy BOTH its own reserve and the frame.
-- The cap is smaller than the frame, so the frame test looks redundant --
-- it is not, because the frame also holds asynchronous traffic admitted
-- earlier, and the periodic reserve says nothing about that.
decide : process (req_valid, async_blocked, req_is_periodic,
fits_cap, fits_frame)
begin
if req_valid = '0' then
reason_s <= R_NONE;
elsif async_blocked = '1' then
reason_s <= R_PREEMPTED;
elsif req_is_periodic = '1' then
if fits_cap = '0' then
reason_s <= R_OVER_CAP;
elsif fits_frame = '0' then
reason_s <= R_NO_TIME;
else
reason_s <= R_GRANT;
end if;
else
if fits_frame = '0' then
reason_s <= R_NO_TIME;
else
reason_s <= R_GRANT;
end if;
end if;
end process;
grant_s <= '1' when reason_s = R_GRANT else '0';
grant <= grant_s;
reason <= reason_code(reason_s);
regs : process (clk, rst_n)
begin
if rst_n = '0' then
used_r <= (others => '0');
pused_r <= (others => '0');
fr_c <= (others => '0');
gr_c <= (others => '0');
nt_c <= (others => '0');
oc_c <= (others => '0');
pe_c <= (others => '0');
elsif rising_edge(clk) then
if frame_start = '1' then
-- A new frame: both budgets reset. Nothing carries over -- an
-- unspent reservation is not credit, it is gone.
used_r <= (others => '0');
pused_r <= (others => '0');
fr_c <= fr_c + 1;
else
if grant_s = '1' then
used_r <= used_after(TW-1 downto 0);
-- Only a periodic grant consumes the periodic reserve. Charging
-- async traffic to it would make the cap bind on traffic it was
-- never meant to limit.
if req_is_periodic = '1' then
pused_r <= pused_after(TW-1 downto 0);
end if;
gr_c <= gr_c + 1;
end if;
if reason_s = R_NO_TIME then
nt_c <= nt_c + 1;
end if;
if reason_s = R_OVER_CAP then
oc_c <= oc_c + 1;
end if;
if reason_s = R_PREEMPTED then
pe_c <= pe_c + 1;
end if;
end if;
end if;
end process;
n_frames <= std_logic_vector(fr_c);
n_granted <= std_logic_vector(gr_c);
n_no_time <= std_logic_vector(nt_c);
n_over_cap <= std_logic_vector(oc_c);
n_preempted <= std_logic_vector(pe_c);
end architecture;9. Seeing the End of a Frame
A frame filling up, and the transaction that does not fit
usb_frame_scheduler — admission at the frame boundary
10 cyclesCycle 3 and cycle 7 are both refusals and they mean entirely different things. At cycle 3 the frame is nearly full. At cycle 7 the frame has room — time_left is zero only because the async traffic filled it; had it not, a periodic request could still be refused by a full reserve while time_left read four. That is why reason exists.
10. The Testbenches
The exhaustive domain is every reachable budget state against every request:
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
periodic time is a SUBSET of frame time, so the reachable
pairs are those with pused <= min(used, PERIODIC_CAP)
143 reachable (time_used, periodic_used) pairs
x 2 (req_valid) x 2 (periodic/async)
x 8 (req_len) x 2 (periodic_pending)
= 9152 pointsAnd every budget state is reached by granting actual transactions — goto_budget issues periodic grants to build the periodic total and then async grants for the remainder — rather than by forcing registers. That matters here more than usual: the reachable set is defined by what the design will actually do, so constructing it through the design is what proves the set is right.
10.1 Verilog testbench
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
`timescale 1ns/1ps
module tb_fs_v;
localparam FRAME_UNITS = 16, PERIODIC_CAP = 12, TW = 5;
reg clk=0, rst_n=0;
reg frame_start=0, req_valid=0, req_is_periodic=0, periodic_pending=0;
reg [2:0] req_len=0;
wire grant;
wire [2:0] reason;
wire [TW-1:0] time_used, periodic_used, time_left, periodic_left;
wire [31:0] n_frames, n_granted, n_no_time, n_over_cap, n_preempted;
always #5 clk=~clk;
usb_frame_scheduler #(.FRAME_UNITS(FRAME_UNITS),
.PERIODIC_CAP(PERIODIC_CAP), .TW(TW)) dut (
.clk(clk), .rst_n(rst_n), .frame_start(frame_start),
.req_valid(req_valid), .req_is_periodic(req_is_periodic),
.req_len(req_len), .periodic_pending(periodic_pending),
.grant(grant), .reason(reason), .time_used(time_used),
.periodic_used(periodic_used), .time_left(time_left),
.periodic_left(periodic_left), .n_frames(n_frames),
.n_granted(n_granted), .n_no_time(n_no_time), .n_over_cap(n_over_cap),
.n_preempted(n_preempted));
localparam [2:0] R_NONE=0, R_GRANT=1, R_NO_TIME=2, R_OVER_CAP=3,
R_PREEMPTED=4;
// ---- SHADOW MODEL of the two budget accumulators ----
integer s_used, s_pused;
integer m_fr, m_gr, m_nt, m_oc, m_pe;
integer errors=0, i, tu, pu, a, b, c, d, k;
integer n_exh=0;
integer n_reason [0:4];
integer n_pairs=0, n_exact=0, n_capbind=0;
task check(input cond, input [639:0] msg);
begin if (!cond) begin errors=errors+1;
if (errors <= 25)
$display(" FAIL: %0s (sof=%b vld=%b per=%b len=%0d pend=%b | grant=%b reason=%0d used=%0d pused=%0d || model used=%0d pused=%0d, t=%0t)",
msg, frame_start, req_valid, req_is_periodic, req_len,
periodic_pending, grant, reason, time_used, periodic_used,
s_used, s_pused, $time);
end end
endtask
task check_comb;
reg e_fits_frame, e_fits_cap, e_blocked, e_grant;
reg [2:0] e_reason;
integer after, pafter;
begin
// The model adds in the integer domain and compares with plain
// relational operators, where the design widens by one bit and
// compares vectors -- a different route to the same answer, and one
// that cannot share an overflow bug with it.
after = s_used + req_len;
pafter = s_pused + req_len;
e_fits_frame = (after <= FRAME_UNITS);
e_fits_cap = (pafter <= PERIODIC_CAP);
e_blocked = periodic_pending && !req_is_periodic;
e_grant = req_valid && !e_blocked
&& (req_is_periodic ? (e_fits_cap && e_fits_frame)
: e_fits_frame);
if (!req_valid) e_reason = R_NONE;
else if (e_blocked) e_reason = R_PREEMPTED;
else if (req_is_periodic) e_reason = !e_fits_cap ? R_OVER_CAP
: !e_fits_frame ? R_NO_TIME
: R_GRANT;
else e_reason = !e_fits_frame ? R_NO_TIME
: R_GRANT;
check(grant === e_grant, "grant matches the model");
check(reason === e_reason, "reason matches the model");
check(time_used === s_used[TW-1:0], "time_used matches the model");
check(periodic_used === s_pused[TW-1:0], "periodic_used matches the model");
check(time_left === (FRAME_UNITS - s_used), "time_left matches");
check(periodic_left === (PERIODIC_CAP - s_pused), "periodic_left matches");
// ---- SAFETY PROPERTIES, independent of the model ----
// 1. THE property. Never admit a transaction that will not finish
// before the next SOF. There is no way to stop it once started.
if (grant)
check((s_used + req_len) <= FRAME_UNITS,
"a transaction was admitted that cannot finish inside the frame");
// 2. The periodic reserve is never exceeded.
if (grant && req_is_periodic)
check((s_pused + req_len) <= PERIODIC_CAP,
"a periodic grant exceeded the reserved budget");
// 3. A transaction that exactly fills the remaining budget FITS.
// Refusing it wastes the last slot of every frame.
if (req_valid && !periodic_pending && !req_is_periodic
&& ((s_used + req_len) == FRAME_UNITS))
check(grant,
"an async transaction that exactly fills the frame was refused");
// 4. Periodic outranks async absolutely.
if (req_valid && periodic_pending && !req_is_periodic)
check(!grant,
"an async transaction was admitted ahead of a pending periodic one");
// 5. The accumulators never exceed their budgets.
check(time_used <= FRAME_UNITS[TW-1:0], "time_used exceeded the frame");
check(periodic_used <= PERIODIC_CAP[TW-1:0], "periodic_used exceeded the cap");
// 6. Periodic time is a subset of frame time.
check(periodic_used <= time_used,
"more periodic time was used than total frame time");
// 7. grant and the reason agree.
check((reason === R_GRANT) === grant, "reason disagrees with grant");
// 8. No request, no answer.
if (!req_valid) check(!grant && (reason === R_NONE),
"a grant or a refusal with no request");
if (e_reason <= 4) n_reason[e_reason] = n_reason[e_reason] + 1;
if (e_grant && ((s_used + req_len) == FRAME_UNITS)) n_exact = n_exact + 1;
if (req_valid && req_is_periodic && !e_fits_cap) n_capbind = n_capbind + 1;
end
endtask
task model_step;
reg e_fits_frame, e_fits_cap, e_blocked, e_grant;
reg [2:0] e_reason;
integer after, pafter;
begin
after = s_used + req_len;
pafter = s_pused + req_len;
e_fits_frame = (after <= FRAME_UNITS);
e_fits_cap = (pafter <= PERIODIC_CAP);
e_blocked = periodic_pending && !req_is_periodic;
e_grant = req_valid && !e_blocked
&& (req_is_periodic ? (e_fits_cap && e_fits_frame)
: e_fits_frame);
if (!req_valid) e_reason = R_NONE;
else if (e_blocked) e_reason = R_PREEMPTED;
else if (req_is_periodic) e_reason = !e_fits_cap ? R_OVER_CAP
: !e_fits_frame ? R_NO_TIME
: R_GRANT;
else e_reason = !e_fits_frame ? R_NO_TIME
: R_GRANT;
if (frame_start) begin
s_used = 0; s_pused = 0; m_fr = m_fr + 1;
end else begin
if (e_grant) begin
s_used = after;
if (req_is_periodic) s_pused = pafter;
m_gr = m_gr + 1;
end
if (e_reason == R_NO_TIME) m_nt = m_nt + 1;
if (e_reason == R_OVER_CAP) m_oc = m_oc + 1;
if (e_reason == R_PREEMPTED) m_pe = m_pe + 1;
end
end
endtask
task step;
begin
#1;
check_comb;
model_step;
@(posedge clk); #1;
check(time_used === s_used[TW-1:0], "time_used tracked the model");
check(periodic_used === s_pused[TW-1:0], "periodic_used tracked the model");
check(n_frames === m_fr[31:0], "n_frames matches the model");
check(n_granted === m_gr[31:0], "n_granted matches the model");
check(n_no_time === m_nt[31:0], "n_no_time matches the model");
check(n_over_cap === m_oc[31:0], "n_over_cap matches the model");
check(n_preempted === m_pe[31:0], "n_preempted matches the model");
end
endtask
task idle_in;
begin frame_start=0; req_valid=0; periodic_pending=0; end
endtask
task hard_reset;
begin
rst_n=0; idle_in; req_is_periodic=0; req_len=0;
@(posedge clk); #1; @(posedge clk); #1; rst_n=1; #1;
s_used=0; s_pused=0;
m_fr=0; m_gr=0; m_nt=0; m_oc=0; m_pe=0;
end
endtask
// Drive the budgets to a chosen (time_used, periodic_used) using only
// granted transactions -- periodic first to build the periodic total, then
// async for the remainder. No register forcing.
task goto_budget(input integer want_used, input integer want_pused);
integer left, chunk;
begin
hard_reset;
frame_start=1; step; idle_in;
left = want_pused;
while (left > 0) begin
chunk = (left > 7) ? 7 : left;
req_valid=1; req_is_periodic=1; req_len=chunk[2:0];
periodic_pending=0; step; idle_in;
left = left - chunk;
end
left = want_used - want_pused;
while (left > 0) begin
chunk = (left > 7) ? 7 : left;
req_valid=1; req_is_periodic=0; req_len=chunk[2:0];
periodic_pending=0; step; idle_in;
left = left - chunk;
end
#1;
check(time_used === want_used[TW-1:0],
"goto_budget reached the frame total");
check(periodic_used === want_pused[TW-1:0],
"goto_budget reached the periodic total");
end
endtask
initial begin
for (i=0;i<5;i=i+1) n_reason[i]=0;
hard_reset;
check(time_used === 5'd0, "reset leaves the frame budget empty");
check(time_left === FRAME_UNITS[TW-1:0], "with the whole frame available");
// ===== A. EXHAUSTIVE admission sweep =====
// Every REACHABLE (time_used, periodic_used) pair -- periodic time is a
// subset of frame time, so pused <= min(used, PERIODIC_CAP) -- against
// every request: valid/not, periodic/async, all 8 lengths, and a pending
// periodic request or not.
//
// 143 reachable budget pairs x 2 x 2 x 8 x 2 = 9152 points
for (tu=0; tu<=FRAME_UNITS; tu=tu+1)
for (pu=0; pu<=((tu < PERIODIC_CAP) ? tu : PERIODIC_CAP); pu=pu+1) begin
n_pairs = n_pairs + 1;
for (a=0;a<2;a=a+1) // req_valid
for (b=0;b<2;b=b+1) // req_is_periodic
for (c=0;c<8;c=c+1) // req_len
for (d=0;d<2;d=d+1) begin // periodic_pending
goto_budget(tu, pu);
req_valid=a[0]; req_is_periodic=b[0]; req_len=c[2:0];
periodic_pending=d[0]; frame_start=0;
step;
n_exh = n_exh + 1;
idle_in;
end
end
$display(" exhaustive admission sweep: %0d points over %0d reachable budget pairs",
n_exh, n_pairs);
// ===== B. directed: the end of a frame =====
hard_reset; frame_start=1; step; idle_in;
check(n_frames === 32'd1, "the SOF started a frame");
// 1. An async transaction with the whole frame free.
req_valid=1; req_is_periodic=0; req_len=3'd5; step; idle_in;
#1;
check(!grant,
"grant is a one-cycle decision and the request has been withdrawn");
check(time_used === 5'd5, "five units used");
check(time_left === 5'd11, "eleven left");
// 2. THE case. 11 units remain and a 7-unit transaction is offered:
// it fits. Then 4 remain and a 7-unit one is offered: it does NOT.
req_valid=1; req_is_periodic=0; req_len=3'd7; #1;
check(grant, "seven units fit in the eleven that remain");
step; idle_in;
check(time_used === 5'd12, "twelve used");
check(time_left === 5'd4, "four left");
req_valid=1; req_is_periodic=0; req_len=3'd7; #1;
check(!grant,
"seven units do NOT fit in four -- and there is no way to stop a transaction once started");
check(reason === R_NO_TIME, "which is exactly why it was refused");
step; idle_in;
check(time_used === 5'd12, "and nothing was consumed");
// 3. A transaction that EXACTLY fills the remaining budget fits.
req_valid=1; req_is_periodic=0; req_len=3'd4; #1;
check(grant,
"four units exactly fill the four that remain -- <= not <");
step; idle_in;
check(time_used === 5'd16, "the frame is exactly full");
check(time_left === 5'd0, "with nothing left");
// 4. And now nothing fits, not even a zero-length request... which does.
req_valid=1; req_is_periodic=0; req_len=3'd1; #1;
check(!grant, "one more unit does not fit");
step; idle_in;
req_valid=1; req_is_periodic=0; req_len=3'd0; #1;
check(grant, "but a zero-length transaction still fits in zero time");
step; idle_in;
// ===== C. directed: the periodic reserve =====
hard_reset; frame_start=1; step; idle_in;
// 5. Periodic traffic up to the cap.
req_valid=1; req_is_periodic=1; req_len=3'd7; step; idle_in;
req_valid=1; req_is_periodic=1; req_len=3'd5; step; idle_in;
check(periodic_used === 5'd12, "twelve units of periodic traffic");
check(periodic_left === 5'd0, "which is the whole reserve");
check(time_used === 5'd12, "and twelve units of the frame");
// 6. THE cap. More periodic traffic is refused even though the FRAME
// has room -- the reserve protects the asynchronous traffic.
req_valid=1; req_is_periodic=1; req_len=3'd2; #1;
check(!grant, "more periodic traffic is refused");
check(reason === R_OVER_CAP,
"because the periodic RESERVE is full, not the frame");
check(time_left === 5'd4, "even though four units of the frame remain");
step; idle_in;
// 7. Those four units are available to ASYNC traffic. That is what the
// cap is for.
req_valid=1; req_is_periodic=0; req_len=3'd4; #1;
check(grant, "and asynchronous traffic CAN use them");
check(reason === R_GRANT, "which is the point of reserving only 12 of 16");
step; idle_in;
check(time_used === 5'd16, "the frame is full");
check(periodic_used === 5'd12, "with the periodic reserve untouched by it");
// ===== D. directed: priority =====
hard_reset; frame_start=1; step; idle_in;
// 8. An async request waits while a periodic one is pending.
req_valid=1; req_is_periodic=0; req_len=3'd2; periodic_pending=1; #1;
check(!grant, "an async request waits for a pending periodic one");
check(reason === R_PREEMPTED, "and is told why");
step; idle_in;
check(time_used === 5'd0, "nothing was consumed");
// 9. The periodic request runs.
req_valid=1; req_is_periodic=1; req_len=3'd2; periodic_pending=1; #1;
check(grant, "the periodic request is not blocked by itself");
step; idle_in;
// 10. And now the async one can go.
req_valid=1; req_is_periodic=0; req_len=3'd2; periodic_pending=0; #1;
check(grant, "with nothing periodic pending, async proceeds");
step; idle_in;
// 11. A new frame wipes both budgets. An unspent reserve is not credit.
frame_start=1; step; idle_in;
check(time_used === 5'd0, "the SOF reset the frame budget");
check(periodic_used === 5'd0, "and the periodic reserve");
check(n_frames === 32'd2, "two frames");
// ===== E. randomised =====
hard_reset;
for (i=0;i<40000;i=i+1) begin
frame_start = ({$random}%10)==0;
req_valid = ({$random}%4)!=0;
req_is_periodic = ({$random}%3)==0;
req_len = {$random}%8;
periodic_pending = ({$random}%5)==0;
step;
end
for (i=0;i<5;i=i+1)
check(n_reason[i] > 500, "every admission outcome was reached");
check(n_exact > 200, "exact-fit admissions happened often");
check(n_capbind > 500, "the periodic reserve bound often");
$display("");
$display(" REACH: exhaustive=%0d over %0d budget pairs | outcomes: none=%0d grant=%0d no-time=%0d over-cap=%0d preempted=%0d",
n_exh, n_pairs, n_reason[0], n_reason[1], n_reason[2],
n_reason[3], n_reason[4]);
$display(" CASES: exact-fit grants=%0d periodic-cap refusals=%0d",
n_exact, n_capbind);
$display(" COUNTERS: frames=%0d granted=%0d no-time=%0d over-cap=%0d preempted=%0d",
n_frames, n_granted, n_no_time, n_over_cap, n_preempted);
$display(" [Verilog] usb_frame_scheduler: %0d errors", errors);
$display(" [Verilog] %0s", errors==0 ? "PASS" : "FAIL");
$display("");
$finish;
end
endmodule10.2 SystemVerilog testbench
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
`timescale 1ns/1ps
module tb_fs_sv;
import usb_sched_pkg::*;
localparam FRAME_UNITS = 16, PERIODIC_CAP = 12, TW = 5;
logic clk=0, rst_n=0;
logic frame_start=0, req_valid=0, req_is_periodic=0, periodic_pending=0;
logic [2:0] req_len=0;
logic grant;
sched_reason_e reason;
logic [TW-1:0] time_used, periodic_used, time_left, periodic_left;
logic [31:0] n_frames, n_granted, n_no_time, n_over_cap, n_preempted;
// 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 = 22303;
always #5 clk=~clk;
usb_frame_scheduler #(.FRAME_UNITS(FRAME_UNITS),
.PERIODIC_CAP(PERIODIC_CAP), .TW(TW)) dut (
.clk, .rst_n, .frame_start, .req_valid, .req_is_periodic, .req_len,
.periodic_pending, .grant, .reason, .time_used, .periodic_used,
.time_left, .periodic_left, .n_frames, .n_granted, .n_no_time,
.n_over_cap, .n_preempted);
// ---- SHADOW MODEL of the two budget accumulators ----
int s_used, s_pused;
int m_fr, m_gr, m_nt, m_oc, m_pe;
int errors=0, i, tu, pu, a, b, c, d, k;
int n_exh=0;
int n_reason [5];
int n_pairs=0, n_exact=0, n_capbind=0;
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.
sched_reason_e rs_v;
if (!cond) begin
errors++;
rs_v = reason;
if (errors <= 25)
$display(" FAIL: %0s (sof=%b vld=%b per=%b len=%0d pend=%b | grant=%b reason=%s used=%0d pused=%0d || model used=%0d pused=%0d, t=%0t)",
msg, frame_start, req_valid, req_is_periodic, req_len,
periodic_pending, grant, rs_v.name(), time_used,
periodic_used, s_used, s_pused, $time);
end
endtask
task automatic check_comb;
bit e_fits_frame, e_fits_cap, e_blocked, e_grant;
sched_reason_e e_reason;
int after, pafter;
begin
// The model adds in the integer domain and compares with plain
// relational operators, where the design widens by one bit and
// compares vectors -- a different route to the same answer, and one
// that cannot share an overflow bug with it.
after = s_used + req_len;
pafter = s_pused + req_len;
e_fits_frame = (after <= FRAME_UNITS);
e_fits_cap = (pafter <= PERIODIC_CAP);
e_blocked = periodic_pending && !req_is_periodic;
e_grant = req_valid && !e_blocked
&& (req_is_periodic ? (e_fits_cap && e_fits_frame)
: e_fits_frame);
// Icarus will not take an enum-valued ternary without a cast, so the
// model states the refusal chain as nested if/else.
if (!req_valid) e_reason = R_NONE;
else if (e_blocked) e_reason = R_PREEMPTED;
else if (req_is_periodic) begin
if (!e_fits_cap) e_reason = R_OVER_CAP;
else if (!e_fits_frame) e_reason = R_NO_TIME;
else e_reason = R_GRANT;
end else begin
if (!e_fits_frame) e_reason = R_NO_TIME;
else e_reason = R_GRANT;
end
check(grant === e_grant, "grant matches the model");
check(reason === e_reason, "reason matches the model");
check(time_used === TW'(s_used), "time_used matches the model");
check(periodic_used === TW'(s_pused), "periodic_used matches the model");
check(time_left === (FRAME_UNITS - s_used), "time_left matches");
check(periodic_left === (PERIODIC_CAP - s_pused), "periodic_left matches");
// ---- SAFETY PROPERTIES, independent of the model ----
// 1. THE property. Never admit a transaction that will not finish
// before the next SOF. There is no way to stop it once started.
if (grant)
check((s_used + req_len) <= FRAME_UNITS,
"a transaction was admitted that cannot finish inside the frame");
// 2. The periodic reserve is never exceeded.
if (grant && req_is_periodic)
check((s_pused + req_len) <= PERIODIC_CAP,
"a periodic grant exceeded the reserved budget");
// 3. A transaction that exactly fills the remaining budget FITS.
// Refusing it wastes the last slot of every frame.
if (req_valid && !periodic_pending && !req_is_periodic
&& ((s_used + req_len) == FRAME_UNITS))
check(grant,
"an async transaction that exactly fills the frame was refused");
// 4. Periodic outranks async absolutely.
if (req_valid && periodic_pending && !req_is_periodic)
check(!grant,
"an async transaction was admitted ahead of a pending periodic one");
// 5. The accumulators never exceed their budgets.
check(time_used <= TW'(FRAME_UNITS), "time_used exceeded the frame");
check(periodic_used <= TW'(PERIODIC_CAP), "periodic_used exceeded the cap");
// 6. Periodic time is a subset of frame time.
check(periodic_used <= time_used,
"more periodic time was used than total frame time");
// 7. grant and the reason agree.
check((reason === R_GRANT) === grant, "reason disagrees with grant");
// 8. No request, no answer.
if (!req_valid) check(!grant && (reason === R_NONE),
"a grant or a refusal with no request");
n_reason[int'(e_reason)] = n_reason[int'(e_reason)] + 1;
if (e_grant && ((s_used + req_len) == FRAME_UNITS)) n_exact = n_exact + 1;
if (req_valid && req_is_periodic && !e_fits_cap) n_capbind = n_capbind + 1;
end
endtask
task automatic model_step;
bit e_fits_frame, e_fits_cap, e_blocked, e_grant;
sched_reason_e e_reason;
int after, pafter;
begin
after = s_used + req_len;
pafter = s_pused + req_len;
e_fits_frame = (after <= FRAME_UNITS);
e_fits_cap = (pafter <= PERIODIC_CAP);
e_blocked = periodic_pending && !req_is_periodic;
e_grant = req_valid && !e_blocked
&& (req_is_periodic ? (e_fits_cap && e_fits_frame)
: e_fits_frame);
// Icarus will not take an enum-valued ternary without a cast, so the
// model states the refusal chain as nested if/else.
if (!req_valid) e_reason = R_NONE;
else if (e_blocked) e_reason = R_PREEMPTED;
else if (req_is_periodic) begin
if (!e_fits_cap) e_reason = R_OVER_CAP;
else if (!e_fits_frame) e_reason = R_NO_TIME;
else e_reason = R_GRANT;
end else begin
if (!e_fits_frame) e_reason = R_NO_TIME;
else e_reason = R_GRANT;
end
if (frame_start) begin
s_used = 0; s_pused = 0; m_fr = m_fr + 1;
end else begin
if (e_grant) begin
s_used = after;
if (req_is_periodic) s_pused = pafter;
m_gr = m_gr + 1;
end
if (e_reason == R_NO_TIME) m_nt = m_nt + 1;
if (e_reason == R_OVER_CAP) m_oc = m_oc + 1;
if (e_reason == R_PREEMPTED) m_pe = m_pe + 1;
end
end
endtask
task automatic step;
begin
#1;
check_comb;
model_step;
@(posedge clk); #1;
check(time_used === TW'(s_used), "time_used tracked the model");
check(periodic_used === TW'(s_pused), "periodic_used tracked the model");
check(n_frames === 32'(m_fr), "n_frames matches the model");
check(n_granted === 32'(m_gr), "n_granted matches the model");
check(n_no_time === 32'(m_nt), "n_no_time matches the model");
check(n_over_cap === 32'(m_oc), "n_over_cap matches the model");
check(n_preempted === 32'(m_pe), "n_preempted matches the model");
end
endtask
task automatic idle_in;
begin frame_start=0; req_valid=0; periodic_pending=0; end
endtask
task automatic hard_reset;
begin
rst_n=0; idle_in; req_is_periodic=0; req_len=0;
@(posedge clk); #1; @(posedge clk); #1; rst_n=1; #1;
s_used=0; s_pused=0;
m_fr=0; m_gr=0; m_nt=0; m_oc=0; m_pe=0;
end
endtask
// Drive the budgets to a chosen (time_used, periodic_used) using only
// granted transactions -- periodic first to build the periodic total, then
// async for the remainder. No register forcing.
task automatic goto_budget(input int want_used, input int want_pused);
int left, chunk;
begin
hard_reset;
frame_start=1; step; idle_in;
left = want_pused;
while (left > 0) begin
chunk = (left > 7) ? 7 : left;
req_valid=1; req_is_periodic=1; req_len=3'(chunk);
periodic_pending=0; step; idle_in;
left = left - chunk;
end
left = want_used - want_pused;
while (left > 0) begin
chunk = (left > 7) ? 7 : left;
req_valid=1; req_is_periodic=0; req_len=3'(chunk);
periodic_pending=0; step; idle_in;
left = left - chunk;
end
#1;
check(time_used === TW'(want_used),
"goto_budget reached the frame total");
check(periodic_used === TW'(want_pused),
"goto_budget reached the periodic total");
end
endtask
initial begin
void'($urandom(urandom_seed));
foreach (n_reason[i]) n_reason[i]=0;
hard_reset;
check(time_used === 5'd0, "reset leaves the frame budget empty");
check(time_left === TW'(FRAME_UNITS), "with the whole frame available");
// ===== A. EXHAUSTIVE admission sweep =====
// Every REACHABLE (time_used, periodic_used) pair -- periodic time is a
// subset of frame time, so pused <= min(used, PERIODIC_CAP) -- against
// every request: valid/not, periodic/async, all 8 lengths, and a pending
// periodic request or not.
//
// 143 reachable budget pairs x 2 x 2 x 8 x 2 = 9152 points
for (tu=0; tu<=FRAME_UNITS; tu=tu+1)
for (pu=0; pu<=((tu < PERIODIC_CAP) ? tu : PERIODIC_CAP); pu=pu+1) begin
n_pairs = n_pairs + 1;
for (a=0;a<2;a=a+1) // req_valid
for (b=0;b<2;b=b+1) // req_is_periodic
for (c=0;c<8;c=c+1) // req_len
for (d=0;d<2;d=d+1) begin // periodic_pending
goto_budget(tu, pu);
req_valid=a[0]; req_is_periodic=b[0]; req_len=c[2:0];
periodic_pending=d[0]; frame_start=0;
step;
n_exh = n_exh + 1;
idle_in;
end
end
$display(" exhaustive admission sweep: %0d points over %0d reachable budget pairs",
n_exh, n_pairs);
// ===== B. directed: the end of a frame =====
hard_reset; frame_start=1; step; idle_in;
check(n_frames === 32'd1, "the SOF started a frame");
// 1. An async transaction with the whole frame free.
req_valid=1; req_is_periodic=0; req_len=3'd5; step; idle_in;
#1;
check(!grant,
"grant is a one-cycle decision and the request has been withdrawn");
check(time_used === 5'd5, "five units used");
check(time_left === 5'd11, "eleven left");
// 2. THE case. 11 units remain and a 7-unit transaction is offered:
// it fits. Then 4 remain and a 7-unit one is offered: it does NOT.
req_valid=1; req_is_periodic=0; req_len=3'd7; #1;
check(grant, "seven units fit in the eleven that remain");
step; idle_in;
check(time_used === 5'd12, "twelve used");
check(time_left === 5'd4, "four left");
req_valid=1; req_is_periodic=0; req_len=3'd7; #1;
check(!grant,
"seven units do NOT fit in four -- and there is no way to stop a transaction once started");
check(reason === R_NO_TIME, "which is exactly why it was refused");
step; idle_in;
check(time_used === 5'd12, "and nothing was consumed");
// 3. A transaction that EXACTLY fills the remaining budget fits.
req_valid=1; req_is_periodic=0; req_len=3'd4; #1;
check(grant,
"four units exactly fill the four that remain -- <= not <");
step; idle_in;
check(time_used === 5'd16, "the frame is exactly full");
check(time_left === 5'd0, "with nothing left");
// 4. And now nothing fits, not even a zero-length request... which does.
req_valid=1; req_is_periodic=0; req_len=3'd1; #1;
check(!grant, "one more unit does not fit");
step; idle_in;
req_valid=1; req_is_periodic=0; req_len=3'd0; #1;
check(grant, "but a zero-length transaction still fits in zero time");
step; idle_in;
// ===== C. directed: the periodic reserve =====
hard_reset; frame_start=1; step; idle_in;
// 5. Periodic traffic up to the cap.
req_valid=1; req_is_periodic=1; req_len=3'd7; step; idle_in;
req_valid=1; req_is_periodic=1; req_len=3'd5; step; idle_in;
check(periodic_used === 5'd12, "twelve units of periodic traffic");
check(periodic_left === 5'd0, "which is the whole reserve");
check(time_used === 5'd12, "and twelve units of the frame");
// 6. THE cap. More periodic traffic is refused even though the FRAME
// has room -- the reserve protects the asynchronous traffic.
req_valid=1; req_is_periodic=1; req_len=3'd2; #1;
check(!grant, "more periodic traffic is refused");
check(reason === R_OVER_CAP,
"because the periodic RESERVE is full, not the frame");
check(time_left === 5'd4, "even though four units of the frame remain");
step; idle_in;
// 7. Those four units are available to ASYNC traffic. That is what the
// cap is for.
req_valid=1; req_is_periodic=0; req_len=3'd4; #1;
check(grant, "and asynchronous traffic CAN use them");
check(reason === R_GRANT, "which is the point of reserving only 12 of 16");
step; idle_in;
check(time_used === 5'd16, "the frame is full");
check(periodic_used === 5'd12, "with the periodic reserve untouched by it");
// ===== D. directed: priority =====
hard_reset; frame_start=1; step; idle_in;
// 8. An async request waits while a periodic one is pending.
req_valid=1; req_is_periodic=0; req_len=3'd2; periodic_pending=1; #1;
check(!grant, "an async request waits for a pending periodic one");
check(reason === R_PREEMPTED, "and is told why");
step; idle_in;
check(time_used === 5'd0, "nothing was consumed");
// 9. The periodic request runs.
req_valid=1; req_is_periodic=1; req_len=3'd2; periodic_pending=1; #1;
check(grant, "the periodic request is not blocked by itself");
step; idle_in;
// 10. And now the async one can go.
req_valid=1; req_is_periodic=0; req_len=3'd2; periodic_pending=0; #1;
check(grant, "with nothing periodic pending, async proceeds");
step; idle_in;
// 11. A new frame wipes both budgets. An unspent reserve is not credit.
frame_start=1; step; idle_in;
check(time_used === 5'd0, "the SOF reset the frame budget");
check(periodic_used === 5'd0, "and the periodic reserve");
check(n_frames === 32'd2, "two frames");
// ===== E. randomised =====
hard_reset;
for (i=0;i<40000;i=i+1) begin
frame_start = ($urandom%10)==0;
req_valid = ($urandom%4)!=0;
req_is_periodic = ($urandom%3)==0;
req_len = 3'($urandom%8);
periodic_pending = ($urandom%5)==0;
step;
end
foreach (n_reason[i])
check(n_reason[i] > 500, "every admission outcome was reached");
check(n_exact > 200, "exact-fit admissions happened often");
check(n_capbind > 500, "the periodic reserve bound often");
$display("");
$display(" REACH: exhaustive=%0d over %0d budget pairs | outcomes: none=%0d grant=%0d no-time=%0d over-cap=%0d preempted=%0d",
n_exh, n_pairs, n_reason[0], n_reason[1], n_reason[2],
n_reason[3], n_reason[4]);
$display(" CASES: exact-fit grants=%0d periodic-cap refusals=%0d",
n_exact, n_capbind);
$display(" COUNTERS: frames=%0d granted=%0d no-time=%0d over-cap=%0d preempted=%0d",
n_frames, n_granted, n_no_time, n_over_cap, n_preempted);
$display(" [SystemVerilog] usb_frame_scheduler: %0d errors", errors);
$display(" [SystemVerilog] %0s", errors==0 ? "PASS" : "FAIL");
$display("");
$finish;
end
endmodule10.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_sched_pkg.all;
entity tb_fs_vhdl is
end entity;
architecture sim of tb_fs_vhdl is
constant FRAME_UNITS : natural := 16;
constant PERIODIC_CAP : natural := 12;
constant TW : natural := 5;
signal clk : std_logic := '0';
signal rst_n : std_logic := '0';
signal frame_start, req_valid, req_is_periodic : std_logic := '0';
signal periodic_pending : std_logic := '0';
signal req_len : std_logic_vector(2 downto 0) := (others => '0');
signal grant : std_logic;
signal reason : std_logic_vector(2 downto 0);
signal time_used, periodic_used, time_left, periodic_left
: std_logic_vector(TW-1 downto 0);
signal n_frames, n_granted, n_no_time, n_over_cap, n_preempted
: std_logic_vector(31 downto 0);
signal running : boolean := true;
type cnt5_t is array (0 to 4) of integer;
begin
clk <= not clk after 5 ns when running else '0';
dut : entity work.usb_frame_scheduler
generic map (FRAME_UNITS => FRAME_UNITS, PERIODIC_CAP => PERIODIC_CAP,
TW => TW)
port map (clk => clk, rst_n => rst_n, frame_start => frame_start,
req_valid => req_valid, req_is_periodic => req_is_periodic,
req_len => req_len, periodic_pending => periodic_pending,
grant => grant, reason => reason, time_used => time_used,
periodic_used => periodic_used, time_left => time_left,
periodic_left => periodic_left, n_frames => n_frames,
n_granted => n_granted, n_no_time => n_no_time,
n_over_cap => n_over_cap, n_preempted => n_preempted);
stim : process
variable seed1 : positive := 3733;
variable seed2 : positive := 8291;
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 two budget accumulators.
variable s_used, s_pused : integer := 0;
variable m_fr, m_gr, m_nt, m_oc, m_pe : integer := 0;
variable n_exh, n_pairs, n_exact, n_capbind : integer := 0;
variable n_reason : cnt5_t := (others => 0);
procedure check(cond : boolean; msg : string) is
begin
if not cond then
errors := errors + 1;
if errors <= 25 then
report " FAIL: " & msg
& " (sof=" & std_logic'image(frame_start)(2)
& " vld=" & std_logic'image(req_valid)(2)
& " per=" & std_logic'image(req_is_periodic)(2)
& " len=" & integer'image(to_integer(unsigned(req_len)))
& " pend=" & std_logic'image(periodic_pending)(2)
& " | grant=" & std_logic'image(grant)(2)
& " reason=" & integer'image(to_integer(unsigned(reason)))
& " used=" & integer'image(to_integer(unsigned(time_used)))
& " pused=" & integer'image(to_integer(unsigned(periodic_used)))
& " || model used=" & integer'image(s_used)
& " pused=" & integer'image(s_pused)
& ")" 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;
procedure model(variable e_grant : out boolean;
variable e_reason : out sched_reason_t) is
variable after_v, pafter_v, len_v : integer;
variable ff, fc, blk : boolean;
begin
len_v := to_integer(unsigned(req_len));
after_v := s_used + len_v;
pafter_v := s_pused + len_v;
ff := after_v <= FRAME_UNITS;
fc := pafter_v <= PERIODIC_CAP;
blk := periodic_pending = '1' and req_is_periodic = '0';
if req_valid = '0' then e_reason := R_NONE;
elsif blk then e_reason := R_PREEMPTED;
elsif req_is_periodic = '1' then
if not fc then e_reason := R_OVER_CAP;
elsif not ff then e_reason := R_NO_TIME;
else e_reason := R_GRANT;
end if;
else
if not ff then e_reason := R_NO_TIME;
else e_reason := R_GRANT;
end if;
end if;
e_grant := e_reason = R_GRANT;
end procedure;
procedure check_comb is
variable e_grant : boolean;
variable e_reason : sched_reason_t;
variable len_v : integer;
begin
model(e_grant, e_reason);
len_v := to_integer(unsigned(req_len));
check((grant = '1') = e_grant, "grant matches the model");
check(reason = reason_code(e_reason), "reason matches the model");
check(to_integer(unsigned(time_used)) = s_used,
"time_used matches the model");
check(to_integer(unsigned(periodic_used)) = s_pused,
"periodic_used matches the model");
check(to_integer(unsigned(time_left)) = FRAME_UNITS - s_used,
"time_left matches the model");
check(to_integer(unsigned(periodic_left)) = PERIODIC_CAP - s_pused,
"periodic_left matches the model");
-- ---- SAFETY PROPERTIES, independent of the model ----
-- 1. THE property. Never admit a transaction that will not finish
-- before the next SOF.
if grant = '1' then
check(s_used + len_v <= FRAME_UNITS,
"a transaction was admitted that cannot finish inside the frame");
end if;
-- 2. The periodic reserve is never exceeded.
if grant = '1' and req_is_periodic = '1' then
check(s_pused + len_v <= PERIODIC_CAP,
"a periodic grant exceeded the reserved budget");
end if;
-- 3. A transaction that exactly fills the remaining budget FITS.
if req_valid = '1' and periodic_pending = '0'
and req_is_periodic = '0' and (s_used + len_v) = FRAME_UNITS then
check(grant = '1',
"an async transaction that exactly fills the frame was refused");
end if;
-- 4. Periodic outranks async absolutely.
if req_valid = '1' and periodic_pending = '1'
and req_is_periodic = '0' then
check(grant = '0',
"an async transaction was admitted ahead of a pending periodic one");
end if;
-- 5. The accumulators never exceed their budgets.
check(to_integer(unsigned(time_used)) <= FRAME_UNITS,
"time_used exceeded the frame");
check(to_integer(unsigned(periodic_used)) <= PERIODIC_CAP,
"periodic_used exceeded the cap");
-- 6. Periodic time is a subset of frame time.
check(to_integer(unsigned(periodic_used))
<= to_integer(unsigned(time_used)),
"more periodic time was used than total frame time");
-- 7. grant and the reason agree.
check((reason = reason_code(R_GRANT)) = (grant = '1'),
"reason disagrees with grant");
-- 8. No request, no answer.
if req_valid = '0' then
check(grant = '0' and reason = reason_code(R_NONE),
"a grant or a refusal with no request");
end if;
n_reason(sched_reason_t'pos(e_reason))
:= n_reason(sched_reason_t'pos(e_reason)) + 1;
if e_grant and (s_used + len_v) = FRAME_UNITS then
n_exact := n_exact + 1;
end if;
if req_valid = '1' and req_is_periodic = '1'
and (s_pused + len_v) > PERIODIC_CAP then
n_capbind := n_capbind + 1;
end if;
end procedure;
procedure model_step is
variable e_grant : boolean;
variable e_reason : sched_reason_t;
variable len_v : integer;
begin
model(e_grant, e_reason);
len_v := to_integer(unsigned(req_len));
if frame_start = '1' then
s_used := 0; s_pused := 0; m_fr := m_fr + 1;
else
if e_grant then
s_used := s_used + len_v;
if req_is_periodic = '1' then
s_pused := s_pused + len_v;
end if;
m_gr := m_gr + 1;
end if;
if e_reason = R_NO_TIME then m_nt := m_nt + 1; end if;
if e_reason = R_OVER_CAP then m_oc := m_oc + 1; end if;
if e_reason = R_PREEMPTED then m_pe := m_pe + 1; end if;
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(time_used)) = s_used,
"time_used tracked the model");
check(to_integer(unsigned(periodic_used)) = s_pused,
"periodic_used tracked the model");
check(n_frames = std_logic_vector(to_unsigned(m_fr, 32)),
"n_frames matches the model");
check(n_granted = std_logic_vector(to_unsigned(m_gr, 32)),
"n_granted matches the model");
check(n_no_time = std_logic_vector(to_unsigned(m_nt, 32)),
"n_no_time matches the model");
check(n_over_cap = std_logic_vector(to_unsigned(m_oc, 32)),
"n_over_cap matches the model");
check(n_preempted = std_logic_vector(to_unsigned(m_pe, 32)),
"n_preempted matches the model");
end procedure;
procedure idle_in is
begin
frame_start <= '0'; req_valid <= '0'; periodic_pending <= '0';
end procedure;
procedure setlen(n : integer) is
begin
req_len <= std_logic_vector(to_unsigned(n, 3));
end procedure;
procedure hard_reset is
begin
rst_n <= '0'; idle_in; req_is_periodic <= '0'; setlen(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_used := 0; s_pused := 0;
m_fr := 0; m_gr := 0; m_nt := 0; m_oc := 0; m_pe := 0;
end procedure;
-- Drive the budgets to a chosen (time_used, periodic_used) using only
-- granted transactions -- periodic first to build the periodic total,
-- then async for the remainder. No register forcing.
procedure goto_budget(want_used : integer; want_pused : integer) is
variable left, chunk : integer;
begin
hard_reset;
frame_start <= '1'; step; idle_in;
left := want_pused;
while left > 0 loop
if left > 7 then chunk := 7; else chunk := left; end if;
req_valid <= '1'; req_is_periodic <= '1'; setlen(chunk);
periodic_pending <= '0'; step; idle_in;
left := left - chunk;
end loop;
left := want_used - want_pused;
while left > 0 loop
if left > 7 then chunk := 7; else chunk := left; end if;
req_valid <= '1'; req_is_periodic <= '0'; setlen(chunk);
periodic_pending <= '0'; step; idle_in;
left := left - chunk;
end loop;
wait for 1 ns;
check(to_integer(unsigned(time_used)) = want_used,
"goto_budget reached the frame total");
check(to_integer(unsigned(periodic_used)) = want_pused,
"goto_budget reached the periodic total");
end procedure;
variable iv, pmax : integer;
begin
hard_reset;
check(to_integer(unsigned(time_used)) = 0,
"reset leaves the frame budget empty");
check(to_integer(unsigned(time_left)) = FRAME_UNITS,
"with the whole frame available");
-- ===== A. EXHAUSTIVE admission sweep =====
-- Every REACHABLE (time_used, periodic_used) pair -- periodic time is a
-- subset of frame time, so pused <= min(used, PERIODIC_CAP) -- against
-- every request: valid/not, periodic/async, all 8 lengths, and a pending
-- periodic request or not.
--
-- 143 reachable budget pairs x 2 x 2 x 8 x 2 = 9152 points
for tu in 0 to FRAME_UNITS loop
if tu < PERIODIC_CAP then pmax := tu; else pmax := PERIODIC_CAP; end if;
for pu in 0 to pmax loop
n_pairs := n_pairs + 1;
for a in 0 to 1 loop
for b in 0 to 1 loop
for c in 0 to 7 loop
for d in 0 to 1 loop
goto_budget(tu, pu);
if a = 1 then req_valid <= '1'; else req_valid <= '0'; end if;
if b = 1 then req_is_periodic <= '1';
else req_is_periodic <= '0'; end if;
setlen(c);
if d = 1 then periodic_pending <= '1';
else periodic_pending <= '0'; end if;
frame_start <= '0';
step;
n_exh := n_exh + 1;
idle_in;
end loop;
end loop;
end loop;
end loop;
end loop;
end loop;
report " exhaustive admission sweep: " & integer'image(n_exh)
& " points over " & integer'image(n_pairs)
& " reachable budget pairs" severity note;
-- ===== B. directed: the end of a frame =====
hard_reset; frame_start <= '1'; step; idle_in;
check(n_frames = std_logic_vector(to_unsigned(1, 32)),
"the SOF started a frame");
-- 1. An async transaction with the whole frame free.
req_valid <= '1'; req_is_periodic <= '0'; setlen(5); step; idle_in;
wait for 1 ns;
check(grant = '0',
"grant is a one-cycle decision and the request has been withdrawn");
check(to_integer(unsigned(time_used)) = 5, "five units used");
check(to_integer(unsigned(time_left)) = 11, "eleven left");
-- 2. THE case. 11 remain and a 7-unit transaction fits; then 4 remain
-- and a 7-unit one does not.
req_valid <= '1'; req_is_periodic <= '0'; setlen(7); wait for 1 ns;
check(grant = '1', "seven units fit in the eleven that remain");
step; idle_in;
check(to_integer(unsigned(time_used)) = 12, "twelve used");
check(to_integer(unsigned(time_left)) = 4, "four left");
req_valid <= '1'; req_is_periodic <= '0'; setlen(7); wait for 1 ns;
check(grant = '0',
"seven units do NOT fit in four -- and there is no way to stop a transaction once started");
check(reason = reason_code(R_NO_TIME),
"which is exactly why it was refused");
step; idle_in;
check(to_integer(unsigned(time_used)) = 12, "and nothing was consumed");
-- 3. A transaction that EXACTLY fills the remaining budget fits.
req_valid <= '1'; req_is_periodic <= '0'; setlen(4); wait for 1 ns;
check(grant = '1',
"four units exactly fill the four that remain -- <= not <");
step; idle_in;
check(to_integer(unsigned(time_used)) = 16, "the frame is exactly full");
check(to_integer(unsigned(time_left)) = 0, "with nothing left");
-- 4. Nothing more fits, except a zero-length request.
req_valid <= '1'; req_is_periodic <= '0'; setlen(1); wait for 1 ns;
check(grant = '0', "one more unit does not fit");
step; idle_in;
req_valid <= '1'; req_is_periodic <= '0'; setlen(0); wait for 1 ns;
check(grant = '1',
"but a zero-length transaction still fits in zero time");
step; idle_in;
-- ===== C. directed: the periodic reserve =====
hard_reset; frame_start <= '1'; step; idle_in;
-- 5. Periodic traffic up to the cap.
req_valid <= '1'; req_is_periodic <= '1'; setlen(7); step; idle_in;
req_valid <= '1'; req_is_periodic <= '1'; setlen(5); step; idle_in;
check(to_integer(unsigned(periodic_used)) = 12,
"twelve units of periodic traffic");
check(to_integer(unsigned(periodic_left)) = 0,
"which is the whole reserve");
check(to_integer(unsigned(time_used)) = 12,
"and twelve units of the frame");
-- 6. THE cap. More periodic traffic is refused even though the FRAME has
-- room -- the reserve protects the asynchronous traffic.
req_valid <= '1'; req_is_periodic <= '1'; setlen(2); wait for 1 ns;
check(grant = '0', "more periodic traffic is refused");
check(reason = reason_code(R_OVER_CAP),
"because the periodic RESERVE is full, not the frame");
check(to_integer(unsigned(time_left)) = 4,
"even though four units of the frame remain");
step; idle_in;
-- 7. Those four units are available to ASYNC traffic.
req_valid <= '1'; req_is_periodic <= '0'; setlen(4); wait for 1 ns;
check(grant = '1', "and asynchronous traffic CAN use them");
check(reason = reason_code(R_GRANT),
"which is the point of reserving only 12 of 16");
step; idle_in;
check(to_integer(unsigned(time_used)) = 16, "the frame is full");
check(to_integer(unsigned(periodic_used)) = 12,
"with the periodic reserve untouched by it");
-- ===== D. directed: priority =====
hard_reset; frame_start <= '1'; step; idle_in;
-- 8. An async request waits while a periodic one is pending.
req_valid <= '1'; req_is_periodic <= '0'; setlen(2);
periodic_pending <= '1'; wait for 1 ns;
check(grant = '0', "an async request waits for a pending periodic one");
check(reason = reason_code(R_PREEMPTED), "and is told why");
step; idle_in;
check(to_integer(unsigned(time_used)) = 0, "nothing was consumed");
-- 9. The periodic request runs.
req_valid <= '1'; req_is_periodic <= '1'; setlen(2);
periodic_pending <= '1'; wait for 1 ns;
check(grant = '1', "the periodic request is not blocked by itself");
step; idle_in;
-- 10. And now the async one can go.
req_valid <= '1'; req_is_periodic <= '0'; setlen(2);
periodic_pending <= '0'; wait for 1 ns;
check(grant = '1', "with nothing periodic pending, async proceeds");
step; idle_in;
-- 11. A new frame wipes both budgets.
frame_start <= '1'; step; idle_in;
check(to_integer(unsigned(time_used)) = 0,
"the SOF reset the frame budget");
check(to_integer(unsigned(periodic_used)) = 0,
"and the periodic reserve");
check(n_frames = std_logic_vector(to_unsigned(2, 32)), "two frames");
-- ===== E. 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, 10); if iv = 0 then frame_start <= '1';
else frame_start <= '0'; end if;
rnd(iv, 4); if iv /= 0 then req_valid <= '1';
else req_valid <= '0'; end if;
rnd(iv, 3); if iv = 0 then req_is_periodic <= '1';
else req_is_periodic <= '0'; end if;
rnd(iv, 8); setlen(iv);
rnd(iv, 5); if iv = 0 then periodic_pending <= '1';
else periodic_pending <= '0'; end if;
step;
end loop;
for i in 0 to 4 loop
check(n_reason(i) > 500, "every admission outcome was reached");
end loop;
check(n_exact > 200, "exact-fit admissions happened often");
check(n_capbind > 500, "the periodic reserve bound often");
report " REACH: exhaustive=" & integer'image(n_exh)
& " over " & integer'image(n_pairs)
& " budget pairs | outcomes: none=" & integer'image(n_reason(0))
& " grant=" & integer'image(n_reason(1))
& " no-time=" & integer'image(n_reason(2))
& " over-cap=" & integer'image(n_reason(3))
& " preempted=" & integer'image(n_reason(4)) severity note;
report " CASES: exact-fit grants=" & integer'image(n_exact)
& " periodic-cap refusals=" & integer'image(n_capbind) severity note;
report " COUNTERS: frames="
& integer'image(to_integer(unsigned(n_frames)))
& " granted=" & integer'image(to_integer(unsigned(n_granted)))
& " no-time=" & integer'image(to_integer(unsigned(n_no_time)))
& " over-cap=" & integer'image(to_integer(unsigned(n_over_cap)))
& " preempted=" & integer'image(to_integer(unsigned(n_preempted)))
severity note;
report " [VHDL] usb_frame_scheduler: " & 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;11. Exhaustive Verification
| Measure | Verilog | SystemVerilog | VHDL |
|---|---|---|---|
| Exhaustive points | 9152 | 9152 | 9152 |
| Reachable budget pairs | 143 | 143 | 143 |
R_NONE reached | 23742 | 23691 | 23810 |
R_GRANT reached | 39371 | 39315 | 39320 |
R_NO_TIME reached | 9914 | 10104 | 10035 |
R_OVER_CAP reached | 1826 | 1809 | 1703 |
R_PREEMPTED reached | 5164 | 5098 | 5149 |
| exact-fit grants | 3097 | 3005 | 3007 |
| periodic-cap refusals | 1826 | 1809 | 1703 |
| frames | 4032 | 3913 | 3988 |
| transactions granted | 13849 | 13904 | 13824 |
| Result | PASS | PASS | PASS |
All five admission outcomes are reached thousands of times and the testbenches assert it.
Exact-fit grants (~3000) is the row that makes §2's <=-not-< claim evidence. A transaction filling the remaining budget precisely is a single point in a large space, and it was hit three thousand times because the exhaustive sweep visits every budget state and every length — not because the randomiser happened to find it.
12. Mutation Testing
| # | Mutation | Verilog | SysVer | VHDL |
|---|---|---|---|---|
| N1 | "is there time left?" instead of "enough time?" | 202433 | 206200 | 207017 |
| N2 | the periodic reserve is checked against the frame | 129043 | 127163 | 131062 |
| N3 | periodic no longer outranks async | 215078 | 215292 | 216456 |
| N4 | a periodic request is not checked against the frame | 201083 | 204096 | 204133 |
| N5 | < instead of <= — an exact fit is refused | 183714 | 179943 | 181266 |
| N6 | an async grant also charges the periodic reserve | 313464 | 315969 | 314790 |
| N7 | the budgets are not reset at the SOF | 351303 | 349510 | 347852 |
| — | unmutated baseline | 0 | 0 | 0 |
All seven die, all counts distinct, columns within 3%.
N1 is the mutation this chapter is about, at ~205 000. Note that it is not the largest: it is wrong only for requests that would overrun, which is a minority of them. N7 (no SOF reset) and N6 (async charged to the reserve) score higher because they are wrong constantly, and that ordering is worth reading the right way round — mutation counts measure how often a bug is observable, not how bad it is. N1 is the most dangerous mutation in the table and the fourth-largest number in it.
N2 at ~129 000 is the smallest, and it is the starvation bug: the periodic reserve is checked against the whole frame, so periodic traffic can fill every frame and bulk transfers never complete. It scores lowest because it only differs from correct behaviour once periodic usage passes the cap — which requires the sweep to drive the reserve to its limit, and is exactly what the 143-pair budget enumeration is for.
13. Debugging Walkthrough: The Webcam That Glitches When the Disk Is Busy
The report. A USB webcam drops frames intermittently — but only while a USB mass-storage device on the same bus is being written to. The camera alone is fine. The disk alone is fine. Together, the camera glitches and the disk is slightly slow.
Step 1 — whose fault is it? The instinct is bandwidth: two devices, not enough bus. Check the numbers. The camera's isochronous reservation plus the disk's actual throughput is well under the frame budget. There is bandwidth to spare.
Step 2 — what does "drops frames" mean at the bus level? Capture. The camera's isochronous transactions are occasionally missing from a frame — not NAKed, not errored, simply not scheduled. Isochronous endpoints have no retry, so a missed transaction is a lost frame.
Step 3 — when are they missed? Correlate against the disk traffic. A camera transaction is missed only in frames where a bulk transfer was scheduled first.
Step 4 — why that is wrong. Periodic traffic has a reservation and a deadline this frame; bulk has neither. A bulk transaction admitted ahead of a pending periodic one consumes frame time the periodic transaction was promised — and when the periodic request finally arrives, the frame no longer has room for it.
Step 5 — why it needs both devices. With only the camera there is nothing to go first. With only the disk there is no deadline to miss. The bug requires a periodic request to be pending at the moment an async one is offered, which is the one condition neither device produces alone.
Step 6 — the cause. The arbiter granted whatever was presented, in arrival order. Mutation N3, in production.
14. UVM: Filling a Frame Deliberately
14.1 The transaction
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
class usb_sched_item extends uvm_sequence_item;
`uvm_object_utils(usb_sched_item)
rand bit frame_start;
rand bit req_valid;
rand bit req_is_periodic;
rand bit [2:0] req_len;
rand bit periodic_pending;
// A frame is many transactions long, so an SOF is rare per cycle.
constraint c_frame_rate { frame_start dist {0 := 9, 1 := 1}; }
// Roughly a third of traffic is periodic on a mixed bus.
constraint c_mix {
req_valid dist {1 := 3, 0 := 1};
req_is_periodic dist {0 := 2, 1 := 1};
periodic_pending dist {0 := 4, 1 := 1};
}
// An SOF and a request cannot be acted on in the same cycle -- the budget
// reset takes the cycle. Soft, so the adversarial sequence can present
// both and check which wins.
constraint c_not_both { soft !(frame_start && req_valid); }
function new(string name = "usb_sched_item"); super.new(name); endfunction
function string convert2string();
return $sformatf("sof=%0b vld=%0b per=%0b len=%0d pend=%0b",
frame_start, req_valid, req_is_periodic, req_len,
periodic_pending);
endfunction
endclass14.2 Sequences
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
// THE sequence for this chapter. It fills a frame to within a few units of
// the budget and THEN offers a transaction too long to fit -- the population
// in which "is there time left?" and "is there enough time left?" give
// different answers. Uniform random traffic reaches it only by accident,
// because it requires the budget to be nearly full AND the request to be
// long, and those are independent.
class fill_then_overrun_seq extends uvm_sequence #(usb_sched_item);
`uvm_object_utils(fill_then_overrun_seq)
function new(string name = "fill_then_overrun_seq"); super.new(name); endfunction
localparam int FRAME_UNITS = 16;
task body();
repeat (300) begin
usb_sched_item it;
int unsigned used = 0;
int unsigned target = $urandom_range(FRAME_UNITS - 6, FRAME_UNITS - 1);
// start a frame
it = usb_sched_item::type_id::create("it");
start_item(it);
it.c_frame_rate.constraint_mode(0);
it.c_not_both.constraint_mode(0);
if (!it.randomize() with { frame_start == 1; req_valid == 0; })
`uvm_error("RAND", "SOF randomize failed")
finish_item(it);
// fill it to `target` with async traffic
while (used < target) begin
int unsigned chunk = (target - used) > 7 ? 7 : (target - used);
it = usb_sched_item::type_id::create("it");
start_item(it);
it.c_frame_rate.constraint_mode(0);
it.c_mix.constraint_mode(0);
it.c_not_both.constraint_mode(0);
if (!it.randomize() with { frame_start == 0; req_valid == 1;
req_is_periodic == 0;
periodic_pending == 0;
req_len == chunk; })
`uvm_error("RAND", "fill randomize failed")
finish_item(it);
used += chunk;
end
// ...and now offer something that will NOT fit
it = usb_sched_item::type_id::create("it");
start_item(it);
it.c_frame_rate.constraint_mode(0);
it.c_mix.constraint_mode(0);
it.c_not_both.constraint_mode(0);
if (!it.randomize() with { frame_start == 0; req_valid == 1;
periodic_pending == 0;
req_len > (FRAME_UNITS - target); })
`uvm_error("RAND", "overrun randomize failed")
finish_item(it);
end
endtask
endclass
// THE other boundary: a transaction that fills the remaining budget EXACTLY.
// This is the population that separates <= from <, and it is a single point
// for each budget state.
class exact_fit_seq extends uvm_sequence #(usb_sched_item);
`uvm_object_utils(exact_fit_seq)
function new(string name = "exact_fit_seq"); super.new(name); endfunction
localparam int FRAME_UNITS = 16;
task body();
repeat (300) begin
usb_sched_item it;
int unsigned remain = $urandom_range(1, 7);
int unsigned used = FRAME_UNITS - remain;
int unsigned done = 0;
it = usb_sched_item::type_id::create("it");
start_item(it);
it.c_frame_rate.constraint_mode(0);
it.c_not_both.constraint_mode(0);
if (!it.randomize() with { frame_start == 1; req_valid == 0; })
`uvm_error("RAND", "SOF randomize failed")
finish_item(it);
while (done < used) begin
int unsigned chunk = (used - done) > 7 ? 7 : (used - done);
it = usb_sched_item::type_id::create("it");
start_item(it);
it.c_frame_rate.constraint_mode(0);
it.c_mix.constraint_mode(0);
it.c_not_both.constraint_mode(0);
if (!it.randomize() with { frame_start == 0; req_valid == 1;
req_is_periodic == 0;
periodic_pending == 0;
req_len == chunk; })
`uvm_error("RAND", "prefill randomize failed")
finish_item(it);
done += chunk;
end
// exactly the remaining budget: this MUST be granted
it = usb_sched_item::type_id::create("it");
start_item(it);
it.c_frame_rate.constraint_mode(0);
it.c_mix.constraint_mode(0);
it.c_not_both.constraint_mode(0);
if (!it.randomize() with { frame_start == 0; req_valid == 1;
req_is_periodic == 0;
periodic_pending == 0;
req_len == remain; })
`uvm_error("RAND", "exact randomize failed")
finish_item(it);
end
endtask
endclass
// Priority inversion: an async request offered while a periodic one is
// pending, with the frame NOT full. Nothing is short of bandwidth here --
// the only correct reason to refuse is priority.
class priority_inversion_seq extends uvm_sequence #(usb_sched_item);
`uvm_object_utils(priority_inversion_seq)
function new(string name = "priority_inversion_seq"); super.new(name); endfunction
task body();
repeat (400) begin
usb_sched_item it;
it = usb_sched_item::type_id::create("it");
start_item(it);
it.c_frame_rate.constraint_mode(0);
it.c_not_both.constraint_mode(0);
if (!it.randomize() with { frame_start == 1; req_valid == 0; })
`uvm_error("RAND", "SOF randomize failed")
finish_item(it);
// an empty frame, a pending periodic request, and an async offer
it = usb_sched_item::type_id::create("it");
start_item(it);
it.c_frame_rate.constraint_mode(0);
it.c_mix.constraint_mode(0);
it.c_not_both.constraint_mode(0);
if (!it.randomize() with { frame_start == 0; req_valid == 1;
req_is_periodic == 0;
periodic_pending == 1;
req_len inside {[1:4]}; })
`uvm_error("RAND", "inversion randomize failed")
finish_item(it);
end
endtask
endclass14.3 The scoreboard
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
class usb_sched_scoreboard extends uvm_scoreboard;
`uvm_component_utils(usb_sched_scoreboard)
uvm_analysis_imp #(usb_sched_mon_item, usb_sched_scoreboard) ap;
localparam int FRAME_UNITS = 16;
localparam int PERIODIC_CAP = 12;
// The scoreboard keeps its OWN budgets, in plain integers. Mirroring the
// design's widened-vector arithmetic would let it share an overflow bug.
int unsigned sb_used, sb_pused;
int unsigned n_grant, n_no_time, n_over_cap, n_preempt, n_exact;
int unsigned n_overrun_offered;
function new(string name, uvm_component parent);
super.new(name, parent);
ap = new("ap", this);
endfunction
function void write(usb_sched_mon_item t);
int after = sb_used + t.req_len;
int pafter = sb_pused + t.req_len;
bit fits_frame = (after <= FRAME_UNITS);
bit fits_cap = (pafter <= PERIODIC_CAP);
bit blocked = t.periodic_pending && !t.req_is_periodic;
if (t.frame_start) begin
sb_used = 0; sb_pused = 0;
return;
end
// ---- THE property. Nothing is admitted that cannot FINISH. ----
if (t.grant && !fits_frame)
`uvm_error("OVERRUN",
$sformatf("admitted a %0d-unit transaction with only %0d units left -- it will still be on the wire at the next SOF, and every device on the bus loses its timing reference",
t.req_len, FRAME_UNITS - sb_used))
if (!fits_frame) n_overrun_offered++;
// ---- The periodic reserve is never exceeded ----
if (t.grant && t.req_is_periodic && !fits_cap)
`uvm_error("RESERVE",
"a periodic grant exceeded the reserved budget -- bulk traffic on this bus can now be starved indefinitely")
// ---- An exact fit is a fit ----
if (t.req_valid && !blocked && !t.req_is_periodic
&& (after == FRAME_UNITS)) begin
if (!t.grant)
`uvm_error("EXACT_FIT",
"a transaction that exactly fills the frame was refused -- the last slot of every frame is being wasted")
n_exact++;
end
// ---- Periodic outranks async, absolutely ----
if (t.req_valid && blocked && t.grant)
`uvm_error("PRIORITY",
"an async transaction was admitted ahead of a pending periodic one -- the periodic reservation for this frame is now gone")
// ---- The reason must be the RIGHT one: three refusals, three fixes ----
begin
sched_reason_e expect_why;
if (!t.req_valid) expect_why = R_NONE;
else if (blocked) expect_why = R_PREEMPTED;
else if (t.req_is_periodic && !fits_cap) expect_why = R_OVER_CAP;
else if (!fits_frame) expect_why = R_NO_TIME;
else expect_why = R_GRANT;
if (t.reason != expect_why)
`uvm_error("REASON",
$sformatf("reason=%s, expected %s -- NO_TIME, OVER_CAP and PREEMPTED need three different responses from whoever is tuning this system",
t.reason.name(), expect_why.name()))
case (expect_why)
R_GRANT: n_grant++;
R_NO_TIME: n_no_time++;
R_OVER_CAP: n_over_cap++;
R_PREEMPTED: n_preempt++;
default: ;
endcase
end
// ---- Advance the scoreboard's own budgets ----
if (t.grant) begin
sb_used = after;
// ONLY a periodic grant charges the reserve.
if (t.req_is_periodic) sb_pused = pafter;
end
if (t.time_used !== sb_used)
`uvm_error("BUDGET", $sformatf("time_used=%0d, scoreboard=%0d",
t.time_used, sb_used))
if (t.periodic_used !== sb_pused)
`uvm_error("BUDGET", $sformatf("periodic_used=%0d, scoreboard=%0d",
t.periodic_used, sb_pused))
endfunction
function void report_phase(uvm_phase phase);
`uvm_info("SB", $sformatf(
"grants=%0d no-time=%0d over-cap=%0d preempted=%0d exact-fits=%0d",
n_grant, n_no_time, n_over_cap, n_preempt, n_exact), UVM_LOW)
if (n_overrun_offered == 0) `uvm_error("COVERAGE",
"no transaction too long for the remaining frame was ever offered -- the rule this block exists for is untested")
if (n_exact == 0) `uvm_error("COVERAGE",
"no exact-fit transaction was ever offered -- <= versus < is untested")
if (n_over_cap == 0) `uvm_error("COVERAGE",
"the periodic reserve never bound")
if (n_preempt == 0) `uvm_error("COVERAGE",
"no priority inversion was ever presented")
endfunction
endclass14.4 Functional coverage
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
covergroup frame_sched_cg with function sample(
bit [4:0] used, bit [4:0] pused, bit [2:0] len, bit periodic,
bit pending, sched_reason_e reason);
cp_reason : coverpoint reason {
bins all[] = {R_NONE, R_GRANT, R_NO_TIME, R_OVER_CAP, R_PREEMPTED};
}
// The budget expressed as how FULL the frame is, in the bands where the
// decision changes. An absolute coverpoint on `used` closes happily while
// never once landing near the boundary.
cp_fullness : coverpoint used {
bins empty = {0};
bins early = {[1:8]};
bins late = {[9:15]}; // where the admission test starts to bite
bins full = {16};
}
// THE coverpoint. Does the request fit in what remains? Expressed as the
// RELATIONSHIP, because separate coverpoints on `used` and `len` both
// close while never recording whether the sum crossed the budget.
cp_fit : coverpoint (used + len) {
bins under = {[0:15]};
bins exact = {16}; // the <= versus < boundary
bins over = {[17:23]}; // the overrun this block must refuse
}
// THE cross. Every fit outcome at every fullness band -- "exact at full"
// and "over at late" are the two bins the whole chapter is about.
x_fit_fullness : cross cp_fit, cp_fullness;
// The reserve, expressed relative to the cap.
cp_reserve : coverpoint pused {
bins unused = {0};
bins partial = {[1:11]};
bins at_cap = {12};
}
cp_periodic : coverpoint periodic { bins per = {1}; bins async = {0}; }
x_reserve : cross cp_reserve, cp_periodic;
// Priority inversion with the frame NOT full -- the only case in which
// PREEMPTED is the correct answer rather than an artefact of a full frame.
cp_pending : coverpoint pending { bins pending = {1}; bins quiet = {0}; }
x_priority : cross cp_pending, cp_periodic, cp_fullness;
endgroupcp_fit binning used + len rather than either operand is the same lesson as 21.2's cp_len_rel and 21.1's cp_match: the interesting event is a relationship, and a coverage model built from the port list never records it. Separate coverpoints on used and len both close at 100% while the sum never once reaches 16.
15. SystemVerilog Assertions
Azvya Education Pvt. Ltd.VLSI Mentor
Snippet
module usb_frame_scheduler_sva
import usb_sched_pkg::*;
#(
parameter int FRAME_UNITS = 16,
parameter int PERIODIC_CAP = 12,
parameter int TW = 5
) (
input logic clk,
input logic rst_n,
input logic frame_start,
input logic req_valid,
input logic req_is_periodic,
input logic [2:0] req_len,
input logic periodic_pending,
input logic grant,
input sched_reason_e reason,
input logic [TW-1:0] time_used,
input logic [TW-1:0] periodic_used,
input logic [TW-1:0] time_left,
input logic [TW-1:0] periodic_left
);
default clocking cb @(posedge clk); endclocking
default disable iff (!rst_n);
// ---- 1. THE property. Nothing is admitted that cannot FINISH. ----
property p_never_overrun_the_frame;
grant |-> ((time_used + TW'(req_len)) <= TW'(FRAME_UNITS));
endproperty
a_never_overrun_the_frame : assert property (p_never_overrun_the_frame)
else $error("admitted a %0d-unit transaction with %0d left -- it will overrun the SOF",
req_len, time_left);
// ---- 2. ...and the periodic reserve is never exceeded. ----
property p_never_exceed_reserve;
(grant && req_is_periodic)
|-> ((periodic_used + TW'(req_len)) <= TW'(PERIODIC_CAP));
endproperty
a_never_exceed_reserve : assert property (p_never_exceed_reserve)
else $error("a periodic grant exceeded the reserve -- bulk traffic can now be starved");
// ---- 3. An exact fit IS a fit. The other half of property 1: without
// ---- this, "refuse everything" satisfies property 1 perfectly.
property p_exact_fit_is_granted;
(req_valid && !periodic_pending && !req_is_periodic
&& ((time_used + TW'(req_len)) == TW'(FRAME_UNITS))) |-> grant;
endproperty
a_exact_fit_is_granted : assert property (p_exact_fit_is_granted)
else $error("a transaction that exactly fills the frame was refused");
// ---- 4. Periodic outranks async absolutely. ----
property p_periodic_outranks_async;
(req_valid && periodic_pending && !req_is_periodic) |-> !grant;
endproperty
a_periodic_outranks_async : assert property (p_periodic_outranks_async)
else $error("an async transaction was admitted ahead of a pending periodic one");
// ---- 5. The budgets never exceed themselves. ----
property p_budgets_bounded;
(time_used <= TW'(FRAME_UNITS))
&& (periodic_used <= TW'(PERIODIC_CAP))
&& (periodic_used <= time_used);
endproperty
a_budgets_bounded : assert property (p_budgets_bounded);
// ---- 6. ONLY a periodic grant charges the reserve. ----
property p_async_does_not_charge_reserve;
(grant && !req_is_periodic && !frame_start)
|=> (periodic_used == $past(periodic_used));
endproperty
a_async_does_not_charge_reserve :
assert property (p_async_does_not_charge_reserve)
else $error("an async grant charged the periodic reserve -- the cap now binds on traffic it was never meant to limit");
// ---- 7. The SOF resets both budgets, completely. ----
property p_sof_resets_budgets;
frame_start |=> ((time_used == '0) && (periodic_used == '0));
endproperty
a_sof_resets_budgets : assert property (p_sof_resets_budgets)
else $error("the SOF did not reset the budget -- an unspent reservation is not credit");
// ---- 8. The budget moves ONLY on a grant or an SOF. ----
property p_budget_moves_only_for_a_reason;
(!$stable(time_used)) |-> $past(grant || frame_start);
endproperty
a_budget_moves_only_for_a_reason :
assert property (p_budget_moves_only_for_a_reason);
// ---- 9. grant and reason are one decision, not two. ----
property p_grant_iff_reason_grant;
grant == (reason == R_GRANT);
endproperty
a_grant_iff_reason_grant : assert property (p_grant_iff_reason_grant)
else $error("the scheduler granted while reporting a refusal, or the reverse");
// ---- 10. The refusal reported is the FIRST one that applies. ----
property p_reason_priority;
(req_valid && periodic_pending && !req_is_periodic)
|-> (reason == R_PREEMPTED);
endproperty
a_reason_priority : assert property (p_reason_priority);
// ---- Cover: the boundary populations were actually reached. ----
c_exact_fit : cover property ((grant &&
((time_used + TW'(req_len)) == TW'(FRAME_UNITS))));
c_overrun_refused : cover property ((req_valid && !grant &&
((time_used + TW'(req_len)) > TW'(FRAME_UNITS))));
c_reserve_bound : cover property ((reason == R_OVER_CAP));
c_inversion : cover property ((reason == R_PREEMPTED));
c_frame_exactly_full : cover property ((time_used == TW'(FRAME_UNITS)));
endmodule
bind usb_frame_scheduler usb_frame_scheduler_sva
#(.FRAME_UNITS(FRAME_UNITS), .PERIODIC_CAP(PERIODIC_CAP), .TW(TW))
u_sva (.*);16. Common Misconceptions
"The scheduler can stop a transaction that is running late." It cannot. Once the token is out, the device replies at the bus's pace and nothing aborts it. The only decision point is before the token.
"Checking that the frame is not full is enough." It is right except at the end of every frame, which is the only place it matters.
"A transaction that exactly fills the frame is too risky." It fits. Refusing it wastes the last slot of every frame, permanently and silently.
"The periodic cap limits periodic traffic." It protects asynchronous traffic. Periodic already has priority; without the cap, bulk transfers would never complete on a busy isochronous bus.
"Periodic and async should be arbitrated fairly." Periodic has a deadline this frame; async has no deadline at all. Fairness between them is a priority inversion with a friendly name.
"An unspent periodic reservation carries into the next frame." It does not. The budget resets at every SOF; an unused reservation is gone, not banked.
"An async grant should count against the total, which includes the reserve." It counts against the frame, never against the reserve. Charging it to the reserve makes the cap bind on traffic it was never meant to limit (N6, 314 000 failures).
"Bandwidth to spare means deadlines will be met." Total bandwidth is an average; a deadline is not. A bus can be 40% idle and still miss every deadline if the idle time is in the wrong part of the frame.
17. Exercises
1. Change fits_frame to used_r < FRAME_UNITS (mutation N1) and predict which of the eight safety properties fires first. Then explain why N1 scores lower than N7, and why that ordering says nothing about which bug is worse.
2. Compute the sums in TW bits instead of TW+1. Find the budget state and request length at which the truncated comparison says "it fits" about a transaction that does not, and confirm the exhaustive sweep catches it.
3. The VHDL originally used natural range 0 to FRAME_UNITS and four mutants produced FATAL. Restore that version, re-run N1, and write down exactly what information is lost when a mutant crashes instead of failing.
4. Property 1 and property 3 pin the boundary from both sides. Find the pair that pins the periodic reserve the same way, and show that property 2 alone is satisfied by a design that never grants a periodic request at all.
5. Add a third traffic class — high-speed split transactions, which have a deadline two frames out rather than one. What does the priority chain become, and which of the five reason values splits into two?
6. The mutation generator's str.replace silently produced a mutant identical to the baseline. Write the check that would have caught it without an assert — that is, a property of the generated files themselves — and say which you would rather have in a CI job.
18. Summary
| Idea | Why it matters |
|---|---|
| The frame boundary is observed by devices | an overrun disturbs the whole bus, not one transfer |
| You cannot stop a transaction once started | so admission asks about the future |
| "enough time left", not "time left" | wrong only at the end of every frame |
An exact fit is a fit (<=, not <) | or the last slot of every frame is wasted |
| Sums computed one bit wider | the frame end is where a narrow add overflows |
| The periodic cap protects async traffic | without it, bulk never completes |
| Periodic outranks async absolutely | it has a deadline this frame; async has none |
| Only a periodic grant charges the reserve | or the cap binds on the wrong traffic |
| The SOF resets both budgets | an unspent reservation is not credit |
grant is derived from reason | one decision, two views, no disagreement |
| 9152 points over 143 reachable budget pairs | every budget state × every request |
| 7 mutations, all killed in 3 languages | after a generator bug produced a false zero |
Tooling
| Step | Command |
|---|---|
| Verilog-2005 | iverilog -g2005 -o fs_v.out fs_v.v fs_v_tb.v && ./fs_v.out |
| SystemVerilog | iverilog -g2012 -o fs_sv.out fs_sv.sv fs_sv_tb.sv && ./fs_sv.out |
| VHDL-2008 analyse | nvc --std=2008 -a fs_vhdl.vhd fs_vhdl_tb.vhd |
| VHDL-2008 elaborate | nvc --std=2008 -e tb_fs_vhdl |
| VHDL-2008 run | nvc --std=2008 -r tb_fs_vhdl |
| One mutation | iverilog -g2005 -DMUT_N1 -o mm fs_v_mut.v fs_v_tb.v && ./mm |
All three implementations pass with 0 errors: 9152 exhaustive admission points over 143 reachable budget pairs, 40 000 randomised cycles, every admission outcome reached and asserted reached.
Chapter 22.4 — Host Resource Management closes the module with the structures that sit under all of this: xHCI's slots, contexts and doorbells. Its defining rule is an ownership one, like the cycle bit — software may not write a context hardware owns, which is why there are two of them — and its sharpest detail is that a Configure Endpoint command's Drop flags are applied before its Add flags, so dropping and adding the same endpoint in one command is not a contradiction but a re-initialisation.
Continue learning
Related tutorials
- 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.
- Related topic
EHCI Overview
EHCI has no command queue — it is a DMA engine walking a linked list software edits underneath it, around a ring with no end, where a link pointer is a packed word and the terminate bit must be read first.
- Related topic
xHCI Overview
xHCI shares a ring between software and hardware using one Cycle bit per TRB and no pointer exchange at all — and an unowned entry holds the previous lap's complete, plausible descriptor.
- Related topic
Host Resource Management
Software cannot edit a context hardware owns, so xHCI has two of them — and inside a Configure Endpoint command the Drop flags are applied before the Add flags, making drop+add an atomic re-initialisation.
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.