Module 12: Memory System Organization & Hierarchy

Tags: #◇Computer Science #◇CSARCH2 #◇Computer Architecture #◇Hardware Modeling #◇Memory System Organization & Hierarchy

◇Overview

The performance of modern computing systems is fundamentally bounded by the Memory Wall—the widening latency gap between high-speed CPU execution units and high-capacity storage subsystems. Because no single semiconductor technology can simultaneously achieve picosecond access times, terabyte capacities, non-volatility, and low unit cost, computer architects construct a tiered Memory Hierarchy. This module analyzes the physical properties of modern memory technologies (SRAM, DRAM, SDRAM/DDR, Flash), formalizes the Principle of Locality (Temporal and Spatial), and establishes the quantitative trade-offs governing memory access latency, bandwidth, capacity, and cost per bit.

◇Key Definitions

• Memory Hierarchy: A tiered architectural arrangement of storage technologies organized such that levels closest to the CPU offer the fastest access speeds and smallest capacities, while lower levels provide progressively larger capacities at lower costs and longer latencies.
• Static RAM (SRAM): A volatile memory technology that stores each bit using a 6-transistor (6T) cross-coupled bistable inverter latch, offering sub-nanosecond access times without requiring periodic refresh cycles.
• Dynamic RAM (DRAM): A volatile memory technology that stores each bit as an electrical charge on a microscopic capacitor paired with an access transistor (1T-1C), requiring periodic read-and-rewrite refresh cycles due to charge leakage.
• Row Address Strobe (RAS) / Column Address Strobe (CAS): Control strobes used in DRAM address multiplexing to latch the row address and column address across shared pin lines in two consecutive steps.
• Double Data Rate (DDR) SDRAM: Synchronous DRAM that transfers data words on both the rising and falling edges of the memory clock bus, doubling effective data bandwidth.
• Temporal Locality: The empirical tendency of a program to access the exact same memory locations repeatedly within a short temporal window (e.g., loop counters, hot code paths, stack frames).
• Spatial Locality: The empirical tendency of a program to access memory locations physically adjacent to recently accessed addresses (e.g., linear array traversals, sequential instruction streams).

◇Theoretical Framework / Core Concepts

1. The Architectural Memory Hierarchy Pyramid

+-------------------------------------------------------------------------+
|                        THE MEMORY HIERARCHY PYRAMID                     |
|                                                                         |
|                     / \                                                 |
|                    /   \        Level 0: CPU Registers                  |
|                   / CPU \       (< 1 ns, 1 - 2 KB, ~$10,000/GB)         |
|                  / Regs  \                                              |
|                 /---------\     Level 1: L1 Cache (On-Chip SRAM)        |
|                /  L1 Cache \    (0.5 - 2 ns, 32 - 128 KB)               |
|               /-------------\   Level 2: L2 Cache (On-Chip SRAM)        |
|              /   L2 Cache    \  (3 - 10 ns, 512 KB - 2 MB)              |
|             /-----------------\ Level 3: L3 Cache (Shared SRAM)         |
|            /     L3 Cache      \ (10 - 25 ns, 16 - 128 MB)              |
|           /---------------------\                                       |
|          /     Main Memory       \ Level 4: Main DRAM (DDR5 SDRAM)      |
|         /     (DDR4 / DDR5)       \ (50 - 100 ns, 16 - 128 GB, ~$3/GB)  |
|        /---------------------------\                                    |
|       /      Secondary Storage      \ Level 5: NVMe SSD / NAND Flash    |
|      /      (NVMe / SATA Flash)      \ (10 - 100 us, 512 GB - 8 TB)     |
|     /---------------------------------\                                 |
|    /         Tertiary Storage          \ Level 6: Magnetic HDD / Tape   |
|   /      (Magnetic Disk, Cloud)         \ (5 - 15 ms, 10 - 100 TB)      |
|  +---------------------------------------+                              |
+-------------------------------------------------------------------------+

Hierarchy Scaling Trends:

Moving from top (Registers) to bottom (Tertiary Disk):

1. Access Latency: Increases exponentially (from $< 1\text{ ns}$ to $10\text{ ms}$, a factor of $10^7$).
2. Storage Capacity: Increases exponentially (from kilobytes to terabytes).
3. Cost per Bit ($\char"24 /\text{bit}$): Decreases by orders of magnitude.
4. Access Frequency by CPU: Decreases sharply due to filtering by upper levels.

2. Physical Memory Technologies Compared

SRAM Cell (6T Bistable Latch):        DRAM Cell (1T-1C Capacitor):
      Vdd       Vdd                                Word Line (Row)
       |         |                                      |
     +---+     +---+                                    v
     | P |     | P |                              +-----------+
     +---+     +---+                              | Transistor|
       |         |                                +-----------+
       +----+----+                                      |
       |    |    |                                      v
     +---+  |  +---+                              +-----------+
BL---| N |  +--| N |---~BL                        | Storage   | (Capacitor C)
     +---+     +---+                              | Capacitor |
       |         |                                +-----------+
      Gnd       Gnd                                     |
                                                       Gnd
- No refresh needed; fast; low density.   - Must refresh; tiny cell; high density.

3. The Principle of Locality

The effectiveness of the memory hierarchy rests on the empirical observation that programs do not access all code and data uniformly:

Memory Address Space
  ^
  |        [ Loop Code Block ]  <--- High Temporal Locality (Instructions executed 10,000x)
  |        +-----------------+
  |        | Inst 1, 2, 3, 4 |
  |        +-----------------+
  |
  |        [ Array Buffer ]     <--- High Spatial Locality (Elements A[0], A[1], A[2] in sequence)
  |        +-----------------+
  |        | A[0]| A[1]| A[2]|
  |        +-----------------+
  +--------------------------------------------------------> Time

1. Temporal Locality (Locality in Time):
   • If an address is accessed at time $t$, it is highly likely to be accessed again at time $t + \Delta t$.
   • Exploited by: Retaining recently accessed data blocks in high-speed upper cache levels.
2. Spatial Locality (Locality in Space):
   • If address $A$ is accessed at time $t$, nearby addresses $A \pm k$ are highly likely to be accessed soon.
   • Exploited by: Fetching multi-word cache blocks (lines) of 32, 64, or 128 contiguous bytes whenever a single word is referenced.

◇Worked Examples / Calculations / Hardware Traces

Example 1: DRAM Refresh Overhead Calculation

Problem: A 16 GiB DDR4 DRAM module contains 65,536 rows per bank across 8 banks. The memory controller must refresh all rows every $64\text{ ms}$ to prevent capacitor charge degradation.

• Each row refresh operation takes $35\text{ ns}$ of busy bus time ($t_{\text{RFC}}$).

Calculate:

1. The total time spent refreshing the DRAM module per $64\text{ ms}$ retention interval.
2. The percentage of total memory availability lost to refresh cycles (the refresh overhead).

Solution:

1. Total Refresh Time per Interval:
   $\text{Total Rows} = 65,536\text{ rows}$
   $\text{Total Refresh Time} = 65,536 \times 35 \times 10^{-9}\text{ s} \approx 0.00229376\text{ seconds} = 2.294\text{ ms}$

2. Refresh Overhead Percentage:
   $\text{Overhead} = \frac{\text{Total Refresh Time}}{\text{Refresh Interval}} \times 100\% = \frac{2.294\text{ ms}}{64.0\text{ ms}} \times 100\% \approx 3.58\%$

Analysis: Refresh cycles consume approximately $3.58\%$ of total memory subsystem bandwidth, during which regular CPU memory read/write requests are queued or stalled.

Example 2: Analyzing Code for Temporal vs Spatial Locality

Problem: Analyze the following matrix processing algorithm in C for spatial and temporal locality on an $N \times N$ integer matrix:

int sum = 0;
for (int j = 0; j < N; j++) {
    for (int i = 0; i < N; i++) {
        sum += matrix[i][j]; // Column-major access
    }
}

Solution:

1. Scalar Variable sum:
   • Temporal Locality: Extremely High. The variable sum is read and updated on every iteration of the inner loop ($N^2$ times).
   • Spatial Locality: N/A (Scalar stored in register).
2. Matrix Array matrix[i][j] (Stored in Row-Major order in C memory):
   • In C, 2D arrays are stored in memory row-by-row: matrix[0][0], matrix[0][1], ..., matrix[0][N-1], matrix[1][0], ...
   • The loop iterates over i in the inner loop: successive memory addresses accessed are separated by $N \times 4\text{ bytes}$ (stride $= N$).
   • Spatial Locality: Extremely Poor. Because stride $= N$, every read misses the current cache block for large $N$.
   • Optimization: Inverting loop nest order (for i outer, for j inner) converts the stride to $+1$ (sequential access), maximizing spatial locality and improving cache hit rate from $< 10\%$ to $> 95\%$.

◇Complexity Analysis / Common Pitfalls

• Row-Major vs Column-Major Memory Traversal: Accessing multi-dimensional arrays along the wrong dimension (stride-$N$ access) causes continuous cache misses because hardware loads contiguous multi-word lines that are never utilized before eviction.
• Volatile vs Non-Volatile Disparities: A common misconception is assuming Flash memory functions identical to DRAM. Flash requires block-level erasure cycles prior to page-level writes, creating an asymmetric write-latency penalty not present in DRAM.
• SRAM Density vs Latency: Attempting to build gigabytes of primary memory out of 6T SRAM cells is physically unviable because 6 transistors per bit consume massive silicon die real estate, driving wafer fabrication costs beyond commercial feasibility.

◇References & Navigation

• Previous Topic: ◇Control Unit Design & Microprogramming
• Next Topic: ◇Cache Memory Principles & Mapping Architectures
• Related Notes: ◇Functional Units & Performance Fundamentals, ◇Cache Replacement Policies & Write Strategies