Modular Construction and Optimization of the UZP Sparse Format for SpMV on CPUs
summary
Format encodes sparse coordinates as a union of integer polyhedra intersected with affine lattices so SpMV uses regular loops instead of index indirection, and UZP interoperates with CSR/COO. A Rust miner called c polyhedrator extracts low-dimensional C‑polyhedra; tuners (eg aggregation tuner and favor locality tuner plus a specialized‑dictionary tuner) explore representation variants. Implementation reconstructs 100M nonzeros in minutes, scales near‑linearly, and on 200+ SuiteSparse matrices yields solid average speedups, with peak performance approaching memory‑bandwidth limits.
AI-written summary · about
chapters (12)
- 0:00UZP format intro for SPMV
- 1:26Polyhedra in sparse matrices
- 3:31Polyhedral sparse structures
- 6:20Modular construction with C-polyhedra
- 8:47Four-step UCP plan
- 10:10UCP workflow example
- 12:41UCP tuners for performance
- 14:50Experimental setup
- 15:53Performance vs CSR
- 18:23MACVET comparison
- 19:25Compression analysis
- 20:07Conclusion
related talks
28mSpEQ: Translation of Sparse Codes using Equivalences
01h 04mCompile-time sparse matrices
15mCompacting Points-To Sets Through Object Clustering
18mDistVS: Large-scale Vector Search with Compute-Memory Disaggregation
20mBoosting Video Codec With RISC-V Vector Extension
37mUnstructured Sparsity Meets Tensor Cores: Lessons from Sparse Attention and MoE
51mPl/cuda the fusion of HPC grade power
44mPolars; DataFrames in the multi-core era