Gpu engine compresses large graphs for memory efficient products
A GPU Engine for Sparse Matrix-Vector Products on $k^2$-Tree-Compressed Graphs
Data Structures and AlgorithmsDatabasesDistributed, Parallel, and Cluster ComputingMathematical Software
Summary
Working with very large graphs can require a lot of computer memory, which limits what can be processed, especially on GPUs. The authors focus on a compact way to represent these graphs, called the k2-tree, and create a method that performs multiplication between these compressed graphs and vectors efficiently on GPUs. Their approach reads the graph data in an organized way that reduces memory waiting time and predicts memory needs in advance. They show this method uses much less memory than traditional methods while still keeping performance close for many tested graphs.
What this means in practice
- •For gpu software developers: Run large-scale graph algorithms on GPUs with lower memory usage by using k2-tree compression and this engine's traversal method.
- •For big data engineers: Process massive network or social graphs on limited-memory GPU devices, benefiting from memory-efficient sparse matrix-vector multiplication.
Authors
Francesco Tosoni, Gabriele Mencagli
Abstract
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.