Memory Hierarchy: Caches, RAM, Storage & Speed Tradeoffs

Why Memory Hierarchy Matters

Computers need fast access to data but cheap storage for large datasets. A single memory technology (e.g., only RAM) cannot satisfy both needs:

• Speed: Registers (1–4 cycles) > L1 cache (3–5 cycles) > L2/L3 (10–40 cycles) > RAM (100+ cycles) > SSD (microseconds) > HDD (milliseconds).
• Cost: 1 GB of RAM costs ~$10, while 1 GB of SSD costs ~$0.10. Tradeoffs are inevitable.

classDiagram
    class MemoryHierarchy {
        +Speed ↑ (faster at top)
        +Cost ↓ (cheaper at bottom)
        +Layers: Registers → L1 → L2 → L3 → RAM → SSD → HDD
    }
    class Cache {
        +Types: Direct-Mapped / Associative / Set-Associative
        +Policies: Write-Through / Write-Back
        +Metrics: Hit Rate / Miss Rate / Miss Penalty
    }
    MemoryHierarchy "1" *-- "5" Cache : contains

1. The Memory Hierarchy Layers

The goal: keep frequently used data closer to the CPU to minimize access time.

Key Idea: Higher layers are smaller but faster; lower layers are larger but slower. The CPU uses copy-on-write and prefetching to move data up the hierarchy.

2. How Caches Work: Mapping Strategies

Caches store copies of frequently used RAM blocks. The cache mapping determines where a RAM block can be stored.

A. Direct-Mapped Cache

• Definition: Each RAM block maps to exactly one cache line (determined by block_address % number_of_lines).
• Pros: Simple, fast lookup.
• Cons: Conflict misses (two frequently used blocks map to the same cache line).

Worked Example (Direct-Mapped): Assume a 4-block cache (lines 0–3) and RAM blocks B0, B1, B2, B3, B4.

• Access sequence: B0 → B1 → B2 → B3 → B4 → B0
• Misses: B0, B1, B2, B3, B4 (all first accesses).
• Conflict Miss: When B4 maps to line 0, it evicts B0 (even though B0 is still needed).

B. Fully Associative Cache

• Definition: A RAM block can go anywhere in the cache.
• Pros: No conflict misses; higher hit rate.
• Cons: Slow lookup (requires searching all cache lines).

Worked Example (Fully Associative): Same sequence B0 → B1 → B2 → B3 → B4 → B0:

• All blocks fit in cache (no evictions).
• Hit Rate = 5/6 ≈ 83% (vs. 0% in direct-mapped due to conflict).

C. Set-Associative Cache (Best of Both Worlds)

• Definition: Cache is divided into sets; each block maps to a specific set but can replace any line in that set.
• Example: 4-way set-associative with 4 sets → 16 cache lines (4 lines/set).

Worked Example (Set-Associative): Assume 2-way set-associative cache with 2 sets (4 lines total).

• Access sequence: B0 → B2 → B4 → B6 → B0
• B0 maps to Set 0, B2 to Set 0 → conflict in Set 0.
• Solution: Replace one line in Set 0 (e.g., LRU eviction).

3. Cache Performance Metrics

Worked Example (AMAT Calculation):

• L1 Cache: Hit time = 5 cycles, Miss rate = 5%, Miss penalty = 100 cycles.
• AMAT = 5 + (0.05 × 100) = 10 cycles.

4. Cache Write Policies

When the CPU writes to a cache line, how is the lower-level memory updated?

Worked Example (Write-Back):

1. CPU writes to Cache[0] (value = 10).
2. Cache[0] is modified but RAM is not updated yet (dirty bit = 1).
3. When Cache[0] is evicted, it writes back to RAM (saving time).

5. Cache Coherence (Multi-Core Systems)

In multi-core CPUs, each core has its own cache. How do we ensure all caches have consistent data?

MESI Protocol (Mostly Used)

Example (MESI in Action):

• Core 1 writes to Cache[5] → state M.
• Core 2 reads Cache[5] → Core 1 sends data; Core 2’s cache line becomes S.
• Core 1 modifies Cache[5] again → invalidates Core 2’s S state.

6. Real-World Applications of Memory Hierarchy

A. eSewa (Nepal’s Digital Payment System)

• Problem: Millions of transactions per second → RAM bottlenecks.
• Solution:
  • L1/L2 Caches: Store frequently accessed user profiles (e.g., user_id → balance).
  • SSD Prefetching: Predict next transactions (e.g., if user A pays electricity, prefetch their phone bill data).
  • Write-Back Caches: Reduce RAM write latency for payment logs.

B. Pathao (Ride-Hailing App)

• Problem: Real-time driver-location updates → high I/O load.
• Solution:
  • Multi-Level Caches: L1 for active drivers, L2 for nearby drivers, RAM for all drivers.
  • Set-Associative Mapping: Avoid conflict misses for hotspots (e.g., Thapathali, Lakshmi Path).
  • Write-Through for Safety: Critical updates (e.g., ride cancellations) go to RAM immediately.

C. NEPSE (Nepal Stock Exchange)

• Problem: High-frequency trading → microsecond delays matter.
• Solution:
  • L3 Cache: Stores recent stock prices (e.g., NABIL, NMB, NTC).
  • Prefetching: Predicts next trades based on historical patterns.
  • Non-Uniform Memory Access (NUMA): Distributes data across multiple RAM banks for parallel processing.

7. Exam Tip: How This Unit is Tested

1. Definitions & Comparisons (3–5 marks):
   • Differentiate direct-mapped vs. associative caches.
   • Explain write-through vs. write-back with examples.
2. Calculations (5–10 marks):
   • Given a cache size, block size, and access pattern, calculate hit rate, miss rate, AMAT.
   • Example:

     "A 16 KB, 4-way set-associative cache has 64-byte blocks. If the access sequence is B0, B16, B32, B48, B0, what is the miss rate?"

3. Real-World Scenarios (5 marks):
   • Relate cache optimizations to eSewa, Pathao, or NEPSE.
   • Example:

     "How would you improve the performance of a ride-hailing app’s driver-location system using memory hierarchy?"

4. Diagrams (5 marks):
   • Draw a direct-mapped cache with given mappings.
   • Show a MESI state transition for a write operation.

Common Pitfalls:

• Forgetting to include miss penalty in AMAT calculations.
• Confusing set-associative with fully associative in mapping.
• Ignoring eviction policies (LRU vs. FIFO) in worked examples.

8. Key Formulas to Memorize

9. Worked Example: Cache Simulation

Problem: A direct-mapped cache has 4 lines (0–3). RAM blocks are accessed in this order: B0, B4, B8, B12, B0, B4, B8, B12 Assume blocks map to cache lines as: Bx → line (x mod 4).

Steps:

1. B0 → Miss (load to line 0).
2. B4 → Miss (load to line 0) → evicts B0.
3. B8 → Miss (load to line 0) → evicts B4.
4. B12 → Miss (load to line 0) → evicts B8.
5. B0 → Miss (load to line 0) → evicts B12.
6. B4 → Hit (in line 0).
7. B8 → Hit (in line 0).
8. B12 → Hit (in line 0).

Results:

• Hits: 3 (B4, B8, B12 in steps 6–8).
• Misses: 5.
• Hit Rate: 3/8 = 37.5%.
• Miss Rate: 5/8 = 62.5%.

Improvement: Use 2-way set-associative to reduce conflict misses.

10. Visual Summary: Memory Hierarchy in Action

flowchart LR
    subgraph CPU["CPU Core"]
        L1["L1 Cache\n(3-5 cycles)"] -->|"Hit"| CPU
        L1 -->|"Miss"| L2["L2 Cache\n(10-40 cycles)"]
        L2 -->|"Miss"| RAM["Main RAM\n(100+ cycles)"]
        RAM -->|"Miss"| SSD["SSD\n(µs)"]
        SSD -->|"Miss"| HDD["HDD\n(ms)"]
    end
    label "Faster\nAccess" -->> CPU
    label "Slower\nAccess" -->> HDD

11. Real Picture: Inside a Modern CPU Cache

12. Real Picture: SSD vs. HDD Speed

13. Final Checklist for Exams

✅ Can you draw a direct-mapped cache with given mappings? ✅ Can you calculate AMAT given hit/miss rates and penalties? ✅ Can you explain MESI states for cache coherence? ✅ Can you compare write-through vs. write-back with pros/cons? ✅ Can you relate memory hierarchy to eSewa/Pathao/NEPSE?