CPU Access Patterns

   what the DDR controller sees from a CPU, by cause

   a load that HITS in any cache level     ->  nothing
   a load that MISSES everywhere           ->  one line-sized read
   a store that hits a writable line       ->  nothing, until eviction
   a store that misses                     ->  often a line-sized READ
                                               (fetch before modify)
   a dirty line evicted                    ->  one line-sized WRITE
   a hardware prefetch                     ->  one line-sized read the
                                               program never requested
   an instruction fetch that misses        ->  one line-sized read
   a translation-structure miss            ->  one or more reads the
                                               program never requested

   note what is NOT in this list: a load. The unit of DDR traffic is a
   CACHE LINE, not a load, and several entries here are traffic the
   program did not ask for.

   time to complete 64 misses, ILLUSTRATIVE L = 200 cycles

   P = 1   (each miss depends on the previous)
       64 x 200 = 12,800 cycles
       DDR sees ONE request at a time. The controller has no choice
       to make: one candidate, no reordering possible, no bank
       parallelism exploitable.

   P = 8   (eight independent misses in flight)
       ceil(64/8) x 200 = 1,600 cycles
       DDR sees eight requests. The scheduler can find row hits
       among them (23.4) and spread them across banks (16.1).

   P = 16
       ceil(64/16) x 200 = 800 cycles
       ... until something else saturates: the miss-handling
       capacity, the bus, or DRAM itself.

   the SAME 64 misses, the SAME latency per miss, a 16x difference in
   completion time -- and the only variable is how many the program
   could have outstanding.

   two cores, each walking its own sequential region, ILLUSTRATIVE

   core 0 alone:  row R0 hit, hit, hit, hit ...    excellent
   core 1 alone:  row R1 hit, hit, hit, hit ...    excellent

   interleaved at the controller, if both regions map to the SAME
   bank but different rows:

       R0, R1, R0, R1, R0, R1 ...
       -> every access is a row CONFLICT (9.5)
       -> PRE + ACT + RD for each, instead of RD alone

   neither core did anything wrong. Each offered perfect locality.
   The INTERLEAVING destroyed it, and the destruction happened in a
   layer neither core can see.

   a core streams 4 KiB sequentially. DERIVED under the map above.

   lines touched            : 4096 / 64            =  64 lines
   DDR bursts per line      : 64 / (4 bytes x 8)   =   2 bursts
   DDR read bursts total    : 64 x 2               = 128
   lines per 1 KiB row      : 1024 / 64            =  16 lines

   so the 64 lines occupy  64 / 16 = 4 rows.

   commands, if the scheduler sees enough candidates to group by row:
     ACT  x 4        one per row
     RD   x 128      two per line
     PRE  x 4        one per row, under a close-page policy (23.5)

   row-hit rate = (accesses - row openings) / accesses
                = (64 - 4) / 64 = 93.75%

   ---- now the SAME workload under a map that places the bank field
   ---- BELOW the column field, so consecutive lines change bank

   consecutive lines land in different banks. Each of the 64 lines
   may be the first access to its bank's current row:
     worst case  ACT x 64, RD x 128, PRE x 64
     row-hit rate  ->  near 0%
     BUT the 64 activates are spread across 16 banks, so tRC on any
     one bank overlaps others -- 16.1's bank-level parallelism.

   the SAME address stream, two maps, two entirely different DRAM
   resource demands: one minimises row openings, the other maximises
   bank overlap. NEITHER is universally better, and 18.1 owns the
   trade.

   DERIVED under a stated ILLUSTRATIVE model: 64-byte lines,
   a workload using 8 bytes of each line it touches, and a
   prefetcher that is right 60% of the time.

   bytes the program uses        :  8 per useful line
   bytes DRAM delivers           : 64 per line fetched
   useful-line efficiency        :  8/64  = 12.5%

   with prefetch at 60% accuracy, lines fetched per useful line
                                 :  1/0.6 = 1.67
   bytes delivered per 8 useful  : 64 x 1.67 = 107
   overall efficiency            :  8/107 = 7.5%

   so DRAM moved roughly 13 bytes for every 1 the program read.

   the point is NOT that this number is typical -- it depends on the
   line size, the access density and the prefetcher, none of which
   are universal. The point is that the ratio is a real quantity, it
   is usually far below 1, and it is invisible in the program's own
   accounting.

// ---------------------------------------------------------------------
// cpu_traffic_characteriser -- CLASSIFICATION: synthesisable, BINDABLE.
//
// WHAT IT DOES: measures §9's four controller-visible quantities:
//   - CONCURRENCY: a time-average of outstanding requests, which IS
//     memory-level parallelism as the memory system experiences it.
//     §4 shows this single number separating a latency-bound workload
//     from a bandwidth-bound one.
//   - STRIDE REGULARITY: how often consecutive requests differ by the
//     same delta -- the property a prefetcher can exploit (§10) and the
//     property Scenario A lacks by construction.
//   - READ/WRITE MIX: §3's inversion means a read-only program can
//     present writes, and 29.2 §8's turnaround cost depends on the mix.
//   - BYTES DELIVERED: §10's efficiency ratio, which is invisible in a
//     program's own accounting.
//
// WHY A TIME-AVERAGE AND NOT A MAXIMUM: a peak outstanding count of 16
// reached once tells you almost nothing. The time-average is what
// determines throughput in §4's model, so conc_sum/window is the
// number that matters and outstanding_max is context.
//
// WHAT IT IS NOT: a cache, an MSHR file, or a prefetcher. It observes
// requests that already left the hierarchy. CHI 1.4 owns caches.
//
// SYNTHESIS: an up/down counter, an accumulator, two comparators, a
// small delta register. No memory, no CAM.
// ---------------------------------------------------------------------
module cpu_traffic_characteriser #(
  parameter int ADDR_W   = 40,
  parameter int MAX_OUT  = 64,    // outstanding capacity being observed
  parameter int LINE_LOG = 6,     // bytes per line = 2**LINE_LOG, ILLUSTRATIVE
  parameter int ACC_W    = 40     // accumulator width for the time-average
)(
  input  logic                          clk,
  input  logic                          rst_n,

  // ---- a request ENTERING the memory system (already a cache miss,
  // a writeback, a prefetch or a translation read -- this block cannot
  // and does not distinguish them; §1 lists the causes)
  input  logic                          req_fire,
  input  logic                          req_is_read,
  input  logic [ADDR_W-1:0]             req_addr,
  input  logic [15:0]                   req_bytes,

  // ---- a request completing
  input  logic                          done_fire,

  // ---- bytes the requester actually consumed, where a platform can
  // report it; tie to zero when unavailable and read the ratio as
  // unavailable rather than as zero.
  input  logic                          used_valid,
  input  logic [15:0]                   used_bytes,

  input  logic                          clear,

  // ---- published
  output logic [$clog2(MAX_OUT+1)-1:0]  outstanding,
  output logic [$clog2(MAX_OUT+1)-1:0]  outstanding_max,
  output logic [ACC_W-1:0]              conc_sum,      // sum of outstanding
  output logic [ACC_W-1:0]              window_cycles,
  output logic [31:0]                   reqs_read,
  output logic [31:0]                   reqs_write,
  output logic [31:0]                   stride_regular,
  output logic [31:0]                   stride_irregular,
  output logic [ACC_W-1:0]              bytes_delivered,
  output logic [ACC_W-1:0]              bytes_used,
  output logic                          used_ever_reported,
  output logic                          overflow_seen
);
  initial begin
    if (MAX_OUT  < 2) $fatal(1, "cpu_traffic_characteriser: MAX_OUT must be >= 2 (got %0d)", MAX_OUT);
    if (ADDR_W   < 8) $fatal(1, "cpu_traffic_characteriser: ADDR_W must be >= 8");
    if (LINE_LOG < 1 || LINE_LOG >= ADDR_W)
      $fatal(1, "cpu_traffic_characteriser: LINE_LOG must be in 1..ADDR_W-1");
    // The accumulator must hold MAX_OUT per cycle for a useful window.
    // Too narrow and conc_sum saturates early, making the time-average
    // silently wrong rather than loudly wrong.
    if (ACC_W < $clog2(MAX_OUT+1) + 16)
      $fatal(1, "cpu_traffic_characteriser: ACC_W too narrow for a useful window");
  end

  logic [ADDR_W-1:0] prev_addr;
  logic [ADDR_W-1:0] prev_delta;
  logic              have_prev, have_delta;

  logic [ADDR_W-1:0] this_delta;
  always_comb begin
    // Unsigned difference in line units. A descending stream produces
    // a large value rather than a negative one, which is fine: the
    // test is whether the delta REPEATS, not its sign.
    this_delta = (req_addr >> LINE_LOG) - (prev_addr >> LINE_LOG);
  end

  always_ff @(posedge clk) begin
    if (!rst_n || clear) begin
      outstanding        <= '0;
      outstanding_max    <= '0;
      conc_sum           <= '0;
      window_cycles      <= '0;
      reqs_read          <= '0;
      reqs_write         <= '0;
      stride_regular     <= '0;
      stride_irregular   <= '0;
      bytes_delivered    <= '0;
      bytes_used         <= '0;
      used_ever_reported <= 1'b0;
      prev_addr          <= '0;
      prev_delta         <= '0;
      have_prev          <= 1'b0;
      have_delta         <= 1'b0;
      overflow_seen      <= 1'b0;
    end else begin
      if (window_cycles != {ACC_W{1'b1}}) window_cycles <= window_cycles + 1'b1;

      // The time-average's numerator. Accumulated BEFORE this cycle's
      // arrivals and departures are applied, so it integrates the
      // occupancy that actually held during the cycle.
      if (conc_sum <= {ACC_W{1'b1}} - MAX_OUT)
        conc_sum <= conc_sum + {{(ACC_W-$clog2(MAX_OUT+1)){1'b0}}, outstanding};
      else
        overflow_seen <= 1'b1;   // §12: say so rather than wrap silently

      // ---- outstanding, with simultaneous arrive/complete handled.
      // Both in one cycle leaves the count unchanged, which is correct
      // and is the case a naive if/else-if gets wrong by dropping one.
      if (req_fire && !done_fire) begin
        if (outstanding != MAX_OUT[$clog2(MAX_OUT+1)-1:0])
          outstanding <= outstanding + 1'b1;
        else
          overflow_seen <= 1'b1;
      end else if (done_fire && !req_fire) begin
        if (outstanding != '0) outstanding <= outstanding - 1'b1;
        else overflow_seen <= 1'b1;   // completion with nothing outstanding
      end

      if (outstanding > outstanding_max) outstanding_max <= outstanding;

      if (req_fire) begin
        if (req_is_read) begin
          if (reqs_read  != 32'hFFFF_FFFF) reqs_read  <= reqs_read  + 1'b1;
        end else begin
          if (reqs_write != 32'hFFFF_FFFF) reqs_write <= reqs_write + 1'b1;
        end

        if (bytes_delivered <= {ACC_W{1'b1}} - 16'hFFFF)
          bytes_delivered <= bytes_delivered + {{(ACC_W-16){1'b0}}, req_bytes};

        // ---- stride regularity. Needs TWO previous requests: one to
        // form a delta, and a delta to compare against. Counting
        // before that would classify the first two requests on no
        // evidence, which §5's scenario A would then look regular in.
        if (have_prev && have_delta) begin
          if (this_delta == prev_delta) begin
            if (stride_regular != 32'hFFFF_FFFF) stride_regular <= stride_regular + 1'b1;
          end else begin
            if (stride_irregular != 32'hFFFF_FFFF) stride_irregular <= stride_irregular + 1'b1;
          end
        end
        if (have_prev) begin
          prev_delta <= this_delta;
          have_delta <= 1'b1;
        end
        prev_addr <= req_addr;
        have_prev <= 1'b1;
      end

      // §10's ratio. used_ever_reported distinguishes "the platform
      // does not report this" from "the program used zero bytes",
      // which a zero accumulator alone cannot.
      if (used_valid) begin
        used_ever_reported <= 1'b1;
        if (bytes_used <= {ACC_W{1'b1}} - 16'hFFFF)
          bytes_used <= bytes_used + {{(ACC_W-16){1'b0}}, used_bytes};
      end
    end
  end
endmodule

// Bound to §12's characteriser. Every property carries
// `disable iff (!rst_n)`, and every antecedent is covered below.
//
// NOTE: every property here constrains COUNTING. None of them says
// anything about a cache, a program, or a workload -- the block
// observes requests and cannot see their cause (§1 lists eight causes
// it cannot distinguish).
module cpu_traffic_sva #(
  parameter int MAX_OUT = 64, parameter int ACC_W = 40
)(
  input logic clk, rst_n, clear,
  input logic req_fire, done_fire, req_is_read, used_valid, used_ever_reported,
  input logic overflow_seen,
  input logic [$clog2(MAX_OUT+1)-1:0] outstanding, outstanding_max,
  input logic [ACC_W-1:0] conc_sum, window_cycles, bytes_delivered, bytes_used,
  input logic [31:0] reqs_read, reqs_write, stride_regular, stride_irregular
);
  // ---- P1. INVARIANT. Outstanding never exceeds the observed
  // capacity. The counter is sized for MAX_OUT+1 values -- COUNT
  // versus INDEX -- so this cannot wrap silently.
  property p_outstanding_bounded;
    @(posedge clk) disable iff (!rst_n)
      (outstanding <= MAX_OUT);
  endproperty
  assert property (p_outstanding_bounded)
    else $error("characteriser: outstanding %0d exceeds MAX_OUT", outstanding);

  // ---- P2. FORBIDDEN. Simultaneous arrival and completion leaves the
  // count unchanged. §12: a naive if/else-if drops one, and under a
  // saturated stream this is the common case.
  property p_simultaneous_is_neutral;
    @(posedge clk) disable iff (!rst_n)
      (req_fire && done_fire) |=> (outstanding == $past(outstanding));
  endproperty
  assert property (p_simultaneous_is_neutral)
    else $error("characteriser: simultaneous arrive/complete changed the count");

  // ---- P3. An arrival alone increments.
  property p_arrival_increments;
    @(posedge clk) disable iff (!rst_n)
      (req_fire && !done_fire && outstanding != MAX_OUT)
        |=> (outstanding == $past(outstanding) + 1);
  endproperty
  assert property (p_arrival_increments)
    else $error("characteriser: an arrival did not increment");

  // ---- P4. A completion alone decrements.
  property p_completion_decrements;
    @(posedge clk) disable iff (!rst_n)
      (done_fire && !req_fire && outstanding != 0)
        |=> (outstanding == $past(outstanding) - 1);
  endproperty
  assert property (p_completion_decrements)
    else $error("characteriser: a completion did not decrement");

  // ---- P5. FORBIDDEN. A completion with nothing outstanding is
  // recorded as an overflow, never silently ignored: it means a
  // response exists for a request this block never saw.
  property p_underflow_is_recorded;
    @(posedge clk) disable iff (!rst_n)
      (done_fire && !req_fire && outstanding == 0) |=> overflow_seen;
  endproperty
  assert property (p_underflow_is_recorded)
    else $error("characteriser: underflow not recorded");

  // ---- P6. INVARIANT. The high-water mark bounds the live count and
  // never falls -- it is the context for the time-average.
  property p_max_bounds_and_monotone;
    @(posedge clk) disable iff (!rst_n)
      (outstanding_max >= outstanding) || (outstanding == 0);
  endproperty
  assert property (p_max_bounds_and_monotone)
    else $error("characteriser: max understates outstanding");

  // ---- P7. INVARIANT. conc_sum never exceeds MAX_OUT per cycle of
  // window. A time-average above the capacity would be arithmetically
  // impossible and means the two accumulate on different events.
  property p_average_is_feasible;
    @(posedge clk) disable iff (!rst_n)
      (conc_sum <= window_cycles * MAX_OUT) || overflow_seen;
  endproperty
  assert property (p_average_is_feasible)
    else $error("characteriser: concurrency sum exceeds the feasible maximum");

  // ---- P8. PARTITION. Reads plus writes account for every request.
  // §3's inversion means the mix matters, and a request in neither
  // bucket means the direction was never captured.
  property p_direction_partition;
    @(posedge clk) disable iff (!rst_n)
      ((reqs_read + reqs_write) <= 32'hFFFF_FFFF);
  endproperty
  assert property (p_direction_partition)
    else $error("characteriser: direction counters overflowed");

  property p_request_counted_once;
    @(posedge clk) disable iff (!rst_n)
      (req_fire && req_is_read) |=> (reqs_read == $past(reqs_read) + 1);
  endproperty
  assert property (p_request_counted_once)
    else $error("characteriser: a read request was not counted exactly once");

  // ---- P9. FORBIDDEN. Stride classification requires two prior
  // requests. §12: classifying earlier would score the first
  // comparison on no evidence, and a false "regular" would mislabel
  // the pointer-chasing scenario this block exists to identify.
  property p_no_stride_before_two;
    @(posedge clk) disable iff (!rst_n)
      ((reqs_read + reqs_write) < 32'd2)
        |-> ((stride_regular + stride_irregular) == 32'd0);
  endproperty
  assert property (p_no_stride_before_two)
    else $error("characteriser: classified a stride with fewer than two requests");

  // ---- P10. INVARIANT. Stride classifications never exceed requests.
  property p_strides_le_requests;
    @(posedge clk) disable iff (!rst_n)
      ((stride_regular + stride_irregular) <= (reqs_read + reqs_write));
  endproperty
  assert property (p_strides_le_requests)
    else $error("characteriser: more stride classifications than requests");

  // ---- P11. FORBIDDEN. Bytes used never exceed bytes delivered. §10's
  // ratio is an efficiency and a value above 1 would mean the
  // requester consumed data DRAM never sent.
  property p_efficiency_at_most_one;
    @(posedge clk) disable iff (!rst_n)
      used_ever_reported |-> (bytes_used <= bytes_delivered);
  endproperty
  assert property (p_efficiency_at_most_one)
    else $error("characteriser: bytes_used %0d exceeds bytes_delivered %0d",
                bytes_used, bytes_delivered);

  // ---- P12. FORBIDDEN. The used-reported flag is sticky. §12: a
  // platform that cannot report and a program that used nothing are
  // different facts, and a zero accumulator cannot distinguish them.
  property p_used_flag_sticky;
    @(posedge clk) disable iff (!rst_n)
      (used_ever_reported && !clear) |=> used_ever_reported;
  endproperty
  assert property (p_used_flag_sticky)
    else $error("characteriser: used_ever_reported dropped");

  // ---- P13. FORBIDDEN. Overflow is sticky. A saturated accumulator
  // makes the time-average silently wrong, so the flag must survive.
  property p_overflow_sticky;
    @(posedge clk) disable iff (!rst_n)
      (overflow_seen && !clear) |=> overflow_seen;
  endproperty
  assert property (p_overflow_sticky)
    else $error("characteriser: overflow flag cleared without a clear");

  // ---- antecedent covers.
  cover property (@(posedge clk) disable iff (!rst_n) req_fire);
  cover property (@(posedge clk) disable iff (!rst_n) done_fire);
  cover property (@(posedge clk) disable iff (!rst_n) req_fire && done_fire);
  cover property (@(posedge clk) disable iff (!rst_n) req_fire && req_is_read);
  cover property (@(posedge clk) disable iff (!rst_n) req_fire && !req_is_read);
  cover property (@(posedge clk) disable iff (!rst_n) outstanding == 0);
  cover property (@(posedge clk) disable iff (!rst_n) outstanding == 1);
  cover property (@(posedge clk) disable iff (!rst_n) outstanding == MAX_OUT);
  cover property (@(posedge clk) disable iff (!rst_n) stride_regular != 32'd0);
  cover property (@(posedge clk) disable iff (!rst_n) stride_irregular != 32'd0);
  cover property (@(posedge clk) disable iff (!rst_n) used_valid);
  cover property (@(posedge clk) disable iff (!rst_n) !used_ever_reported);
  cover property (@(posedge clk) disable iff (!rst_n) overflow_seen);
  // P9's antecedent: fewer than two requests seen. Reachable only at
  // the start of a run, so publishing it is what distinguishes "the
  // property held during the early window" from "the window never
  // existed".
  cover property (@(posedge clk) disable iff (!rst_n)
                  (reqs_read + reqs_write) < 32'd2);
  cover property (@(posedge clk) disable iff (!rst_n) clear);
endmodule

// SIMULATION-ONLY. Independent reference. It replays the event stream
// into QUEUES and computes concurrency by INTEGRATING a timeline,
// rather than by an incremental up/down counter -- a different
// formulation, so agreement is evidence.
class traffic_reference;
  int  arrive_cycle[$];
  int  depart_cycle[$];
  int  addrs[$];
  bit  is_read[$];
  int  now;

  function void tick(); now++; endfunction

  function void arrive(int addr, bit rd);
    arrive_cycle.push_back(now);
    addrs.push_back(addr);
    is_read.push_back(rd);
  endfunction

  function void depart(); depart_cycle.push_back(now); endfunction

  // Concurrency by integration: for each cycle, count how many
  // requests had arrived and not yet departed. Deliberately O(n*m) and
  // structurally unlike the DUT's counter.
  function real average_concurrency(int window);
    int total = 0;
    for (int c = 0; c < window; c++) begin
      int live = 0;
      foreach (arrive_cycle[i])
        if (arrive_cycle[i] <= c
            && (i >= depart_cycle.size() || depart_cycle[i] > c)) live++;
      total += live;
    end
    if (window == 0) return -1.0;        // not zero: no window
    return real'(total) / real'(window);
  endfunction

  // Stride regularity by rescanning the address list, needing two
  // prior requests exactly as the DUT does.
  function int regular_count(int line_log);
    int n = 0;
    if (addrs.size() < 3) return 0;
    for (int i = 2; i < addrs.size(); i++) begin
      int d1 = (addrs[i]   >> line_log) - (addrs[i-1] >> line_log);
      int d2 = (addrs[i-1] >> line_log) - (addrs[i-2] >> line_log);
      if (d1 == d2) n++;
    end
    return n;
  endfunction

  function int reads();
    int n = 0; foreach (is_read[i]) if (is_read[i]) n++; return n;
  endfunction

  // §4's model, for comparison against a measured completion time.
  // Returns -1.0 when concurrency is zero, because dividing by it
  // would report an infinite speedup rather than "no data".
  function real predicted_cycles(int misses, int latency, real concurrency);
    if (concurrency <= 0.0) return -1.0;
    return real'(misses) * real'(latency) / concurrency;
  endfunction
endclass

  TWO PASSING TRAFFIC CHARACTERISATIONS

  (A) the characteriser was never exercised
        all 13 properties            PASS
        outstanding / max            0 / 0
        conc_sum                     0
        reqs_read / reqs_write       0 / 0
        stride_regular/irregular     0 / 0
        used_ever_reported           0
        ------------------------------------------------
        cover req_fire               0 hits
        ... all 14 covers            0 hits

        six of thirteen properties are implications and never armed.
        The seven INVARIANTS -- outstanding bound, max bound,
        feasible average, direction partition, strides bounded,
        efficiency, and both sticky flags -- pass on zeros.

        "traffic characterisation: concurrency 0, no irregular
        strides" is produced by this run AND by an idle system.
        window_cycles is the field that separates them.

  (B) two workloads, identical miss counts, opposite bottlenecks
        both streams: 262,144 line-sized reads to the same address set

        POINTER CHASE                    STREAMING
        outstanding_max        1         outstanding_max       16
        avg concurrency      0.98        avg concurrency     14.7
        stride_regular          31       stride_regular   262,080
        stride_irregular   262,081       stride_irregular        62
        reqs_read          262,144       reqs_read        262,144
        reqs_write             118       reqs_write         4,096
        ------------------------------------------------
        all 13 properties      PASS      all 13 properties  PASS
        all 14 covers          HIT       all 14 covers      HIT

        identical read counts. Identical addresses touched. A ~15x
        difference in average concurrency, and therefore -- by §5's
        model -- a ~15x difference in completion time on the same
        hardware.

        and the DDR-visible consequence differs in kind, not degree:
        at concurrency 1 the scheduler has ONE candidate, so 23.4's
        reordering, 16.1's bank parallelism and 23.3's row-hit
        opportunity are all unavailable. The memory system's entire
        optimisation machinery is idle.

    diagnosis : (A) is the vacuity case. (B) is the chapter: the
      bottleneck was set by DEPENDENCY STRUCTURE, not by miss count,
      and no controller tuning changes it.

    the fix : (A) read window_cycles first. (B) nothing in the memory
      system -- the lever is the program's dependency structure, and
      §4 says so.