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. Algorithms ‘Software-heavy’ 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 algorithms for cache compression. Firstly, these algorithms typically construct ‘software-heavy’ 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
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
Cache_Compression_Report.docx