Memory Hierarchy and Cache Architecture

SS2 Term 1 • Week 1

About 45 minutes

In Senior Secondary 1, you learned how the Central Processing Unit executes instructions using the Fetch-Decode-Execute cycle and how the system buses transport electrical signals.

However, an engineering dilemma exists in computer systems design: CPUs operate at billions of cycles per second (Gigahertz), while main memory (DRAM) takes tens of nanoseconds to respond. If the CPU had to wait for main memory on every single memory access, it would spend more than 90% of its operating time idling in empty wait states.

To solve this speed mismatch, computer engineers developed the Memory Hierarchy. In this lesson, we analyze how tiered storage and multi-level caching allow computers to operate at peak speed.

Learning Outcomes

By the end of this lesson, you will be able to:

Map the complete Memory Hierarchy from internal registers to offline optical/tape archives.
Evaluate the performance trade-offs between access latency, cost per megabyte, and physical capacity.
Explain Locality of Reference: Temporal Locality and Spatial Locality.
Trace Cache Operations: Cache Hits, Cache Misses, and Multi-level Cache (L1, L2, L3) topology.

Key Vocabulary

Term	Technical Definition
Memory Hierarchy	A structured organization of storage levels arranged by speed, capacity, and cost to maximize system throughput.
Latency	The time delay between initiating a memory read request and the arrival of the first valid data byte.
SRAM (Static RAM)	High-speed, low-density memory using 6-transistor flip-flops; retains data without periodic electrical refreshing. Used in cache.
DRAM (Dynamic RAM)	High-density, lower-cost memory using 1 transistor and 1 capacitor per bit; requires periodic electrical refreshing. Used in main memory.
Temporal Locality	The behavioral tendency of programs to reuse memory locations that have been recently accessed (e.g., counters in a loop).
Spatial Locality	The tendency of programs to access memory locations physically adjacent to recently accessed locations (e.g., sequential array elements).
Cache Hit / Miss	A hit occurs when requested data is found in cache; a miss occurs when it must be retrieved from slower main memory.

The Memory Pyramid

The memory hierarchy is conventionally visualized as a pyramid. At the narrow apex is the fastest, smallest, and most expensive storage; at the broad base is the slowest, largest, and most affordable storage.

                  ▲  [ FASTEST / SMALLEST / MOST EXPENSIVE ]
                 / \
                /CPU\      Level 0: CPU Registers (64-128 bytes, < 1 ns)
               /-----\
              / Cache \    Level 1-3: SRAM Cache (L1: 64KB, L2: 512KB, L3: 16MB, 1-10 ns)
             /---------\
            / Main Memory\ Level 4: Synchronous DRAM (8GB - 64GB, 50-80 ns)
           /---------------\
          / Secondary Storage\ Level 5: NVMe SSD / Hard Disk (512GB - 4TB, 10-100 μs)
         /---------------------\
        /  Archival / Cloud Cold \ Level 6: Magnetic Tape / Cloud Cold Archive (PBs, ms-min)
       /-------------------------\
       ▼  [ SLOWEST / LARGEST / CHEAPEST PER GIGABYTE ]

Comparative Metrics

CPU Registers: Directly wired to the ALU. Read/write latency is typically 1 clock cycle (~0.3 nanoseconds at 3.5 GHz).
L1 Cache (Split into L1-Instruction and L1-Data): Located inside each CPU core. Operates in 2 to 4 clock cycles (~1 ns).
L2 Cache: Dedicated to each CPU core, slightly larger (512 KB to 1 MB). Latency: 10 to 15 clock cycles.
L3 Cache: Shared across all processor cores on the silicon die (16 MB to 64 MB). Latency: 30 to 50 clock cycles.
Main System Memory (RAM): Placed on external DIMM slots connected via the memory controller bus. Latency: 60 to 100 ns.
Solid-State Drive (SSD): Non-volatile flash NAND accessed via PCIe bus. Latency: 10 to 50 microseconds (10,000 ns).

The Physics of Locality: Why Caching Works

If main RAM is 100 times slower than the CPU, why do modern computers run so quickly? The answer is Locality of Reference. Programs rarely access memory randomly; they exhibit predictable patterns:

1. Temporal Locality (Time)

When a program accesses memory address X, it will likely access X again very soon. Example: A for loop counter int i = 0 is read, incremented, and checked on every iteration of the loop. Storing variable i in L1 cache prevents hundreds of slow trips to RAM.

2. Spatial Locality (Space / Proximity)

When a program accesses memory address X, it will likely access neighboring addresses X+1, X+2, and X+3 next. Example: When iterating through an array or executing instructions in sequential order, CPU prefetchers grab an entire Cache Line (usually 64 continuous bytes) at once rather than fetching individual bytes.

Memory Address: [0x1000] [0x1004] [0x1008] [0x100C] [0x1010] ...
                     ▲
            CPU asks for this single integer...
            Cache controller loads entire 64-byte block into L1!
            Subsequent reads for 0x1004 and 0x1008 are INSTANT CACHE HITS!

Worked Example: Calculating Effective Memory Access Time (EMAT)

Computer engineers measure memory performance using the Effective Memory Access Time (EMAT) formula:

$$\text{EMAT} = (h \times t_c) + ((1 - h) \times (t_c + t_m))$$

Where: - $h$ is the Hit Ratio (percentage of requests found in cache, e.g., $95\% = 0.95$). - $t_c$ is the Cache Access Time (e.g., $2\text{ ns}$). - $t_m$ is the Main Memory Access Time (e.g., $80\text{ ns}$).

Calculation:

Suppose a system has a $95\%$ cache hit rate ($h = 0.95$), cache latency of $2\text{ ns}$, and main memory latency of $80\text{ ns}$:

$$\text{Hit contribution} = 0.95 \times 2\text{ ns} = 1.9\text{ ns}$$

$$\text{Miss contribution} = 0.05 \times (2\text{ ns} + 80\text{ ns}) = 0.05 \times 82\text{ ns} = 4.1\text{ ns}$$

$$\text{EMAT} = 1.9\text{ ns} + 4.1\text{ ns} = 6.0\text{ ns}$$

Insight: Without cache, every access would take $80\text{ ns}$. With a $95\%$ hit rate, the average access time drops to just $6\text{ ns}$—more than 13 times faster!

Practical Activity: Memory Hierarchy Latency Simulation

In this hands-on activity, you will write a small Python benchmarking program to observe the performance difference caused by spatial locality when traversing a multi-dimensional array.

Step 1: Open Your Terminal or Python Editor

Launch a Python 3 interactive session or create cache_test.py.

Step 2: Implement Row-Major vs Column-Major Traversal

import time

SIZE = 3000
# Initialize a 2D matrix (3000 x 3000 integers)
matrix = [[1 for _ in range(SIZE)] for _ in range(SIZE)]

# Test 1: Row-Major Traversal (High Spatial Locality)
start_time = time.perf_counter()
total_row = 0
for row in range(SIZE):
    for col in range(SIZE):
        total_row += matrix[row][col]
row_duration = time.perf_counter() - start_time
print(f"Row-major (sequential) duration: {row_duration:.4f} seconds")

# Test 2: Column-Major Traversal (Low Spatial Locality - Cache Thrashing)
start_time = time.perf_counter()
total_col = 0
for col in range(SIZE):
    for row in range(SIZE):
        total_col += matrix[row][col]
col_duration = time.perf_counter() - start_time
print(f"Column-major (strided) duration:    {col_duration:.4f} seconds")

speedup = col_duration / row_duration
print(f"Sequential access was {speedup:.2f}x faster due to CPU cache hits!")

Step 3: Run the Program

Execute the benchmark in your terminal:

python cache_test.py

Expected Results and Model Output

When you run cache_test.py, your terminal will display timing figures similar to this:

Row-major (sequential) duration: 0.2841 seconds
Column-major (strided) duration:    1.4120 seconds
Sequential access was 4.97x faster due to CPU cache hits!

Analysis:

Both loops perform the exact same number of operations ($3,000 \times 3,000 = 9,000,000$ additions). However, Test 1 walks through contiguous memory addresses, loading complete cache lines with almost 100% hit rates. Test 2 jumps across memory strides of 3,000 elements on every inner iteration, causing frequent cache misses and forcing the CPU to fetch data from system RAM repeatedly!

Common Mistakes to Avoid

Confusing L1/L2 Cache with Browser or Web Cache: CPU cache is hardware SRAM physically fabricated on the silicon die. Web browser cache is software files stored on your hard drive to avoid re-downloading images from the internet.
Believing Larger Cache is Always Better Regardless of Cost: Doubling cache capacity increases the physical silicon area, increases signal propagation latency, and sharply increases power consumption and heat dissipation.
Assuming Cache Miss Penalty is Fixed: Multi-level caches cushion misses: a miss in L1 goes to L2; if L2 has the data, the penalty is tiny compared to going all the way to external RAM.

Notebook Summary

The Memory Hierarchy balances speed, capacity, and manufacturing cost across multiple physical tiers.
Registers and SRAM Caches are fastest and closest to the CPU; DRAM provides main volatile memory; SSDs and Hard Disks provide non-volatile mass storage.
Locality of Reference enables small caches to achieve high hit rates ($>90\%$):
Temporal Locality: Reusing recently accessed data.
Spatial Locality: Accessing adjacent data in contiguous blocks (cache lines).
Effective Memory Access Time (EMAT) determines real-world system instruction execution speed.

Optional Extension Challenge

Research the concept of Cache Coherence in multi-core processors. If Core 1 modifies a variable stored in its private L1 cache, how does Core 2 prevent reading an outdated value from its own private L1 cache? Write a brief 4-sentence paragraph explaining the MESI Protocol (Modified, Exclusive, Shared, Invalid).