Host Scheduling Algorithm

Chapters 17.1 and 17.2 built time: a 1 ms frame, and eight 125 µs microframes inside it. Every one of them is an opportunity — a moment at which the host may place work on the bus.

Neither chapter decided what to place.

This one does, and it is the centre of the module. Several flows are waiting and they have incompatible requirements: an isochronous endpoint holding a reservation 16.4 already admitted, an interrupt endpoint whose 15.4 deadline is approaching, a control transfer that must never be starved, and bulk traffic that will take whatever is left.

They cannot all go first. And the useful insight is not which one wins — it is that "which one wins" is the last of five questions, and the commonest scheduler defect is answering it without having asked the other four.

1. Scheduling Is Not One Decision

Write the decision out as the pipeline it actually is:

   does work EXIST?                  -> pending
        |  & enabled  & budget
   COULD it be serviced now?         -> eligible
        |  periodic obligations first
   does POLICY permit it now?        -> candidate
        |  round-robin among equals
   is it SELECTED?                   -> grant
        |
   did it COMPLETE?                  -> serviced
        |  otherwise
   it is STILL PENDING               -> deferred

Six words, six different states, and none of them is a synonym for another:

2. Where the Policy Comes From — and Where It Does Not

This is the module's most important boundary and it must be stated before any RTL.

USB requires that periodic obligations be met within their service intervals. An isochronous endpoint admitted under 16.4 gets its slot every service interval; an interrupt endpoint is polled within its bInterval (15.4). Those are protocol requirements, and a host that misses them is non-compliant.

USB does not mandate how a controller chooses among the rest. It does not require round-robin, it does not require fixed priority by endpoint index, it does not require the arbiter in this chapter.

Every RTL block in this chapter is one legal implementation of a requirement, not the requirement. A different compliant controller may use deadline-ordered selection, weighted credits, or a wholly static schedule computed at configuration time — and this chapter's verification would reject it, correctly, because it verifies this policy.

3. Eligibility Is a Conjunction, and Each Term Is Independent

   eligible  =  pending  &  enabled  &  can_fit

Three terms, three different sources, no ordering between them.

pending comes from the requester: work arrived and has not been serviced. It is state, and §5 is about keeping it.

enabled comes from configuration: the endpoint exists and is not halted. A pending requester on a disabled endpoint stays pending — the work is not lost, it is simply not a candidate.

can_fit comes from the budget, and Chapter 17.4 computes it. A transaction the remaining frame budget cannot accommodate is not eligible, however important it is.

Computing eligibility before selection is the architecture, not a style choice. A design that folds the budget test into the priority chain has made fits a tie-breaker rather than a precondition — and will grant work that cannot be performed whenever the highest-priority requester happens not to fit.

4. Periodic and Opportunistic

The one precedence USB's obligations genuinely motivate:

Periodic obligations are considered first. An isochronous or interrupt endpoint with an eligible obligation this opportunity outranks any amount of bulk traffic, because missing its interval is a compliance failure while delaying bulk is not.

Among the opportunistic, something must break the tie, and the choice has consequences:

Neither is universally better and this chapter uses both: fixed priority among periodic requesters, round-robin among opportunistic ones. §13 measures what that costs in fairness, and the answer is not zero.

5. Request Retention, and the Set/Clear Collision

The two invariants that live in the sequential half:

      pend_next = (pend & ~cleared) | req;

Read it as two statements. A requester is cleared only by service — not by losing, not by becoming ineligible, not by a frame boundary. And the set term is ORed in last, which decides the collision:

A new request arriving in the same cycle its predecessor is serviced must survive. The requester asked again; the fact that its previous work was completing at that instant is irrelevant to whether the new work exists. Writing (pend | req) & ~cleared instead — clearing after the OR — loses it, and §12 measures that at 4019 failures.

Losing a turn and losing the work are different things, and a single line decides which one the hardware implements.

6. The Hardware, Before Any Language

The design is deliberately two modules, and the boundary is the architecture:

usb_sched_select — combinational. Given the current situation — who is pending, who is enabled, who fits, who is periodic, where the pointer is — who should win? No state, no memory, no history.

usb_sched_arbiter — sequential. What is still owed, and whose turn is next. Two invariants and nothing else.

Separating them is not tidiness. Deciding is a function of the present; remembering is state. Conflating them produces schedulers whose defects only appear after some particular history — and it makes the decision impossible to test exhaustively, which §10 shows is otherwise entirely practical.

State retained: pend_r (who is owed), ptr_r (who is considered first next).

On reset or bus reset: nothing is pending, and the pointer starts at requester 0.

Every opportunity: eligibility is computed, periodic candidates are considered first by lowest index, opportunistic candidates by an ordered search starting at the pointer, and at most one grant is issued.

On service: the granted requester is cleared. The pointer advances only when an opportunistic requester wins — honouring a periodic obligation is not a turn in the rotation, and charging one would let periodic traffic consume opportunistic requesters' places.

The pointer is one-hot and advances by rotation, {grant[N-2:0], grant[N-1]}. The rotate makes the wrap automatic; an increment-and-compare needs the bound written out, and that is where off-by-one defects live.

Exactly one transition removes a requester from the system, and it is serviced. Every other outcome — not eligible, not selected, budget exhausted — returns it to Pending. That single-exit property is what §5's retention expression implements and what mutation S2 destroys.

7. Verilog

The RTL contract

• What it models: the arbitration performed at one scheduling opportunity, and the state carried between opportunities.
• Why it exists: because §1's six states are distinct and §2's obligations require a precedence.
• Inputs: req (pulse, new work), enabled, periodic, can_fit (levels), serviced (pulse), bus_reset.
• Authoritative state: pend_r, ptr_r. Nothing else is stored.
• Derived state: eligible, grant, grant_valid — all combinational, recomputed every opportunity.
• Outputs: pending, eligible, grant, grant_valid, rr_ptr.
• Hardware implied: one N-bit register, one N-bit one-hot register, two priority searches, a handful of gates.
• Reset: asynchronous active-low rst_n; bus_reset synchronous and equivalent; both clear pending and reset the pointer to requester 0.
• Priority: eligibility is a precondition, not a tie-break. Periodic outranks opportunistic. Within periodic, lowest index. Within opportunistic, cyclic order from the pointer.
• Latency: the grant is combinational from the current state; pending and rr_ptr update on the next edge.
• Boundary behaviour: the pointer rotates, so the wrap from the last requester to the first is automatic.
• Collision behaviour: req and serviced for the same requester in one cycle leaves it pending (§5).
• Assumptions: one grant per opportunity; serviced refers to the requester currently granted; can_fit is already computed for the current budget.
• Omissions: no transfer descriptors, no per-endpoint error state, no retirement, no split transactions, no speed handling.
• What DV should verify: that a grant is always eligible; that an eligible periodic obligation is never bypassed; that losers remain pending; that a same-cycle request survives; that the pointer wraps; that no requester starves.

// usb_sched_select -- WHO should be serviced at this opportunity.
//
// Pure combinational, and deliberately a separate module from the state that
// surrounds it. That boundary is the chapter's architecture: deciding is a
// function of the current situation, while REMEMBERING what is still owed is
// state, and conflating them is how schedulers acquire defects that only
// appear after some particular history.
//
// It also makes the decision exhaustively testable. With four requesters the
// whole input domain is 16 x 16 x 16 x 16 x 4 = 262144 points, which is a
// number a testbench can simply visit rather than sample.
//
// POLICY vs PROTOCOL. USB requires periodic obligations to be met within
// their service intervals; it does NOT mandate round-robin among the rest,
// nor fixed priority by index among periodic requesters. Those are THIS
// controller's policy. A different compliant controller may choose otherwise.
module usb_sched_select #(
  parameter integer N = 4
) (
  input  wire [N-1:0] pending,
  input  wire [N-1:0] enabled,
  input  wire [N-1:0] periodic,
  input  wire [N-1:0] can_fit,
  input  wire [N-1:0] rr_ptr,     // one-hot: who is considered FIRST
  output wire [N-1:0] eligible,
  output wire [N-1:0] grant,      // one-hot; zero when nothing is selected
  output wire         grant_valid
);
  // ELIGIBILITY: three independent terms, ANDed. A requester that is pending
  // but disabled is not a candidate, and neither is one the budget cannot
  // accommodate. Priority never overrides either -- that is the whole point
  // of separating eligibility from selection.
  assign eligible = pending & enabled & can_fit;

  wire [N-1:0] elig_per = eligible &  periodic;
  wire [N-1:0] elig_opp = eligible & ~periodic;

  // Among periodic obligations: lowest index first.
  integer gi;
  reg [N-1:0] sel_per;
  always @* begin
    sel_per = {N{1'b0}};
    for (gi = N-1; gi >= 0; gi = gi - 1)
      if (elig_per[gi]) sel_per = ({{(N-1){1'b0}}, 1'b1} << gi);
  end

  // Among the opportunistic: an ordered search of N positions starting at
  // the pointer. Written as an explicit search so the WRAP is visible; a
  // plain priority encoder hides exactly the case that breaks.
  integer k, idx, ptr_idx;
  reg [N-1:0] sel_opp;
  reg found;
  always @* begin
    ptr_idx = 0;
    for (k = 0; k < N; k = k + 1)
      if (rr_ptr[k]) ptr_idx = k;
    sel_opp = {N{1'b0}};
    found   = 1'b0;
    for (k = 0; k < N; k = k + 1) begin
      idx = (ptr_idx + k) % N;          // THE WRAP: modulo, not saturation
      if (!found && elig_opp[idx]) begin
        sel_opp = ({{(N-1){1'b0}}, 1'b1} << idx);
        found   = 1'b1;
      end
    end
  end

  // Periodic outranks opportunistic. This is the one precedence USB's
  // service-interval obligations actually motivate.
  assign grant       = (elig_per != {N{1'b0}}) ? sel_per : sel_opp;
  assign grant_valid = (grant != {N{1'b0}});
endmodule


// usb_sched_arbiter -- what is still OWED, and whose turn is next.
//
// The state half. Two invariants live here and nothing else does:
//   * a requester that loses arbitration is STILL PENDING;
//   * a new request arriving in the same cycle its predecessor is serviced
//     is NOT lost.
module usb_sched_arbiter #(
  parameter integer N = 4
) (
  input  wire          clk,
  input  wire          rst_n,
  input  wire          bus_reset,
  input  wire [N-1:0]  req,        // pulse: new work arrived for requester i
  input  wire [N-1:0]  enabled,    // level: the endpoint is configured
  input  wire [N-1:0]  periodic,   // level: this is a periodic obligation
  input  wire [N-1:0]  can_fit,    // level: the budget permits it (ch 17.4)
  input  wire          serviced,   // pulse: the granted work completed
  output wire [N-1:0]  pending,
  output wire [N-1:0]  eligible,
  output wire [N-1:0]  grant,
  output wire          grant_valid,
  output wire [N-1:0]  rr_ptr
);
  reg [N-1:0] pend_r;
  reg [N-1:0] ptr_r;

  assign pending = pend_r;
  assign rr_ptr  = ptr_r;

  usb_sched_select #(.N(N)) sel (
    .pending(pend_r), .enabled(enabled), .periodic(periodic),
    .can_fit(can_fit), .rr_ptr(ptr_r),
    .eligible(eligible), .grant(grant), .grant_valid(grant_valid));

  wire [N-1:0] clear_mask = (serviced && grant_valid) ? grant : {N{1'b0}};

  always @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      pend_r <= {N{1'b0}};
      ptr_r  <= {{(N-1){1'b0}}, 1'b1};      // consider requester 0 first
    end else if (bus_reset) begin
      pend_r <= {N{1'b0}};
      ptr_r  <= {{(N-1){1'b0}}, 1'b1};
    end else begin
      // REQUEST RETENTION -- the invariant this module exists to uphold.
      //
      //     pend_next = (pend & ~cleared) | req
      //
      // NOT `pend_next <= req`, which silently drops every requester that
      // lost arbitration. And the SET term is ORed in LAST, so a new request
      // arriving in the same cycle its predecessor is serviced SURVIVES:
      // losing a turn and losing the work are different things.
      pend_r <= (pend_r & ~clear_mask) | req;

      // The pointer advances ONLY when an OPPORTUNISTIC requester wins. A
      // periodic grant is not a turn in the round-robin, so honouring an
      // obligation must not cost an opportunistic requester its place.
      if (serviced && grant_valid && ((grant & ~periodic) != {N{1'b0}})) begin
        // Rotate to the position after the winner. The rotate makes the wrap
        // automatic; an increment-and-compare needs the bound written out,
        // and that is where off-by-one defects live.
        ptr_r <= {grant[N-2:0], grant[N-1]};
      end
    end
  end
endmodule

Two details are worth naming.

The opportunistic search is an explicit ordered scan with a modulo index, not a priority encoder over a pre-rotated mask. Both synthesise to similar logic; only one makes the wrap visible in the source. The line computing the cyclic index is the line that has to be right, and it is worth being able to point at it.

The pointer advances on an opportunistic win, not on any grant. Those differ exactly when a periodic obligation wins, which is §4's rule. The SystemVerilog states the same condition more directly.

8. SystemVerilog

package usb_sched_pkg;
  // What KIND of work a requester represents. A distinct type rather than a
  // bare bit, because the precedence between the two is the one thing USB's
  // service-interval obligations actually motivate.
  typedef enum logic { K_OPPORTUNISTIC, K_PERIODIC } kind_e;

  // Why this opportunity produced the grant it did. Naming the outcomes
  // makes them exhaustive, and makes "nothing was eligible" distinguishable
  // from "something was eligible and lost" -- which a bare grant vector
  // cannot express and which section 16's debugging depends on.
  typedef enum logic [1:0] {
    G_NONE,        // nothing was eligible at this opportunity
    G_PERIODIC,    // a periodic obligation was selected
    G_ROUNDROBIN   // an opportunistic requester was selected
  } gkind_e;
endpackage

module usb_sched_select_sv
  import usb_sched_pkg::*;
#(
  parameter int unsigned N = 4
) (
  input  logic [N-1:0] pending,
  input  logic [N-1:0] enabled,
  input  logic [N-1:0] periodic,
  input  logic [N-1:0] can_fit,
  input  logic [N-1:0] rr_ptr,
  output logic [N-1:0] eligible,
  output logic [N-1:0] grant,
  output logic         grant_valid,
  output gkind_e       grant_kind
);
  initial begin
    if (N < 2) $fatal(1, "N=%0d: an arbiter of one needs no policy", N);
  end

  // ELIGIBILITY: three independent terms. Priority never overrides either of
  // the other two -- that is why eligibility is computed before selection
  // rather than inside it.
  assign eligible = pending & enabled & can_fit;

  wire [N-1:0] elig_per = eligible &  periodic;
  wire [N-1:0] elig_opp = eligible & ~periodic;

  logic [N-1:0] sel_per, sel_opp;
  always_comb begin
    sel_per = '0;
    for (int gi = N-1; gi >= 0; gi--)
      if (elig_per[gi]) sel_per = (N'(1) << gi);
  end

  always_comb begin
    int ptr_idx, idx;
    bit found;
    ptr_idx = 0;
    for (int k = 0; k < N; k++)
      if (rr_ptr[k]) ptr_idx = k;
    sel_opp = '0;
    found   = 1'b0;
    for (int k = 0; k < N; k++) begin
      idx = (ptr_idx + k) % N;          // THE WRAP: modulo, not saturation
      if (!found && elig_opp[idx]) begin
        sel_opp = (N'(1) << idx);
        found   = 1'b1;
      end
    end
  end

  always_comb begin
    if      (elig_per != '0) begin grant = sel_per; grant_kind = G_PERIODIC;    end
    else if (sel_opp  != '0) begin grant = sel_opp; grant_kind = G_ROUNDROBIN;  end
    else                     begin grant = '0;      grant_kind = G_NONE;        end
  end

  assign grant_valid = (grant_kind != G_NONE);
endmodule


module usb_sched_arbiter_sv
  import usb_sched_pkg::*;
#(
  parameter int unsigned N = 4
) (
  input  logic          clk,
  input  logic          rst_n,
  input  logic          bus_reset,
  input  logic [N-1:0]  req,
  input  logic [N-1:0]  enabled,
  input  logic [N-1:0]  periodic,
  input  logic [N-1:0]  can_fit,
  input  logic          serviced,
  output logic [N-1:0]  pending,
  output logic [N-1:0]  eligible,
  output logic [N-1:0]  grant,
  output logic          grant_valid,
  output gkind_e        grant_kind,
  output logic [N-1:0]  rr_ptr
);
  usb_sched_select_sv #(.N(N)) sel (
    .pending(pending), .enabled(enabled), .periodic(periodic),
    .can_fit(can_fit), .rr_ptr(rr_ptr),
    .eligible(eligible), .grant(grant), .grant_valid(grant_valid),
    .grant_kind(grant_kind));

  wire [N-1:0] clear_mask = (serviced && grant_valid) ? grant : '0;

  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n || bus_reset) begin
      pending <= '0;
      rr_ptr  <= N'(1);                 // consider requester 0 first
    end else begin
      // REQUEST RETENTION. The SET term is ORed in LAST, so a new request
      // arriving in the same cycle its predecessor is serviced SURVIVES:
      // losing a turn and losing the work are different things.
      pending <= (pending & ~clear_mask) | req;

      // The pointer advances ONLY on an opportunistic grant. Honouring a
      // periodic obligation must not cost an opportunistic requester its
      // place in the rotation -- which `grant_kind` states directly rather
      // than re-deriving from the periodic mask.
      if (serviced && (grant_kind == G_ROUNDROBIN))
        rr_ptr <= {grant[N-2:0], grant[N-1]};   // rotate: the wrap is free
    end
  end
endmodule

gkind_e is the addition that earns its place. G_NONE, G_PERIODIC and G_ROUNDROBIN distinguish nothing was eligible from a periodic obligation won from the rotation advanced — and a bare grant vector cannot express the first distinction at all. §16's debugging depends on it: "no grant" and "no candidates" are different facts, and a scheduler that cannot tell an engineer which occurred cannot explain itself.

It also makes the pointer rule direct. The Verilog re-derives was the winner opportunistic from the periodic mask; the SystemVerilog reads grant_kind == G_ROUNDROBIN. One expression instead of two that must agree.

9. VHDL

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

package usb_sched_pkg is
  -- Why this opportunity produced the grant it did. A distinct type with no
  -- numeric encoding: "nothing was eligible" and "something was eligible and
  -- lost" are different outcomes, and a bare grant vector cannot tell them
  -- apart -- which is exactly what section 16's debugging needs.
  type gkind_t is (G_NONE, G_PERIODIC, G_ROUNDROBIN);
end package;

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use work.usb_sched_pkg.all;

entity usb_sched_select_vhdl is
  generic ( N : positive := 4 );
  port (
    pending     : in  std_logic_vector(N-1 downto 0);
    enabled     : in  std_logic_vector(N-1 downto 0);
    periodic    : in  std_logic_vector(N-1 downto 0);
    can_fit     : in  std_logic_vector(N-1 downto 0);
    rr_ptr      : in  std_logic_vector(N-1 downto 0);
    eligible    : out std_logic_vector(N-1 downto 0);
    grant       : out std_logic_vector(N-1 downto 0);
    grant_valid : out std_logic;
    grant_kind  : out gkind_t
  );
end entity;

architecture rtl of usb_sched_select_vhdl is
  constant ZERO : std_logic_vector(N-1 downto 0) := (others => '0');
  signal elig, elig_per, elig_opp : std_logic_vector(N-1 downto 0);
  signal sel_per, sel_opp : std_logic_vector(N-1 downto 0);
begin
  assert N >= 2
    report "an arbiter of one needs no policy" severity failure;

  -- ELIGIBILITY: three independent terms. Priority never overrides either of
  -- the other two, which is why eligibility is computed before selection.
  elig     <= pending and enabled and can_fit;
  elig_per <= elig and periodic;
  elig_opp <= elig and (not periodic);
  eligible <= elig;

  -- Among periodic obligations: lowest index first.
  process (elig_per)
    variable v : std_logic_vector(N-1 downto 0);
  begin
    v := (others => '0');
    for gi in N-1 downto 0 loop
      if elig_per(gi) = '1' then
        v := (others => '0');
        v(gi) := '1';
      end if;
    end loop;
    sel_per <= v;
  end process;

  -- Among the opportunistic: an ordered search of N positions starting at
  -- the pointer. Written as an explicit search so the WRAP is visible.
  process (elig_opp, rr_ptr)
    variable ptr_idx, idx : integer range 0 to N-1;
    variable found : boolean;
    variable v : std_logic_vector(N-1 downto 0);
  begin
    ptr_idx := 0;
    for k in 0 to N-1 loop
      if rr_ptr(k) = '1' then ptr_idx := k; end if;
    end loop;
    v := (others => '0');
    found := false;
    for k in 0 to N-1 loop
      idx := (ptr_idx + k) mod N;        -- THE WRAP: modulo, not saturation
      if (not found) and elig_opp(idx) = '1' then
        v := (others => '0');
        v(idx) := '1';
        found := true;
      end if;
    end loop;
    sel_opp <= v;
  end process;

  -- Periodic outranks opportunistic: the one precedence USB's
  -- service-interval obligations actually motivate.
  grant      <= sel_per when elig_per /= ZERO else sel_opp;
  grant_kind <= G_PERIODIC   when elig_per /= ZERO else
                G_ROUNDROBIN when sel_opp  /= ZERO else
                G_NONE;
  grant_valid <= '0' when (elig_per = ZERO and sel_opp = ZERO) else '1';
end architecture;


library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use work.usb_sched_pkg.all;

entity usb_sched_arbiter_vhdl is
  generic ( N : positive := 4 );
  port (
    clk         : in  std_logic;
    rst_n       : in  std_logic;
    bus_reset   : in  std_logic;
    req         : in  std_logic_vector(N-1 downto 0);
    enabled     : in  std_logic_vector(N-1 downto 0);
    periodic    : in  std_logic_vector(N-1 downto 0);
    can_fit     : in  std_logic_vector(N-1 downto 0);
    serviced    : in  std_logic;
    pending     : out std_logic_vector(N-1 downto 0);
    eligible    : out std_logic_vector(N-1 downto 0);
    grant       : out std_logic_vector(N-1 downto 0);
    grant_valid : out std_logic;
    grant_kind  : out gkind_t;
    rr_ptr      : out std_logic_vector(N-1 downto 0)
  );
end entity;

architecture rtl of usb_sched_arbiter_vhdl is
  constant ZERO : std_logic_vector(N-1 downto 0) := (others => '0');
  signal pend_r : std_logic_vector(N-1 downto 0) := (others => '0');
  signal ptr_r  : std_logic_vector(N-1 downto 0) := (others => '0');
  signal g_int  : std_logic_vector(N-1 downto 0);
  signal gv_int : std_logic;
  signal gk_int : gkind_t;
  signal clear_mask : std_logic_vector(N-1 downto 0);
begin
  pending     <= pend_r;
  rr_ptr      <= ptr_r;
  grant       <= g_int;
  grant_valid <= gv_int;
  grant_kind  <= gk_int;

  sel : entity work.usb_sched_select_vhdl
    generic map (N => N)
    port map (pend_r, enabled, periodic, can_fit, ptr_r,
              eligible, g_int, gv_int, gk_int);

  clear_mask <= g_int when (serviced = '1' and gv_int = '1') else ZERO;

  process (clk, rst_n)
  begin
    if rst_n = '0' then
      pend_r <= (others => '0');
      ptr_r  <= (0 => '1', others => '0');   -- consider requester 0 first
    elsif rising_edge(clk) then
      if bus_reset = '1' then
        pend_r <= (others => '0');
        ptr_r  <= (0 => '1', others => '0');
      else
        -- REQUEST RETENTION. The SET term is ORed in LAST, so a new request
        -- arriving in the same cycle its predecessor is serviced SURVIVES:
        -- losing a turn and losing the work are different things.
        pend_r <= (pend_r and (not clear_mask)) or req;

        -- The pointer advances ONLY on an opportunistic grant. Honouring a
        -- periodic obligation must not cost an opportunistic requester its
        -- place, which grant_kind states directly rather than re-deriving.
        if serviced = '1' and gk_int = G_ROUNDROBIN then
          ptr_r <= g_int(N-2 downto 0) & g_int(N-1);   -- rotate: wrap is free
        end if;
      end if;
    end if;
  end process;
end architecture;

gkind_t has no numeric encoding, so the three outcomes cannot be compared against integers and any case over them must be exhaustive — the property 16.3 and 16.5 also relied on.

The selector is a separate entity instantiated by the arbiter, exactly as in the other two. §6's module boundary is not a language artefact; it is the architecture, and all three express it the same way.

The pointer rotate is a concatenation in all three languages — one of the few places in this curriculum where they agree not merely in behaviour but in shape.

10. Comparing the Three

All three describe the same hardware, and §12's counts agree to within the difference their randomisers make.

11. Exhaustive Verification, and the Coupling That Hid Four Defects

The selection function has a small domain, so it is not sampled — it is visited.

Four requesters means pending, enabled, periodic and can_fit are each 16 values, and the pointer is one of 4 positions:

   16 x 16 x 16 x 16 x 4  =  262144

  exhaustive selection sweep: 262144 of 262144 points verified

Every point is checked against six properties: eligibility is the conjunction, the grant matches the reference model, the grant is at most one-hot, grant_valid tracks it, a granted requester is always eligible, and an eligible periodic obligation is never bypassed. There is no coverage question left about the decision.

The reference model is structurally different from the design (§37 of this curriculum's standard). The DUT scans positions in order and stops at the first hit; the model assigns every candidate a rank — its cyclic distance from the pointer — and selects the minimum:

        for (m = 0; m < N; m = m + 1) begin
          if (eo[m]) begin
            rank = (m - ptr_i + N) % N;      // cyclic distance from the pointer
            if (rank < best_rank) begin best_rank = rank; best = m; end
          end
        end

Rank-and-minimise cannot reproduce a scan-and-stop defect: a wrap that saturates, a search that begins in the wrong place, a stop condition that never fires.

The directed scenarios cover what the sweep cannot, because the sweep has no history:

  REACH: exhaustive=262144 grants=5076 periodic-wins=2962 opportunistic-wins=2114
  REACH: wins per requester = 1398 1298 1217 1163  (fairness)

12. Mutation Testing — Across All Three Languages

S1 and S7 are the largest at ~208 700, and both are eligibility defects. That is the exhaustive sweep working exactly as intended: an eligibility error is wrong at a large fraction of 262 144 points, so it cannot hide anywhere.

S5 — reversing the precedence — costs 25 799, an order of magnitude less than an eligibility defect, because it only matters when a periodic and an opportunistic candidate are eligible simultaneously. The measured run had 2962 periodic wins, and S5 is wrong on the subset of those where opportunistic work was also available.

S4 is the smallest at 2046, and for the reason §4 predicts: the wrap matters only when the last requester wins and another is waiting behind position 0. It is the classic round-robin defect and the classic round-robin blind spot at once, and it is why the directed sequence drives the last-requester case explicitly rather than trusting the random phase to produce it.

13. Fairness Is Not Free, and the Numbers Say So

The measured win distribution over 5076 grants:

  wins per requester = 1398 1298 1217 1163

That is not uniform, and the design is not defective. The skew comes from §4's policy choice: fixed priority by index among periodic requesters. When several periodic obligations are eligible at once, the lowest index wins every time — so requester 0 collects a share of the 2962 periodic wins that requester 3 never can.

The opportunistic half is fair; the periodic half is not, and the composition is the 1398-to-1163 spread.

14. Assertions

  // A1. SAFETY, and the property §3 exists for: a granted requester is
  //     ALWAYS eligible. Not merely pending -- eligible.
  property p_grant_implies_eligible;
    @(posedge clk) disable iff (!rst_n || bus_reset)
      grant_valid |-> ((grant & ~eligible) == '0);
  endproperty
  a_grant_implies_eligible: assert property (p_grant_implies_eligible);

  // A2. SAFETY: at most one grant. Stated with $onehot0 so it also holds
  //     when nothing is selected.
  property p_grant_onehot0;
    @(posedge clk) disable iff (!rst_n)
      $onehot0(grant);
  endproperty
  a_grant_onehot0: assert property (p_grant_onehot0);

  // A3. SAFETY, §2's one normative precedence: an eligible periodic
  //     obligation is never bypassed by opportunistic work.
  property p_periodic_precedence;
    @(posedge clk) disable iff (!rst_n || bus_reset)
      ((eligible & periodic) != '0) |-> ((grant & periodic) != '0);
  endproperty
  a_periodic_precedence: assert property (p_periodic_precedence);

  // A4. RETENTION, §5, and the property the coupled scoreboard could not
  //     check: a pending requester stays pending unless it was SERVICED.
  //     Phrased against the observed inputs, never against the DUT's own
  //     next-state expression.
  property p_retention;
    @(posedge clk) disable iff (!rst_n || bus_reset)
      ($past(pending) & ~pending & ~$past(req)) ==
      ($past(pending) & ~pending & $past(serviced_mask));
  endproperty
  a_retention: assert property (p_retention);

  // A5. COLLISION, §5: a new request in the service cycle survives.
  property p_same_cycle_request_survives;
    @(posedge clk) disable iff (!rst_n || bus_reset)
      (req[0] && serviced && grant[0]) |=> pending[0];
  endproperty
  a_same_cycle_request_survives: assert property (p_same_cycle_request_survives);

  // A6. PROGRESS, under explicit assumptions -- see the contract table.
  //     A requester that stays pending, stays eligible, and keeps being
  //     offered opportunities is granted within N of them.
  property p_no_starvation;
    @(posedge clk) disable iff (!rst_n || bus_reset)
      (eligible[0] && !grant[0]) |-> ##[1:N] grant[0];
  endproperty
  a_no_starvation: assert property (p_no_starvation);

Assertion contracts

A1 is the assertion that looks sufficient and is not. §47's argument in its sharpest form: a scheduler that grants nothing, ever, satisfies A1, A2, A3, A4 and A5 perfectly. Every safety property here is an implication antecedent on something happening, and a design that does nothing makes every antecedent false.

A6 is the only property that fails for a do-nothing scheduler, and it is the only one that needs its assumptions written down. Every request is eventually served is not a property of this design and would be false: a requester that is disabled for ever, or whose cost never fits, is never served and correctly so. The bounded form — within N opportunities, given continuous eligibility and no unbounded periodic load — is what the round-robin policy actually guarantees, and it is guaranteed by the pointer, which is why mutations S3 and S4 are fairness defects rather than safety defects.

A4 is written against $past(req) and an observed service mask, not against the design's next-state expression. That is §11's lesson turned into an assertion: a property phrased in terms of the computation under test cannot detect an error in that computation.

15. Verification: Where UVM Finally Earns Its Place

Chapters 17.1 and 17.2 declined UVM and said the scenario space would arrive here. It has.

What changed is that the interesting properties span histories. A counter's correctness is a function of its inputs; a scheduler's correctness is a function of what it did last time — the pointer, the pending set, the accumulated fairness. §11 is the direct evidence: the defects that mattered were invisible to a per-cycle check and required a model carrying state.

The coverage model is where this environment earns the most, because §12 and §13 are both coverage questions that no check raises:

  cross: eligible_count     x  winner_index
  cross: periodic_eligible  x  opportunistic_eligible   -- the collision
  bin:   pointer_position   { 0, 1, .. N-1 }            -- every position
  bin:   pointer_wrap_events                            -- last -> first
  cross: previous_winner    x  next_winner              -- rotation order
  bin:   same_cycle_req_and_service                     -- §5's collision
  bin:   deferral_run_length { 1, 2, .. N, >N }         -- starvation pressure
  bin:   win_share_per_requester                        -- §13's fairness

pointer_wrap_events is the bin that matters most, and §12 says why: S4 — the wrap defect — is the smallest count in the matrix at 2046, because the wrap is the rarest transition. A standing coverage bin reports its absence; a mutation score does not, and the directed test that currently guarantees it is one line that a future edit could silently remove.

And win_share_per_requester turns §13 into a regression artefact. The 1398-to-1163 spread was measured by hand once; a cover bin reports it every run, and a change to the periodic policy that quietly starved requester 3 would show up as a bin going to zero rather than as an argument about fairness.

The monitor must not compute the expected winner, and the reference model must keep its own pointer. §11 is the whole argument: a scoreboard that reads the DUT's scheduling state verifies self-consistency, not correctness. That is the one rule this environment exists to enforce.

16. Debugging: the Endpoint That Is Never Serviced

A bulk endpoint is configured, its driver has queued work, and the device never receives a token for it. Other endpoints on the same device work normally. The endpoint is not halted, the transfers do not time out with an error — they simply never complete. Unplugging and re-enumerating restores it, for a while.

"Never serviced" has five distinct causes and they are distinguished in order, which is why §1's six states are worth separating in the first place. The debug is the pipeline, read backwards.

Was work pending? If the request never reached the scheduler, nothing downstream matters. A driver that queued a transfer whose completion never fired may never have rung the doorbell at all.

Was it eligible? §3's conjunction has three terms and any one of them is sufficient to exclude a requester without any error being reported anywhere:

This is why eligible is an output of the design and not an internal signal. A scheduler that exposes only grant cannot answer the second question, and the engineer is left guessing between three causes that look the same.

Was there a candidate at all? §8's grant_kind distinguishes nothing was eligible from something won. G_NONE with a non-empty pending is the signature of an eligibility problem; G_PERIODIC every opportunity is the signature of the next question.

Did policy permit it? If periodic obligations are eligible at every opportunity, opportunistic work never runs — and that is not a bug in the arbiter, it is overcommitment: the admitted periodic load leaves no opportunity spare. §2's precedence is working exactly as specified and the fault is upstream, in what was admitted.

Did it lose the rotation for ever? If the pointer never advances past a particular position, one requester wins repeatedly and the rest starve. That is mutation S3, and it is visible immediately in the pointer trace — which is why rr_ptr is an output.

The first divergence. Compare the bench's independent pointer and pending set against the design's, opportunity by opportunity. The first opportunity where they differ is the bug — and §11 is the reminder that the comparison only works if the model maintained its own.

17. Common Misconceptions

"A scheduler is an arbiter." Arbitration is the fifth of six questions (§1). Four of the commonest defects live in the other five states.

"Pending means serviceable." Pending means the work exists. Eligibility needs enabled and can_fit as well (§3), and neither is a tie-break.

"Higher priority means it gets serviced." Priority orders candidates. An ineligible requester of any priority is not a candidate (§3).

"A request that loses arbitration can be cleared." It is deferred, not dropped (§5). pend_r <= req is a one-line data-loss bug worth 12 456 failures (§12).

"Round-robin guarantees fairness." It bounds starvation among the requesters it arbitrates. §13 measured a 1398-to-1163 spread caused by the periodic half, which round-robin never touches.

"Fixed priority is always wrong." It is the right choice for periodic obligations here, and §4 gives the trade rather than a verdict.

"USB mandates iso, then interrupt, then control, then bulk." USB mandates that periodic obligations be met within their service intervals (§2). The rest is controller policy, and this chapter's round-robin is one legal choice among many.

"If every grant is legal, the scheduler is correct." §14: a scheduler that grants nothing satisfies every safety property in this chapter.

"262144 exhaustive points means the design is verified." §11: it means the decision is verified. The four invariants about state were each caught by one directed check until the scoreboard was fixed.

18. Exercises

1. Given pending = 1011, enabled = 1110, periodic = 1000, can_fit = 0111 and the pointer at requester 1, work out eligible and grant by hand. Then change can_fit to 1111 and explain why the winner changes.

2. Implement the arbiter with fixed priority everywhere — no pointer, no rotation — and determine which of §14's assertions still hold. State precisely which one fails and under what stimulus.

3. §11 showed a coupled scoreboard cannot detect S2, S3, S4 or S6. Construct a directed test for each that would catch it without an independent model, and say how many cycles each needs.

4. Extend the design to eight requesters. Compute the new exhaustive domain size and decide whether it is still practical to visit; if not, choose the subspace you would exhaust and justify it.

5. §13 measured a 1398-to-1163 win spread. Change the periodic policy from fixed priority to round-robin within the periodic class, predict the new spread, then measure it.

6. Write a bounded fairness property for a requester that is eligible only intermittently, and state the assumptions that make it provable. Explain why A6 as written does not cover that case.

7. Mutation S8 lets the search continue past the first hit, producing multiple grants. Determine which of §14's assertions catches it first, and whether the exhaustive sweep or the random phase finds it sooner.

19. Summary

Scheduling is six questions, not one (§1) — does work exist, could it be serviced, does policy permit it, is it selected, did it complete, and is it still owed. Pending, eligible, granted and deferred are four different states, and conflating any two is the commonest scheduler defect.

USB requires periodic obligations to be met within their service intervals. It requires nothing else about how a controller chooses (§2). Round-robin, fixed priority by index, and one grant per opportunity are this controller's policy and this chapter's simplification — not the protocol.

Eligibility is a conjunction of three independent terms (§3), computed before selection. Folding the budget into the priority chain makes fits a tie-break rather than a precondition.

Losing arbitration does not clear a request (§5). pend_next = (pend & ~cleared) | req, with the set term last so a same-cycle request survives.

The selection function was verified exhaustively — 262 144 of 262 144 points (§11) — against a reference model that selects by rank-and-minimise where the design scans-and-stops.

And yet the four mutations testing this chapter's central invariants each died by a single check (§11), because the scoreboard was handed the DUT's own pending and rr_ptr as inputs. A model that consumes the state under test can only verify self-consistency. Making it predict its own state took S2 from 2 to 12 456, S3 from 1 to 6338, S4 from 1 to 2046 and S6 from 1 to 4019.

Eight mutations, all killed in all three languages (§12), with eligibility defects largest at ~208 700 and the round-robin wrap smallest at 2046 — the rarest transition and the classic blind spot.

Every grant is legal and the win distribution is still skewed (§13): 1398 to 1163, caused by fixed priority among periodic requesters. Local correctness does not imply composition correctness, and no per-decision check can see it.

20. Tooling, Honestly

All three benches perform the full 262 144-point exhaustive sweep, and all three carry the independent scoreboard of §11. Their randomised phases use different generators, which is where the counts diverge.

21. What Comes Next

This chapter treated the budget as a single bit. can_fit arrived from somewhere, said yes or no, and the arbiter used it as one of three eligibility terms.

Chapter 17.4 is where that bit comes from, and it is not a constant. The frame's allocation is refreshed at every boundary and consumed transaction by transaction, so can_fit is a function of everything already committed to the frame — which means the arbiter's answer depends on decisions it made earlier in the same millisecond.

It also introduces a distinction this chapter did not need: a scheduler has two numbers for every transaction. What it expects the work to cost, used to decide; and what the work actually cost, known only afterwards and used to correct the ledger. A design that uses one number for both makes correct decisions and keeps a wrong account — and the two failures look nothing alike.

Browse the full path on the USB tutorials index.