{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,28]],"date-time":"2026-06-28T04:38:19Z","timestamp":1782621499762,"version":"3.54.5"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA1","license":[{"start":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T00:00:00Z","timestamp":1714348800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["1909661, 2019306, 2118709, 2212371"],"award-info":[{"award-number":["1909661, 2019306, 2118709, 2212371"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2024,4,29]]},"abstract":"<jats:p>The ongoing trend of hardware specialization has led to a growing use of custom data formats when processing sparse workloads, which are typically memory-bound. These formats facilitate optimized software\/hardware implementations by utilizing sparsity pattern- or target-aware data structures and layouts to enhance memory access latency and bandwidth utilization. However, existing sparse tensor programming models and compilers offer little or no support for productively customizing the sparse formats. Additionally, because these frameworks represent formats using a limited set of per-dimension attributes, they lack the flexibility to accommodate numerous new variations of custom sparse data structures and layouts. To overcome this deficiency, we propose UniSparse, an intermediate language that provides a unified abstraction for representing and customizing sparse formats. Unlike the existing attribute-based frameworks, UniSparse decouples the logical representation of the sparse tensor (i.e., the data structure) from its low-level memory layout, enabling the customization of both. As a result, a rich set of format customizations can be succinctly expressed in a small set of well-defined query, mutation, and layout primitives. We also develop a compiler leveraging the MLIR infrastructure, which supports adaptive customization of formats, and automatic code generation of format conversion and compute operations for heterogeneous architectures. We demonstrate the efficacy of our approach through experiments running commonly-used sparse linear algebra operations with specialized formats on multiple different hardware targets, including an Intel CPU, an NVIDIA GPU, an AMD Xilinx FPGA, and a simulated processing-in-memory (PIM) device.<\/jats:p>","DOI":"10.1145\/3649816","type":"journal-article","created":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T17:53:50Z","timestamp":1714413230000},"page":"137-165","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["UniSparse: An Intermediate Language for General Sparse Format Customization"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1534-3500","authenticated-orcid":false,"given":"Jie","family":"Liu","sequence":"first","affiliation":[{"name":"Cornell University, Ithaca, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6637-553X","authenticated-orcid":false,"given":"Zhongyuan","family":"Zhao","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-4555-2077","authenticated-orcid":false,"given":"Zijian","family":"Ding","sequence":"additional","affiliation":[{"name":"University of California, Los Angeles, Los Angeles, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1488-1622","authenticated-orcid":false,"given":"Benjamin","family":"Brock","sequence":"additional","affiliation":[{"name":"Intel, San Jose, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3275-7791","authenticated-orcid":false,"given":"Hongbo","family":"Rong","sequence":"additional","affiliation":[{"name":"Intel, San Jose, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0778-0308","authenticated-orcid":false,"given":"Zhiru","family":"Zhang","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,4,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1863543.1863581"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/060676489"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1654059.1654078"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3544559"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/165939.166023"},{"key":"e_1_2_1_6_1","volume-title":"US Department of Commerce","author":"Boisvert Ronald F","unstructured":"Ronald F Boisvert, Ronald F Boisvert, and Karin A Remington. 1996. The matrix market exchange formats: Initial design. 5935, US Department of Commerce, National Institute of Standards and Technology."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2008.4536313"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1583991.1584053"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1837853.1693471"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276493"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","unstructured":"Stephen Chou Fredrik Kjolstad and Saman Amarasinghe. 2020. Automatic generation of efficient sparse tensor format conversion routines. 823\u2013838. isbn:9781450376136 https:\/\/doi.org\/10.1145\/3385412.3385963 10.1145\/3385412.3385963","DOI":"10.1145\/3385412.3385963"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Stephen Chou Fredrik Kjolstad and Saman Amarasinghe. 2020. Automatic generation of efficient sparse tensor format conversion routines. https:\/\/github.com\/stephenchouca\/taco\/tree\/pldi20ae","DOI":"10.1145\/3385412.3385963"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3470496.3527431"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FCCM.2014.23"},{"key":"e_1_2_1_16_1","unstructured":"Takeshi Fukaya Koki Ishida Akie Miura Takeshi Iwashita and Hiroshi Nakashima. 2021. Accelerating the SpMV kernel on standard CPUs by exploiting the partially diagonal structures. arXiv preprint arXiv:2105.04937."},{"key":"e_1_2_1_17_1","unstructured":"Trevor Gale Erich Elsen and Sara Hooker. 2019. The state of sparsity in deep neural networks. arXiv preprint arXiv:1902.09574."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1177\/1094342015593156"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","unstructured":"Weihua Hu Matthias Fey Marinka Zitnik Yuxiao Dong Hongyu Ren Bowen Liu Michele Catasta and Jure Leskovec. 2020. Open Graph Benchmark: Datasets for Machine Learning on Graphs. Advances in Neural Information Processing Systems https:\/\/doi.org\/10.5555\/3495724.3497579","DOI":"10.5555\/3495724.3497579"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD51958.2021.9643582"},{"key":"e_1_2_1_21_1","first-page":"139","volume-title":"Workshop on Profile and Feedback-Directed Compilation","author":"Im Eun-Jin","year":"1998","unstructured":"Eun-Jin Im and Katherine Yelick. 1998. Model-based memory hierarchy optimizations for sparse matrices. Workshop on Profile and Feedback-Directed Compilation, 139 (1998)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2019.00521"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","unstructured":"Robert Johansson and Robert Johansson. 2015. Sparse Matrices and Graphs. Numerical Python: A Practical Techniques Approach for Industry 235\u2013254. https:\/\/doi.org\/10.1007\/978-1-4842-0553-2_10 10.1007\/978-1-4842-0553-2_10","DOI":"10.1007\/978-1-4842-0553-2_10"},{"key":"e_1_2_1_24_1","volume-title":"ITPACKV 2D user\u2019s guide. Texas Univ","author":"Kincaid David R","unstructured":"David R Kincaid, Thomas C Oppe, and David M Young. 1989. ITPACKV 2D user\u2019s guide. Texas Univ., Austin, TX (USA). Center for Numerical Analysis."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133901"},{"key":"e_1_2_1_26_1","unstructured":"Fredrik Kjolstad Shoaib Kamil Stephen Chou David Lugato and Saman Amarasinghe. 2019. The Tensor Algebra Compiler. https:\/\/github.com\/tensor-compiler\/taco"},{"key":"e_1_2_1_27_1","volume-title":"Compiling parallel sparse code for user-defined data structures","author":"Kotlyar Vladimir","unstructured":"Vladimir Kotlyar, Keshav Pingali, and Paul Stodghill. 1997. Compiling parallel sparse code for user-defined data structures. Cornell University."},{"key":"e_1_2_1_28_1","volume-title":"MLIR: A compiler infrastructure for the end of Moore\u2019s law. arXiv preprint arXiv:2002.11054.","author":"Lattner Chris","year":"2020","unstructured":"Chris Lattner, Mehdi Amini, Uday Bondhugula, Albert Cohen, Andy Davis, Jacques Pienaar, River Riddle, Tatiana Shpeisman, Nicolas Vasilache, and Oleksandr Zinenko. 2020. MLIR: A compiler infrastructure for the end of Moore\u2019s law. arXiv preprint arXiv:2002.11054."},{"key":"e_1_2_1_29_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Jie Liu Zhongyuan Zhao Zijian Ding Benjamin Brock Hongbo Rong and Zhiru Zhang. 2024. UniSparse: An Intermediate Language for General Sparse Format Customization. https:\/\/github.com\/cornell-zhang\/UniSparse","DOI":"10.1145\/3649816"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","unstructured":"Jie Liu Zhongyuan Zhao Zijian Ding Benjamin Brock Hongbo Rong and Zhiru Zhang. 2024. UniSparse: An Intermediate Language for General Sparse Format Customization. https:\/\/doi.org\/10.5281\/zenodo.10464500 10.5281\/zenodo.10464500","DOI":"10.5281\/zenodo.10464500"},{"key":"e_1_2_1_32_1","volume-title":"SIPR: A new framework for generating efficient code for sparse matrix computations. Languages and Compilers for Parallel Computing, 213\u2013229.","author":"Pugh William","year":"1999","unstructured":"William Pugh and Tatiana Shpeisman. 1999. SIPR: A new framework for generating efficient code for sparse matrix computations. Languages and Compilers for Parallel Computing, 213\u2013229."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718003"},{"key":"e_1_2_1_34_1","volume-title":"FROSTT: The Formidable Repository of Open Sparse Tensors and Tools","author":"Smith Shaden","year":"2017","unstructured":"Shaden Smith, Jee W. Choi, Jiajia Li, Richard Vuduc, Jongsoo Park, Xing Liu, and George Karypis. 2017. FROSTT: The Formidable Repository of Open Sparse Tensors and Tools. http:\/\/frostt.io\/"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3489517.3530420"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490422.3502357"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO50266.2020.00068"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","unstructured":"Ruiqin Tian Luanzheng Guo Jiajia Li Bin Ren and Gokcen Kestor. 2021. A High Performance Sparse Tensor Algebra Compiler in MLIR. 12 https:\/\/doi.org\/10.1109\/LLVMHPC54804.2021.00009 10.1109\/LLVMHPC54804.2021.00009","DOI":"10.1109\/LLVMHPC54804.2021.00009"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3582016.3582047"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3649816","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3649816","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:54:06Z","timestamp":1750287246000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3649816"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,29]]},"references-count":39,"journal-issue":{"issue":"OOPSLA1","published-print":{"date-parts":[[2024,4,29]]}},"alternative-id":["10.1145\/3649816"],"URL":"https:\/\/doi.org\/10.1145\/3649816","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,29]]},"assertion":[{"value":"2024-04-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}