Memory Hierarchy & Cache Design: Mapping, Coherence & Performance

Core Concepts: Why Memory Hierarchy Exists

The Memory Wall Problem

Modern CPUs execute instructions at GHz speeds (3–5 GHz in today’s processors), but DRAM access takes 50–100 ns (a 1000× slower bottleneck). This mismatch creates the "memory wall"—a performance ceiling where the CPU waits idle for memory.

Key Idea: The hierarchy exploits the locality principle:

• Temporal locality: Recently accessed data will be reused soon (e.g., loop variables).
• Spatial locality: Nearby data in memory is often accessed together (e.g., array elements).

Cache Mapping Techniques: How Data Fits into Cache

1. Direct Mapping

Definition: Each main memory block maps to exactly one cache line (determined by a modulo operation). Formula: Cache line index = (Block address) MOD (Number of cache lines)

Pros/Cons:

Worked Example: eSewa Transaction Queue

• Scenario: eSewa processes payments in batches. If payment records are stored in memory blocks 0, 4, 8, ... (strided access) and the cache has 4 lines, every 4th transaction causes a cache miss (conflict miss).
• Solution: Use a larger cache or set-associative mapping (below).

2. Fully Associative Mapping

Definition: Any main memory block can map to any cache line (like a parking lot with no assigned spots). Lookup: Requires searching all cache lines (slow but flexible).

Pros/Cons:

Real-World Analogy: Pathao Ride Queue

• Scenario: Pathao’s server assigns rides to drivers dynamically (like fully associative cache). If a driver is busy, the next ride can go to any available driver (no fixed slot).
• Problem: Scaling to millions of drivers requires set-associative mapping (next section).

3. Set-Associative Mapping

Definition: A compromise—divide cache into sets, and each set has multiple lines (e.g., 2-way or 4-way set-associative). Formula: Set index = (Block address) MOD (Number of sets) Line within set = (Block address / Number of sets) MOD Associativity

Pros/Cons:

Worked Example: Ncell’s Call Routing

• Scenario: Ncell routes calls to towers in sets (e.g., 4 towers per set, 2-way associative). If Tower A is busy, the call can go to Tower B in the same set.
• Assumptions:
  • Cache size = 8 blocks (4 sets × 2 lines/set).
  • Memory block for a call record = address MOD 4 (set index) + address / 4 MOD 2 (line within set).

Cache Performance Metrics

Hit Time, Miss Rate, and Hit Rate

Formula for Average Memory Access Time (AMAT): $$\text{AMAT}=\text{Hit Time}+\text{Miss Rate}\times \text{Miss Penalty}$$

Example Calculation:

• L1 Cache: Hit Time = 2 cycles, Miss Rate = 5%, Miss Penalty = 20 cycles.
• AMAT = 2 + 0.05 × 20 = 3 cycles.

Cache Coherence: The Multiprocessor Challenge

Problem: Stale Data in Shared Caches

In multicore systems (e.g., Intel Core i7, AMD Ryzen), multiple cores access shared memory. If Core 1 writes to a cache line and Core 2 reads it from its own cache, Core 2 gets dirty (stale) data.

sequenceDiagram
    participant Core1
    participant Core2
    participant SharedMemory
    Core1->>SharedMemory: Write data (X=10)
    Core1->>Core1: Invalidate its cache line
    Core2->>Core2: Reads same address (still X=5!)
    Core2->>Core2: Uses stale data (X=5)

Solution: MESI Protocol

States:

• M (Modified): Only this core has a dirty copy (not in memory).
• E (Exclusive): Only this core has a clean copy (matches memory).
• S (Shared): Multiple cores have clean copies.
• I (Invalid): Stale data (must fetch from memory).

stateDiagram-v2
    [*] --> M: Write by core
    M --> E: Writeback to memory
    E --> S: Other core reads
    S --> I: Core writes (invalidates others)
    I --> M: Fetch from memory
    M --> M: Rewritten
    S --> S: Shared read

Worked Example: NEPSE Stock Trading

• Scenario: Two traders (Core 1 and Core 2) access the same stock price (e.g., NEPSE index).
  • Core 1 reads price (X=2000) → S state.
  • Core 2 reads same price → S state (shared).
  • Core 1 updates price (X=2010) → M state, invalidates Core 2’s cache.
  • Core 2 must fetch fresh data from memory before reading again.

Real-World Applications

1. eSewa: Transaction Processing with Cache

• Idea Used: Temporal locality in payment records.
• How:
  • Frequent transactions (e.g., mobile recharge) reuse the same cache lines.
  • eSewa’s servers use L3 cache (large, shared) to reduce RAM access for high-frequency operations.
• Example:
  • User A pays ₹500 to User B. The transaction record stays in cache for subsequent checks (e.g., refunds).
  • Miss Rate: <1% for hot transactions (high hit rate).

2. Pathao: Ride Assignment with Set-Associative Mapping

• Idea Used: Set-associative cache for dynamic driver assignment.
• How:
  • Pathao’s backend divides drivers into "sets" (e.g., 4 sets of 1000 drivers each).
  • A ride request maps to a set based on location hash → reduces conflict misses when drivers are busy.
• Example:
  • Ride in Kathmandu (set 0): If all drivers in line 0 are busy, Pathao checks line 1 in the same set.

3. NTC’s Network Traffic Routing

• Idea Used: Cache coherence for real-time updates.
• How:
  • NTC’s central server updates internet speeds for different regions (e.g., Kathmandu, Pokhara).
  • Edge caches (in ISP routers) use MESI-like protocols to avoid stale speed data.
• Example:
  • NTC updates Pokhara’s speed to 50 Mbps → invalidates old cache entries in ISP routers → forces fresh fetch.

Exam Tip: How to Score Full Marks

1. Diagrams Are Mandatory:

   • Always draw direct/associative/set-associative cache mappings for mapping questions.
   • For coherence, show a MESI state diagram or sequence diagram.

2. Define Terms Precisely:

   • Conflict miss: Miss due to mapping collisions (not capacity).
   • Cold start miss: First access to a new block (not in cache).
   • Capacity miss: Cache is full (even with perfect mapping).

3. Worked Examples:

   • For AMAT: Always show the formula and plug in numbers.
   • For mapping: Show the modulo operation (e.g., "Block 5 → Set 1 (5 MOD 4) → Line 1 (5/4 MOD 2)").

4. Common Pitfalls:

   • ❌ Saying "cache reduces memory size" → ✅ Cache is smaller but faster.
   • ❌ MESI states as "Modified, Exclusive, Shared, Invalid" without explaining transitions.
   • ❌ Ignoring miss penalty in AMAT calculations.

5. Real-World Links:

   • Relate conflict misses to Daraz’s order queue (strided access).
   • Relate cache coherence to bank transactions (shared ledgers).