Cache Mapping Techniques

Introduction

When a block of data arrives from main memory, WHERE in the cache should it go? This seemingly simple question has three answers, each with different trade-offs. The mapping technique determines which cache locations a memory block can occupy, affecting hit rate, hardware complexity, and access speed. Understanding these techniques is essential for cache design and for writing cache-friendly code.

The Problem

Main memory is much larger than cache. If memory has 1 million blocks and cache has 1,000 lines, each cache line must serve multiple memory blocks. The mapping technique defines the relationship between memory blocks and cache lines.

Direct-Mapped Cache

Concept

Each memory block maps to exactly one cache line. The mapping is determined by the block address modulo the number of cache lines:

Example

Cache with 8 lines, memory blocks 0-31:

Address Breakdown

Lookup Process

1. Extract index → go directly to that cache line
2. Compare tag with stored tag
3. If match AND valid bit = 1 → HIT (return data at offset)
4. If no match → MISS (fetch from memory, replace this line)

Advantages

• Simple hardware: Only one comparator needed (one possible location)
• Fast access: No searching — go directly to the indexed line
• Low power: Only one tag to check

Disadvantages

• Conflict misses: Multiple blocks mapping to same line thrash each other
• Example: Alternating access to blocks 0 and 8 causes 100% miss rate (both map to line 0!)

Fully Associative Cache

Concept

A memory block can go in ANY cache line. No fixed mapping — search all lines.

Lookup Process

1. Compare requested tag with ALL stored tags simultaneously
2. If any match → HIT (return data from that line)
3. If no match → MISS (fetch, replace using LRU/random policy)

Address Breakdown

No index field! Any block can go anywhere.

Advantages

• No conflict misses: Any block fits anywhere — maximum flexibility
• Best hit rate: Only compulsory and capacity misses occur

Disadvantages

• Expensive hardware: Need one comparator PER cache line (compare tag with ALL lines in parallel)
• Slow: Many parallel comparisons add delay
• Impractical for large caches: 1000 lines = 1000 comparators

Practical Use

• Very small caches (TLB with 32-64 entries)
• Specialized caches where maximum hit rate is critical

Set-Associative Cache

Concept

A compromise: the cache is divided into sets, each containing multiple ways. A memory block maps to a specific SET (like direct-mapped) but can go in ANY WAY within that set (like fully associative within the set).

N-way set-associative: Each set has N lines (N ways)

Address Breakdown

Lookup Process

1. Extract set index → identify the correct set
2. Compare tag with ALL ways in that set (N comparisons)
3. If any way matches → HIT
4. If no match → MISS (replace one way in the set using replacement policy)

Relationships

• 1-way set-associative = Direct-mapped (1 way per set = each set has one line)
• N-way with 1 set = Fully associative (one set containing all lines)
• N-way with k sets = Standard set-associative (most common)

Common Configurations

Why N-way Reduces Conflicts

In direct-mapped, blocks 0 and 8 fight for the same line. In 2-way, they can both be in the same SET (one in way 0, one in way 1) — no conflict!

Comparison Table

Practical Design Choices

Modern processors typically use:

• L1 Cache: 4-8 way set-associative (balance speed and hit rate)
• L2 Cache: 8-16 way set-associative
• L3 Cache: 12-20 way set-associative (maximize hit rate, latency less critical)
• TLB: Fully associative (small, critical for every access)

Replacement Policies (for associative caches)

When all ways in a set are full and a new block arrives, which way to evict?

• LRU (Least Recently Used): Evict the way accessed longest ago. Best hit rate but complex tracking.
• Pseudo-LRU: Approximation of LRU with simpler hardware (tree-based)
• Random: Surprisingly good performance, trivial hardware
• FIFO: Evict oldest loaded block

Key Takeaways

1. Direct-mapped: Simple and fast but suffers conflict misses (one location per block)
2. Fully associative: Best hit rate but impractical for large caches (too many comparators)
3. Set-associative: The practical compromise — reduces conflicts while limiting hardware
4. Higher associativity → fewer conflict misses but slower access and more power
5. Modern L1 caches use 4-8 way; L2/L3 use 8-20 way
6. Set index determines WHICH set; tag comparison determines WHICH way (if any) hits
7. The choice of mapping technique directly impacts miss rate and access time