Address Breakdown: Tag, Index, and Offset

A cache is organized as an array of lines (also called sets in a direct-mapped cache, since each set holds exactly one line), each line holding a fixed-size block of contiguous bytes copied from main memory. When the CPU issues a memory address, hardware must answer three questions using only bit-slicing — no multiplication, no memory access, no loop — because this has to complete inside cache-access time. The address is partitioned, from least-significant to most-significant bit, into three contiguous fields:

• Block offset: the low-order bits that select a specific byte (or word) within a block. Its width is fixed by block size: a block of $B$ bytes needs $\log_2 B$ offset bits, because that many bits are exactly enough to enumerate $B$ distinct byte positions.
• Index: the next bits up, which select which line (in a direct-mapped cache) or which set (in a set-associative cache) the block should live in. Its width is $\log_2(\text{number of sets})$.
• Tag: all remaining high-order bits. The tag is stored alongside the data in the cache line and is compared against the incoming address's tag bits to confirm this is actually the block we think it is, not some other block that happens to map to the same index.

The key structural fact is that index selects a location, tag confirms identity. Two different memory blocks can share the same index (they must — there are vastly more possible blocks than there are cache lines) so the tag exists precisely to disambiguate that inevitable collision. A cache hit occurs only when the valid bit is set and the stored tag equals the incoming tag; the index merely got you to the right shelf, the tag confirms it's the right book.

Computing the split is a small, deterministic procedure driven by three geometric parameters: total address width $A$ (in bits), cache capacity $C$ (bytes of data storage), and block size $B$ (bytes per line). For a direct-mapped cache, associativity is 1, so:

``` FUNCTION AddressBreakdown(AddressWidth A, CacheSize C, BlockSize B): // Step 1: number of blocks the cache can hold (= number of lines, // since this is direct-mapped: 1 line per set) NumLines := C / B ASSERT NumLines is a power of two // required for clean bit-slicing ASSERT B is a power of two // Step 2: offset field width OffsetBits := log2(B) // Step 3: index field width IndexBits := log2(NumLines) // Step 4: tag field gets whatever bits remain TagBits := A - IndexBits - OffsetBits ASSERT TagBits >= 0 // sanity check: fields must fit RETURN (TagBits, IndexBits, OffsetBits)

FUNCTION Decompose(Address, TagBits, IndexBits, OffsetBits): Offset := Address[0 : OffsetBits-1] // low bits Index := Address[OffsetBits : OffsetBits+IndexBits-1] // middle bits Tag := Address[OffsetBits+IndexBits : A-1] // high bits RETURN (Tag, Index, Offset)

FUNCTION CacheLookup(Address, Cache[NumLines]): (Tag, Index, Offset) := Decompose(Address, ...) Line := Cache[Index] IF Line.valid AND Line.tag == Tag: RETURN HIT, Line.data[Offset] ELSE: RETURN MISS ``` Every step is a bit-slice or a `log2` of a power-of-two quantity — both O(1) operations realizable directly in wiring (address lines physically route to the tag-comparator, the set decoder, and the output multiplexer with no arithmetic unit involved). The two `ASSERT`s in `AddressBreakdown` are not defensive programming flourishes; they encode the real design constraint that block size and line count must be powers of two, precisely so that the field boundaries fall on fixed bit positions rather than requiring a division or modulo circuit at access time.

Reading the figure: the index field is decoded to select exactly one row of the cache array (a wire per possible index value, or a small decoder), the tag field feeds into a comparator wired to that row's stored tag, and the offset field drives a multiplexer that picks the right byte out of the 32-byte block once a hit is confirmed. All three happen in parallel — that parallelism, enabled entirely by the fixed positional split, is why a cache lookup fits in one cycle.

Time complexity of the breakdown itself: computing the three field widths from $(A, C, B)$ is $O(1)$ — three `log2` evaluations of quantities known at design time, done once when the cache is designed, not per-access. At run time, decomposing an actual address into its tag/index/offset values is also $O(1)$: it is pure bit-slicing (selecting fixed ranges of an already-available bit vector), which in hardware is just wiring — zero gate delays, unlike an ALU operation. This is precisely why powers-of-two sizing is mandatory: a non-power-of-two block size would force a division or modulo circuit into the critical path of every memory access, which is far slower than routing wires.

Space: no extra space is used by the decomposition; the fields are views into the existing address bits. The cache's own space is $O(\text{NumLines} \times (\text{TagBits} + \text{ValidBit} + B \cdot 8))$ bits, but that is cache storage, not decomposition cost.

Correctness argument. The claim to justify is: the tag/index/offset split, computed as above, produces a decomposition where (a) every valid address maps to exactly one (tag, index, offset) triple, (b) the mapping is invertible, and (c) two addresses collide in the same cache line if and only if they share the same index.

• (a) Totality and (b) invertibility. Because offset, index, and tag are defined as three disjoint, contiguous, exhaustive bit ranges of the address — $[0, \text{OffsetBits})$, $[\text{OffsetBits}, \text{OffsetBits}+\text{IndexBits})$, and the remaining high bits — every bit of the address belongs to exactly one field. Concatenating $(\text{Tag}, \text{Index}, \text{Offset})$ back together, in that order, reconstructs the original address bit-for-bit. This is just the standard fact that any bit-string of length $A$ can be uniquely partitioned into contiguous sub-strings of lengths summing to $A$; here $\text{TagBits} + \text{IndexBits} + \text{OffsetBits} = A$ by construction (Step 4 of the algorithm defines TagBits as exactly the remainder).

• (c) Collision iff same index. By definition, the cache places a block at row `Index` of the array. Two addresses $x, y$ with $\text{Index}(x) = \text{Index}(y)$ but $\text{Tag}(x) \neq \text{Tag}(y)$ are mapped to the same physical line, so loading $y$ after $x$ evicts $x$'s block — this is the direct-mapped conflict the tag exists to detect (via the stored-tag comparison at lookup, per `CacheLookup` above). Conversely, if $\text{Index}(x) \neq \text{Index}(y)$, the two addresses occupy different array rows and cannot conflict. This establishes the index field is both necessary and sufficient to determine placement, matching the direct-mapped invariant: "line number = index; block currently resident there is identified by its stored tag."

• Offset correctness follows from $B = 2^{\text{OffsetBits}}$: the offset field ranges over exactly $\{0, \dots, B-1\}$, so it can address every byte in the block and no more, with no wasted or insufficient bits.

Honest tradeoffs. This scheme is only correct/optimal under the powers-of-two assumption; a cache with a non-power-of-two number of lines or block size cannot use pure bit-slicing and loses the O(1)-in-hardware property. Increasing index bits (more lines, same total capacity ⇒ smaller blocks, or more capacity at fixed block size) reduces conflict misses but shrinks the tag field is unaffected in this trade — rather, more lines at fixed capacity means smaller blocks and worse spatial locality exploitation. Increasing offset bits (bigger blocks) improves spatial locality reuse but increases miss penalty (more bytes to fetch on a miss) and, at fixed capacity, reduces the number of lines, which increases conflict misses. These tensions are exactly what motivates moving to Set-Associative Caches, where the index selects a set of several candidate lines rather than a single line, trading some of this rigidity for fewer conflict evictions at the cost of needing several parallel tag comparators.

Consider a direct-mapped cache with:

• Address width $A = 32$ bits
• Cache size $C = 8\text{ KiB} = 8192$ bytes
• Block size $B = 32$ bytes

Step 1 — number of lines:

Step 2 — offset bits:

Step 3 — index bits:

Step 4 — tag bits:

Sanity check: $19 + 8 + 5 = 32$ ✓ — matches the figure above. Now trace a concrete address. Take the byte address `0x00001A34`, written in binary (32 bits): ``` 0000 0000 0000 0000 0001 1010 0011 0100 ``` Splitting from the low bit:

So this address is checked against line 137 of the cache. If line 137's valid bit is set and its stored tag equals `0` (19 bits of zero), this is a hit, and the data returned is byte 20 of that line's 32-byte block. If the stored tag differs — say the line currently holds a block with tag `5` because some other address that also indexes to 137 was accessed more recently — this is a miss, and the cache must fetch the 32-byte block containing `0x00001A34` from the next level of the memory hierarchy, evicting whatever was in line 137. Now contrast with a second address, `0x00003A34`: ``` 0000 0000 0000 0000 0011 1010 0011 0100 ```

This address has the same index (137) and the same offset (20), but tag bits [31:13] now read `0000000000000000010` = value 2, differing from the first address's tag of 0. These two addresses collide in the cache: whichever was accessed most recently occupies line 137, and accessing the other forces an eviction — exactly the conflict-miss behavior the correctness argument above predicts, and exactly why the tag field must be compared on every access rather than trusted implicitly.

The tag/index/offset decomposition is not attributed to a single inventor; it emerged as engineers built the first cache memories to bridge the growing speed gap between processors and main memory. The foundational conceptual leap — a small, fast associative memory automatically holding recently used data from a larger, slower store — traces to early work on associative memory and virtual memory management in the 1960s.

Every general-purpose processor built today — from smartphone application processors to server-class CPUs — decomposes physical or virtual addresses into tag/index/offset fields at every L1, L2, and L3 cache access, millions of times per second. Compiler writers exploit knowledge of index-field width when reasoning about cache-conscious data layout: choosing array strides that avoid mapping hot data structures to the same small set of index values, which would otherwise thrash a direct-mapped or low-associativity cache. Operating-system designers rely on the same bit-slicing principle when implementing page tables and TLBs (translation lookaside buffers), which are themselves small associative caches indexed by virtual page number. Hardware description languages (Verilog/VHDL) implementing real cache controllers literally instantiate wires at exactly these bit positions — the "arithmetic" described here is, in silicon, just a choice of which address pins connect to which decoder and comparator inputs. Understanding this decomposition is also the direct prerequisite for reasoning about Set-Associative Caches (where the index selects a set of candidate lines checked in parallel) and for computing Cache Performance and Average Memory Access Time, since hit rate — and therefore average latency — depends directly on how index-field collisions distribute real program addresses across cache lines.

Ask the tutor: How does the tag/index/offset split change once a cache becomes set-associative instead of direct-mapped?