To calculate these theoretical models, we took periodic snapshots of cache contents throughout the test and passed them to Python scripts which implemented these models. One snapshot of the entropy for graph-analytics benchmark is presented below. Figure 1 Theoretical compressibility of a cache snapshot But this compressibility isn’t constant and varies over time as Figure 2 and Figure 3 suggest. But we note that across the duration of the test the compressibility is consistently > 2x. There are numerous instances where the compressibility is significantly higher. Figure 2 Theoretical compressibility of graph-analytics in Zero Information Entropy model Figure 3 Theoretical compressibility of graph-analytics in Markov Zeroth Order model This trend was visible across the workloads we tested, suggesting that theoretical compressibility in the form of low-entropy is present. ‘Software-heavy’ Algorithms Considering the entropy of cache-contents, we next analyze the ability of conventional, industry-standard compression techniques in exploiting cache compression. We picked two industry-standard tools – DEFLATE, part of the widely used gzip utility and Lempel-Ziv-Welch compression algorithms. Standard open-source implementations were downloaded from the internet. We noted two major drawbacks in using such ‘software-heavy’ algorithms for cache compression. Firstly, these algorithms typically construct very large dictionaries (order of 32K to 64K entries). Such large dictionaries are infeasible for hardware implementation. So we reduced the dictionary sizes and studied the variation in compressibility. In the following pages, compression ratio is defined as the ratio of uncompressed size to compressed size of cache contents. Figure 4 Compression efficiency of DEFLATE across dictionary sizes
Base Delta Immediate Compression potential – judge the potential of compression using the standard BDI algorithm, using a single base and multiple bases. Entropy analysis of symbols (at words and bytes granularity) using Zero Information Model and Markov Zeroth Order Model. Plot insightful histograms & plots of above trends Easily extendable for functions due to modular design. We were able to pass on this tool to another team working on cache compression and they were able to find it useful. We plan to open-source this tool shortly. We present some graphs generated using this tool in the Appendix B. Cache Contents Decomposition Using the above tool we were able to decompose the contents of each cache in the system across workloads. We identify that a major chunk of the cache contents for data caches fit within the limited set of patterns we defined in the previous section. This analysis suggests that any compression algorithm that tries to compress only these common patterns should be capable of significant compression. However, we also note that the cache composition varies throughout the test and decomposed snapshots reveal a varying trend. However, we note a consistent trend of >30% of the cache contents fitting within these patterns across workloads and test duration. These results are consistent with a similar analysis done in [2] Figure 6 L2 cache line decomposition for graph-analytics Cache Compression Algorithms Algorithms developed for the purpose of cache compression broadly fall into two categories - schemes - Most proposals in hardware cache or memory compression are hardware implementations of dictionary-based software compression algorithms. Such hardware