2
\$\begingroup\$

Let's consider a four-way set-associative cache, just like this one:

figure 5.18 from Computer Organization and Design (David A. Patterson and John L. Hennessy), section 5.4.

As you can see this cache has a read port but there is no write port. I was wondering if you guys could help me figure out how one would implement such a port in this set-associative cache.

I don't think the write method is relevant here, because I'm interested in how a MIPS processor or its memory management unit would write to cache, but if I'm wrong let's say this cache uses the write-back method to write data to main memory.

The book I've taken the picture from also says that caches, rather, SRAMs only have one access port which provides both read and write.

Thank you.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Single-port SRAM means you can either read or write at a time cz there will be only one address bus. But it doesn't always mean that there is only single data bus for both read and write. \$\endgroup\$
    – Mitu Raj
    Commented Sep 3, 2019 at 11:57
  • 1
    \$\begingroup\$ The actual write is not an issue: 'just' write in one set on a cache-miss. (You have the valid, tag, data & the address) What is absent here is that you often want a 'replacement' algorithm. Those have some sort of 'history' status bits which are not present here. So all you can do is random replacement. \$\endgroup\$
    – Oldfart
    Commented Sep 3, 2019 at 12:18
  • \$\begingroup\$ Random replacement is also a surprisingly good replacement strategy in many practical usage patterns. Not spectacularly good but competing with the other candidates and less prone to most pathological usage patterns. \$\endgroup\$
    – Dan
    Commented Sep 3, 2019 at 17:51

1 Answer 1

Reset to default
1
\$\begingroup\$

That is one of the key questions in designing a set-associative cache — what is the "replacement strategy?" In other words, when you need to write to the cache, which element of the set do you write to?

There are a number of basic rules:

  • An element that is "empty" can be written to.
  • An element that is "dirty" (hasn't been copied back to main memory yet) CANNOT be written to.
  • Of the remaining elements (not empty and not dirty), picking the correct one to replace is a key factor in the overall performance of the cache.

Round-robin replacement (a simple counter) is cheap and easy to implement.

LRU (least-recently used) attempts to take advantage of the "locality of reference" (in both time and space) exhibited by the vast majority of software, but requires more logic to implement.

\$\endgroup\$
4
  • \$\begingroup\$ Thank you for the answer. I guess that "empty" means the valid bit is zero, so this would require an AND with the index of each line: if (valid bit = 0) then you can write here. We also need to check the dirty bit, and only if it's zero may the MMU write in that line: if (dirty bit = 0) you can write here. This is what I've been able to gather from your helpful comment. I'm not interested in a overly complicated LRU mechanism, let's suppose a random block is picked. My question is: from a strictly graphic point of view, how would change the figure above to implement a read port? \$\endgroup\$
    – SkullHex2
    Commented Sep 4, 2019 at 12:30
  • \$\begingroup\$ Just some general comments: First, the incoming data and its associated tag needs to get routed to all of the memories. Each memory has a separate write enable, and they are all connected to a decoder driven by the replacement algorithm, whatever that might be. The valid and dirty bits require special handling, because they need to be globally reset whenever the system powers up or the software decides to "flush" the cache. \$\endgroup\$
    – Dave Tweed
    Commented Sep 4, 2019 at 12:46
  • \$\begingroup\$ One last question about the valid and dirty bits: the system just powered up, so both the bits of a certain line are zero. Then the memory management unit writes a word in that line, which obviously can store more than a single word. Does it have to assert the valid bit? Or should it wait before the entire line has been written to? Basically what I'm asking is, when exactly does the MMU replace the valid and dirty bits? Oh, I just remembered: where does the data come from? Does it come from the register file, and is it written with an instruction such as a store word? Thank you. \$\endgroup\$
    – SkullHex2
    Commented Sep 9, 2019 at 15:55
  • \$\begingroup\$ If the CPU (not the MMU) writes a word to an address that isn't already in the cache, you have two choices: You can bring the entire line into cache from main memory and then update the word, making the line both valid and dirty, or you can simply write the word directly to memory, bypassing the cache altogether, leaving the line not valid and not dirty. Most systems do the former, because then all transfers between cache and memory (both reads and writes) are done as whole lines, simplifying the system design. \$\endgroup\$
    – Dave Tweed
    Commented Sep 9, 2019 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.