retagged by
6,682 views
22 votes
22 votes

Cache 1

Direct Mapping

  17 tag

 10 block

5 word

 

Cache 2

Set Assosicative  2- way associative
 

18

9

5

Cache 3


Associative Cache

  27

  5


 

  1. Calculate Hit Latenncy in Each of Three Cache Memory if
  • 2 to 1 MUX / OR  has latency of 0.6ns
  • k-bit comparator has katency of k/10 ns

      2.How much number of MUX / OR ? camparators are used in each of three

retagged by

3 Answers

Best answer
13 votes
13 votes
First of all what has a multiplexer and comparator have to do in a cache? Lets see:

In a cache memory implementation we allow a set of main memory frames to be mapped to a particular cache entry. So, once we reach an entry in cache we also need to know which 1 of the $n$ possible entries is currently being present there. For this purpose we use tag bits. And we need $\log n$ bits for this and we also needs to compare all these bits using a comparator to ensure "cache hit". So, in a direct mapped cache, first we index to an entry using index bits and then compare the tag bits. So, we can solve case 1 here:

The second part - 10 bits for block is used for indexing. The final part is offset within a cache entry and is not relevant for this question. So, hit latency will be

Cache indexing time (lets assume negligible as no data given in question) + Tag comparison time

$= 17/10 = 1.7 ns $

PS: Actually this is the time till we identify a cache hit. After this we have to decide which word in the block is requested, which requires a 32-1 MUX here as word bits are 5. (this is why usually offset bits is power of 2)

For direct mapped entry we assumed that each cache entry can hold a single cache block. But this changes in a set-associative cache and with a 2-way set, each cache entry can hold 2 cache blocks. i.e., after indexing to a cache, we have to compare the tag bits of 2 entries. But this comparison can be done in parallel and result be multiplexed. We also need an OR gate to determine the output of tag comparison for 2 set entries. The tag comparison result of the entries serve as select lines to the MUX. So, here hit time

$ = 18/10 + 0.6 + 0.6 = 3.0 ns$

A fully associative cache means we do not need to index and all entries goes to a single slot. So, we need to compare the tag bits of all the cache entries to determine a hit and then has to multiplex this output. Hit time

$ = 27/10 + x$

I used $x$ because here we need 1024-1 multiplexer as we had used all 10 block bits - which gives 1024 entries in a set. Can we get this time from 2-1 multiplexer? We can but not doing the calculation here.

Reference: https://courses.cs.washington.edu/courses/cse378/09au/lectures/cse378au09-19.pdf
edited by
7 votes
7 votes

Need verification from Arjun Sir,

For (A)Direct Mapped Cache:

So, hit latency comes to be Line decoding time(Assume 0 if not given) +Tag comparison time+AND GATE delay.

AND gate delay is not given so assume it to be zero, Hit time=$\frac{17}{10}=1.7ns$

Since other delays which were present, but assumed to be zero(either not given or told to be zero), the cache hit time must be atleast 1.7ns here should be the correct way to say this.

(B)Set Associative cache design:

 So, here we can see that after the Tag comparison is done, and assuming AND gate delay to be zero, we see that the multiplexor uses the lines of the tag comparison result as it's input to decide which one of the block of the set must be selected. So, After TAG comparison is done, MUX and the or gate can produce the result in parallel.

Also, note that the set decoding time if given is to be taken into account while calculating hit time.

So, here Cache hit time=$1.8(tag)+0.6(\,or\,+MUX\,delay\,in\,parallel)=2.4ns$ (Remember cache hit time is atleast this).

(C)Associative Cache: So, here my cache has $2^{10}$ lines and each tag has 27 bits. So, for all $2^{10}$ lines, the tag comparison will be done in parallel and this will take $2.7ns$. After this, we will have 1024 lines of tag comparator output. Since now we need to select 1 block out of 1024, we need the functionality of a 1024X1 MUX. But we have only 2X1 MUX.

So, my 1024x1 MUX, can be implemented like below

Image URL:https://gateoverflow.in/?qa=blob&qa_blobid=15779298586899863341

So, we need 512 in count 2X1 Mux at first level to select out of 1024 lines,

256 at the second level,128 at third,64 at fourth,32 at fifth,16 at sixth,8 at seventh,4 at eight,2 at level 9, and finally 1(a single) 2x1 mux at 10th level.

So, total 10 level of multiplexing needed and this will take $10*0.6=6ns$

So, cache hit time here=$2.7+6=8.7ns.$

 

–1 votes
–1 votes

Now we simply talk about the direct mapping

In direct mapping mapping number of multiplexer required depend upon the number of tag bits or size of comparator

Along with only only one k-bit comparator required;

In most of the cases time taken for the multiplexer taken as zero

Now 

Number of Tag bits=17bits; So 17 bit comparator and 17 multiplexer

Total time taken=k/10+0.6=2.3ns

Now we talk about set associative mapping::

No multiplexer;

Only compartor;

Time taken=1.7ns

Related questions

1 votes
1 votes
0 answers
1
AnilGoudar asked Nov 9, 2017
925 views
How to approach hit latency problems in cache mapping techniques.Please explain with an example.Thank in advance.
4 votes
4 votes
1 answer
2
mcjoshi asked Sep 23, 2016
931 views
In a cache organized memory there exist $30$% of compulsory misses, $10$% capacity misses, $12$% conflict misses. If cache is fully associative Find the average access ti...
0 votes
0 votes
0 answers
3
Ray Tomlinson asked Aug 22, 2023
228 views
is this formula is correct if it is correct then in gate 2006 Question 75 why they not used this formulahttps://gateoverflow.in/43565/gate-cse-2006-question-75