Metraipolis › archive › dc_e679eba24de5

A GPU Engine for Sparse Matrix-Vector Products on $k^2$-Tree-Compressed Graphs — arXiv:2611.03610

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.03610
License (as archived)
CC0-1.0
Archived
2026-11-03T18:26:55.092Z
SHA-256 of the archived text
93e7a45863d455d732e0c63ce9196a31e47391a78107dff5fb388e392c355230
Stable URL of this page
https://metraipolis.com/documento/dc_e679eba24de5

How to cite

A GPU Engine for Sparse Matrix-Vector Products on $k^2$-Tree-Compressed Graphs — arXiv:2611.03610 — arXiv (en), https://arxiv.org/abs/2611.03610 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e679eba24de5 (Metraipolis archive dc_e679eba24de5, sha256 93e7a45863d455d732e0c63ce9196a31e47391a78107dff5fb388e392c355230)
BibTeX
@misc{dce679eba24de5,
  title = {A GPU Engine for Sparse Matrix-Vector Products on $k^2$-Tree-Compressed Graphs — arXiv:2611.03610},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.03610},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e679eba24de5; sha256 93e7a45863d455d732e0c63ce9196a31e47391a78107dff5fb388e392c355230},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.03610. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The $k^2$-tree is a compact representation of Boolean matrices: it stores the recursive hierarchy of their non-empty submatrices, with neither values nor coordinates, and serves rows and columns alike. Its traversal, however, locates the children of each node by rank queries, a chain of dependent irregular loads that leaves a GPU waiting on memory. We implement sparse matrix-vector multiplication (SpMV) on $k^2$-trees for the GPU. Since the traversal does not depend on the vector, the positions of the children are static: we descend the tree one level at a time and obtain them from a parallel prefix sum or from a sampled directory of about 0.1 bits per node. Descending in tiles bounds the temporary memory by the depth of the tree, so the device memory of a product is known before it runs. The same traversal computes right and left products, for one vector or a batch, over the plus-times, Boolean and tropical semirings. We evaluate the engine on an NVIDIA GB10 and an H100 with fourteen Wikidata, Software Heritage, web and social graphs of up to 1.2 billion edges, against cuSPARSE, a grammar-compressed GPU engine and a Boolean CSR. Our results show that the tree is 2.3-27x smaller than the CSR of cuSPARSE and that, with its last internal level cached, a product takes 0.7-2.4x the time of cuSPARSE on the right and 0.27-2.6x on the left. On a 1.2-billion-edge graph, a product needs 1.1 GB on the device, 9x less than cuSPARSE. The engine is memory bounded: the $k^2$-tree is the format of choice when device memory, not time, is the constraint.

Tema degli esploratori: calcolo e infrastrutture (elenco arXiv cs.DC, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Databases (cs.DB); Distributed, Parallel, and Cluster Computing (cs.DC); Mathematical Software (cs.MS).
Pagina del lavoro: https://arxiv.org/abs/2611.03610 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T18:10:22.868Z dalla pagina https://arxiv.org/list/cs.DC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).