{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T11:04:34Z","timestamp":1784199874978,"version":"3.55.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T00:00:00Z","timestamp":1749772800000},"content-version":"vor","delay-in-days":3,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"US National Science Foundation","doi-asserted-by":"crossref","award":["2009020"],"award-info":[{"award-number":["2009020"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]},{"name":"MICIU","award":["PID2022-136435NB-I00, FPU2022\/01651"],"award-info":[{"award-number":["PID2022-136435NB-I00, FPU2022\/01651"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2025,6,10]]},"abstract":"<jats:p>Sparse data structures are ubiquitous in modern computing, and numerous formats have been designed to represent them. These formats may exploit specific sparsity patterns, aiming to achieve higher performance for key numerical computations than more general-purpose formats such as CSR and COO.<\/jats:p>\n                  <jats:p>In this work presents UZP, a new sparse format based on polyhedral sets of integer points. UZP is a flexible format that subsumes CSR, COO, DIA, BCSR, etc., by raising them to a common mathematical abstraction: a union of integer polyhedra, each intersected with an affine lattice. We present a modular approach to building and optimizing UZP: it captures equivalence classes for the sparse structure, enabling the tuning of the representation for target-specific and application-specific performance considerations. UZP is built from any input sparse structure using integer coordinates, and is interoperable with existing software using CSR and COO data layouts. We provide detailed performance evaluation of UZP on 200+ matrices from SuiteSparse, demonstrating how simple and mostly unoptimized generic executors for UZP can already achieve solid performance by exploiting \ud835\udcb5-polyhedra structures.<\/jats:p>","DOI":"10.1145\/3729335","type":"journal-article","created":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T16:02:27Z","timestamp":1749830547000},"page":"2106-2130","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Modular Construction and Optimization of the UZP Sparse Format for SpMV on CPUs"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5982-9118","authenticated-orcid":false,"given":"Alonso","family":"Rodr\u00edguez-Iglesias","sequence":"first","affiliation":[{"name":"Universidade da Coru\u00f1a, a Coru\u00f1a, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-3147-2179","authenticated-orcid":false,"given":"Santoshkumar T.","family":"Tongli","sequence":"additional","affiliation":[{"name":"Colorado State University, Fort Collins, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-1447-5683","authenticated-orcid":false,"given":"Emily","family":"Tucker","sequence":"additional","affiliation":[{"name":"Colorado State University, Fort Collins, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5103-3097","authenticated-orcid":false,"given":"Louis-No\u00ebl","family":"Pouchet","sequence":"additional","affiliation":[{"name":"Colorado State University, Fort Collins, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0338-3655","authenticated-orcid":false,"given":"Gabriel","family":"Rodr\u00edguez","sequence":"additional","affiliation":[{"name":"Universidade da Coru\u00f1a, a Coru\u00f1a, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9670-1933","authenticated-orcid":false,"given":"Juan","family":"Touri\u00f1o","sequence":"additional","affiliation":[{"name":"Universidade da Coru\u00f1a, a Coru\u00f1a, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,13]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/223428.207157"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314615"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2004.1342537"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/1654059.1654078"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375595"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/1583991.1554053"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2008.4536313"},{"key":"e_1_3_2_9_2","unstructured":"Kazem Cheshmi. 2023. Partially Strided Codellet GitHub repository. https:\/\/github.com\/sparse-specialize\/partially-strided-codelet. Commit: c03d0593411c5a0fc96b561de152695c45335ba04."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC41404.2022.00037"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","unstructured":"K. Cheshmi S. Kamil M.M. Strout and M.M. Dehnavi. 2017. Sympiler: transforming sparse matrix codes by decoupling symbolic analysis. In International Conference for High Performance Computing https:\/\/doi.org\/10.1145\/3126908.3126936 10.1145\/3126908.3126936.","DOI":"10.1145\/3126908.3126936"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2018.00065"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3581784.3607097"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/1837853.1693471"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3276493"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/224170.224420"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC41404.2022.00071"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","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 (2021). https:\/\/doi.org\/10.48550\/arXiv.2105.04937 10.48550\/arXiv.2105.04937.","DOI":"10.48550\/arXiv.2105.04937"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/1229428.1229478"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3520484"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3293833.3295712"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3559009.3569668"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3133901"},{"key":"e_1_3_2_25_2","unstructured":"A. LaMielle and M. Strout. 2010. Enabling Code Generation within the Sparse Polyhedral Framework. Technical Report CS-10-102 Colorado State University. https:\/\/www.cs.colostate.edu\/TechReports\/Reports\/2010\/tr10-102.pdf"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/CGO51591.2021.9370308"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/2751205.2751208"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3295500.3356216"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/169627.169752"},{"key":"e_1_3_2_30_2","unstructured":"L.-N. Pouchet. 2011. PolyBench: The Polyhedral Benchmarking suite version PolyBench\/C 4.2.1. http:\/\/polybench.cf.net"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","unstructured":"L.-N. Pouchet G. Rodr\u00edguez and colleagues. 2025. Artifact for PLDI'25 Modular Construction and Optimization of the UZP Sparse Format for SpMV on CPUs. https:\/\/doi.org\/10.5281\/zenodo.15240673 10.5281\/zenodo.15240673.","DOI":"10.5281\/zenodo.15240673"},{"key":"e_1_3_2_32_2","unstructured":"L.-N. Pouchet G. Rodr\u00edguez and colleagues. 2025. The UZP sparse format. https:\/\/github.com\/UDC-GAC\/uzp-sparse-format"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/2685500.2688515"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/2854038.2854056"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2018.2853747"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(96)90129-D"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/2751205.2751244"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/SUPERC.1994.344269"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2833179.2833183"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37658-0_5"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2018.2857721"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/2838734"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2016.40"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15582-6_49"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-57502-2_42"},{"key":"e_1_3_2_46_2","unstructured":"R.W. Vuduc. 2004. Automatic Performance Tuning of Sparse Matrix Kernels. Ph.D. Dissertation University of California."},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2002.10025"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/3591302"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/1183401.1183444"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2008.12.006"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/3168818"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3729335","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3729335","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T10:05:00Z","timestamp":1784196300000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3729335"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,10]]},"references-count":50,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2025,6,10]]}},"alternative-id":["10.1145\/3729335"],"URL":"https:\/\/doi.org\/10.1145\/3729335","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,10]]},"assertion":[{"value":"2024-11-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}