64 views
Is there any multiplexer(s) present in the implementation of Direct Mapped Cache?

If yes, then the Hit latency would be Multiplexer latency + Comparator Latency?
asked | 64 views
0

Why do you think we need a MUX here?

The decoder selects one of the cache lines using line number provided, and when that line is selected, the respective tag value is compared with the tag of given address and also it is checked that the entry of cache must be a valid entry( valid bit set-for memory protection).

the above comment (by Ayush) is taken from the following question

https://gateoverflow.in/43565/gate2006-75 - go through the discussion here

Also see the last part here- http://fourier.eng.hmc.edu/e85_old/lectures/memory/node4.html , : implementation of 2 way set associative - since we had 2 "lines" where our element could have been present so we need 2X1 mux , in direct map case we have only one line where our required word could be present so no need to have a multiplexer

(Def of Multiplexer: In electronics, a multiplexer (or mux) is a device that selects between several analog or digital input signals and forwards it to a single output line, here we have only one input {since we have a match with exact one line}, so no multiplexer required)

There is no multiplexer present in the $\text{Direct mapped cache}$ but it is used in $\text{Set associative cache}$. The format of Direct mapped cache is

 Tag Line Offset Word Offset

So only comparator is required to to match with tag bits, and once tags are matched that line is selected.

$\textbf{PS:- Edit}$

There are two scenarios:

$\underline{\textbf{1) When Cache is empty or some needed block is not present in the cache : -}}$

Each main memory block gets mapped to a fixed block in the cache memory. So when a block is not present in the cache then main memory block is added to particular fixed block in cache memory and this is decided by formula

$\textbf{cache line( or block) = k % S}$ where

$\text{k is block of main memory}$

$\text{S is number of blocks of cache memory}$

$\underline{\textbf{2) When desired cache block is present in the cache memory: - }}$

When CPU is looking for some data then it searches within the blocks present in the cache memory. In order to find the correct cache block(or line) it uses comparator to match with tag bits. If the one of the tag bits gets matched with the CPU generated tag bits then that block is send to the CPU otherwise(when desired block is not present in the cache memory) desired main memory block is brought to the cache memory using above formula $k \% S$.

For more reference: Refer slide number 14

https://web.stanford.edu/class/ee282h/handouts/Handout28.pdf

answered by Active (1.8k points)
reshown ago by
+2
Okay. We use a comparator to compare tag bits from the address with the tag bits of some line of cache. How do you exactly identify that line? I mean how do you know this particular line's tag bits you need to compare?
0
Its a sequential checking with all lines tag bits, thats why we have some cache hit time which comes due to sequential checking with all the tag bits
0

@Sumiran Agrawal

Check the answer now.

0
Thank you for your answer. But this is like quite confusing as different resources state different matter.
0
If you follow non-standard resources you will be confused. Thats inevitable.
+3
@Karan How many lines are going to CPU from cache? When cache line is selected it must be multiplexed rt?
+3

@!KARAN

Can you please provide any good reference for your claim "Its a sequential checking with all lines tag bits". It is not mentioned in your given link. If it is checked sequentially then what is purpose to divide address into one of the fields as "Line Offset " ?

Please check the screenshot from NPTEL  https://nptel.ac.in/courses/106103068/module03_memory/lecture_02/slides/slide9.htm

Here, It is mentioned that " Next 7 bits are used to select a block out of 128 blocks (which is the capacity of the cache)."

So, selecting a cache block(line) , We need MUX. Right ?

The previous ans given by me is wrong.

$\textbf{Multiplexer}$ is used in the Direct mapped cache.

The format of Direct mapped cache is

 Tag Line Offset Word Offset

Each main memory block gets mapped to a $\textbf{fixed block}$ in the cache memory and this is decided by formula

$\textbf{cache line( or block) = k % S}$ where

k is a block of main memory

S is the number of blocks of cache memory

CPU generated address is searched in the directed mapped cache format.

When CPU is looking for data then it is first searched in the cache memory by using $\text{Line Offset}$.

$\text{Why Line Offset is used first?}$ This is because each main memory block has contention to get mapped to same cache block. Once a block is selected then its tag is compared with CPU generated tag, if tag is matched then then one of the word from the selected block is sent to the CPU.

$\text{How a word is fetched from the selected cache block? }$ All the words in a block becomes input to the multiplexer and the $\text{CPU generated Word Offset}$ becomes the select line of the multiplexer which enables the particular input line and the desired word appears at the output from the set of words in a block.

answered ago by Active (1.8k points)
edited ago by

1
2