⚑ Cache Memory

Fast, Small, and Essential: Understanding Computer Cache Architecture

What is Cache Memory?

Cache memory is a small, fast memory placed between the CPU and main memory. It exploits the principle of locality of reference, significantly reducing average memory access time and improving overall system performance.

5-10Γ—

Faster than Main Memory

80-90%

Typical Hit Rate

512-32K

Words Capacity Range

🎯 Locality of Reference

Analysis of typical programs reveals two key patterns that make cache memory effective:

πŸ“

Temporal Locality

Recently accessed memory locations are likely to be accessed again soon

πŸ“Š

Spatial Locality

Memory locations near recently accessed locations are likely to be accessed

πŸ”„

Loop Behavior

Program loops repeatedly access the same instructions and data

πŸ“ˆ

90-10 Rule

Programs spend 90% of time executing only 10% of code

βš™οΈ How Cache Works

πŸ” Basic Cache Operation β–Ό

When the CPU needs data:

  1. CPU sends address to check if word is in cache
  2. Cache Hit: Word found in cache β†’ data sent to CPU immediately
  3. Cache Miss: Word not in cache β†’ main memory accessed, entire block transferred to cache
  4. Block Transfer: Multiple words transferred together to exploit spatial locality

Average Access Time = Cache Time Γ— Hit Rate + Main Memory Time Γ— Miss Rate

Example: With 10ns cache, 1000ns main memory, and 90% hit rate:
Average = 10Γ—0.9 + 1000Γ—0.1 = 109ns (much better than 1000ns!)

πŸ“¦ Block Size & Transfer β–Ό

Cache memory stores blocks of words rather than individual words. Block sizes vary from one word to about 16 words. When a miss occurs, the entire block containing the requested word is transferred from main memory to cache.

Why blocks? This exploits spatial locality - if you need one word, you'll likely need nearby words too!

πŸ—ΊοΈ Cache Mapping Techniques

Three primary methods organize how main memory addresses map to cache locations:

1. Associative Mapping

Most Flexible

β€’ Any block can go anywhere in cache
β€’ Full address stored as tag
β€’ All tags searched simultaneously
β€’ Highest hit rate
β€’ Most expensive hardware

2. Direct Mapping

Simplest & Fastest

β€’ Each block has exactly one cache location
β€’ Address = Tag + Index + Word
β€’ Fast and simple
β€’ Lower hit rate
β€’ Conflicts if same index needed

3. Set-Associative

Best Compromise

β€’ Cache divided into sets
β€’ Block can go in any location within set
β€’ Combines benefits of both methods
β€’ 2-way, 4-way, 8-way common
β€’ Balanced cost and performance

Address Structure Comparison

Mapping Type Address Components Search Method
Associative Tag (full) + Word Search all tags in parallel
Direct Tag + Index + Word Direct index lookup, compare one tag
Set-Associative Tag + Set Index + Word Index to set, search tags within set

✍️ Cache Write Operations

πŸ“ Write-Through β–Ό

Updates both cache and main memory simultaneously

Advantages:

  • Main memory always has valid data
  • Simplifies I/O operations
  • No data loss if system fails

Disadvantage: Slower because every write waits for main memory

⚑ Write-Back β–Ό

Updates only cache initially, writes to memory only when block is replaced

Advantages:

  • Faster - no waiting for main memory
  • Multiple writes to same location only write once to memory
  • Used in typical programs (10-30% of references are writes)

Implementation: Uses "valid bit" to track if cache block has been modified

πŸ”„ Replacement Algorithms

When cache is full and a new block is needed, which block should be replaced?

🎲

Random

Simplest method - randomly select a block to replace

πŸ₯‡

FIFO

First In, First Out - replace oldest block in cache

⏰

LRU

Least Recently Used - most common, best performance

LRU Performance: Selects the item that has been unused for the longest time. Both FIFO and LRU algorithms provide similar hit rates, with LRU having a slight advantage as set size increases.

πŸš€ Cache Initialization

βš™οΈ Power-On Initialization β–Ό

When power is applied to the computer or when programs are loaded:

  1. Cache is empty and considered invalid
  2. Valid bits set to indicate no valid data
  3. First loads from main memory transfer blocks to cache
  4. Valid bits updated as blocks are loaded
  5. Subsequent accesses can hit cache

Important: The introduction of a new word automatically replaces invalid data. Thus initialization conditions are restored during normal operation.

πŸ“Š Performance Example

Real-World Scenario

System Configuration:

  • Cache access time: 10 nanoseconds
  • Main memory access time: 1000 nanoseconds
  • Hit ratio: 90% (typical for well-designed cache)

Performance Calculation:

Average access time = (0.9 Γ— 10ns) + (0.1 Γ— 1000ns) = 9ns + 100ns = 109ns

Result: Nearly 10Γ— faster than accessing main memory directly! This is why cache is crucial for modern computer performance.

🎯 Key Takeaways

Speed Hierarchy

Cache sits between fast CPU and slower main memory, providing optimal balance

Locality Principle

Programs naturally exhibit temporal and spatial locality, making cache effective

Mapping Trade-offs

Associative = flexible, Direct = fast, Set-Associative = balanced compromise

Write Strategies

Write-through = safer, Write-back = faster for typical workloads

Virtual Memory