{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/121428"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/121428","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Byte-select compression","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-12-04 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-12-04 without embargo terms","abstract_has_math":false,"creators":["Tomei, Matthew J"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Kumar, Rakesh","Beckmann, Bradford M","Huang, Jian","Lumetta, Steven S","Wood, David A"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023-08","date_published":"2023-08","updated_at":"2026-07-22T22:24:57Z","subjects":["Cache Compression","Link Compression","Byte-select Compression","Compression Algorithms"],"languages":["en","eng"],"rights":["Copyright 2023 Matthew Tomei"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/121428","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Kumar, Rakesh","Beckmann, Bradford M","Huang, Jian","Lumetta, Steven S","Wood, David A"]},{"key":"dc:creator","label":"Author","values":["Tomei, Matthew J"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2023-08","2023-06-26"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Cache Compression","Link Compression","Byte-select Compression","Compression Algorithms"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2023 Matthew Tomei"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/121428"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-12-04 without embargo terms","The student, Matthew Tomei, accepted the attached license on 2023-06-22 at 17:19.","The student, Matthew Tomei, submitted this Dissertation for approval on 2023-06-22 at 17:41.","This Dissertation was approved for publication on 2023-06-26 at 15:09.","DSpace SAF Submission Ingestion Package generated from Vireo submission #19453 on 2023-12-04 at 17:00:10","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."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Byte-select compression"]}]}],"canonical_facts":{"dc:contributor":["Kumar, Rakesh","Beckmann, Bradford M","Huang, Jian","Lumetta, Steven S","Wood, David A"],"dc:creator":["Tomei, Matthew J"],"dc:date":["2023-08","2023-06-26"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-12-04 without embargo terms","The student, Matthew Tomei, accepted the attached license on 2023-06-22 at 17:19.","The student, Matthew Tomei, submitted this Dissertation for approval on 2023-06-22 at 17:41.","This Dissertation was approved for publication on 2023-06-26 at 15:09.","DSpace SAF Submission Ingestion Package generated from Vireo submission #19453 on 2023-12-04 at 17:00:10","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."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/121428"],"dc:language":["en","eng"],"dc:rights":["Copyright 2023 Matthew Tomei"],"dc:subject":["Cache Compression","Link Compression","Byte-select Compression","Compression Algorithms"],"dc:title":["Byte-select compression"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:57Z"}