{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/150186"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/150186","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Unified Compilation for Lossless Compression and Sparse Computing","abstract":"Achieving high performance for computations on tensors depends heavily on the formats used to store them. While sparse tensors are very common, there are more general patterns in data which can sometimes be better captured using lossless compression. We show how to extend sparse tensor algebra compilers to support lossless compression techniques, including variants of run-length encoding and Lempel-Ziv compression. We develop new abstractions to represent losslessly compressed data as a generalized form of sparse tensors, with repetitions of values (which are compressed out in storage) represented by non-scalar, dynamic fill values. We then show how a compiler can use these abstractions to emit efficient code that computes on losslessly compressed data. By unifying lossless compression with sparse tensor algebra, our technique is able to generate code that computes with both losslessly compressed data and sparse data, as well as generate code that computes directly on compressed data without needing to first decompress it. We evaluate two implementations of our techniques, using a prototype compiler based on TACO, and an implementation of our formats within Finch. Our evaluation using our TACO compiler shows our technique generates efficient image and video processing kernels that compute on losslessly compressed data. We find that the generated kernels are up to 16.3× faster than equivalent dense kernels generated by TACO, a tensor algebra compiler, and up to 16.1× faster than OpenCV, a widely used image processing library. Using our Finch formats, we see compression ratios up to 25× with run-time speedups up to 3.1× over dense computation for reduction computations.","abstract_html":"Achieving high performance for computations on tensors depends heavily on the formats used to store them. While sparse tensors are very common, there are more general patterns in data which can sometimes be better captured using lossless compression. We show how to extend sparse tensor algebra compilers to support lossless compression techniques, including variants of run-length encoding and Lempel-Ziv compression. We develop new abstractions to represent losslessly compressed data as a generalized form of sparse tensors, with repetitions of values (which are compressed out in storage) represented by non-scalar, dynamic fill values. We then show how a compiler can use these abstractions to emit efficient code that computes on losslessly compressed data. By unifying lossless compression with sparse tensor algebra, our technique is able to generate code that computes with both losslessly compressed data and sparse data, as well as generate code that computes directly on compressed data without needing to first decompress it. We evaluate two implementations of our techniques, using a prototype compiler based on TACO, and an implementation of our formats within Finch. Our evaluation using our TACO compiler shows our technique generates efficient image and video processing kernels that compute on losslessly compressed data. We find that the generated kernels are up to 16.3× faster than equivalent dense kernels generated by TACO, a tensor algebra compiler, and up to 16.1× faster than OpenCV, a widely used image processing library. Using our Finch formats, we see compression ratios up to 25× with run-time speedups up to 3.1× over dense computation for reduction computations.","abstract_has_math":false,"creators":["Donenfeld, Daniel"],"institution":"Massachusetts Institute of Technology","degree_name":"Master","degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science","school":null,"contributors":[],"advisors":["Amarasinghe, Saman"],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023-02","date_published":"2023-02","updated_at":"2026-07-22T22:22:03Z","subjects":[],"languages":[],"rights":["In Copyright - Educational Use Permitted","Copyright MIT"],"rights_urls":["http://rightsstatements.org/page/InC-EDU/1.0/"],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1721.1/150186","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Amarasinghe, Saman"]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"]},{"key":"dc:creator","label":"Author","values":["Donenfeld, Daniel"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2023-03-31T14:38:20Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2023-03-31T14:38:20Z"]},{"key":"dc:date.issued","label":"Date","values":["2023-02"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master","Master of Science in Electrical Engineering and Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["In Copyright - Educational Use Permitted","Copyright MIT"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://rightsstatements.org/page/InC-EDU/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1721.1/150186"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Achieving high performance for computations on tensors depends heavily on the formats used to store them. While sparse tensors are very common, there are more general patterns in data which can sometimes be better captured using lossless compression. We show how to extend sparse tensor algebra compilers to support lossless compression techniques, including variants of run-length encoding and Lempel-Ziv compression. We develop new abstractions to represent losslessly compressed data as a generalized form of sparse tensors, with repetitions of values (which are compressed out in storage) represented by non-scalar, dynamic fill values. We then show how a compiler can use these abstractions to emit efficient code that computes on losslessly compressed data. By unifying lossless compression with sparse tensor algebra, our technique is able to generate code that computes with both losslessly compressed data and sparse data, as well as generate code that computes directly on compressed data without needing to first decompress it. We evaluate two implementations of our techniques, using a prototype compiler based on TACO, and an implementation of our formats within Finch. Our evaluation using our TACO compiler shows our technique generates efficient image and video processing kernels that compute on losslessly compressed data. We find that the generated kernels are up to 16.3× faster than equivalent dense kernels generated by TACO, a tensor algebra compiler, and up to 16.1× faster than OpenCV, a widely used image processing library. Using our Finch formats, we see compression ratios up to 25× with run-time speedups up to 3.1× over dense computation for reduction computations."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["S.M."]},{"key":"dc:title","label":"Title","values":["Unified Compilation for Lossless Compression and Sparse Computing"]}]}],"canonical_facts":{"dc:contributor.advisor":["Amarasinghe, Saman"],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"],"dc:creator":["Donenfeld, Daniel"],"dc:date.accessioned":["2023-03-31T14:38:20Z"],"dc:date.available":["2023-03-31T14:38:20Z"],"dc:date.issued":["2023-02"],"dc:description.abstract":["Achieving high performance for computations on tensors depends heavily on the formats used to store them. While sparse tensors are very common, there are more general patterns in data which can sometimes be better captured using lossless compression. We show how to extend sparse tensor algebra compilers to support lossless compression techniques, including variants of run-length encoding and Lempel-Ziv compression. We develop new abstractions to represent losslessly compressed data as a generalized form of sparse tensors, with repetitions of values (which are compressed out in storage) represented by non-scalar, dynamic fill values. We then show how a compiler can use these abstractions to emit efficient code that computes on losslessly compressed data. By unifying lossless compression with sparse tensor algebra, our technique is able to generate code that computes with both losslessly compressed data and sparse data, as well as generate code that computes directly on compressed data without needing to first decompress it. We evaluate two implementations of our techniques, using a prototype compiler based on TACO, and an implementation of our formats within Finch. Our evaluation using our TACO compiler shows our technique generates efficient image and video processing kernels that compute on losslessly compressed data. We find that the generated kernels are up to 16.3× faster than equivalent dense kernels generated by TACO, a tensor algebra compiler, and up to 16.1× faster than OpenCV, a widely used image processing library. Using our Finch formats, we see compression ratios up to 25× with run-time speedups up to 3.1× over dense computation for reduction computations."],"dc:description.degree":["S.M."],"dc:identifier.uri":["https://hdl.handle.net/1721.1/150186"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["In Copyright - Educational Use Permitted","Copyright MIT"],"dc:rights.uri":["http://rightsstatements.org/page/InC-EDU/1.0/"],"dc:title":["Unified Compilation for Lossless Compression and Sparse Computing"],"dc:type":["Thesis"],"thesis:degree_name":["Master","Master of Science in Electrical Engineering and Computer Science"]},"updated_at":"2026-07-22T22:22:03Z"}