The Gateway to Computer Science Excellence
+8 votes

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?

  1. $24$ bits and $0$ bits
  2. $28$ bits and $4$ bits
  3. $24$ bits and $4$ bits
  4. $28$ bits and $0$ bits
in CO and Architecture by Veteran
edited by | 6k views
I got B as the answer
There is no index bits in associative cache...index bits will be 0
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

7 Answers

+31 votes
Best answer

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).

by Boss
edited by

@Shaik Masthan , whenever a proccess is created ->> its memory (Secondary or virtual memory) occupied space is cut into equal size page (happens to equal to frame size , becoz later it has to fit into PH. Memory's frame) ----> Associative cache has no specified place for any incoming page ----> Tag Bit may represent all the permutation of page address (Permuatation of Page address ) ---> 28 Tag bits which is absolutely fine.

My Question is :

Since the memory is Byte addressable so PC (or any other addressing mode) will always generate byte addressable address -> it has to refer one among 16 memory addressable block (of one page as well), So may I ask why the index (Block offset) is not 4 . Since no one said that before so it is quite apparent that I may be wrong , Pls correct me.



There are no index bits in a fully associative cache. The index bits are used to uniquely identify which set the block belongs. In a fully associative cache, all blocks are essentially part of the same set so we don't require index bits.

Is this offset field formula valid for all 3 types of Cache associativity?

I mean $\log (cache\;block\;size\;)$

Yes... but just remember to convert block size in terms of bytes before applying the formula.

For eg:- cache block is 4 W and size of each word is 2B. So bits for cache block size will be log(4*2) and not log(4).


Thanks, Man!



Here index field $0$, but what is index ield mean? Isnot index field means same as Tag bit??


In direct mapping,


Index field is used to find the line in which the cache block can be found. Then we go that cache line.

Tag bit tells which block of main memory is currently stored in a particular cache line.

In associative cache a block could be stored in any line of cache. So we need to check each line of cache.


Hence , we compare the tag bits of desired block with tag bits of each line and if it matches $\implies$ it is the line where the desired block is stored. Hence we don't require index bits.

+5 votes

In associative mapping there are no index field.

by Boss
+1 vote
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
by Junior
edited by
+1 vote

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

by Loyal
0 votes
index bit will be zero
edited by
0 votes
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
by Loyal
0 votes

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.           


Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,215 questions
60,022 answers
94,709 users