3
\$\begingroup\$

When dealing with a fully associative cache, why is it necessary to use an offset (or word), if the entire cache is being searched anyway what will the offset do for you?

\$\endgroup\$
3
  • \$\begingroup\$ Could you give more context please? Where did you read about the offset? What cache are you talking about? I'm asking because it seems quite architecture dependent \$\endgroup\$
    – clabacchio
    Mar 4, 2012 at 14:19
  • 1
    \$\begingroup\$ It's from my textbook, you can see it here on page 328-329 \$\endgroup\$
    – David
    Mar 4, 2012 at 14:38
  • \$\begingroup\$ seems off-topic to me: should go on SO or another site dealing with software \$\endgroup\$
    – Jason S
    Apr 3, 2012 at 15:22

2 Answers 2

4
\$\begingroup\$

It's necessary because, as the text says, you copy an entire page in the cache when a specific value is required. A page consists in more bytes (32 if I'm correct), and accessing the single location in the cache line requires an address (the offset).

So, in the fully associative architecture, the block in the RAM can be mapped in each block of the cache, but still the single byte has to be addressed by the offset.

\$\endgroup\$
4
  • \$\begingroup\$ Maybe I'm misunderstanding something, but I thought that it is not accessing a single location using the address. Instead it is searching throughout the entire cache simultaneously comparing the tag bits... \$\endgroup\$
    – David
    Mar 4, 2012 at 14:49
  • \$\begingroup\$ I thought the tag is an identifier, to ensure that this is the right data and the word bit contains the offset. \$\endgroup\$
    – David
    Mar 4, 2012 at 14:56
  • \$\begingroup\$ @David I was wrong: look at page 328 for the picture. The Tag and Offset are different parts of the address, and the Offset is used for addressing the byte, while the Tag is a different thing (more significant bits of the Physical address) \$\endgroup\$
    – clabacchio
    Mar 4, 2012 at 15:00
  • \$\begingroup\$ @clabacchio is correct from my understanding. When we deal with caches we are using units of "blocks" - which are several bytes in size, but in a memory lookup, we are addressing to individual bytes. So the tag addresses to the block, while the offset addresses to the byte within the block. Eviction and writing into the cache is done at the block level. \$\endgroup\$
    – Jon L
    Apr 3, 2012 at 16:11
1
\$\begingroup\$

Why is the offset necessary for a typical cache?

A typical CPU cache is physically arranged something like this:

  • tag-bits byte byte byte byte byte byte byte byte byte byte byte byte byte byte byte byte
  • tag-bits byte byte byte byte byte byte byte byte byte byte byte byte byte byte byte byte
  • tag-bits byte byte byte byte byte byte byte byte byte byte byte byte byte byte byte byte
  • tag-bits byte byte byte byte byte byte byte byte byte byte byte byte byte byte byte byte
  • ... (many other rows omitted) ...
  • tag-bits byte byte byte byte byte byte byte byte byte byte byte byte byte byte byte byte

Each row, often called a "cache line" or "block", stores bunch of data byte values copied from some location in main memory, and also stores "tag-bits" that indicate which particular location in main memory that cache line came from. (In this example, each row holds 16 data byte values, and some tag-bits).

When the CPU wants to LOAD a byte value from some address, if you are lucky a copy of that value is already in the cache ... somewhere.

With a fully-associative cache, any cache line could have come from any location in memory, so the MMU has check all of them -- the tag-bits of each and every cache line -- to see which (if any) matches the address you're trying to load from. If you are lucky, you have a hit -- one of the cache lines has tag-bits that matches the tag-bits of the address the CPU is trying to LOAD, so the byte value you are trying to LOAD is somewhere in that cache line.

When people say a fully-associative cache means the MMU is "searching the entire cache", they really only mean the MMU is reading all the tag-bits and comparing them to the "tag-bits" part of the desired address. The MMU doesn't actually read any of the data bytes in the cache during that search.

For this example cache layout, when the CPU tries to load the byte at address ABCD1234, the MMU splits that address into the tag-bits "ABCD123" and the offset "4". If any of the rows of the cache has tag-bits ABCD123, matching the address, that cache line holds every byte value from address ABCD1230 through ABCD123F. So you are lucky -- the byte value you are trying to load is somewhere in that row.

The "offset" is the last part of the address the CPU is trying to LOAD -- in this example, the "4".

The offset is necessary to indicate which particular location in a cache-line holds the particular byte value the CPU is trying to LOAD.

Is the offset really necessary?

In principle, a person could design a cache such that each and every byte in the cache has its own tag-bits -- a cache with a cache-line size of 1 data byte. Such a cache wouldn't need an offset.

However, no one ever does it that way. Historically, people have spent a lot of time experimenting with different block sizes. They typically find that, for a given amount of money or area, a block size around 16 to 64 bytes performs the best. Spending the same amount of money or area on a cache designed with longer or shorter rows (in the extreme case, rows of 1 data byte) gives worse performance. (Asking "Why do cache block sizes that are "too short" or "too long" give worse performance?" would make an excellent separate question).

Over half the processors manufactured these days don't have any cache at all. Nowadays, whenever a processor does have cache, it nearly always has the cache and the MMU hard-wired onto the same chip as the CPU. In either case, it's not possible for a normal human to experiment with different block sizes. So today (unlike the situation a few decades ago) you're stuck with whatever block size some other person designed and baked into your CPU chip, a block size that is invariably larger than 1 byte and therefore needs an "offset".

on-topicness

I'm a little surprised that anyone would suggest this is a "software question" that is off-topic at the Electronics stackexchange. My understanding is that it's impossible to change the CPU cache-line-size with software, right?

Maybe if there existed a Computer Architecture & Organization site, this question would be off-topic here and on-topic there. But at the moment, here at Electronics seems to be the most on-topic place for this question.

Related:

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.