Memory Interleaving [7M]

Need: CPU is faster than DRAM. Single memory module can serve only one access at a time (access time $t_a \approx 60ns$). Pipelining requests to multiple modules can increase effective bandwidth and hide latency (similar to pipeline).

Definition: Divide main memory into $m$ independent modules/banks that can be accessed in parallel/overlapped. Interleaving defines how consecutive addresses are spread across modules.

1. Types:

• High-order interleaving (Memory banking): MSB selects module.
  Address: | Module (k bits) | Offset (n-k bits) |
  e.g. 4 modules (0-3), addresses 0-255: Module 0 holds 0-63, M1:64-127, M2:128-191, M3:192-255. Consecutive addresses map to same module -> no advantage for sequential access. Useful when program has locality in different segments (code in M0, data in M1).

• Low-order interleaving (true interleaved): LSB selects module.
  Address: | Offset | Module |
  e.g. 4 modules: $Addr$ mapping -> Module = $Addr \mod 4$.
  Module 0: 0,4,8,12... Module1:1,5,9... Sequential addresses map to successive modules.

Low-order is generally called memory interleaving and used for cache line fill and vector access.

Example: 4-way low-order, $t_a=80ns$ , $t_c=40ns$ cycle.

Without interleaving: 4 words sequentially takes $4 \times 80 = 320ns$.
With interleaving: Issue request to M0 at $t=0$, M1 at $t=20ns$, M2 at $40ns$, M3 at $60ns$ (pipelined). M0 returns at $80ns$, M1 at $100ns$... Total $\approx 80+3\times20 = 140ns$ . Effective access time $\approx t_c$ not $t_a$.

2. Address generation:

For $m=2^k$ modules, $k$ bits of address select module. For low-order $k$ LSBs.
Memory controller has $m$ MAR/MDR, can latch $m$ requests.

3. Advantages:

• Higher bandwidth : $m$ times potential.
• Reduced effective access time for sequential / stride-1 and vector operations.
• Avoids bank conflicts : If accesses are uniformly distributed, probability of conflict $\approx 1/m$.
• Essential for cache block transfer (burst mode) and SIMD/vector processors.

4. Disadvantages / Limitations:

• Bank conflict: If successive accesses map to same module before it recovers (e.g. stride = $m$), pipeline stalls. e.g. stride 4 with 4 modules -> all accesses to M0.
• Cost: $m$ sets of decoders, buffers, bus arbitration more complex.
• Not helpful for random access with poor locality.

5. Relation to DRAM banks:
Modern DDR SDRAM internally has 4-16 banks with interleaving. Also C-access interleaving used in supercomputers (e.g. Cray). Need also interleaved cache (non-blocking).

Diagram: CPU Address Bus -> Decoder (LSB->Bank Select) -> Banks 0..m-1 -> Data Bus Multiplexer -> CPU.

Conclusion: Low-order $m$-way interleaving converts memory latency-bound system into bandwidth-bound by overlapping access cycles.