The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+2 votes

Common Data For Questions 1 and Question 2 

Direct Mapping cache given below 

17-tag | 10-block | 5-word , 2 to 1 MUX / OR  has latency of 0.6ns ,k-bit comparator has katency of k/10 ns

Question 1 

If a two- way set associative cache is constructed from the given directmapped cache then the ratio of hitlatency of directmapped cache to 2-way set associative cache would be ___________

Question 2 
Number of MUX/OR  and Compators Needed in Direct Mapped Cache (#MUX/OR , Comparator) are 

  1.  (1,17)
  2. (17,1)
  3. (1024,1)
  4. None
asked in CO & Architecture by Active (1.9k points)
retagged by | 383 views
a) 0.7

b) d (20, 1)
Can you explain your answer ?

2 Answers

+3 votes

Solution to 1st part :

Given ,

No of bits for tag  =  17

No of bits for block = 10

No of bits for offset = 5

So this is for direct mapped..We know 

In direct mapped we do not need multiplexer as no of ways in each set = 1 

So only hit only will be due to tag comparator only..

Given latency due to k - bit comparator = k / 10  =  17 / 10  = 1.7 ns

Now for set associative ,

No of sets = No of lines (blocks) / Associativity

                = 1024 / 2 

                = 512

Hence set bits = log2 512   =  9 

As block size remains the same in either case , so the one bit which has been decreased due to formation of sets becomes part of tag field..

So no of tag bits now = 17 + 1  = 18

So latency due to comparator  =  1.8 ns

  Latency due to mux   =  0.6 ns

So total latency of given 2 way set assocative cache  =  2.4 ns

So ratio of hit latency of direct to set assocative cache  =  1.7 / 2.4  

                                                                                  =  0.708 correct to 3 decimal places

answered by Veteran (100k points)


Check the use of multiplexers in direct mapped cache and set associative cache:


Now, we calculate delay for direct mapped cache.

We need 32 X 1 mux which can be obtained using 2 X 1 MUX by having  total of 32+31=63 MUX

This will comprise 5 levels of MUX.

So, delay due to MUX's = 5 * delay of each MUX  (since every MUX at each stage would give output almost at the same time)

                                          = 5 * 0.6

                                          = 3 ns

Delay due to comparators = 1.7 ns

So, total delay = 3 + 1.7 = 4.7 ns


Now, we calculate delay for set associative cache

We need 2    32 X 1 MUX's since we have 2-way set associative cache.

So, delay due to MUX's = delay of single 32 X 1 MUX   formed using 2 X 1 MUX's (since both the MUX's will give output at same time)

                                          = 3 ns

Delay due to comparator = 1.8 ns

So, total delay = 3 + 1.8 = 4.8 ns


So, required ratio = $\frac{4.7}{4.8}$ = 0.97

Also, MUX's required for Direct mapped cache = 63

@sushant,you said muliplxer will be 32 X1 but multilpxer takes input from each line in direct cache,so its size should be 1024'nt it?

and number of multiplexers is equal to number of tag bits

you can refer this video also

@Akriti. Both the things are right. The pdf by MIT uses decoder instead of mux. But your answer matches with options. So, will go with that. Thanks.
Could you also paste the link for set associative mapping hardware implementation? I'm mot getting.
Plz also tell how it would work for set associative cache.
I think the MUX configuration would be same i.e. 1024*1 but the tag bits increase to 19.

So, 19 multiplers of 1024 * 1 configuration for set associative right?
Or would it be 256*1 mux to get the set and 19 mux of 2*1 configuration?
@sushant,for direct mapped cache..17 (1024x1 )MUX will be required because number of tags bits are bit from each line to one multiplexer..but the problem is here we are given that we have to use 2x1 mux only,so it would be like 512,256,128,64,32,16,8,4,2,1 i.e 10 levels of MUX,and further we have to take care of number of multiplexers cording to tags bits as well..which i am not understanding

for set associtive,there is no video for which there is a video by him in which he is explaining about the MUX part,but yes,since now in set associtive,each set will give a entry to the MUX,so i think its configuration should be 512x1 and again,number of MUX should be 18 here as 18 bits are there for tag in set associtive..

BUT i am not sure about set associtive part.

further no option is matching
sushant,there are 9 bits for set now,pls check and 18 bits for tag

For Direct mapped, you are right.

17 multiplexers of 1024*1 configuration.

Now, 1024*1 can be constructed from 2*1 by 10 levels of mux. So, 10*(delay of each mux) is the delay for 1024*1 mux.

Now, all these 17 mux work in paralellel. So, we consider delay of only single 1024*1 mux.

So, delay of 1024*1 mux = 10*(delay of each 2*1 mux) = 10*0.6ns = 60ns

delay due to comprator = 17/10 ns = 1.7 ns

So, hit latency = 60ns + 1.7 ns = 61.7 ns


For set associative , even I am not sure how it works.

0 votes
no. of mux is 17

size of mux is 10(10X1) which is not possible it will be 16X1

but 2X1 MUX is used so no. of mux17X15

and no of comparater is always 1 in direct mapping
answered by Active (1.2k points)
What is the number of max actually ? 17 or 17X15 ?   Moreover  Please explain How are you getting theses values ?

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
49,540 questions
54,099 answers
71,006 users