Cache Address Partitioning: Tag, Index, and Offset

Modern processor caches use physical address partitioning to rapidly determine whether requested data resides in cache memory or must be fetched from main memory. By interpreting a standard binary physical address as three distinct bitfields—the Block Offset, the Set Index, and the Tag—the hardware can index specific cache locations and verify data validity in constant time without scanning the entire cache storage.

The Tripartite Division of a Binary Address

Every memory address generated by the CPU is an \(N\)-bit binary value representing a specific byte in physical memory. The cache controller divides these \(N\) bits from right to left (least significant to most significant) into three fields:

[ Tag Bits ] [ Index Bits ] [ Offset Bits ]

1. Offset Bits (Least Significant Bits)

The Block Offset determines the specific byte within a cache line. Because caches transfer data in fixed-size multi-byte blocks (typically 64 bytes) rather than individual bytes, the offset addresses individual bytes within that block.

• Formula: \(\text{Offset Bits} = \log_2(\text{Cache Line Size in Bytes})\)
• Example: For a standard 64-byte cache line, \(\log_2(64) = 6\) bits are required (Bits \(0\) through \(5\)).

2. Index Bits (Middle Bits)

The Index bits select the specific set (or row) in the cache where the target block must reside. The number of index bits depends directly on the total number of sets available in the cache.

• Formula: \(\text{Index Bits} = \log_2(\text{Number of Sets})\)
• Number of Sets Calculation: \(\text{Number of Sets} = \frac{\text{Total Cache Size}}{(\text{Line Size} \times \text{Associativity})}\)
• Example: For a cache with 512 sets, \(\log_2(512) = 9\) bits are required.

In direct-mapped caches, the number of sets equals the total number of cache lines. In set-associative caches, multiple lines (ways) share the same index. Fully associative caches do not use index bits (\(\text{Index Bits} = 0\)) because a block can reside in any location.

3. Tag Bits (Most Significant Bits)

Because multiple memory addresses share the same Index and Offset bits, the Tag acts as a unique identifier for the memory block currently occupying a cache line. The remaining high-order bits of the physical address are stored alongside the cached data in dedicated tag memory.

• Formula: \(\text{Tag Bits} = \text{Total Address Bits} - (\text{Index Bits} + \text{Offset Bits})\)

The Hardware Lookup Mechanism

When the CPU requests a physical address, the cache controller performs the lookup using the partitioned bits:

1. Set Selection: The controller uses the Index bits to immediately route to the target set in the cache array using hardware multiplexers.
2. Tag Matching: The controller reads the stored tags for all ways in that selected set and compares them simultaneously against the Tag bits of the requested address using hardware comparators.
3. Hit/Miss Determination: If a stored tag matches the requested tag and the line’s valid bit is set (\(1\)), a Cache Hit occurs. If no tag matches, a Cache Miss occurs, triggering a memory fetch.
4. Data Extraction: On a hit, the Offset bits select the precise requested bytes out of the retrieved cache line to forward to CPU registers.

Practical Example

Consider a system with a 32-bit physical address space, a 32 KB total cache size, 64-byte line size, and 4-way set associativity:

• Offset: \(\log_2(64) = 6\text{ bits}\) (Bits \([5:0]\))
• Total Lines: \(32,768\text{ bytes} / 64\text{ bytes} = 512\text{ lines}\)
• Total Sets: \(512\text{ lines} / 4\text{ ways} = 128\text{ sets}\)
• Index: \(\log_2(128) = 7\text{ bits}\) (Bits \([12:6]\))
• Tag: \(32 - (7 + 6) = 19\text{ bits}\) (Bits \([31:13]\))

If the processor queries address 0x004A3F88 (0000 0000 0100 1010 0011 1111 1000 1000 in binary): * Tag (Bits 31–13): 0000 0000 0100 1010 001 (0x00251) * Index (Bits 12–6): 111 1110 (Set index 126) * Offset (Bits 5–0): 00 1000 (Byte offset 8)

The cache accesses Set 126, compares the 19-bit Tag against the tags in all 4 ways, and reads data beginning at byte offset 8 upon a match.