Cache Addressing: Length of Index, Block offset, Byte offset & Tag?

Question

Let's say I know the following values:

W = Word length (= 32 bits)
S = Cache size in words
B = Block size in words
M = Main memory size in words

How do I calculate how many bits are needed for:

- Index
- Block offset
- Byte offset
- Tag

a) in Direct Mapped Cache b) in Fully Associative Cache?

Solution

The address may be split up into the following parts:

[ tag | index | block or line offset | byte offset ]

Number of byte offset bits

0 for word-addressable memory, log₂(bytes per word) for byte addressable memory

Number of block or line offset bits

log₂(words per line)

Number of index bits

log₂(CS), where CS is the number of cache sets.

• For Fully Associative, CS is 1. Since log₂(1) is 0, there are no index bits.
• For Direct Mapped, CS is equal to CL, the number of cache lines, so the number of index bits is log₂(CS) === log₂(CL).
• For n-way Associative CS = CL ÷ n: log₂(CL ÷ n) index bits.

How many cache lines you have got can be calculated by dividing the cache size by the block size = S/B (assuming they both do not include the size for tag and valid bits).

Number of tag bits

Length of address minus number of bits used for offset(s) and index. The Length of the the addresses can be calculated using the size of the main memory, as e.g. any byte needs to be addressed, if it's a byte addressable memory.

Source: http://babbage.cs.qc.edu/courses/cs343/cache_parameters.xhtml