Memory Hierarchy & Cache Design: Mapping, Replacement & Performance

TAKEAWAYS:

• Memory hierarchy is a layered design where smaller, faster layers (cache) hide the latency of larger, slower layers (RAM/disk) via locality principles (temporal/spatial).
• Cache mapping determines how main memory blocks map to cache lines: direct mapping is simple but prone to conflicts; associative mapping is flexible but expensive; set-associative offers a middle ground.
• Replacement policies (LRU, FIFO, random) decide which cache line to evict when full, directly impacting hit rates and performance.
• Cache performance is measured by hit time, miss penalty, and hit rate, with the average memory access time (AMAT) formula: $\text{AMAT}=\text{Hit Time}+(\text{Miss Rate}\times \text{Miss Penalty})$.
• Write policies (write-through vs. write-back) trade off consistency for speed, with write-back reducing bus traffic but requiring dirty-bit tracking.
• Real-world systems (e.g., Intel Core i7, ARM Cortex) use multi-level caches (L1/L2/L3) with different associativities and sizes to optimize for different workloads.

1. Why Memory Hierarchy? The Speed-Cost Tradeoff

Computers need fast access to data (e.g., CPU registers) but cannot afford to store all data in fast memory (expensive). The solution: a layered hierarchy where each layer is faster but smaller and more costly than the one below it.

graph TD
    A["CPU Registers\n(~1 cycle, ~KB)"] -->|"Fastest"| B["L1 Cache\n(~3-5 cycles, ~KB-MB)"]
    B --> C["L2 Cache\n(~10-20 cycles, ~MB)"]
    C --> D["L3 Cache\n(~30-50 cycles, ~MB-GB)"]
    D --> E["Main Memory (RAM)\n(~100-300 cycles, ~GB-TB)"]
    E --> F["Secondary Storage (Disk/SSD)\n(~1M+ cycles, ~TB-PB)"]
    F -->|"Slowest"| G["Tertiary Storage (Tape)\n(~10M+ cycles, ~PB-YB)"]

Key Principle: Locality – Programs tend to access the same data repeatedly (temporal locality) or nearby data (spatial locality). The hierarchy exploits this to keep frequently used data in faster layers.

In the Real World

1. WhatsApp (Meta) uses a multi-level cache hierarchy in its servers:

   • L1/L2 caches store frequently accessed message metadata (e.g., chat histories of active users).
   • RAM holds full message payloads for quick retrieval.
   • SSDs store long-term messages, with prefetching (spatial locality) to load related messages before they’re needed.
   • Example: When you open a chat, WhatsApp’s servers cache the last 100 messages in L2 and prefetch the next 50 to reduce disk I/O.

2. eSewa (Nepal Government) processes billions of transactions annually using a write-back cache policy in its database servers:

   • L3 cache holds frequently accessed bill records (e.g., electricity/water bills for a specific ward).
   • Dirty bits track modified cache lines (e.g., a bill payment update), which are written back to RAM only when evicted, reducing disk writes.
   • Example: During peak hours (e.g., 6–8 PM), eSewa’s caches hit rate exceeds 95% due to temporal locality (same users paying bills repeatedly).

3. Daraz (Alibaba Group) uses set-associative caches in its recommendation engine:

   • L1 cache stores user session data (e.g., items viewed in the last 5 minutes).
   • L2 cache holds product catalog metadata (e.g., price, stock) for spatial locality (users often view related products).
   • Example: When you search for a phone, Daraz’s cache preloads accessories (cases, chargers) into nearby cache sets to reduce RAM access.

2. Cache Basics: How It Works

A cache is a small, fast memory layer between the CPU and RAM. It stores copies of frequently used data to reduce average access time.

Key Components of a Cache

1. Cache Lines: Fixed-size blocks (e.g., 64 bytes) transferred between RAM and cache.
2. Tags: Identify which main memory block is stored in a cache line.
3. Index: Determines the cache set (for set-associative caches).
4. Valid Bit: Indicates if the cache line contains valid data.
5. Dirty Bit: (For write-back caches) Marks if the cache line has been modified and needs writing back to RAM.

Cache Mapping: How Data Finds Its Home in Cache

The mapping function determines where a main memory block is placed in the cache. Three main types:

A. Direct Mapping

• Simplest and fastest: Each main memory block maps to exactly one cache line.
• Formula: $$\text{Cache Line}=(\text{Memory Block Number})\mathrm{mod}(\text{Number of Cache Lines})$$
• Problem: Conflict misses occur when two frequently used blocks map to the same cache line.

graph LR
    A["Main Memory\nBlock 0"] -->|"0 mod 8 = 0"| B["Cache Line 0"]
    C["Main Memory\nBlock 8"] -->|"8 mod 8 = 0"| B
    D["Main Memory\nBlock 16"] -->|"16 mod 8 = 0"| B
    E["Main Memory\nBlock 1"] -->|"1 mod 8 = 1"| F["Cache Line 1"]

Example (Direct Mapping Conflict):

• Suppose a cache has 8 lines (index 0–7).
• Block 0 (from RAM) maps to Cache Line 0.
• Later, Block 8 also maps to Cache Line 0 → Block 0 is evicted (even if still needed soon).
• Real-world tie-in: Imagine NTC’s billing system where two popular payment methods (e.g., Khalti and eSewa) keep evicting each other from cache, causing slowdowns.

B. Fully Associative Mapping

• Most flexible: Any main memory block can go into any cache line.
• No conflicts, but slow (requires searching all cache lines for a match).
• Used in small, high-speed caches (e.g., CPU register files).

graph TD
    A["Main Memory\nBlock X"] -->|"Can go anywhere"| B["Cache Line 0"]
    A --> C["Cache Line 1"]
    A --> D["Cache Line 2"]
    A --> E["Cache Line 3"]

Example (Fully Associative Cache):

• Ncell’s customer service chatbot uses a small associative cache to store frequently asked questions (FAQs).
• When a user asks, "How to check my balance?", the system searches all cache lines for a match before checking the database.

C. Set-Associative Mapping

• Compromise: Cache is divided into sets, and each block maps to a specific set but can go into any line within that set.
• Example: A 4-way set-associative cache with 8 sets means each block maps to one of 8 sets, and within that set, it can go into any of 4 lines.

graph TD
    A["Main Memory\nBlock 0"] -->|"Set 0"| B["Set 0"]
    B --> C["Line 0"]
    B --> D["Line 1"]
    B --> E["Line 2"]
    B --> F["Line 3"]
    G["Main Memory\nBlock 8"] -->|"Set 1"| H["Set 1"]

Example (Set-Associative Cache in Banks):

• Global IME Bank’s ATM system uses a 2-way set-associative L2 cache to store:
  • Set 0: Account balances for users A–D.
  • Set 1: Account balances for users E–H.
• If user A and user E access their accounts simultaneously, their data won’t conflict (unlike direct mapping).

Comparison Table: Mapping Techniques

3. Cache Replacement Policies: What to Evict?

When a cache is full and a new block needs to be loaded, a replacement policy decides which block to evict. Common policies:

A. Least Recently Used (LRU)

• Evicts the block not used for the longest time.
• Most effective for temporal locality.
• Implementation: Requires hardware support (e.g., a stack or timestamp for each block).

Example (LRU in Pathao’s Ride-Hailing):

• Pathao’s servers cache driver locations for a specific area.
• If the cache is full and a new driver enters the area, the least recently used driver’s location (e.g., a driver who hasn’t accepted a ride in 10 minutes) is evicted.

B. First-In-First-Out (FIFO)

• Evicts the block that arrived first.
• Simple but suboptimal (doesn’t consider usage patterns).
• Used in older systems where LRU is too costly.

Example (FIFO in NTC’s Network Routers):

• NTC’s routers cache frequent IP routes (e.g., to Kathmandu University).
• If the cache is full, the oldest route entry (even if still heavily used) is replaced.

C. Random Replacement

• Evicts a random block.
• Fast but unpredictable performance.

Example (Random Replacement in YouTube’s CDN):

• YouTube’s content delivery network (CDN) caches video chunks for users in Nepal.
• If a new chunk needs to be loaded, a random cached chunk (e.g., a less popular video segment) is evicted.

Comparison Table: Replacement Policies

4. Write Policies: How to Handle Cache Writes

When the CPU writes to a cached block, the system must decide whether to update the cache, RAM, or both.

A. Write-Through

• Writes to both cache and RAM immediately.
• Pros: Always consistent (no stale data).
• Cons: Slower (extra RAM write), more bus traffic.

Example (Write-Through in Banks):

• When you transfer money via an ATM, the transaction is written to both the ATM’s cache and the bank’s main database immediately.
• Downside: Slower transactions during peak hours (e.g., 10 AM–12 PM).

B. Write-Back (Copy-Back)

• Writes only to cache; RAM is updated only when the block is evicted.
• Pros: Faster, less bus traffic.
• Cons: Risk of data loss if cache is cleared (requires dirty bit).

Example (Write-Back in eSewa):

• When you pay a bill, eSewa’s server marks the cache line as "dirty" and updates RAM only when the block is evicted (e.g., after 10 minutes of inactivity).
• Advantage: Reduces disk I/O by ~70% during high traffic.

Comparison Table: Write Policies

5. Cache Performance Metrics

To evaluate cache effectiveness, we use:

A. Hit Time (t_h)

• Time to access a block if it’s in cache.
• Goal: Minimize $t_h$ (e.g., 1–3 CPU cycles for L1).

B. Miss Rate (MR)

• Fraction of memory accesses that miss the cache.
• Goal: Minimize $MR$ (e.g., L1 hit rate > 95%).

C. Miss Penalty (t_m)

• Time to fetch a block from the next level (e.g., RAM).
• Goal: Reduce $t_m$ (e.g., 100–300 cycles for RAM).

D. Average Memory Access Time (AMAT)

$$\text{AMAT}=t_h+(\text{MR}\times t_m)$$ Example Calculation:

• Suppose:
  • $t_h=2$ cycles (L1 cache hit time).
  • $MR=5\%=0.05$.
  • $t_m=100$ cycles (RAM access time).
• Then: $$\text{AMAT}=2+(0.05\times 100)=2+5=7\text{ cycles}$$

Real-World Example (Intel Core i7):

• L1 Cache: $t_h=1$ cycle, $MR=2\%$, $t_m=10$ cycles (L2). $$\text{AMAT}=1+(0.02\times 10)=1.2\text{ cycles}$$
• L2 Cache: $t_h=4$ cycles, $MR=5\%$, $t_m=100$ cycles (RAM). $$\text{AMAT}=4+(0.05\times 100)=9\text{ cycles}$$

6. Cache Design Tradeoffs

7. Advanced: Multi-Level Caches

Modern CPUs use multiple cache levels to optimize for different workloads:

graph TD
    A["CPU"] --> B["L1 Cache\n(Private, Small, Fast)\n32KB-64KB"]
    A --> C["L2 Cache\n(Private/Shared, Medium, Slower)\n256KB-1MB"]
    A --> D["L3 Cache\n(Shared, Large, Slowest)\n1MB-64MB"]
    B -->|"Miss"| C
    C -->|"Miss"| D
    D -->|"Miss"| E["Main Memory (RAM)"]

Example (Intel Core i7-12700K):

• L1: 32KB (8-way associative), $t_h=1$ cycle.
• L2: 1MB (private per core), 12-way associative.
• L3: 20MB (shared), 16-way associative.

8. Real Hardware: A Look Inside a CPU Cache

classDiagram
    class CacheLine {
        +Tag: 20 bits
        +Index: 6 bits
        +Valid: 1 bit
        +Dirty: 1 bit
        +Data: 64 bytes
    }
    class CacheSet {
        +Lines: CacheLine[]
    }
    class Cache {
        +Sets: CacheSet[]
        +Mapping: Direct/Associative/Set-Associative
    }
    Cache "1" --> "*" CacheSet : contains
    CacheSet "1" --> "*" CacheLine : contains

9. Worked Example: Cache Hit/Miss Analysis

Scenario: A direct-mapped cache with:

• Cache size: 16 blocks (index 0–15).
• Block size: 64 bytes.
• Main memory: 256 blocks (addresses 0–255).
• Access sequence: 0, 16, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 240.

Step 1: Determine mapping.

• Cache line = (Memory Block) mod 16.
• Example:
  • Block 0 → Line 0 (0 mod 16).
  • Block 16 → Line 0 (16 mod 16 = 0).
  • Block 32 → Line 0 (32 mod 16 = 0).

Step 2: Simulate accesses.

Result: All accesses miss because they all map to Cache Line 0 (conflict misses). Hit Rate: 0%.

Real-World Tie-In:

• This is like Kathmandu traffic where all routes lead to the same bottleneck (e.g., Thapathali–Kageshwori road). A set-associative cache would distribute blocks across multiple lines, reducing conflicts.

10. Exam Tip: How to Score Full Marks

1. Diagrams are mandatory:

   • Always draw block diagrams for cache mapping (direct/associative/set-associative).
   • Label tags, indices, valid/dirty bits, and data arrays.
   • Example: For a 4-way set-associative cache with 8 sets, show 8 sets, each with 4 lines.

2. Define terms precisely:

   • Conflict miss: Miss due to mapping (not capacity).
   • Capacity miss: Miss because cache is full.
   • Cold-start miss: First access to a new block.

3. Compare mapping techniques:

   • Use a table (as above) to highlight trade-offs (speed vs. complexity).

4. Calculate AMAT:

   • Always show the formula and plug in numbers.
   • Example: If $t_h=2$, $MR=0.1$, $t_m=100$, then $\text{AMAT}=2+(0.1\times 100)=12$.

5. Relate to real systems:

   • Mention Intel/ARM caches, banking systems (eSewa), or e-commerce (Daraz) in explanations.
   • Example: "Like how Daraz prefetches related products into cache, a set-associative cache reduces conflict misses by distributing blocks across multiple lines."

6. Common pitfalls:

   • Direct mapping: Forgetting to mention conflict misses.
   • LRU: Not explaining how it requires hardware support (e.g., timestamps).
   • Write-back: Forgetting to mention the dirty bit.

Past Exam Questions Covered in This Note

Final Summary

• Memory hierarchy exploits locality to reduce average access time.
• Cache mapping (direct/associative/set-associative) trades off speed vs. flexibility.
• Replacement policies (LRU/FIFO/random) impact hit rates.
• Write policies (write-through/write-back) balance consistency vs. speed.
• AMAT is the key metric: $\text{AMAT}=t_h+(MR\times t_m)$.

Remember: In exams, draw diagrams, compare techniques, and tie concepts to real systems (eSewa, Daraz, Intel CPUs).