10

When the CPU with an L1 cache does a write, what normally happens is that (assuming that the cache line that it is writing to is already in the L1 cache) the cache (in addition to updating the data) marks that cache line as dirty, and will write the line out with the updated data at some later time.

One possible optimization would be to have the cache compare the contents of the write and the previous contents of the cache, and if they're the same, don't mark the line as dirty. Because this might allow the cache to avoid write-backs on occasion, I can see how the CPU manufacturer might see this as worth the gates needed to do this logic.

My question: are there CPUs that perform this optimization?

Background as to why I'm asking: I'm writing some code that needs to have constant memory accesses; that is, someone who is able to listen into the behavior of the cache should not be able to deduce what I'm doing. Some of my accesses are writes, and in the obvious way to implement this code, a lot of the writes will be writing the same data that's already there. I need to do the writes because, depending on the data, the data I'm writing may or may not be the same, and it's important to perform the same action regardless. If the CPU optimizes by not actually writing a 'no-change-write', that would mean that the behavior of the cache would vary depending on what I'm doing, which would subvert my goal.

So, is there a CPU that tries to optimize writes in this way?

  • 11
    It's said that there are two truly difficult problems in computer science: cache invalidation, naming things well, and off-by-one errors. This is an example of why the first of these is tricky. – Mason Wheeler Nov 16 '15 at 18:47
  • @poncho you say that "someone who is able to listen into the behavior of the cache should not be able to deduce what I'm doing." Now if some CPUs implemented this "smart write-back" feature which does not invalidate the cache unless data is really updated, then by going one level further away from the CPU in the memory hierarchy, one would be able to observe the traffic/timing differences between real writes and dummy writes. Is this what you are concerned about? – TheCodeArtist Nov 20 '15 at 4:08
  • @poncho Also your real question seems to be about implementing a better privileged/secure mode that does not leak usage info. Maybe you should ask that?... – TheCodeArtist Nov 20 '15 at 4:08
  • 1
    @TheCodeArtist: well, there have been published cryptographical sidechannel attacks where an encryption routine could be attacked by another program running on a different core of the same CPU, by having the attack program monitor the shared cache. I believe such a program could potentially detect whether L1 cache lines were flushed, and hence could deduce information about the program I'm interested in, if the CPU does the optimization under discussion. I'm not talking about a 'secure mode', as I don't assume the ability to modify the CPU or the OS. – poncho Nov 20 '15 at 5:06
  • 4
    Even if this is true today, it's not guaranteed to be true tomorrow. – pjc50 Nov 20 '15 at 23:41
4

From hours of searching, I wasn't able to find a CPU that uses this specific optimization. Most of the optimizations mentioned usually related to hit/miss with read/write operations and data access:

(pages 7 and ) https://cseweb.ucsd.edu/classes/fa14/cse240A-a/pdf/08/CSE240A-MBT-L15-Cache.ppt.pdf

However, that doesn't mean that this optimization can't be performed. In general, it is possible to programmatically access the size of a CPU cache line. It is also possible to access current values in cache registers - but it's somewhat dangerous to do so. If you access the wrong registers at a bad time, you could be tampering with ones related to a running program. Or you could inadvertently modify the contents of the lines you're trying to read.

Obtaining current value in register's cache

Furthermore, all of the theoretical solutions require some form of software implementation (assembler). The closest I've found relates to the ARM architecture, which appears to allow for cache manipulation. In addition to this, you would also need to know the size of a cache line for your desired CPU. You could carefully read the cache contents to a secondary location in memory, in line-sized increments, and compare it to data that is about to be written to the registers (or L1 cache lines, in this case).

Read CPU cache contents

From there, you could devise a software-based system that prevents identical rewrites. While this is a bit simplified, it is so because the solution has to be applicable for any CPU that exists.

Another possibility that I found related to Cache coherence:

Relevant passage from a Wikipedia article about acche coherence

The main point that caught my attention, in relation to this issue, was the Snarfing description:

It is a mechanism where a cache controller watches both address and data in an attempt to update its own copy of a memory location when a second master modifies a location in main memory. When a write operation is observed to a location that a cache has a copy of, the cache controller updates its own copy of the snarfed memory location with the new data.

In other words, there are possibly mechanisms already in place. It's just that they might not be used for the optimization you have suggested. You would have to implement software that performed the read/write comparison.

  • It is also possible to access current values in cache registers - but it's somewhat dangerous to do so. Huh, this makes no sense. Do you mean CPU registers? Compiler generated or hand-written asm code uses registers to hold values that it's operating on... – Peter Cordes Nov 21 '17 at 23:56
  • If you're trying to implement this in software, you'd just have the compiler generate code that does if (mem != x) { mem = x; } instead of mem = x;. This is only sometimes an optimization for shared cache lines in a multi-threaded program, because writing interferes with other threads reading. – Peter Cordes Nov 21 '17 at 23:57
  • 1
    "snarfing" has nothing to do with this. It's just passive snooping. CPU caches use MESI so they can have coherent write-back caches. – Peter Cordes Nov 22 '17 at 0:00
  • @PeterCordes If you find my answer distasteful, I apologize. However, it appears that you have more insight than me on the matter. So, why not answer the question yourself? My response was obviously inadequate by your standards... – TopHatProductions115 Jan 15 '18 at 16:35
  • I did, on a near-duplicate of this question on SO. – Peter Cordes Jan 15 '18 at 21:54
3

Writing to L1 cache is a very, very time critical operation.

Writing the exact same data back seems to be rather rare. An optimisation that speeds things up in this particular case isn't going to get a lot of speedup in total.

On the other hand, this optimisation requires a comparison of old data and new data on every single write to cache memory. What makes this worse, is that it requires that the data to be written has to be actually available at the time of the write!

That is usually not the case on a modern CPU. The data to be written may still be being calculated for example. The cache can still go ahead, load the cache line if needed, mark the cache line as modified and so on, even before the calculation is finished. All the book keeping can already be performed except for the actual modification of the cache line. If you want to compare newly written result and old cache line data, that isn't possible.

As an example, if you have C code a [i] = x / y; the division x / y takes an extraordinary long time to perform on most CPUs. However, most of the work needed to handle storing the result to a [i] has happened long before the division finishes; the only thing missing is the move of eight result bytes to the cache line. An operation flushing the cache line will automatically wait until the division is finished. An operation reading a [i] will likely be redirected to get the result straight from the divider.

  • A cache using MESI for coherence could still do the RFO, but if the data compared the same once it was ready, leave the line in Exclusive state instead of Modified. The real reason it's not done in hardware is that it costs extra cache reads as the data commits to cache, and would require a sort of atomic read/compare/write cycles (with optional setting of the dirty bit) that makes it suck for a pipelined implementation. – Peter Cordes Nov 22 '17 at 0:04
1

One possible optimization would be to have the cache compare the contents of the write and the previous contents of the cache, and if they're the same, don't mark the line as dirty

Won't such optimization double the time CPU needs to write something into cache? Because each cache line write will now be accompanied with a compare operation, which is not free.

So, actually the optimization now will depend on the very vague factor: how many times an average software rewrites its cacheable memory with the same data.

  • This comparison would be implemented within the CPU logic. It would not require an additional CPU operation, but the signal time might increase, which could be a problem or not. – ziggystar Nov 20 '15 at 8:58
  • @ziggystar Well, I am not a hardware master, but I got used to the thought that everything comes with a cost. So does compare operation against cache line. It might be fast. But this is still cost. And I think implementors decided not to pay it. May be even after some thinking and measuring. – Vladislav Rastrusny Nov 20 '15 at 9:00
  • 1
    But you are talking about time, where the cost might only be an increase in the number of gates. – ziggystar Nov 20 '15 at 9:02
  • 1
    @ziggystar: This isn't just more gates. When data is sent to the cache, normally the process of sending the data can mark the cache line as modified. With this "optimisation", the old data and the new data must both pass through these gates which will cause some delay, and only then can the cache be invalidated. You have to squeeze all this into one processor cycle, otherwise writing to a cache line suddenly takes two cycles. And now to make things more complicated, consider what happens when I write eight consecutive words to a cache line. – gnasher729 Dec 6 '15 at 22:17
  • 1
    And each of these writes delays the decision whether the cache line is modified. So when the second write happens, the cache line doesn't know whether it is modified or not (yet). This is going to be fun. – gnasher729 Dec 6 '15 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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