Spatial Locality

Chapter 18.2 §3 established the rule that makes mapping outcomes predictable: a stream exercises exactly the fields whose bit positions its varying address bits overlap. It also left a case unresolved — a 16 KiB stride that collapsed to a single bank under both field orders, because its varying bits touched no middle field at all.

This chapter is about that failure and what can be done about it.

Spatial locality in a DDR system is not a property of the address stream. It is a property of the stream and the map, and a power-of-two stride can align with the map badly enough to make a sixteen-bank device behave like a one-bank device.

1. A Stride Is a Bit Pattern

A stride of S bytes between consecutive accesses does not vary the address arbitrarily. It varies it in a very specific way, and for powers of two the specificity is extreme.

  EDUCATIONAL CONFIGURATION — Chapter 18.1 §1's map throughout.

  stride       addresses visited          bits that CHANGE across 16 accesses
  ──────       ─────────────────          ───────────────────────────────────
     64 B      0, 0x40, 0x80, ...         bits  6..9    (and carries above)
   1 KiB       0, 0x400, 0x800, ...       bits 10..13
  16 KiB       0, 0x4000, 0x8000, ...     bits 14..17

A stride of 2^k leaves every bit below k permanently zero for an aligned start, and varies bits from k upward. So the stride does not merely choose which fields it exercises — it forbids every field below bit k from ever changing.

That is the whole mechanism, and it explains why aliasing is a power-of-two phenomenon rather than bad luck. A stride of 100 bytes varies low bits irregularly and touches many fields; a stride of 1024 varies bits 10 and up and touches nothing below.

2. Why Powers of Two Are Everywhere

The uncomfortable part is that power-of-two strides are not unusual — they are what disciplined software produces.

A row of a 1024 × 1024 array of 4-byte elements is 4096 bytes. A page-aligned structure is a power of two by construction. A power-of-two-sized record in an array of records gives a power-of-two stride between the same field of consecutive records. Alignment requirements, tiling, and padding to a boundary all push allocation sizes toward powers of two.

So the workload behaviour most likely to alias with a binary field map is also the behaviour that good software engineering practice actively encourages. The two disciplines push in the same direction and collide.

This is worth stating because it reframes the problem. Stride aliasing is not an exotic corner case to be handled if convenient. It is the expected interaction between structured data and a binary address decomposition, and a controller that does nothing about it will meet it.

3. The Failure Trace

Chapter 18.2 §1's stream S3 — a 16 KiB stride — run against both field orders, sixteen accesses, all banks starting closed.

  POLICY B, stride 16 KiB, bank field at PA[9:6]

  #   PA        bank  row  col  prior open   relation   next command
  -   -------   ----  ---  ---  ----------   --------   -----------------
  0   0x00000     0     0    0  closed       CLOSED     ACT -> RD
  1   0x04000     0     1    0  row 0        CONFLICT   PRE -> ACT -> RD
  2   0x08000     0     2    0  row 1        CONFLICT   PRE -> ACT -> RD
  3   0x0C000     0     3    0  row 2        CONFLICT   PRE -> ACT -> RD
  4   0x10000     0     4    0  row 3        CONFLICT   PRE -> ACT -> RD
  5   0x14000     0     5    0  row 4        CONFLICT   PRE -> ACT -> RD
  6   0x18000     0     6    0  row 5        CONFLICT   PRE -> ACT -> RD
  7   0x1C000     0     7    0  row 6        CONFLICT   PRE -> ACT -> RD
  ...
  15  0x3C000     0    15    0  row 14       CONFLICT   PRE -> ACT -> RD

  totals: 0 HIT, 15 CONFLICT, 1 CLOSED    banks touched: 1 of 16
  Policy R on the same stream: identical totals, identical single bank.

Every access is a full row cycle in one bank. Fifteen of sixteen banks are idle for the entire stream.

4. Mixing Bits

The standard response is to stop taking the bank index directly from a contiguous slice, and instead compute it from several address bits combined.

The combining function is almost always exclusive-or, for reasons that are practical rather than deep: XOR is one gate deep, it is its own inverse, and — the property that matters most — it distributes uniformly. If any one of its inputs varies uniformly, the output varies uniformly, regardless of what the other inputs do.

Written for this configuration, taking Policy B's bank field and mixing the column field into it:

  EDUCATIONAL HASH — not a vendor mapping, not a standard.

    plain     bank_sel = PA[9:6]

    H1        bank_sel = PA[9:6] ^ PA[13:10]
    H2        bank_sel = PA[9:6] ^ PA[17:14]
    H3        bank_sel = PA[9:6] ^ PA[13:10] ^ PA[17:14]

  In each case bank_sel is four bits: two select the bank group and
  two the bank within it, exactly as the plain field did. The hash
  changes WHICH bank an address lands in, and nothing else about the
  device, the commands, or the timing rules.

This is a real technique and not an invention for teaching: published reverse-engineering work has recovered bank-selection functions from commodity processors and found them to be XORs of physical-address bits, recovered by linear algebra over GF(2) — Chapter 18.4 §4 treats that evidence and its status carefully.

5. What Each Hash Actually Fixes

Sixteen accesses per stream, counting distinct banks touched. Every figure below is computed from the definitions in §4 and the map in 18.1 §1.

Read the H1 and H2 rows against each other, because together they state the rule.

H1 repairs S2 and does nothing for S3. It mixes in PA[13:10], and a 1 KiB stride varies exactly those bits — so the hash output varies. A 16 KiB stride leaves PA[13:10] at zero, so PA[9:6] ^ 0 is still a constant, and the collapse is untouched.

H2 is the exact mirror. It mixes in PA[17:14], which a 16 KiB stride varies and a 1 KiB stride does not.

6. Does the Hash Lose Information?

A reasonable objection: the plain selector reads four address bits and uses them as the bank index. H1 reads eight and produces four. Has it thrown half of them away?

No — and the reason is precise. The four bits PA[13:10] that H1 mixes in are also Policy B's column field, and the column field is still decoded and still emitted. So the complete decode retains both quantities:

  decoded:   row      = PA[21:14]
             column   = PA[13:10]           <- retained, unchanged
             bank_sel = PA[9:6] ^ PA[13:10] <- the hash
             offset   = PA[5:0]

  recover:   PA[9:6]  = bank_sel ^ column

XOR is its own inverse, so mixing in a value that is independently retained elsewhere in the decode is fully reversible. The original bank field comes back by XOR-ing the hash with the column, and from there the whole address reconstructs exactly as Chapter 8.6 §2's round trip requires.

This gives the design rule, and it is the one that separates a sound hash from a broken one:

Every bit a hash consumes must be recoverable from the decoded output — either because it is retained as another field, or because the transform is invertible on its own.

H1, H2 and H3 all satisfy it: each mixes in bits that survive as the column field, the row field, or both.

7. The Hash Path

8. The Hashed Selector

// ─────────────────────────────────────────────────────────────────────
// bank_xor_hash
//
// CLASSIFICATION
//   Synthesizable educational RTL. Purely combinational. One
//   responsibility: produce a bank-selection index by XOR-mixing a
//   contiguous bank slice with other retained address fields, and
//   publish the recovery that proves nothing was lost.
//
// WHAT IT DOES NOT MODEL
//   - Not a mapper. Chapter 8.6's sys_addr_mapper produces the fields;
//     this block transforms ONE of them and leaves the rest alone.
//   - No row, column or offset decode, and it does not narrow any
//     field. §6: a hash READS bits, it must never CONSUME them.
//   - No bank state, no classification, no timing, no scheduling.
//   - No claim of optimality. §5 shows every configuration here is
//     defeated by some stride; the parameter exists so that claim can
//     be tested rather than asserted.
//   - Not a vendor mapping. Real recovered functions are XORs of
//     address bits (18.4 §3), but this is not any particular one.
// ─────────────────────────────────────────────────────────────────────
module bank_xor_hash #(
  // Width of the bank-selection index: bank group bits plus bank bits.
  parameter int SEL_W = 4,
  // Which sources are mixed in. Both zero reduces the block to a plain
  // pass-through, which is the control case §5's first row measures.
  parameter bit MIX_COLUMN = 1'b1,
  parameter bit MIX_ROW    = 1'b0
) (
  // ── The plain bank slice, and the fields mixed into it. Each source
  //    is presented already aligned to SEL_W bits by the caller; the
  //    row field is wider than SEL_W in general, so the caller passes
  //    its low SEL_W bits and that choice is visible at the boundary
  //    rather than hidden inside this module.
  input  logic [SEL_W-1:0] bank_slice,
  input  logic [SEL_W-1:0] column_low,
  input  logic [SEL_W-1:0] row_low,

  // ── The selection index actually used to address the device.
  output logic [SEL_W-1:0] bank_sel,

  // ── The recovery, published as hardware rather than described in a
  //    comment. A consumer that needs the original slice takes it from
  //    here; §9's P2 asserts it equals bank_slice, which is what makes
  //    the losslessness claim checkable instead of merely stated.
  output logic [SEL_W-1:0] bank_slice_recovered,

  // ── True when no source is mixed: the block is a pass-through and
  //    the caller should expect plain-selector behaviour.
  output logic             hash_disabled
);

  // ── A zero-width selection index has no meaning and would make every
  //    signal here illegal.
  if (SEL_W < 1) $fatal(1, "bank_xor_hash: SEL_W must be >= 1");

  // ── The mixing term. Built once and used for both the forward
  //    transform and the recovery, so the two CANNOT disagree: if the
  //    forward path changes, the recovery changes with it. Writing the
  //    recovery as an independent expression would let them drift, and
  //    P2 would then be proving that two copies of the same bug agree.
  logic [SEL_W-1:0] mix;
  always_comb begin
    mix = '0;
    if (MIX_COLUMN) mix = mix ^ column_low;
    if (MIX_ROW)    mix = mix ^ row_low;
  end

  assign hash_disabled = !(MIX_COLUMN || MIX_ROW);

  // ── Forward: the transform. XOR is its own inverse, which is the
  //    entire reason this is reversible at all (§6).
  assign bank_sel = bank_slice ^ mix;

  // ── Reverse: apply the same term again. Because the mixed-in fields
  //    are RETAINED in the decode, the caller can always supply them,
  //    and this recovers the original slice exactly.
  assign bank_slice_recovered = bank_sel ^ mix;

endmodule

Example. With SEL_W = 4, MIX_COLUMN = 1, MIX_ROW = 0 and address 0x01400: the bank slice PA[9:6] is 0x0, the column PA[13:10] is 0x5, so bank_sel = 0x0 ^ 0x5 = 0x5 — bank group 1, bank 1. The plain selector would have produced 0x0, bank group 0, bank 0, which is where the other fifteen accesses of stream S2 also landed. Recovery gives 0x5 ^ 0x5 = 0x0, the original slice.

Synthesis. SEL_W two-input XOR gates per enabled source — for a four-bit index with one source, four gates, one level deep. This is the cheapest structural change available to a memory controller and one of the most consequential, which is the reason it is a standard technique. It adds one gate delay to the address-decode path, which sits well before Chapter 17.1 §14's critical scheduling path and is not a frequency concern.

Extension path. Real selectors often mix more than one bit into each output bit and use different source sets per output. The structure generalises directly: each output bit is an XOR reduction over a chosen subset, which is a matrix over GF(2) — and §9's P2 generalises with it, provided the matrix remains invertible.

9. What the Assertions Prove

These are combinational; the block has no clock. They belong in a testbench or bind unit sampled on the environment's clock, as in Chapter 16.2 §10.

// ── P1. Determinism. The same inputs must always give the same index.
//    Trivial against this RTL and a genuine regression anchor: a hash
//    that acquired state would break every reconstruction downstream.
property p_hash_deterministic;
  @(posedge clk) disable iff (!rst_n)
    ($stable(bank_slice) && $stable(column_low) && $stable(row_low))
      |-> $stable(bank_sel);
endproperty
a_hash_deterministic: assert property (p_hash_deterministic);

// ── P2. THE property. Recovery returns the original slice, which is
//    §6's losslessness claim made checkable. If this fails, address
//    bits have been consumed rather than read, and the decode is
//    many-to-one -- data corruption, not a performance bug.
property p_recovery_exact;
  @(posedge clk) disable iff (!rst_n)
    bank_slice_recovered == bank_slice;
endproperty
a_recovery_exact: assert property (p_recovery_exact);

// ── P3. Injectivity at the boundary, stated the way it is actually
//    checkable: two addresses that share every retained field and
//    differ only in the bank slice must produce DIFFERENT indices.
//    This is what forbids §6's broken narrowed-column variant.
property p_distinct_slices_distinct_sel;
  @(posedge clk) disable iff (!rst_n)
    (probe_valid && probe_column_a == probe_column_b
                 && probe_row_a    == probe_row_b
                 && probe_slice_a  != probe_slice_b)
      |-> (probe_sel_a != probe_sel_b);
endproperty
a_distinct_slices_distinct_sel: assert property (p_distinct_slices_distinct_sel);

// ── P4. The disabled configuration really is a pass-through, so §5's
//    control row measures what it claims to.
property p_disabled_is_passthrough;
  @(posedge clk) disable iff (!rst_n)
    hash_disabled |-> (bank_sel == bank_slice);
endproperty
a_disabled_is_passthrough: assert property (p_disabled_is_passthrough);

// ── Covers. P3 fires only on a probe pair with that exact shape; a
//    random testbench essentially never produces one, so without
//    directed stimulus it passes having checked nothing.
c_slice_pair_probed: cover property
  (@(posedge clk) disable iff (!rst_n)
     probe_valid && probe_column_a == probe_column_b
                 && probe_slice_a  != probe_slice_b);
c_hash_changed_bank: cover property
  (@(posedge clk) disable iff (!rst_n) bank_sel != bank_slice);
c_hash_identity:     cover property
  (@(posedge clk) disable iff (!rst_n) !hash_disabled && bank_sel == bank_slice);

What they prove. That the transform is deterministic, that it preserves the information it reads, and that it cannot map two otherwise-identical addresses onto one bank index.

What they do not prove — and this is the important half. Nothing here says the hash distributes anything. P1 through P4 pass identically on H1, H2, H3 and on the disabled pass-through, including on every collapsed row of §5's table. Correctness and distribution are orthogonal properties, and only the first is assertable: distribution is a statistical property of a stream, which is why it is measured by 18.2's profile rather than asserted here.

c_hash_identity is the subtle cover: an enabled hash whose output happens to equal its input, which occurs whenever the mixed fields XOR to zero. It must be reachable — if it is not, the stimulus has never produced the aligned case, and the aligned case is precisely where §5's collapses live.

10. DV — Measuring Distribution, Not Just Correctness

Verification here splits cleanly into two activities that need different tools, and conflating them is the most common mistake.

Correctness is assertable and belongs with the properties above, plus a reference model. Build the reference from the algebra — mask, shift, XOR — rather than from the RTL's signal names, and check recovery over a swept address space rather than a random sample, because the interesting cases are aligned ones that randomness under-samples.

Distribution is not assertable and needs measurement. Drive a stride sweep through the hash into 18.2's mapping_stream_profile and record banks_touched_count for each stride. The output is §5's table, generated rather than asserted:

  STRIDE SWEEP — banks touched in 16 accesses, SEL_W = 4
    stride        plain   H1     H2     H3
    ───────────   ─────   ────   ────   ────
    64 B  (2^6)    16      16     16     16
    1 KiB (2^10)    1      16      1     16
    16 KiB(2^14)    1       1     16     16
    64 KiB(2^16)    1       4      4      4     <- partial, easy to miss
    256 KiB(2^18)   1       1      1      1     <- H3 defeated

    verdict : H3 distributes the widest range of strides tested and is
              defeated by 2^18. No configuration tested distributes
              every stride, and none can: the hash reads a bounded
              set of bits.
    caution : these are distribution counts on 16-access streams, not
              performance results. Module 23 owns performance.

The 2^16 row is the one to design the report around. A total collapse shows up as 1 and nobody misses it. A partial collapse shows up as 4 — plausible-looking, unremarkable on a dashboard, and a 75 % reduction in available bank parallelism. A sweep that only tests strides expected to be good will never produce that row.

  HASH RECOVERY FAILURE
    configuration : MIX_COLUMN=1, but the column field narrowed to the
                    two bits PA[11:10]; PA[13:12] is read by the hash
                    and retained NOWHERE.

    probe A       : 0x00100   PA[9:6]=0x4  PA[13:10]=0x0
                              sel=0x4  column(2b)=0x0  row=0  off=0
    probe B       : 0x01000   PA[9:6]=0x0  PA[13:10]=0x4
                              sel=0x4  column(2b)=0x0  row=0  off=0

    A xor B       : 0x01100   -- they differ in PA bits 12 and 8
    decoded       : row, sel, column, offset ALL EQUAL
    classification: MANY-TO-ONE DECODE. Two distinct physical
                    addresses select one DRAM location; a write to
                    one silently destroys the other. Data corruption,
                    not a performance defect.

    recovery on A : sel ^ column = 0x4 ^ 0x0 = 0x4, true slice 0x4
                    -> AGREES. P2 does not fire on A.
    recovery on B : sel ^ column = 0x4 ^ 0x0 = 0x4, true slice 0x0
                    -> MISMATCH. P2 fires here.

    first bad field : bank_slice_recovered, on probe B
    caught by       : P2 (recovery) on B; P3 (injectivity) on the pair
    NOT caught by   : any distribution measurement. Both addresses land
                      in bank_sel 0x4, which a stride sweep reports as
                      a perfectly ordinary, well-distributed bank.

Note which probe fires. Recovery agrees on A and fails on B, because A's mixed field happens to be zero and the XOR is the identity there. A checker that sampled only A would report the configuration healthy. That is the argument for sweeping the hashed field rather than sampling it — the aligned cases where the transform is an identity are exactly the ones that hide the defect.

The final two lines are the reason both activities are needed. A distribution sweep would have reported this configuration as healthy.

11. Corner Cases

The identity row earns its cover (c_hash_identity) for a non-obvious reason: an enabled hash producing bank_sel == bank_slice looks like a bug and is not. Suppressing or flagging it would hide exactly the aligned cases where §5's collapses live.

12. Debugging

Symptom: one bank, many conflicts, and everything downstream looks correct. §3. Confirm with 18.2's banks_touched_mask; then XOR consecutive addresses in the stream to find the varying bits; then compare against the bank selector's source bits. If they do not overlap, the diagnosis is complete and the fix is at the mapping layer.

Symptom: distribution improved but is still poor. Partial overlap — §5's 2^16 row. Count the distinct banks reached: a power-of-two fraction of the bank count points straight at a partial-overlap case, and the exponent tells you how many source bits are varying.

Symptom: the hash was enabled and nothing changed. Two candidates, distinguished by one reading. Either the mixed field is constant across this stream — check whether the source bits vary at all — or MIX_COLUMN and MIX_ROW are both zero and the block is a pass-through, which hash_disabled reports directly.

Symptom: intermittent data corruption after a mapping change. Stop measuring distribution and check recovery. §6's narrowed-field error produces exactly this, and it is invisible to every distribution metric. Run the swept recovery check; P2 and P3 are the properties that fire.

Symptom: the reference model agrees with a broken hash. The checker was written by copying the RTL's expression. Rewrite it from the algebra in §4, and prefer a different formulation — masks and shifts against part-selects — so a transcription error cannot be duplicated. Chapter 8.6 §8 established this rule; hashing makes it sharper, because an XOR is short enough to copy without noticing.

13. Misconceptions

“XOR mapping loses address information.” §6 — XOR is its own inverse, and mixing in a retained field is fully reversible. Clue: an objection raised without checking whether the mixed field is still emitted.

“XOR mapping is always reversible.” The opposite error. It is reversible only if every consumed bit is recoverable; §6's narrowed-column variant is a genuine many-to-one decode. Clue: a field-width sum that no longer covers the address.

“Hashing is always better than a direct slice.” §5 — every configuration tested is defeated by some stride, and a hash can move a collapse from an unlikely stride to a likely one. Clue: a hash adopted with no stride sweep.

“A wider hash eliminates aliasing.” It raises the stride at which collapse returns. The address is finite; the hash reads a bounded subset; a defeating stride always exists. Clue: "we hash everything, so we're fine."

“Stride aliasing is a rare corner case.” §2 — power-of-two strides are what aligned, tiled, padded data structures produce. Clue: a validation plan with only sequential and random streams.

“If the hash is correct the mapping is good.” §9 — correctness and distribution are orthogonal, and the assertions pass on every collapsed row. Clue: a hash signed off on assertions alone.

“The scheduler can undo a bad mapping.” §3 — with one bank holding all the work there is nothing to reorder. A scheduler chooses among available parallelism; it cannot create it. Clue: a performance problem escalated to the scheduler team with a single-bank profile attached.

“Changing the mapping changes the timing.” tRP, tRCD and tRAS are unchanged in every trace in this chapter. What changed is how many banks the waiting is spread across. Clue: a remapping justified as "reducing tRCD".

“Spatial locality is a software property.” The same stream is well distributed under one map and collapsed under another. Locality at the DRAM is a property of the stream and the map. Clue: a locality analysis with no mapping stated.

14. Interview Reasoning

“A workload with a 16 KiB stride gets terrible bandwidth. Where do you look?” Compare the stride's varying bits against the bank field's bit positions. The strong answer names the overlap check before naming any component.

“Why are power-of-two strides the dangerous ones?” Because 2^k leaves every bit below k constant, so it can miss an entire field. And §2's follow-up: they are also what well-structured software produces.

“Why might a designer XOR address bits into the bank index?” To make the index vary when the plain slice does not. Then the limit: only for strides that vary the mixed bits.

“What new verification problem does hashing introduce?” Reversibility. A plain slice is trivially lossless; a hash is lossless only if every bit it reads survives in the decode. The properties change from "check the slices" to "check recovery and injectivity".

“How do you prove a transform has not lost information?” Recover the original from the decoded output and compare — §6's sel ^ column. Then check injectivity on pairs differing only in the hashed field. Sampling randomly is not sufficient; the aligned cases must be swept.

“Your hash passes every assertion and the workload still uses four banks.” Correctness and distribution are different properties. Run a stride sweep; a power-of-two fraction of the bank count indicates partial overlap between the stride and the hash's source bits.

“Is hashing always the right answer?” No, and saying so with the reason — a bounded source set always has a defeating stride — is the discriminating answer.

15. Exercises

1. Under Policy B with the plain selector, give every stride from 2^6 to 2^14 that sends all sixteen accesses to one bank. Justify from the bit positions.

2. H1 mixes PA[13:10]. Give the smallest stride greater than 64 B that H1 fails to distribute, and prove it from §1's rule.

3. Verify that H2 distributes stream S3 by decoding the first four addresses by hand.

4. §5's 2^16 row shows 4 of 16 banks under H3. Which two of H3's twelve source bits vary at that stride, and why does that give exactly four banks?

5. Construct a hash for this configuration that is not invertible, without narrowing any field. What property must its source selection violate?

6. Write the reference function for H1 using only masks and shifts, with no part-selects. Confirm it agrees with §8's RTL on 0x01400 and 0x03C00.

7. A colleague proposes hashing the row index instead of the bank index to spread conflicts. Describe what this does to row locality, and say which of §9's properties still hold.

8. c_hash_identity covers an enabled hash whose output equals its input. Give an address where H1 does this, and explain why that case matters for §5's collapses.

16. Where This Goes

Three chapters have treated the mapping as something you choose. Chapter 18.1 chose a field order, 18.2 measured what it produced, and this chapter chose a bank-selection function and measured the limits of what it repairs.

On a real system you usually do not get to choose, and frequently you are not even told what was chosen. The mapping is set by a memory controller you did not design, configured by firmware you did not write, and altered by the DIMM population and BIOS settings of the machine in front of you.

Chapter 18.4 is about working in that situation: what vendors actually document, what has to be inferred, what has been recovered by published research, and — the discipline that matters most — how to tell those three apart before betting a design decision on one.