search
Log In
14 votes
9.1k views

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
edited by
9.1k views
1
I got B as the answer
5
There is no index bits in associative cache...index bits will be 0
1
I think a is the correct answer. As fully Associative cahce do not have index bits. Its address structure is < TAG, WO>
1
As 32 bits physical address, 4 bits are for block offset and so there are 28 bits remaining for Tag
0
option D) as there are no index in fully associative cache.

7 Answers

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


edited by
1

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

1

@dr_Jackal

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.

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

I mean $\log (cache\;block\;size\;)$
1
@JEET

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

@Satbir

Thanks, Man!

0

@Satbir

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

2

In direct mapping,

TAG INDEX OFFSET

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.

TAG OFFSET

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.

7 votes

In associative mapping there are no index field.

4 votes

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

2 votes
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

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

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.           

0 votes
index bit will be zero

edited by
Answer:

Related questions

29 votes
9 answers
1
8.3k views
A certain processor deploys a single-level cache. The cache block size is $8$ words and the word size is $4$ bytes. The memory system uses a $60$-MHz clock. To service a cache miss, the memory controller first takes $1$ cycle to accept the starting ... bandwidth for the memory system when the program running on the processor issues a series of read operations is ______$\times 10^6$ bytes/sec
asked Feb 7, 2019 in CO and Architecture Arjun 8.3k views
22 votes
3 answers
2
6.4k views
The chip select logic for a certain DRAM chip in a memory system design is shown below. Assume that the memory system has $16$ address lines denoted by $A_{15}$ to $A_0$. What is the range of address (in hexadecimal) of the memory system that can get enabled by the chip select (CS) signal? C800 to CFFF CA00 to CAFF C800 to C8FF DA00 to DFFF
asked Feb 7, 2019 in CO and Architecture Arjun 6.4k views
15 votes
7 answers
3
6.2k views
The expenditure on the project _____ as follows: equipment Rs.$20$ lakhs, salaries Rs.$12$ lakhs, and contingency Rs.$3$ lakhs. break down break breaks down breaks
asked Feb 7, 2019 in Verbal Aptitude Arjun 6.2k views
5 votes
6 answers
4
3.6k views
The search engine’s business model ____ around the fulcrum of trust. revolves plays sinks bursts
asked Feb 7, 2019 in Verbal Aptitude Arjun 3.6k views
...