Memory Hierarchy & Organization: Speed, Cost, Trade-offs & Cache

TAKEAWAYS:

• Memory hierarchy is a speed-cost trade-off where smaller, faster layers (cache) sit between the CPU and slower but larger layers (RAM/disk).
• Cache mapping (direct, associative, set-associative) determines how data blocks are placed in cache and how conflicts are resolved.
• Locality principles (temporal and spatial) explain why caches work: programs reuse nearby data and recently accessed data.
• Memory addressing uses base registers, page tables, and segmentation to map virtual addresses to physical memory locations.
• DRAM vs. SRAM differ in speed, power, and cost, with SRAM used exclusively for cache due to its low access time.
• Virtual memory extends physical RAM using disk storage, enabling larger address spaces than available hardware.

The Memory Hierarchy: Why Layers?

Computers use a memory hierarchy to balance three critical factors:

1. Speed (how fast data can be accessed)
2. Capacity (how much data can be stored)
3. Cost (price per unit of storage)

The hierarchy is organized from fastest/smallest (closest to the CPU) to slowest/largest (farther from the CPU):

CPU Registers (ns) → Cache (1–100 ns) → Main Memory (RAM, 100–300 ns) → Secondary Storage (µs–ms)

Why Not Just Use Fast Memory Everywhere?

• Cost: Fast memory (e.g., SRAM) is 10–100x more expensive than slower DRAM.
• Power: Fast memory consumes more power, heating up the system.
• Limited capacity: Even the largest cache today holds <100 MB, while a typical program needs GBs of data.

The hierarchy exploits locality: programs tend to:

• Temporal locality: Reuse recently accessed data (e.g., looping through an array).
• Spatial locality: Access data near recently used memory (e.g., reading consecutive array elements).

Layer 1: CPU Registers (Fastest, Smallest)

Registers are the fastest memory in the system, directly connected to the CPU. They hold:

• Data registers (e.g., AX, BX in 8085) for arithmetic/logic operations.
• Address registers (e.g., PC, SP) for program control.
• Special-purpose registers (e.g., PSW for flags).

Key Properties:

Layer 2: Cache Memory (Fast, but Limited)

Cache sits between the CPU and RAM to reduce the average memory access time (AMAT). It is SRAM-based (static RAM), which is faster but more expensive than DRAM.

Cache Organization

Cache is divided into blocks (or lines), each holding a chunk of data (typically 32–128 bytes). The mapping of main memory to cache uses one of three strategies:

1. Direct-Mapped Cache

• Each memory block maps to exactly one cache line.
• Pros: Simple, fast lookup.
• Cons: Conflict misses (two frequently used blocks map to the same cache line).

stateDiagram-v2
    [*] --> Main_Memory
    Main_Memory --> Cache_Line: Direct Mapping
    Cache_Line --> CPU: Hit
    Cache_Line --> [*]: Miss (replace)

2. Fully Associative Cache

• A memory block can go into any cache line.
• Pros: No conflict misses.
• Cons: Slow lookup (requires searching all lines).

3. Set-Associative Cache (Most Common)

• Cache is divided into sets; each memory block maps to a specific set.
• Within a set, blocks can be placed in any line (like associative but with limited choices).
• Example: 4-way set-associative means 4 lines per set.

Cache Mapping Example: Direct-Mapped

Problem: Suppose a cache has 16 lines and 32-byte blocks. Main memory is 32-bit addressed. How is block 0x12345678 mapped?

1. Block offset: Lower 5 bits (0x18) → identifies byte within block.
2. Index: Next 4 bits (0x56) → selects cache line (0x56 / 16 = line 8).
3. Tag: Remaining bits (0x1234) → stored with the block in cache.

Visualization:

Layer 3: Main Memory (RAM)

RAM is volatile DRAM (Dynamic RAM), where data is stored in capacitors that must be refreshed periodically. Key properties:

How RAM Works Internally

RAM is organized in a 2D grid of rows and columns:

• Row: Activated by Row Address Strobe (RAS).
• Column: Activated by Column Address Strobe (CAS).
• Refresh: Required every 64 ms (for DRAM).

Layer 4: Secondary Storage (Slowest, Largest)

Secondary storage (HDD/SSD) is non-volatile and holds data even when powered off. Key types:

Real-World Example: eSewa App (Nepal)

• Problem: eSewa needs to store millions of transactions securely and quickly.
• Solution:
  • Cache: Frequently accessed user profiles and recent transactions are stored in CPU cache or RAM.
  • Main Memory (RAM): Active sessions and temporary data (e.g., payment processing) reside here.
  • Secondary Storage (SSD): All transactions are logged to SSDs for persistence.
  • Database (SQL/NoSQL): Uses indexing (like cache mapping) to speed up queries.

Memory Addressing: How the CPU Finds Data

The CPU uses addresses to locate data in memory. Two key concepts:

1. Physical vs. Virtual Addressing

2. Address Translation (Paging)

The Memory Management Unit (MMU) translates virtual addresses to physical addresses using a page table:

sequenceDiagram
    CPU->>MMU: Virtual Address (e.g., 0x7FFE8000)
    MMU->>Page_Table: Lookup Page Number (0x7FF)
    Page_Table-->>MMU: Physical Frame (e.g., 0x1234)
    MMU->>CPU: Physical Address (0x12348000)

Example: In a system with 4 KB pages:

• Virtual address 0x7FFE8000:
  • Page number: 0x7FFE8000 >> 12 = 0x7FF (top 20 bits).
  • Offset: 0x8000 (bottom 12 bits).
• The MMU looks up 0x7FF in the page table to find the physical frame (e.g., 0x1234), then combines it with the offset to get 0x12348000.

Virtual Memory: Extending RAM with Disk

When physical RAM is full, the OS uses swap space (on disk) to:

1. Page out: Move rarely used pages to disk.
2. Page in: Load pages back when needed.

Example: Pathao Driver App (Nepal)

• Scenario: A driver’s app needs to display real-time traffic routes and user locations.
• Memory Hierarchy:
  • Cache: Frequently accessed routes (e.g., Kathmandu-Thamel) are cached.
  • RAM: Active user sessions and map tiles.
  • SSD: Full map database (paged in/out as needed).
  • HDD: Backup logs of driver trips.

Trade-off: Swapping slows down the system (thrashing), but enables running large apps (e.g., Adobe Photoshop) on machines with limited RAM.

Cache Performance Metrics

To evaluate cache effectiveness, we use:

1. Hit Time (t_h): Time to access data in cache (e.g., 1 ns).
2. Miss Penalty (t_m): Time to fetch data from RAM (e.g., 100 ns).
3. Hit Rate (H): Probability of finding data in cache (e.g., 95% = 0.95).

Average Memory Access Time (AMAT): $$AMAT=t_h\times H+t_m\times (1-H)$$ Example: For a cache with:

• $t_h=1$ ns,
• $t_m=100$ ns,
• $H=0.95$:

$$AMAT=1\times 0.95+100\times 0.05=0.95+5=5.95\text{ ns}$$ Without cache: 100 ns → 17x speedup!

Real-World Applications of Memory Hierarchy

1. Khalti (Digital Payment System, Nepal)

• Problem: Millions of transactions per second require low-latency access to user accounts and transaction logs.
• Solution:
  • Cache: Frequently accessed user profiles (e.g., top merchants) are cached in L1/L2 cache.
  • RAM: Active transactions are stored in DRAM with in-memory databases (e.g., Redis).
  • SSD: Persistent storage for all transactions (logged to disk every 100 ms).
  • HDD: Archival storage for old transactions (compressed).

2. YouTube (Global)

• Problem: Serving billions of video streams requires fast access to video chunks.
• Solution:
  • CDN Caches: Videos are cached in edge servers worldwide (using set-associative caches).
  • RAM: Active video buffers are stored in DRAM.
  • SSD/HDD: Original videos are stored in distributed storage (e.g., Google Cloud Storage).

3. Nepal Electricity Authority (NEA) Grid Management

• Problem: Real-time monitoring of 1000+ substations requires low-latency data access.
• Solution:
  • Cache: Critical sensor data (e.g., voltage levels) is cached in CPU cache.
  • RAM: Active monitoring data is stored in DRAM with priority queues.
  • SSD: Historical data is stored in time-series databases (e.g., InfluxDB).
  • HDD: Archival logs for audits.

Worked Example: Cache Hit/Miss Analysis

Scenario: A program accesses memory in this order: 0x000, 0x010, 0x020, 0x000, 0x030, 0x040, 0x000, 0x050 Assume:

• Cache size: 4 blocks (direct-mapped).
• Block size: 16 bytes (offset = 4 bits).
• Index bits: 2 (since $2^2=4$ blocks).

Hit Rate: 1 hit / 8 accesses = 12.5% (poor due to conflicts!). Solution: Use set-associative cache (e.g., 2-way) to reduce conflicts.

Memory Hierarchy Trade-offs Table

Exam Tip: How to Score Full Marks

1. Diagrams Are Mandatory:

   • Always draw the memory hierarchy pyramid (speed vs. size).
   • Show cache mapping (direct/associative/set-associative) with labeled blocks.
   • Include address translation (virtual → physical) with page tables.

2. Define Key Terms Clearly:

   • Locality: Temporal vs. spatial.
   • Cache hit/miss: Define with examples.
   • AMAT formula: Derive and explain each term.

3. Real-World Examples:

   • Link cache to eSewa transactions or Pathao routing.
   • Compare HDD vs. SSD in NEA grid monitoring.

4. Worked Problems:

   • Given a memory trace, calculate hit rate and AMAT.
   • For a cache size/block size, determine index/tag bits.

5. Common Pitfalls:

   • Don’t confuse associativity with mapping: Direct-mapped is 1-way, associative is N-way.
   • Don’t forget the offset: It’s part of the address but not stored in cache.
   • Virtual memory ≠ cache: Virtual memory extends RAM with disk; cache is separate.

Summary Checklist

Before the exam, ensure you can: ✅ Explain the memory hierarchy with speed/cost trade-offs. ✅ Compare direct, associative, and set-associative cache mapping. ✅ Calculate AMAT given hit rate and latencies. ✅ Describe address translation (virtual → physical) with page tables. ✅ Give 2 real-world examples (e.g., eSewa, YouTube) of memory hierarchy in action. ✅ Draw a cache block diagram with tags, indices, and offsets. ✅ Explain locality principles (temporal/spatial) with examples.