GATE CSE 2019 | Question: 1

Question

A certain processor uses a fully associative cache of size $16$ kB, The cache block size is $16$ bytes. Assume that the main memory is byte addressable and uses a $32$-bit address. How many bits are required for the Tag and the Index fields respectively in the addresses generated by the processor?

• A. $24$ bits and $0$ bits
• B. $28$ bits and $4$ bits
• C. $24$ bits and $4$ bits
• D. $28$ bits and $0$ bits

Comments

I think a is the correct answer. As fully Associative cahce do not have index bits. Its address structure is < TAG, WO>

---

As 32 bits physical address, 4 bits are for block offset and so there are 28 bits remaining for Tag

---

option D) as there are no index in fully associative cache.

Answer 1

Given that cache is Fully Associative.
$$\begin{array}{|c|c|} \hline
\textbf{Tag Bits}&\textbf{Block Offset}\\ \hline
28 & 4\\ \hline
\end{array}$$ There are no index bits in fully associative cache because every main memory block can go to any location in the cache $\implies$ Index bits $= 0.$

Given that memory is byte addressable and uses $32$-bit address.

Cache Block size is $16$ Bytes $\implies$  Number of bits required for Block Offset  $=⌈\log_216⌉ = 4 \text{ bits}$

$\therefore $ Number of Tag bits $= 32 - 4 = 28.$

Answer is (D).

Comments

@Rish9799 Bhai, please share some references to learn these architecture-related questions.

---

http://euler.ecs.umass.edu/ece232/pdf/15-Cache-11.pdf

You can watch Vishadeep’s Sir lecture too:

https://www.youtube.com/watch?v=vTsJ87JefgU

---

You can think #sets = 1 in case of fully associative cache. Hence no. of bits reqd. for Index (set offset) = $log(1) = log(2^0) = 0 bits$

Answer 2

In associative mapping there is no index field.

Answer 3

Fully Associative Cache has fields: Tag, Offset.

Direct Mapped Cache has fields: Tag, Line No., Offset

Set associative cache has fields: Tag, Set No., Offset

 

As you can see, in fully associative cache, there's no index field. Hence index bits = $0$.

Now, Offset = $4$ bits.

=> Tag $= 32 - 4 = 28$ bits.

 

Option D

Answer 4

In fully associative cache, the cache is organized into a single cache set and all cache lines are part of this set. Hence, we need 0 bits for set number field (index field) as there is only one set.

The address can therefore be effectively broken down into two fields only : tag bits field and offset field.

Since block size is 16 Bytes,

offset field  = $log_{2} (16)$ = 4 bits

Tag bits = Total address bits - offset bits

               = 32 - 4

               = 28 bits

So tag field bits = 28 and index field bits = 0

Option D is correct