0
$\begingroup$

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!!

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So in the fully associative example, the tag is the block number which means that the cache index is 0 $\endgroup$ – TheMathNoob Nov 11 '16 at 22:57
  • $\begingroup$ "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." Is each block mapped to one "line" in the cache or one block in the cache?. What is tag used for? $\endgroup$ – TheMathNoob Nov 11 '16 at 23:26
  • $\begingroup$ Cache line is another term for cache block, the main memory is logically divided into equal sized blocks and cache into equal sized lines ( or blocks) such that a block size = line size. $\endgroup$ – Akash Mahapatra Nov 12 '16 at 0:05
  • 1
    $\begingroup$ In Direct mapping and Set Associative Mapping more than one blocks can be mapped to one line in cache. Tags are used to check which block is mapped to a line. $\endgroup$ – Akash Mahapatra Nov 12 '16 at 0:08
  • $\begingroup$ For the fully associative example, the number of cache lines is 2000 so if we consider a 16 way associative mapping then the number of sets is 2000/16=125. Therefore, the index is log2(125)=7 and the tag is 19 $\endgroup$ – TheMathNoob Nov 12 '16 at 2:19

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.