Question

What are the block tags and block indexes for the below 12-bit memory locations with 256-byte cache?
a. 0001 0110 1010, for 16-byte blocks with direct-mapped cache
b. 0010 0011 1011, for 4-byte blocks with 4-way associative cache

Answer 1

(a) 0001 0110 1010

memory width is 12-bits, cache size = 256 byte, block size = 16 byte and direct-mapped cache.

Block size = 16 bytes, to represent these 16 bytes we need 4 bits (2⁴ = 16 ). Therefore word index = 4 bits.

Total number of blocks in cache = cache size / block size = 256 bytes / 16 bytes = 16 blocks. To represent these 16 blocks we need 4 bits (2⁴ = 8).

Therefore block index = 4 bits.

Tag = total memory width - (block index + word index) = 12 - (4+4) = 12 - 8 = 4 bits.

Tag	block index	word index
4 bits	4 bits	4 bits

Therefore tag index from question (a) is 0001 (From MSB side)

Block index is 0110.

(b) 0010 0011 1011

Given that memory is 12- bit long, cache size = 256 bytes, block size = 4 bytes and 4 way set associative cache.

Block size = 4 bytes, to represent these 4 bytes we need 2 bits (2² = 4). Therefore word offset = 2 bits.

Total number of blocks = cache size / block size = 256 bytes / 4 bytes = 64 blocks, and the cache is 4 way set associative which means each set consist of 4 blocks.

Therefore total number of sets = total number of blocks / set size = 64 blocks / 4 blocks = 16 sets. To represent these 16 sets we need 4 bits ( 2⁴ = 16 ).

Tag = total memory width - (set offset + word offset) = 12 - (4+2) = 12 - 6 = 6 bits.

Tag	Set(block) index	Word index
6	4	2

Therefore tag part = 0010 00 (start from MSB part)

set(block) index = 1110