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

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.

---

Option D is correct

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

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$

---

seems like you are trying to prove everthing even though it does not need😀

.

Answer 2

In associative mapping there is no index field.

Comments

good explaination

 

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

Answer 5

In fully associative cache, search for a block is simultaneously done for all entries based on the Tag.

So no need for indexing ( neither set nor line no).

Total size, tag bits + block offset bits = 32

Block size = 16 B = $2^4$B

So we require 4 bits to address a block. Thus, tag bits = 32 - 4 = 28

Ans D) 28 and 0 bits

Answer 6

fully associative Cahe:  it contains 

                                        

tag	block offset

block size =16Byte

no of bit required to represent block size is  4 bit [2^4]

and physical address size given is 32 bits

therefore, tag bit =32-4=28 bits 

                index field bit=0 bit bz there is no concept of index field in  fully associative cache.