Understanding Cache Mapping and Access (Computer Architecture)

Question

Consider a 512-KByte cache with 64-word cachelines (a cacheline is also known as a cache block, each word is 4-Bytes). This cache uses write-back scheme, and the address is 32 bits wide.

Answer the next questions for Direct Mapped cache, Fully Associative and Way Set Associative

What is the size in bits of the cacheline offset, cachline index and tag?

What I know:

Direct mapped caching allows any given main memory block to be mapped into exactly one unique cache location.

Set-associative mapped cache allows any given main memory block to be mapped into two or more cache locations.

Fully-associative mapped caching allows any given main memory block to be mapped into any cache location.

I don't know how that would make a difference in computing byte offset, index and cache

$Byte offset=log_2(\text{bytes in one cache block})$ $Index=log_2(\text{Number of cache blocks in the cache})$
tag: The rest of bits in the address

Attempt at a solution

I would do the mapped cache part by using the previous expressions. I don't want the answer, but I would like orientation.

Thanks!!

Answer 1

Any physical address consists of two parts : one part is the block offset and the other part is the block number.

Physical Address { Block number, Block Offset}

Block Number has further 2 parts : the index part and the tag.

The memory is assumed to be logically divided into many blocks. A block may contain more than one words in it ( which is indicated by the block size ). To reach to a specific word block offset is used.
Block offset is the number of bits required to address each word in the memory.

For instance, in a byte addressable system ( 1 word = 1 byte ) if the block size = 1 KB then
Block Offset = 10 bits. (Byteoffset=log2(bytes in one cache block)

The block offset remains same in each type of mapping as the number of words in each block do not change.

The implementation of block number is different in different mappings.

In case of Direct mapping the block number has two parts:

block no { tag, line number}

Since each block is mapped to one line in the cache, the "line number" part of block number contains number of bits required to identify each line in the cache.
In this case since cache size = 512 KB and block size = (64 * 4)B = 256 B
The Number of lines in the cache = 512 KB / 256 B = 2 K = 2 ^ 11
Therefore, the number of bits in line number part will be 11.
The remaining bits are tag bits.

Fully Associative Mapping the tag number is same as the block number .
In Fully Associative Mapping any memory block can be mapped to any of the cache lines. So to check which line of the cache a particular block is mapped to every line number is "tagged".

And in Set Associative Mapping the block number is divided into two parts:

block no { tag, set number}

Here, the cache is divided into many sets, so the "set number" part consists of the number of bits required to identify each set uniquely.
Depending on the number of lines in each set ( a K-way set associative mapping will contain K lines in each set), the number of sets can be found out.

Hope this will help you.