RUC. Repositorio da Universidade da Coruña
Publicación
Contribución de congreso (ConferenceOutput)
Modular Construction and Optimization of the UZP Sparse Format for SpMV on CPUs
The latest version of the evaluated artifact is available under DOI: 10.5281/zenodo.15048005. It includes the necessary instructions, software, and scripts to reproduce the experiments in this paper. UZP is also available at https://github.com/UDC-GAC/uzp-sparse-format., [Abstract]: 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. In this work we present 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 layout. 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 Z-polyhedra structures., This work was supported in part by the U.S. National Science Foundation award #2009020; by grant PID2022-136435NB-I00, funded by MICIU/AEI/10.13039/501100011033 and by “ERDF A way of making Europe”, EU; and by the predoctoral grant of Alonso Rodríguez-Iglesias FPU2022/01651, funded by the Ministry of Science, Innovation and Universities. CITIC, as a center accredited for excellence within the Galician University System and a member of the CIGUS Network, receives subsidies from the Department of Education, Science, Universities, and Vocational Training of the Xunta de Galicia. Additionally, it is co-!nanced by the EU through the FEDER Galicia 2021-27 operational program (Ref. ED431G 2023/01).