Byte-select compression

Cache-block (e.g., 64 or 128 bytes) compression is used to improve effective cache capacity and interconnect bandwidth in computer processors. Com- pression algorithms used for these applications are limited in effectiveness of their compression by area and latency constraints. However, the best compression one can achieve under these constraints is unknown. This work explores a class of algorithms, byte-select algorithms. Byte-select algorithms have ideal compression ratios up to 2× greater than state-of-the-art algorithms, while also having favorable area and latency in practice. We explore two methods which search for useful byte-select algorithms. The first method searches for useful whole-block patterns, and the second method searches by mutating graphs representing state-of-the-art algorithms. We show that the pattern-based search can achieve, on average, 23% higher compression ratio and single-cycle decompression when trained and tested on a benchmark set. We also show the graph-based search can achieve, on average, 17.4% higher compression ratio than state-of-the-art on benchmarks unseen during training, and we use the search to generate spaces of algorithms which present tradeoffs between compression, area, and latency. We show that state-of-the-art algorithms’ performance suffers when one considers specific imposed by practical compressed cache implementations. For example, existing algorithms’ compression ratios can be reduced by as much as 39% when one restricts compressed sizes to either be a full cache block or a half block. Our search methods can be used to generate algorithms which target those implementations more specifically, leading to higher compression ratios and lower decompression latencies.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2023

Author dc:creator

• Tomei, Matthew J

Contributors dc:contributor

• Kumar, Rakesh
• Beckmann, Bradford M
• Huang, Jian
• Lumetta, Steven S
• Wood, David A

• Cache Compression
• Link Compression
• Byte-select Compression
• Compression Algorithms

Statement dc:rights

• Copyright 2023 Matthew Tomei

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/121428

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F121428