GATE CSE 2006 | Question: 74

Question

Consider two cache organizations. First one is $32 \; \textsf{KB}\;2\text{-way}$ set associative with $32  \; \text{byte}$ block size, the second is of same size but direct mapped. The size of an address is $32\; \text{bits}$ in  both cases . A $2\text{-to-}1$ multiplexer has latency of $0.6 \; \text{ns}$ while a $k\text{-bit}$ comparator has latency of  $\frac{k}{10} \text{ns}$. The hit latency of the set associative organization is $h_1$ while that of direct mapped is $h_2$.

The value of $h_1$ is: 

• A. $2.4  \text{ ns} $
• B. $2.3  \text{ ns}$ 
• C. $1.8  \text{ ns}$ 
• D. $1.7  \text{ ns}$ 

Comments

@Abhrajyoti00
we will not have Mux in associative cache

---

@JAINchiNMay why?

 

---

@Pranavpurkar @JAINchiNMay Our doubts have been answered by me here: https://gateoverflow.in/1851/gate-cse-2006-question-74?show=382102#c382102

Answer 1

 

Comparison is done in parallel for multiplexer 

---

Comments

So, as comparator compares each bit, that’s why for 18 bits of tag bits we are using 18 bit comparator, right?

---

yes

---

If possible then please share some references where I can read about these architectural things. I did searched few but found it very confusing.

---

Refer udacity playlist

---

https://youtu.be/JRBKPNjV8fY

---

Thanks a lot, your answers and replies have been helping a lot. All the best! :) 

---

First they thought of Direct mapping

Then they got issue's of trashing

Then associative memory came into picture but was expensive

Then they decided for set associative mapping (beech ka rasta) using multiplexers and N comparators

---

Whats the “cost” for associative memory? And does it really prevent thrashing?

---

Sir, maybe because in associative memory each cell must have storage capability, as well as logic circuits (comparatively more number of multiplexers and comparators) are required.

---

You can assume that the size of the memory remains the same. Now why is associative memory more costlier? Is the cost in terms of “money” only?

---

Sir cost depends  on time for no of page faults and replacement algorithm it uses

---

Probability of trashing decrease in Associative memory

---

Sir, associative memory requires an extra associative to guess the content of the word. It needed extra logic circuitry associated with every word that makes this memory more complex, faster and costlier. Each cell must have storage capability as well as logic circuits for matching its content with blocks of Main Memory. This is what I came through. If there’s any other reason too why it’s costlier then please give some insights Sir.

Associative memory does prevent thrashing : 

Reference :  https://cs233.github.io/thrashingandassociativityexample.html

---

Associative memory will always have a better or same hit rate as direct mapped memory for the same size irrespective of the replacement algorithm in use.

Is the above statement true?

---

Yes Sir, it’s true. Because associative memory has the benefit of spatial locality because of which it can store a comparatively larger number of blocks, which eventually helps reduce cache misses.

---

You might get full marks for that for University exams but not at IITs after GATE 😀 In University exams in India, you can mix technical terms and confuse the lecturers and get good marks -- but good IIT faculties easily see through them 😀 That's why many University toppers fail in GATE and many poor scorers do well in GATE.

When cache size is the same how can associative cache contain more number of blocks? If you say by reducing the block size -- no that also remains the same.

---

Oh okay Sir, I understood my mistake. Being having the same size of cache memory in both direct and associative memory, there won’t be any effect until associative memory consumes more space, it will behave the same as direct mapping, right?

Please correct me if I am wrong.

---

Imagine two brothers using their own shelves to store books without sharing. Now if one of the shelf is full of books, one of the brother can't store any more book even if there's space in the other shelf. But if they share the shelves we have better space utilization and they are expected to store more books.

Here, two shelves are like two cache blocks if you assume only one book in a shelf. When not shared, this resembles direct mapped cache and when shared it resembles 2-way associative cache.

Now the answer to my question is No. Can you say why?

---

When the books in the shelves are identified individually is Associate Mapping 

N books -> N cache blocks -> N different location

Search time = O (Cache size / Block size)

{assuming one book in each block} 

and For Direct Mapping Searching time is O(1)

For Set associative mapping time is

O(Cache size / (block size * #Sets)) 

No. of blocks remains the same only time complexity changes

---

By time complexity what you have given is number of blocks in a set. Search happens in them in parallel.

---

So it uses parallel search algorithm?

---

Total cost of a parallel algorithm is the product of time complexity and the number of processors used in that particular algorithm.

Total Cost = Time complexity × Number of processors used

Therefore, the efficiency of a parallel algorithm is −

Efficiency =

Worst case execution time of sequential algorithmo/Worst case execution time of the parallel algorithm

---

Yes, hardware parallelism.

Whats the "unit" of the cost you mentioned?

---

http://www.nitjsr.ac.in/course_assignment/CS16CS601PARALLEL%20ALGORITHMS.pdf 

Sir, The cost is in Big O notation 

---

Sir, I know you already know this, however a glimpse of a different sorting method seen in the cache.

---

yes, there Cost is defined in terms of total number of “steps” done or “instructions” executed. Practically this can relate to say energy consumption but not time taken. Both have their significance. 

But they dont answer my question 😀

Associative memory will always have a better or same hit rate as direct mapped memory for the same size irrespective of the replacement algorithm in use.

Is the above statement true? Why?

---

Yes

Associative memory will always have a better hit rate as direct mapped memory for the same size irrespective of the replacement algorithm in use.

Because Address can be stored in any line in Fully Associative cache

And in direct mapped cache Memory address can be stored in one location in catch

Allowing each address to be stored in multiple locations increase hit ratio in FAM

---

Proving something wrong is easy – a counter example would do. 

Consider a cache of just 2 blocks and direct mapped and the following access sequence.

0,1,2,0,1,2

0 and 2 are mapped to same cache block as they both give $0$ when mod with $2$ where as $1$ is mapped to the second cache block. So, here out of $6$ accesses, only the second access to $1$ will be a hit giving the hit ratio of $1/6.$

Now suppose we do a fully associative cache for above with LRU policy (FIFO also works the same here as we are not accessing any block after a hit in cache). 

• 0 – miss, no replacement
• 1 – miss, no replacement
• 2 – miss, 0 is replaced
• 0 – miss, 1 is replaced
• 1 – miss 2 is replaced
• 2 – miss, 0 is replaced.

Thus our fully associative cache reduced the hit ratio of a direct mapped cache from $1/6$ to $0$ 😅 

---

Associative memory will always have a better or same hit rate as direct mapped memory for the same size irrespective of the replacement algorithm in use.

Is the above statement true? Why?

Sir, here you are using LRU.  

And for these replacement algorithms 

Storage requirements are taken into consideration 

 

---

yes, by “irrespective” it means the statement should hold TRUE for ALL replacement algorithms. Now, if you want to change that condition you are free to change the LRU policy with any other you like. i.e., can you give any replacement policy where associative mapping is guaranteed to outperform direct mapped in terms of hit ratio in ALL scenarios?

---

Yes, Sir it's LRU

No of miss

A,B,C,D,A,B,C,D,A,B

Using 3 clock cycles no of misses we get is

MRU(2Miss)< MIN(5M) < FIFO(7M) < LRU(8M)

 

https://inst.eecs.berkeley.edu/~cs162/fa19/static/sections/section9-sol.pdf

 

Page 4 and 6

---

No. MRU works better for the “example” I gave. But does it always work better for a different access sequence? My question is for “all access sequences”.

---

Yes, Sir for any sequence

---

If MRU works better for any sequence why do we even have LRU as MRU is much easier to implement? So that cant be TRUE. 

Associative cache is “expected” to give a better hit rate than direct mapped cache – but not a guarantee. Like randomized quick sort is expected to run in $O(n \log n)$ time. Expectation matters in practice because exceptions are $\textbf{RARE}$ and often ignored. 

---

Thank-you Sir

---

Thank you very much Sir. Got to know new concepts. Thanks to Mohit too. :)