Byte-select compression

Tomei, Matthew J

Permalink

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

Description

Title

Byte-select compression

Author(s)

Tomei, Matthew J

Issue Date

2023-06-26

Director of Research (if dissertation) or Advisor (if thesis)

Kumar, Rakesh

Doctoral Committee Chair(s)

Kumar, Rakesh

Committee Member(s)

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

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• cache compression
• link compression
• byte-select compression
• compression algorithms

Abstract

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.

Graduation Semester

2023-08

Type of Resource

Thesis

Copyright and License Information

Copyright 2023 Matthew Tomei

Owning Collections