Split a cache address into tag, index and offset

If you can read a hexadecimal pointer but find cache diagrams confusing, start with one fully specified cache. An address does not arrive with a universal tag field already attached. The cache’s capacity, line size, associativity and indexing rule determine which address bits serve each purpose.

We will use a deliberately small model: 16-bit byte addresses, 1,024 bytes of cached data, 16 bytes per line and direct mapping. Every requested byte has exactly one candidate cache line. The examples classify reads in a Python model; they do not measure a processor, fetch memory contents or predict access latency.

Derive the fields from the geometry

A byte address names one byte, so a 16-byte line contains sixteen consecutive addresses. Four bits select a byte within that line because two raised to the fourth power is sixteen. These low four bits are the byte offset. They are not an index into sixteen cache lines.

Dividing the data capacity by the line size gives 1,024 / 16 = 64 lines. Direct mapping provides one line per set, so there are sixty-four sets. Six address bits select a set. The remaining six bits identify which memory block currently occupies that set. Those are the tag bits: sixteen address bits minus four offset bits minus six index bits.

The mapping uses the lowest four bits for offset, the next six for index and the upper six for tag. This is the ordinary contiguous-bit rule declared for this example. In Chris Terman’s Computation Structures cache lecture, the direct-mapped examples similarly select one candidate line, then compare its stored tag and check its valid bit. Our dimensions differ from the lecture’s worked caches.

Capacity here counts data bytes. It does not include tags, valid bits or other implementation storage. Also, “six tag bits” describes our sixteen-bit address space. Applying that width to a wider physical address without recalculating it would discard information needed to distinguish memory blocks.

Split one address, then reconstruct it

Take byte address 0x3A6D, decimal 14,957. Its sixteen binary digits split as 001110 | 100110 | 1101. The fields are tag fourteen, index thirty-eight and offset thirteen. The selected set is thirty-eight; offset thirteen chooses a byte inside whichever sixteen-byte block is being requested.

Clear the offset bits to find the requested block’s base, 0x3A60. Its final byte is 0x3A6F. The cache does not round the request to the nearest line: it selects the aligned block containing that address. In particular, 0x3A6F stays in the same block even though it is adjacent to 0x3A70.

View full-size image ↗

The fields also reconstruct the original address. Shift the tag left ten bits, the index left four bits, then combine those values with the offset. Their bit ranges do not overlap. Numerically, fourteen times 1,024 plus thirty-eight times sixteen plus thirteen equals 14,957. Reconstruction is a useful debugging check because extracting plausible-looking fields is insufficient if one bit was dropped or assigned twice.

The pinned gem5 set-index implementation performs the same kind of shift-and-mask selection and reconstructs an aligned block address from a tag and set. Its base indexing policy derives the number of sets from the number of entries and associativity. These are inspected implementation examples; the following Python code does not run gem5.

The index selects a candidate, not a guaranteed hit

Address 0x3E6D is exactly 1,024 bytes above 0x3A6D. It has the same offset and index, but tag fifteen instead of fourteen. Both requested blocks compete for set thirty-eight. There is room for only one of them there, even if every other set is empty.

A hit requires the selected line to contain valid data and have the requested tag. An empty line whose tag-storage bits happen to be zero must not falsely satisfy a request for tag zero. The model represents an invalid line with None; an actual hardware valid bit performs the corresponding distinction.

Run this Python 3 block. Each trace starts with all lines invalid and fills the entire requested line immediately after a miss. There are no writes, prefetches, invalidations or outstanding requests. Only tags are stored, so this model classifies requests without implementing a memory-data return path.

def split(address):
    if type(address) is not int or not 0 <= address < 65536:
        raise ValueError("address must be a built-in 16-bit unsigned integer")
    return address >> 10, (address >> 4) & 63, address & 15


def trace(addresses):
    tags = [None] * 64
    rows = []
    for address in addresses:
        tag, index, offset = split(address)
        hit = tags[index] is not None and tags[index] == tag
        tags[index] = tag
        rows.append((f"{address:04X}", tag, index, offset,
                     "hit" if hit else "miss"))
    return rows


addresses = [0x3A6D, 0x3A6E, 0x3E6D, 0x3A6D, 0x3A70, 0x3A6F]
assert split(0x3A6D) == (14, 38, 13)
assert (14 << 10) | (38 << 4) | 13 == 0x3A6D
rows = trace(addresses)
assert [row[-1] for row in rows] == ["miss", "hit", "miss", "miss", "miss", "hit"]
assert [row[-1] for row in trace([0, 1])] == ["miss", "hit"]
print(*rows, sep="\n")

The first request fills set thirty-eight with tag fourteen. The next request hits because 0x3A6E is another byte in that same block. The third request replaces the line with tag fifteen, and the fourth replaces it with tag fourteen again. Returning to a recently requested byte can therefore miss; recency alone does not reserve its cache slot.

The fifth request, 0x3A70, selects set thirty-nine and leaves set thirty-eight untouched. The sixth request, 0x3A6F, consequently hits. Four misses and two hits describe exactly these six logical byte requests. They do not specify cycles, transferred bus beats or performance for a real load instruction stream.

View full-size image ↗

The two alternating blocks occupy just thirty-two bytes of the address space, yet conflict in this 1,024-byte cache. Comparing working-set size with total capacity misses that placement constraint. The index mapping matters as well as the number of cached bytes.

A multi-byte access can touch two blocks

Suppose software asks for four bytes starting at 0x3A6E. The addresses are 0x3A6E, 0x3A6F, 0x3A70 and 0x3A71. The first two belong to the block at 0x3A60; the last two belong to the block at 0x3A70. Looking only at the starting address would overlook the second block.

This helper, run after the first block, returns all block bases touched by a positive-length byte interval. It rejects an interval that extends beyond the declared address space instead of silently wrapping it to address zero.

def span_blocks(address, count):
    split(address)
    if type(count) is not int or count < 1:
        raise ValueError("count must be a positive built-in integer")
    if address + count > 65536:
        raise ValueError("the byte interval leaves the address space")
    first = address // 16 * 16
    last = (address + count - 1) // 16 * 16
    return tuple(range(first, last + 16, 16))


assert span_blocks(0x3A6E, 4) == (0x3A60, 0x3A70)
assert span_blocks(0x3A60, 16) == (0x3A60,)
assert span_blocks(0x3A60, 17) == (0x3A60, 0x3A70)
assert span_blocks(0xFFFF, 1) == (0xFFF0,)
print([f"{base:04X}" for base in span_blocks(0x3A6E, 4)])

This is address accounting, not an instruction-set guarantee. Whether an unaligned four-byte instruction is supported, how it is split internally and whether it is atomic require separate architectural rules. Endianness determines how those bytes contribute to a multi-byte value; it does not change the set of byte addresses in this interval.

Change a parameter without carrying over stale fields

Tags and validity cost storage. Our sixty-four lines require sixty-four times seven bits for a six-bit tag and one valid bit: 448 bits, or fifty-six bytes. Adding the 1,024 data bytes gives 1,080 bytes of abstract bit storage. This excludes error correction, write-policy state, coherence state and physical circuit overhead; it is not a chip-area estimate.

Keep capacity and line size fixed but choose two-way associativity. There are still sixty-four lines, now divided into thirty-two sets with two candidate lines each. The offset remains four bits, the index becomes five bits and the tag becomes seven bits. Reusing the direct-mapped six-bit index would describe a different cache. Choosing a victim among multiple candidates is another policy, absent from our one-candidate model.

For practice, exhaust all 65,536 addresses and verify extraction followed by reconstruction. Then change the line size to thirty-two bytes while keeping this direct-mapped cache’s data capacity fixed. Predict the new field widths before editing any masks: five offset bits, five index bits and six tag bits. The conflict distance remains 1,024 bytes under this declared mapping, but each resident block covers twice as many neighboring bytes.

Use this arithmetic to reason about a stated cache design or a controlled trace. Before applying it to a particular processor, establish which address domain and indexing rule that cache actually uses. A virtual pointer alone does not establish the physical tag, and a cache with a different indexing function need not follow these contiguous fields.