CRAM: Efficient Hardware-Based Memory Compression for Bandwidth Enhancement

There are a couple of things that feel concerning about this from a security perspective, as it's optimizations like this that could create another spectre class vulnerability. Mixing cache lines arbitrarily seems bad when you think of virtualization and the dream of memory isolation, you would need a lot more holding data to maintain such an optimization. It is also hard not to be a crypto snob when the author writes 'secure hash' and indicates single DES as a remedy.

I also don't like that there is a claimed speedup figure but it is not clear in a cursory reading and looking at the available tables and graphs what the baseline is? It's all done in emulation (apparently) so it's hard to know if it is amortized because there is no actual time to access or something else, but that could just be my unfamiliarity with that emulator.

I wonder if this very clever approach is interesting in the energy consumption perspective. In this work (http://hpc.pnl.gov/modsim/2014/Presentations/Kestor.pdf ) the author shows (slide 11 ) that it cost 100 times more energy to move data from memory to register than to move data from L1 cache. So, this kind of mechanism could hugely improve the amount of data that could be stored in L1/L2/L3 cache, but what could be the energy cost of compression/decompression step ?

BLOSC already does this with software.

http://blosc.org/

The sales pitch is "faster than memcpy." Fetch data from RAM, decompress it in L1,2,3 caches and run operations on the data. Some very nice benchmarks available.

So they set aside 2 32-bit patterns; when these patterns appear at the end of a 64-byte cache line, they indicate a compressed line; otherwise, the line is literal.

This smells an awful lot like an impossible infinite compression claim; any real compressor must increase the length of at least some inputs due to the pigeonhole principle.

Their solution is to add a 16-entry table to track "lines that look like they have the compressed-line marker, but are not actually compressed" (and they also store such lines inverted in DRAM, but this seems inessential). They claim 16 entries is enough based on probabilistic arguments, but they should be thinking of storing data generated by an adversarial process; one such process would be to choose 60 incompressible bytes followed by the 4-byte compressed line indicator.

Including just one bit of metadata per cache line of memory is 32MiB, more than the 0.75 bits/line (24MiB) calculated on page 5 for the scheme they would like to replace.

Their next bit of handwavium is that they use "DES" to choose line markers in a way dependent on a secret key which can be changed in case of a LUT overflow. I wasn't immediately able to find a modern figure on how fast hardware "DES" is, but a 2003 paper gives a figure of "21 to 37 cycles of latency" https://www.intopix.com/Ressources/WPs_and_Sc_Pub/intoPIX%20... -- will this fit into the time budget or will it slow memory accesses? (They first say this is off the critical path but then that the marker is per-line, I don't see how both are true)

When the limited table is exhausted, a new key is chosen and all of memory must be updated (so you really don't want to do that) They dismiss this by again appealing to the rarity as "1-in-2^512" but if that's true you might as well just design the chip to blow up when the condition arises. If any timing information about "line appears in LUT" is visible to a program, then it is just 16 * 2^32 instead for an adversarial program (you can tweak line 1 until it needs a LUT entry, which takes just 2^32 writes; then repeat for the next line)

I thought that HDMI and DisplayPort used compression, too, sometimes. Even then, your point about generic computing still stands.