Memory Hierarchy, Cache Design & Address Mapping

TAKEAWAYS:

• Memory hierarchy trades off speed, cost, and capacity across registers, cache, RAM, and storage.
• Cache uses spatial and temporal locality to predict and prefetch data the CPU will need next.
• Direct-mapped, fully associative, and set-associative caches balance hit time, miss penalty, and implementation cost.
• Cache mapping schemes determine how physical memory addresses translate into cache lines.
• Cache coherence protocols (like MESI) ensure consistency when multiple cores access shared data.
• Memory bandwidth and latency are critical bottlenecks in modern processor design.

Memory Hierarchy: The Speed-Cost-Capacity Tradeoff

Computers use a memory hierarchy to balance three key factors:

• Speed: How fast data can be accessed (registers are fastest, disk is slowest).
• Cost: Price per byte (registers are most expensive, disk is cheapest).
• Capacity: Total storage available (disk has the most, registers the least).

stateDiagram-v2
    [*] --> Registers: "1-100 bytes, 0.5-2 ns"
    Registers --> L1 Cache: "32-256 KB, 1-4 ns"
    L1 Cache --> L2 Cache: "256 KB-8 MB, 3-10 ns"
    L2 Cache --> L3 Cache: "1-32 MB, 10-50 ns"
    L3 Cache --> Main Memory: "8 GB-128 GB, 50-200 ns"
    Main Memory --> SSD: "128 GB-4 TB, 10-100 µs"
    SSD --> HDD: "1 TB-16 TB, 1-10 ms"
    HDD --> [*]

Why this matters: The CPU spends 90% of its time waiting for memory (Amdahl’s Law). The hierarchy ensures the CPU rarely stalls by keeping frequently used data closer.

Locality Principles

Two key principles explain why caching works:

1. Temporal locality: If a data item is referenced once, it will likely be referenced again soon (e.g., loop variables).
2. Spatial locality: If a data item is referenced, nearby items will likely be referenced soon (e.g., array traversal).

Example: In a loop like for (i=0; i<N; i++) sum += arr[i];, the CPU repeatedly accesses arr[i], arr[i+1], etc. A cache prefetches these sequentially.

Cache Organization: How Data is Stored

Caches store blocks (lines) of data, not individual bytes. A typical cache line is 64 bytes (512 bits). The cache is divided into sets, and each set has ways (number of cache lines per set).

Cache Mapping Schemes

Three main ways to map memory addresses to cache lines:

Example: A 4-way set-associative cache with 1024 sets means:

• Total cache lines = 1024 sets × 4 ways = 4096 lines.
• Cache size = 4096 × 64 bytes = 256 KB.

Address Mapping: How the CPU Finds Data in Cache

The CPU uses the memory address to locate data in cache. The address is split into three parts:

sequenceDiagram
    participant CPU
    participant Cache
    participant RAM
    CPU->>Cache: Access 0x12345678 (Index=0x56, Tag=0x1234)
    Cache-->>CPU: Hit (data found)
    alt Miss
        Cache->>RAM: Fetch block
        RAM-->>Cache: Return block
        Cache-->>CPU: Data
    end

1. Tag: Identifies which memory block is stored in the cache line.
2. Index: Selects the set in the cache.
3. Offset: Selects the byte within the cache line.

Worked Example: Direct-Mapped Cache

Assume:

• Cache size = 16 KB (16 × 1024 bytes).
• Block size = 64 bytes.
• Physical address = 32 bits.

Steps:

1. Calculate number of blocks in cache: $\text{Blocks}=\frac{16\text{ KB}}{64\text{ bytes}}=256\text{ blocks}$.
2. Determine index bits: $\text{Index bits}={\log }_2(256)=8\text{ bits}$.
3. Determine offset bits: $\text{Offset bits}={\log }_2(64)=6\text{ bits}$.
4. Tag bits = Total bits - Index - Offset = 32 - 8 - 6 = 18 bits.

Address breakdown:

Example: For address 0x12345678:

• Index = 0x56 (binary 01010110) → selects cache line 86.
• Tag = 0x1234 (remaining bits).
• Offset = 0x78 → selects byte 120 in the block.

Cache Performance Metrics

Three key metrics define cache performance:

1. Hit Time (t_h): Time to access data if it’s in cache (typically 1-4 ns).
2. Miss Penalty (t_m): Time to fetch data if it’s not in cache (includes accessing RAM and replacing cache line).
3. Miss Rate (m): Fraction of memory accesses that miss the cache (e.g., 5% = 0.05).

Average Memory Access Time (AMAT): $$\text{AMAT}=t_h+m\times t_m$$

Example: For a cache with:

• $t_h=2\text{ ns}$,
• $t_m=100\text{ ns}$,
• $m=0.05$,

$$\text{AMAT}=2+0.05\times 100=7\text{ ns}.$$

Cache Coherence: Handling Multi-Core Systems

When multiple CPU cores access shared data, caches must stay coherent. The MESI protocol (Modified, Exclusive, Shared, Invalid) ensures consistency:

Example: In a dual-core system:

1. Core 1 reads x from RAM → cache line is E.
2. Core 2 reads x → cache line becomes S in both cores.
3. Core 1 writes to x → its cache line becomes M, Core 2’s becomes I.

sequenceDiagram
    Core1->>RAM: Read x (E)
    Core2->>RAM: Read x (S in both)
    Core1->>Core2: Write x (Invalidate Core2's cache)
    Core1->>RAM: Writeback (M->E)

In the Real World

1. WhatsApp (End-to-End Encryption):

   • Uses cache locality to speed up message processing. Frequently accessed user profiles and chat histories are stored in faster memory layers (L1/L2 cache) to reduce latency in real-time messaging.

2. Daraz (E-commerce Order Processing):

   • Database caching (e.g., Redis) stores product catalogs and user sessions in memory to reduce disk I/O. For example, when you view a product, its details are fetched from cache (not disk) to speed up page load.

3. Ncell (Mobile Network Base Stations):

   • Cache memory in base stations stores frequently accessed subscriber data (e.g., call logs, SMS) to reduce latency in voice and data transmission. This is critical for 4G/5G networks where low latency is essential.

Worked Example: Bank Loan Interest Calculation

• A bank’s core system processes thousands of loan interest calculations daily.
• Problem: If loan data is fetched from disk every time, the system would be slow.
• Solution: The bank’s database uses a multi-level cache hierarchy:
  • L1/L2 cache stores active loan records (e.g., recently processed loans).
  • RAM stores all loan data in a structured format.
  • SSD stores historical data.
• Result: Interest calculations complete in milliseconds instead of seconds, improving customer service.

Exam Tip

1. Diagrams are worth 20% of marks: Always draw the memory hierarchy pyramid and cache mapping diagrams in exams. Label all parts (tag, index, offset, sets, ways).
2. Calculate AMAT: Given hit time, miss rate, and miss penalty, always compute AMAT. This is a common 5-mark question.
3. Compare cache schemes: Know when to use direct-mapped (low cost), fully associative (low miss rate), or set-associative (balance).
4. MESI protocol: Expect a short question on cache coherence. Draw the state transitions for a write operation.
5. Real-world applications: Relate cache concepts to databases (e.g., Redis), CPUs (e.g., Intel Core i7), or mobile apps (e.g., WhatsApp). Examiners love practical ties.

Key Formula to Memorize: $$\text{AMAT}=t_h+m\times t_m$$ Key Terms:

• Cache line, block, set, way, hit, miss, miss rate, hit rate, coherence, MESI, direct-mapped, set-associative, fully associative.