Scheduling Optimisation

   candidate A : ready, row HIT,  age 2
   candidate B : ready, row MISS, age 40

   rule 1 (ready)  : tie
   rule 2 (column) : A wins -- and the comparison STOPS
   rule 3 (oldest) : never consulted

// ---------------------------------------------------------------------
// frfcfs_arbiter -- FR-FCFS selection with a bypass cap.
//
// CLASSIFICATION: educational, synthesisable. Implements the three
// priority rules of Rixner et al., ISCA 2000, plus the starvation
// override those rules do not provide (§6).
//
// WHAT IT DOES NOT MODEL:
//   - LEGALITY. `ready` is an INPUT, computed by whoever owns timing
//     (13.4). This block never decides whether a command may issue,
//     and 17.1's commit gate still has the final say (§1).
//   - the queue's storage or its ordering structure (17.2 owns it)
//   - the device, or any timing
//
// THE RULES, in order: ready-first, column-first (row hits), then
// oldest-first. And an OVERRIDE, which is not a fourth rule: it
// replaces the decision entirely when a request reaches its cap,
// because §6 shows rule 3 can never rescue a starving request.
// ---------------------------------------------------------------------
module frfcfs_arbiter #(
  parameter int ENTRIES = 16,
  // Bypass cap: how many times a request may be passed over before it
  // is forced. §5's bound is exactly this value, in displacement.
  // A cap of 0 degenerates to FCFS; a very large cap to uncapped
  // FR-FCFS -- both legal, and §5 quantifies the trade between them.
  parameter int BYPASS_CAP = 4,
  parameter int IDX_W = (ENTRIES <= 1) ? 1 : $clog2(ENTRIES),
  // A COUNT of bypasses up to BYPASS_CAP needs clog2(BYPASS_CAP+1).
  parameter int CAP_W = (BYPASS_CAP <= 0) ? 1 : $clog2(BYPASS_CAP + 1),
  // A COUNT of entries up to ENTRIES needs clog2(ENTRIES+1).
  parameter int OCC_W = $clog2(ENTRIES + 1),
  parameter int AGE_W = 16
) (
  input  logic                clk,
  input  logic                rst_n,

  // ── The queue, as parallel vectors. 17.2 owns the storage; this is
  //    the view a policy needs.
  input  logic [ENTRIES-1:0]  valid,
  // Legality, from 13.4's checker. NOT computed here.
  input  logic [ENTRIES-1:0]  ready,
  // Row hit, from 23.3's locality monitor. Rule 2's input.
  input  logic [ENTRIES-1:0]  is_row_hit,
  // Arrival order. Lower index = older, maintained by the queue.
  input  logic                advance,      // a selection was consumed

  // ── The selection.
  output logic                sel_valid,
  output logic [IDX_W-1:0]    sel_index,
  // Which rule produced it: 0 = hit, 1 = oldest ready, 2 = forced.
  output logic [1:0]          sel_reason,

  // ── Observability. The two numbers §4 reports, live.
  output logic [CAP_W-1:0]    worst_bypass,
  output logic [AGE_W-1:0]    cnt_selected,
  output logic [AGE_W-1:0]    cnt_hits_selected,
  output logic [AGE_W-1:0]    cnt_forced,
  output logic [OCC_W-1:0]    occupancy,
  // Any request currently at the cap. §9's P3 requires it to win.
  output logic                starving,

  output logic                err_select_not_ready,
  output logic                err_cap_exceeded
);

  initial begin
    if (ENTRIES < 1)
      $fatal(1, "frfcfs_arbiter: ENTRIES must be at least 1");
    if (BYPASS_CAP < 0)
      $fatal(1, "frfcfs_arbiter: BYPASS_CAP must not be negative");
  end

  localparam logic [1:0] R_HIT   = 2'd0;
  localparam logic [1:0] R_OLD   = 2'd1;
  localparam logic [1:0] R_FORCE = 2'd2;

  logic [CAP_W-1:0] bypass [ENTRIES];

  // Declared above the assigns that read them.
  logic [IDX_W-1:0] pick;
  logic [1:0]       reason;
  logic             found;

  // ── Candidate sets. A candidate must be valid AND ready: rule 1,
  //    and it is a filter rather than a preference -- an unready
  //    entry is not ranked lower, it is not a candidate at all.
  logic [ENTRIES-1:0] cand, cand_hit, at_cap;
  always_comb begin
    for (int i = 0; i < ENTRIES; i++) begin
      cand[i]     = valid[i] && ready[i];
      cand_hit[i] = cand[i] && is_row_hit[i];
      at_cap[i]   = valid[i] && (BYPASS_CAP > 0)
                              && (bypass[i] >= CAP_W'(BYPASS_CAP));
    end
  end

  // ── THE SELECTION. Priority: override, then rule 2, then rule 3.
  //    Each search takes the LOWEST index, which is the oldest --
  //    that is rule 3, applied inside each class rather than across
  //    classes (§6).
  always_comb begin
    pick   = '0;
    reason = R_OLD;
    found  = 1'b0;

    // Override first. A starving request wins outright, and note it
    // must also be a candidate -- forcing an UNREADY request would
    // hand 17.1's gate something it must reject, wasting the slot.
    for (int i = ENTRIES - 1; i >= 0; i--)
      if (at_cap[i] && cand[i]) begin
        pick = IDX_W'(i); reason = R_FORCE; found = 1'b1;
      end

    // Rule 2: oldest ready row hit.
    if (!found)
      for (int i = ENTRIES - 1; i >= 0; i--)
        if (cand_hit[i]) begin
          pick = IDX_W'(i); reason = R_HIT; found = 1'b1;
        end

    // Rule 3: oldest ready anything.
    if (!found)
      for (int i = ENTRIES - 1; i >= 0; i--)
        if (cand[i]) begin
          pick = IDX_W'(i); reason = R_OLD; found = 1'b1;
        end
  end

  logic [CAP_W-1:0] worst;
  logic [AGE_W-1:0] n_sel, n_hit, n_force;
  logic [OCC_W-1:0] occ;
  logic             bad_sel, cap_over;

  always_comb begin
    occ = '0;
    for (int i = 0; i < ENTRIES; i++) if (valid[i]) occ = occ + OCC_W'(1);
  end

  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      for (int i = 0; i < ENTRIES; i++) bypass[i] <= '0;
      worst <= '0; n_sel <= '0; n_hit <= '0; n_force <= '0;
      bad_sel <= 1'b0; cap_over <= 1'b0;
    end else begin
      bad_sel  <= 1'b0;
      cap_over <= 1'b0;

      if (advance && found) begin
        // ── Charge a bypass to every OLDER valid entry that was not
        //    selected. Only older ones: a newer entry being skipped is
        //    not being passed over, it simply has not waited yet.
        for (int i = 0; i < ENTRIES; i++) begin
          if (valid[i] && (IDX_W'(i) < pick)) begin
            if (bypass[i] == {CAP_W{1'b1}}) cap_over <= 1'b1;
            else                            bypass[i] <= bypass[i] + CAP_W'(1);
            if ((bypass[i] + CAP_W'(1)) > worst) worst <= bypass[i] + CAP_W'(1);
          end
        end
        // The selected entry's counter clears: it is being served.
        bypass[pick] <= '0;

        if (n_sel != {AGE_W{1'b1}}) n_sel <= n_sel + AGE_W'(1);
        if (reason == R_HIT   && n_hit   != {AGE_W{1'b1}}) n_hit   <= n_hit   + AGE_W'(1);
        if (reason == R_FORCE && n_force != {AGE_W{1'b1}}) n_force <= n_force + AGE_W'(1);

        if (!ready[pick]) bad_sel <= 1'b1;
      end
    end
  end

  assign sel_valid         = found;
  assign sel_index         = pick;
  assign sel_reason        = reason;
  assign worst_bypass      = worst;
  assign cnt_selected      = n_sel;
  assign cnt_hits_selected = n_hit;
  assign cnt_forced        = n_force;
  assign occupancy         = occ;
  assign starving          = |at_cap;
  assign err_select_not_ready = bad_sel;
  assign err_cap_exceeded     = cap_over;

endmodule

// Bind unit note: P1-P7 reference frfcfs_arbiter's internals and are
// written as though bound into it, so clk and rst_n are visible.
// P8-P10 reference starvation_bound likewise.

// P1 -- a selection is always a candidate: valid and ready. Rule 1 is
// a filter, not a preference, and this is what makes it one.
property p_selection_is_candidate;
  @(posedge clk) disable iff (!rst_n)
    sel_valid |-> (valid[sel_index] && ready[sel_index]);
endproperty
assert property (p_selection_is_candidate);

// P2 -- when a ready row hit exists and nothing is starving, a hit is
// selected. Rule 2, stated as a checkable obligation rather than an
// intention.
property p_rule2_honoured;
  @(posedge clk) disable iff (!rst_n)
    (sel_valid && !starving && (|cand_hit)) |-> (sel_reason == 2'd0);
endproperty
assert property (p_rule2_honoured);

// P3 -- THE fairness property. When a request is at its cap and is a
// candidate, it is selected. Without this the override is decorative
// and §5's bound does not exist.
property p_starving_request_wins;
  @(posedge clk) disable iff (!rst_n)
    (sel_valid && starving && (|(at_cap & cand)))
      |-> (sel_reason == 2'd2);
endproperty
assert property (p_starving_request_wins);

// P4 -- rule 3 within a class: the selected hit is the oldest hit.
// Lower index is older, so no candidate hit may have a lower index.
property p_oldest_hit_selected;
  @(posedge clk) disable iff (!rst_n)
    (sel_valid && (sel_reason == 2'd0))
      |-> ((cand_hit & ((1 << sel_index) - 1)) == '0);
endproperty
assert property (p_oldest_hit_selected);

// P5 -- the selected entry's bypass counter clears. A counter that
// survived service would force the same entry repeatedly.
property p_served_entry_clears;
  @(posedge clk) disable iff (!rst_n)
    (advance && sel_valid) |=> (bypass[$past(sel_index, 1)] == '0);
endproperty
assert property (p_served_entry_clears);

// P6 -- no bypass counter ever exceeds the cap. §5's bound, as an
// invariant over the state rather than an observation about a trace.
property p_bypass_within_cap;
  @(posedge clk) disable iff (!rst_n)
    (BYPASS_CAP > 0) |-> (worst_bypass <= CAP_W'(BYPASS_CAP));
endproperty
assert property (p_bypass_within_cap);

// P7 -- a newer entry is never charged a bypass. §8's third point:
// charging everything degrades the policy toward FCFS silently.
property p_only_older_charged;
  @(posedge clk) disable iff (!rst_n)
    (advance && sel_valid && (sel_index == '0))
      |=> (worst_bypass == $past(worst_bypass, 1));
endproperty
assert property (p_only_older_charged);

// ── Cover.
cover property (@(posedge clk) disable iff (!rst_n) sel_reason == 2'd0);
cover property (@(posedge clk) disable iff (!rst_n) sel_reason == 2'd1);
// The override actually fired -- a suite that never starves a request
// has not tested the only mechanism providing a bound.
cover property (@(posedge clk) disable iff (!rst_n) sel_reason == 2'd2);
// A request at the cap that is NOT ready: §12's corner case, where the
// override cannot fire and the request waits on legality instead.
cover property (@(posedge clk) disable iff (!rst_n)
                  starving && ((at_cap & cand) == '0));
// A hit available and passed over because something was starving --
// the precise moment throughput is traded for the bound.
cover property (@(posedge clk) disable iff (!rst_n)
                  sel_valid && (|cand_hit) && (sel_reason == 2'd2));
// BYPASS_CAP = 0: the FCFS degenerate case.
cover property (@(posedge clk) disable iff (!rst_n)
                  (BYPASS_CAP == 0) && sel_valid);
// Full queue with a selection: the arbiter under pressure.
cover property (@(posedge clk) disable iff (!rst_n)
                  sel_valid && (occupancy == OCC_W'(ENTRIES)));

// ---------------------------------------------------------------------
// starvation_bound -- an independent watchdog on how long a request
// may go unserved, auditable separately from the policy.
//
// CLASSIFICATION: educational, synthesisable.
//
// WHY SEPARATE: a fairness guarantee entangled with a policy is hard
// to reason about and easy to weaken by accident. This block observes
// selections and knows nothing about the rules that produced them, so
// it holds whatever policy is installed -- including a future one.
//
// WHAT IT DOES NOT MODEL:
//   - the policy, the queue's storage, or legality
//   - a CYCLE bound. §9's callout: the provable bound is positional,
//     because converting positions to cycles needs the workload.
// ---------------------------------------------------------------------
module starvation_bound #(
  parameter int ENTRIES   = 16,
  // Limit in SELECTIONS, not cycles. §9's callout says why.
  parameter int MAX_WAIT  = 32,
  parameter int IDX_W = (ENTRIES <= 1) ? 1 : $clog2(ENTRIES),
  parameter int W_W   = (MAX_WAIT <= 1) ? 1 : $clog2(MAX_WAIT + 2),
  parameter int OCC_W = $clog2(ENTRIES + 1)
) (
  input  logic                clk,
  input  logic                rst_n,

  input  logic [ENTRIES-1:0]  valid,
  input  logic                sel_valid,
  input  logic [IDX_W-1:0]    sel_index,

  // ── Per-entry wait, in selections observed while that entry was
  //    valid and not chosen.
  output logic [W_W-1:0]      worst_wait,
  output logic [IDX_W-1:0]    worst_entry,
  output logic                over_limit,
  output logic [ENTRIES-1:0]  at_limit_mask,
  output logic [15:0]          cnt_violations,

  output logic                err_select_invalid_entry
);

  initial begin
    if (MAX_WAIT < 1)
      $fatal(1, "starvation_bound: MAX_WAIT must be at least 1");
    if (ENTRIES < 1)
      $fatal(1, "starvation_bound: ENTRIES must be at least 1");
  end

  logic [W_W-1:0]      wait_cnt [ENTRIES];
  logic [W_W-1:0]      worst;
  logic [IDX_W-1:0]    worst_i;
  logic [15:0]         n_viol;
  logic                bad_sel;

  logic [ENTRIES-1:0] over;
  always_comb
    for (int i = 0; i < ENTRIES; i++)
      over[i] = valid[i] && (wait_cnt[i] >= W_W'(MAX_WAIT));

  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      for (int i = 0; i < ENTRIES; i++) wait_cnt[i] <= '0;
      worst <= '0; worst_i <= '0; n_viol <= '0; bad_sel <= 1'b0;
    end else begin
      bad_sel <= 1'b0;
      if (sel_valid) begin
        if (!valid[sel_index]) bad_sel <= 1'b1;

        for (int i = 0; i < ENTRIES; i++) begin
          if (!valid[i]) begin
            // An invalid slot has no wait. Not clearing it means a
            // freshly allocated entry inherits the previous
            // occupant's wait -- and is forced immediately.
            wait_cnt[i] <= '0;
          end else if (IDX_W'(i) == sel_index) begin
            wait_cnt[i] <= '0;
          end else begin
            if (wait_cnt[i] != {W_W{1'b1}}) begin
              wait_cnt[i] <= wait_cnt[i] + W_W'(1);
              if ((wait_cnt[i] + W_W'(1)) > worst) begin
                worst   <= wait_cnt[i] + W_W'(1);
                worst_i <= IDX_W'(i);
              end
              if ((wait_cnt[i] + W_W'(1)) == W_W'(MAX_WAIT)
                  && (n_viol != 16'hFFFF))
                n_viol <= n_viol + 16'd1;
            end
          end
        end
      end
    end
  end

  assign worst_wait     = worst;
  assign worst_entry    = worst_i;
  assign over_limit     = |over;
  assign at_limit_mask  = over;
  assign cnt_violations = n_viol;
  assign err_select_invalid_entry = bad_sel;

endmodule

// P8 -- the served entry's wait clears. The same discipline as P5, in
// the watchdog: a wait that survived service would report a permanent
// violation.
property p_watchdog_clears_on_service;
  @(posedge clk) disable iff (!rst_n)
    sel_valid |=> (wait_cnt[$past(sel_index, 1)] == '0);
endproperty
assert property (p_watchdog_clears_on_service);

// P9 -- an invalid entry never carries a wait, so a newly allocated
// entry starts at zero rather than inheriting its predecessor's.
property p_invalid_entry_has_no_wait;
  @(posedge clk) disable iff (!rst_n)
    sel_valid |=> ((|(~valid)) -> (wait_cnt[0] == '0) || valid[0]);
endproperty
assert property (p_invalid_entry_has_no_wait);

// P10 -- a violation is counted once per crossing, not once per cycle
// above the limit. Counting per cycle makes the figure a duration
// rather than an event count.
property p_violation_counted_once;
  @(posedge clk) disable iff (!rst_n)
    (cnt_violations != $past(cnt_violations, 1)) |-> sel_valid;
endproperty
assert property (p_violation_counted_once);

// ── Cover: a violation actually occurred with the arbiter's cap
// disabled -- proving the watchdog catches what the cap would prevent.
cover property (@(posedge clk) disable iff (!rst_n) over_limit);
cover property (@(posedge clk) disable iff (!rst_n)
                  (worst_wait > '0) && !over_limit);

// ---------------------------------------------------------------------
// direction_batcher -- gates which access direction is eligible, so a
// bus turnaround is amortised over a batch instead of paid per burst.
//
// CLASSIFICATION: educational, synthesisable. Implements the batching
// 17.1 named and deferred to Module 23.
//
// WHAT IT DOES NOT MODEL:
//   - the bus or its electrical handover (22.1 owns termination)
//   - LEGALITY (13.4), or selection WITHIN a direction (§8's arbiter)
//   - the read-to-write interval, which 23.2 §7 establishes is not a
//     single published parameter and is therefore a caller value
//
// COMPOSITION: this block chooses the DIRECTION; frfcfs_arbiter
// chooses WITHIN it (§11's callout). Merging them would make the two
// batching objectives compete inside one priority chain.
// ---------------------------------------------------------------------
module direction_batcher #(
  // Bursts served in one direction before a switch is allowed.
  // §11: the returns diminish geometrically and the latency cost
  // doubles, so this is a tuning parameter with no optimal value.
  parameter int BATCH = 4,
  // A starvation cap on the OPPOSITE direction, in batches. Without
  // it a continuous stream in one direction starves the other --
  // exactly §4's unbounded displacement, one level up.
  parameter int OPP_CAP = 2,
  parameter int B_W = (BATCH   <= 1) ? 1 : $clog2(BATCH + 1),
  parameter int C_W = (OPP_CAP <= 1) ? 1 : $clog2(OPP_CAP + 2)
) (
  input  logic            clk,
  input  logic            rst_n,

  // ── What is pending, by direction.
  input  logic            rd_pending,
  input  logic            wr_pending,
  // A burst was served in the current direction.
  input  logic            burst_served,

  // ── The gate. Exactly one is high when anything is pending.
  output logic            rd_eligible,
  output logic            wr_eligible,
  output logic            switching,        // a turnaround is being paid

  // ── Observability. The two numbers §11's table reports.
  output logic [B_W-1:0]  served_in_batch,
  output logic [15:0]     cnt_switches,
  output logic [15:0]     cnt_bursts,
  output logic [C_W-1:0]  opp_starved_batches,
  output logic            forced_switch,

  output logic            err_both_eligible,
  output logic            err_served_with_nothing_pending
);

  initial begin
    if (BATCH < 1)
      $fatal(1, "direction_batcher: BATCH must be at least 1");
    if (OPP_CAP < 1)
      // A cap of zero would switch on every batch regardless of
      // demand, which is BATCH=1 with extra steps.
      $fatal(1, "direction_batcher: OPP_CAP must be at least 1");
  end

  logic           dir_is_write;
  logic [B_W-1:0] in_batch;
  logic [C_W-1:0] opp_wait;
  logic [15:0]    n_sw, n_bu;
  logic           sw, forced;

  // The opposite direction has something pending. Declared above the
  // assigns that read it.
  logic opp_pending;
  assign opp_pending = dir_is_write ? rd_pending : wr_pending;

  logic cur_pending;
  assign cur_pending = dir_is_write ? wr_pending : rd_pending;

  // ── A switch is due when the batch is full, or when the opposite
  //    direction has waited OPP_CAP batches, or when nothing is
  //    pending in the current direction and something is in the other.
  logic batch_full, opp_starving, drained;
  assign batch_full   = (in_batch >= B_W'(BATCH));
  assign opp_starving = (opp_wait >= C_W'(OPP_CAP));
  assign drained      = !cur_pending && opp_pending;

  logic switch_due;
  assign switch_due = opp_pending && (batch_full || opp_starving || drained);

  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      dir_is_write <= 1'b0;      // start on reads; arbitrary and stated
      in_batch     <= '0;
      opp_wait     <= '0;
      n_sw <= '0; n_bu <= '0;
      sw <= 1'b0; forced <= 1'b0;
    end else begin
      sw     <= 1'b0;
      forced <= 1'b0;

      if (switch_due) begin
        dir_is_write <= ~dir_is_write;
        in_batch     <= '0;
        // The direction we are LEAVING has now waited zero batches;
        // the one we are entering had its wait satisfied.
        opp_wait     <= '0;
        sw           <= 1'b1;
        if (opp_starving) forced <= 1'b1;
        if (n_sw != 16'hFFFF) n_sw <= n_sw + 16'd1;
      end else if (burst_served) begin
        if (in_batch != B_W'(BATCH)) in_batch <= in_batch + B_W'(1);
        if (n_bu != 16'hFFFF) n_bu <= n_bu + 16'd1;
        // Charge a batch of waiting to the opposite direction only when
        // a full batch completes -- the unit of OPP_CAP is batches, so
        // charging per burst would make the cap BATCH times tighter
        // than it reads.
        if ((in_batch + B_W'(1)) >= B_W'(BATCH) && opp_pending)
          if (opp_wait != {C_W{1'b1}}) opp_wait <= opp_wait + C_W'(1);
      end
    end
  end

  assign rd_eligible = !dir_is_write && rd_pending;
  assign wr_eligible =  dir_is_write && wr_pending;
  assign switching   = sw;
  assign served_in_batch     = in_batch;
  assign cnt_switches        = n_sw;
  assign cnt_bursts          = n_bu;
  assign opp_starved_batches = opp_wait;
  assign forced_switch       = forced;

  assign err_both_eligible = rd_eligible && wr_eligible;
  assign err_served_with_nothing_pending =
           burst_served && !rd_pending && !wr_pending;

endmodule

// P11 -- exactly one direction is eligible at a time. The gate's whole
// purpose: if both were eligible the turnaround would not be batched
// at all, and §11's table would collapse to its first row.
property p_one_direction_eligible;
  @(posedge clk) disable iff (!rst_n)
    !(rd_eligible && wr_eligible);
endproperty
assert property (p_one_direction_eligible);

// P12 -- the opposite direction is never starved beyond its cap. The
// same bound as §5, applied to directions rather than to requests --
// and needed for the same reason.
property p_opposite_direction_bounded;
  @(posedge clk) disable iff (!rst_n)
    (opp_starved_batches <= C_W'(OPP_CAP));
endproperty
assert property (p_opposite_direction_bounded);

// ── Cover: a forced switch -- the direction-level starvation bound
// actually firing, which a read-heavy trace will never reach.
cover property (@(posedge clk) disable iff (!rst_n) forced_switch);
// A switch caused by the current direction draining rather than by the
// batch filling: the cheap switch, which costs the turnaround but no
// latency to anyone.
cover property (@(posedge clk) disable iff (!rst_n)
                  switching && !$past(batch_full, 1));

// Independent policy reference. Implements the three rules by building
// candidate LISTS and sorting, rather than by the DUT's priority
// loops -- so agreement is evidence rather than tautology.
// SIMULATION-ONLY.
class frfcfs_ref;
  int unsigned cap;
  int unsigned bypass [int];

  // Returns the chosen index, or -1.
  function int choose(bit [63:0] valid, bit [63:0] ready,
                      bit [63:0] hit, int n);
    int forced = -1, best_hit = -1, best_any = -1;
    for (int i = 0; i < n; i++) begin
      bit c = valid[i] && ready[i];
      if (!c) continue;
      if (cap > 0 && bypass.exists(i) && bypass[i] >= cap && forced < 0)
        forced = i;
      if (hit[i] && best_hit < 0) best_hit = i;
      if (best_any < 0)           best_any = i;
    end
    if (forced   >= 0) return forced;
    if (best_hit >= 0) return best_hit;
    return best_any;
  endfunction

  function void charge(int picked, bit [63:0] valid, int n);
    for (int i = 0; i < n; i++)
      if (valid[i] && i < picked)
        bypass[i] = (bypass.exists(i) ? bypass[i] : 0) + 1;
    bypass[picked] = 0;
  endfunction
endclass

  UNBOUNDED VERSUS BOUNDED DISPLACEMENT
    A sustained hit stream to bank 0 row 0, plus one request to
    bank 0 row 9 arriving first. 10,000 selections.

    BYPASS_CAP = 0 (FCFS)
      the row-9 request is served first.       displacement 0
      row work: every subsequent access to row 0 is a conflict.

    BYPASS_CAP disabled (uncapped FR-FCFS)
      selections 1..10000 : all row-0 hits preferred
      the row-9 request is NEVER selected.
      displacement after 10,000 selections : 9,999 and rising
      -> it is not large. It is UNBOUNDED, and no trace length
         reveals a limit because there is none.

    BYPASS_CAP = 4
      selections 1..4    : row-0 hits
      selection 5        : row-9 request FORCED, reason = 2
      displacement       : exactly 4, and it plateaus there
      -> and it plateaus for every trace length, which is the
         difference between a measurement and a bound.

    diagnosis : the uncapped case has no worst case to measure. A
      regression running 1,000 selections reports displacement 999
      and one running 10,000 reports 9,999 -- and neither number is
      a property of the design.
    what NOT to conclude : that a longer regression would find the
      bound. There is no bound to find; §6 explains why rule 3
      cannot supply one.
    caught by : P6, which is an invariant over the counter state and
      therefore holds at every trace length rather than being
      confirmed by one.