Direct Mapping vs Set-Associative Mapping in CPU Cache

This article explains the operational differences between direct-mapped and set-associative CPU cache architectures through the lens of binary address division. You will learn how modern processors break down memory addresses into binary fields—Tag, Index, and Offset—to locate data, how each mapping strategy uses these bits, and the architectural trade-offs between hardware complexity, lookup latency, and conflict misses.

The Binary Structure of Memory Addresses

When a CPU requests data from main memory, it references a binary memory address of \(n\) bits. To determine whether the requested data resides in the cache, the memory address is divided into three distinct bit fields:

1. Block Offset (\(w\) bits): Determines the specific byte within a cache line. If a cache line holds \(B = 2^w\) bytes, the lowest \(w\) bits represent the offset.
2. Index (\(s\) bits): Specifies the cache row (or set) where the block must be placed. For \(S = 2^s\) sets, the middle \(s\) bits act as the index.
3. Tag (\(t\) bits): The remaining higher-order bits (\(t = n - s - w\)) uniquely identify the memory block stored at that location.

+------------------+------------------+------------------+
|    Tag (t bits)  |   Index (s bits) |  Offset (w bits) |
+------------------+------------------+------------------+

Direct-Mapped Cache

In a direct-mapped cache, each block of main memory maps to exactly one specific line in the cache.

Binary Address Mechanics

• Index Bits (\(s\)): Determined by the total number of lines in the cache. If a cache has \(2^s\) total lines, \(s\) bits are allocated to the Index.
• Placement Logic: The cache controller directly uses the \(s\) bits to read that single line. It compares the address’s \(t\)-bit Tag with the Tag stored in that line.
• Hit Condition: If the valid bit is set and the tags match, it is a cache hit.

Advantages and Disadvantages

• Advantage: Minimal hardware complexity and lowest hit latency. Only one tag comparison and no replacement policy logic are required.
• Disadvantage: High rate of conflict misses. If two frequently used addresses share the exact same Index bits but have different Tag bits, they will continuously overwrite each other, a condition known as cache thrashing.

Set-Associative Cache

In an \(N\)-way set-associative cache, the cache is partitioned into sets, and each set contains \(N\) cache lines (or “ways”). A memory block maps to a specific set, but it can reside in any of the \(N\) lines within that set.

Binary Address Mechanics

• Index Bits (\(s\)): Determined by the number of sets, calculated as \(\text{Total Lines} / N\). Because there are fewer sets than total lines, the number of index bits \(s\) decreases compared to a direct-mapped cache of equal capacity.
• Tag Bits (\(t\)): As the index field shrinks by \(\log_2(N)\) bits, the tag field expands by the same amount (\(t = n - s - w\)).
• Placement Logic: The cache controller uses the \(s\) bits to locate the target set, then reads all \(N\) lines in parallel.
• Hit Condition: \(N\) tag comparators simultaneously evaluate whether any line within the set matches the address Tag.

Advantages and Disadvantages

• Advantage: Significantly reduces conflict misses. Multiple memory blocks sharing the same index can reside in the cache simultaneously (up to \(N\) blocks).
• Disadvantage: Higher hardware cost, increased power consumption, and slightly higher latency due to parallel tag comparators, multiplexers, and replacement algorithm tracking (such as Least Recently Used, or LRU).

Binary Trade-Off Comparison

Direct mapping maximizes speed and simplicity by fixing every memory block to a single binary index, while set-associative mapping trades shorter index fields and extra tag comparison hardware to drastically reduce conflict misses.