Tag and Offset

1Learning Outcomes¶

Given a cache, where do we place new lines from memory? We first discuss the most flexible policy, which is also the most challenging to implement in hardware.

2Tag and Offset¶

Recall from earlier:

How do we keep track of address(es) associated with data in a cache line? We note that because the bytes in each line of data are from the same part of memory, their address will share a common set of upper bits (called a tag) and vary in their lower bits.

We therefore store tags with each line in our fully associative cache. In Figure 1, the bytes in the first cache line share the same upper 0x10F tag as the byte with address 0x43F.

For all caches:

• P&H 5.3: “A tag is a field in a table used for a memory hierarchy that contains the address information required to identify whether the associated [line] in the hierarchy corresponds to a requested [word or byte].”

• All bytes in a cache line have different memory addresses (because memory is byte-addressable) that share the same tag associated with the line. They vary in the lower bits of the address, called an offset.

• All bytes in a line (typically sized to a power of two) should be “addressable” by the bits in the offset.

3Fully Associative Caches: Determining Cache Hit¶

For fully associative caches^[1]:

• The process of referring to memory by addresses tags effectively organizes memory into chunks equivalent to the line size.

• The line size and cache size are sufficient to determine how an address can be split into two bitfields representing the tag and offset, respectively.

To summarize, for fully associative caches, we can check for a cache hit for a given address as follows:

1. Build tag and offset from the memory address by splitting it into two fields:

   • Tag: upper bits of address

   • Offset: byte offset within cache line

2. In a fully associative cache, check the tag of every line.

3. Cache Hit If a cache tag matches the provided tag, retrieve the byte with the given offset.