Direct Mapped Cache Multiplexer

Question

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?

Comments

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)

Answer 1

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.

Answer 2

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

Comments

@ankitgupta.1729 @Arjun

Sir,

Are you saying that MUX is used in Direct Mapped Cache$?$

If YES then this answer needs editing : https://gateoverflow.in/43565/gate2006-75

If NO then what is the use of this MUX drawn in this diagram.

Look for this link also. Which shows that MUX is needed.

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-823-computer-system-architecture-fall-2005/assignments/handout6.pdf

Looking at the above picture does it mean that the cache is of let's say x-word then we are going to make use of MUX otherwise not.

---

You can see what the MUX is "selecting".

---

@Arjun

Sir, after finalizing the cache block, $MUX$ is helping in the selection of Block offset within the Block $?$