Introduction to Cache Memory

Imagine you are a librarian who needs to fetch books for many readers. If every time a reader requests a book, you have to go to a huge warehouse far away, it will take a lot of time. But if you keep the most popular books on a small shelf near you, you can quickly hand them out without delay. This is exactly how cache memory works in a computer system.

The Central Processing Unit (CPU) is the brain of the computer, performing millions of operations every second. However, the CPU is extremely fast, while the main memory (RAM) is comparatively slower. This speed difference creates a bottleneck, slowing down the overall system.

Cache memory acts as a small, very fast storage located close to the CPU. It stores frequently accessed data and instructions so that the CPU can retrieve them quickly, improving system performance significantly.

In this chapter, we will explore what cache memory is, how it is organized, the techniques used to manage it, and how to measure its performance.

Cache Memory Basics

What is Cache Memory?

Cache memory is a small-sized, high-speed memory located between the CPU and the main memory. It temporarily holds copies of data and instructions that the CPU is likely to reuse soon.

Why is Cache Needed?

The CPU operates at speeds much faster than the main memory. Without cache, the CPU would spend a lot of time waiting for data to be fetched from the slower main memory. Cache reduces this waiting time by providing faster access to frequently used data.

Cache vs Main Memory

• Size: Cache is much smaller than main memory.
• Speed: Cache is faster than main memory.
• Cost: Cache memory is more expensive per byte than main memory.

Benefits of Cache Memory

• Speeds up data access for the CPU.
• Reduces average memory access time.
• Improves overall system performance.

Cache Organization and Levels

Cache memory is organized in multiple levels to balance speed, size, and cost:

• L1 Cache: Closest to the CPU, smallest size, fastest access.
• L2 Cache: Larger than L1, slower but still faster than main memory.
• L3 Cache: Shared among CPU cores, largest and slowest cache level.

Each cache level stores data in blocks (also called cache lines). The block size is the amount of data transferred between cache and main memory in one operation.

Choosing the right cache size and block size is a trade-off between cost, speed, and hit rate (how often data is found in cache).

Cache Mapping Techniques

When the CPU requests data, the cache must decide where to store or find that data. This is done using cache mapping techniques. There are three main types:

1. Direct Mapping

Each block of main memory maps to exactly one cache line. It is like having a fixed shelf slot for each book in the library.

Advantages: Simple and fast mapping.

Disadvantages: Can cause frequent conflicts if multiple blocks map to the same cache line.

2. Associative Mapping

A block can be placed in any cache line. The cache searches all lines to find a block.

Advantages: Flexible, fewer conflicts.

Disadvantages: More complex and slower to search.

3. Set-Associative Mapping

Combines direct and associative mapping. Cache is divided into sets, each containing multiple lines. A block maps to one set but can be placed in any line within that set.

Advantages: Balances speed and flexibility.

Disadvantages: More complex than direct mapping.

graph TD    A[Memory Address] --> B{Mapping Technique}    B --> C[Direct Mapping]    B --> D[Associative Mapping]    B --> E[Set-Associative Mapping]    C --> F[One Cache Line per Block]    D --> G[Any Cache Line]    E --> H[One Set, Multiple Lines]

Cache Performance Metrics

To evaluate cache effectiveness, we use several key metrics:

• Hit Rate: The fraction of memory accesses found in cache.
• Miss Rate: The fraction of memory accesses not found in cache.
• Average Memory Access Time (AMAT): Average time to access memory considering hits and misses.

Cache Write and Replacement Policies

When the CPU writes data, the cache must decide how and when to update main memory. This is controlled by write policies:

Write-Through

Every write to cache is immediately written to main memory. This keeps memory always updated but increases memory traffic.

Write-Back

Writes are made only to cache. Main memory is updated later when the cache block is replaced. This reduces memory traffic but requires more complex control.

When cache is full and a new block must be loaded, a replacement policy decides which block to remove:

• Least Recently Used (LRU): Replace the block that was used least recently.
• First In First Out (FIFO): Replace the oldest block in cache.

These policies impact cache efficiency and complexity.

Formula Bank

Worked Examples

graph TD    A[Memory Address 11010110] --> B[Tag: 110]    A --> C[Set Index: 101 (Set 5)]    A --> D[Block Offset: 10]    C --> E{Check Set 5}    E --> F[Compare Tag with 110 in Set 5]    F --> G{Hit or Miss}