Search papers, labs, and topics across Lattice.
This paper introduces a GPU engine for efficiently performing right multiplication on grammar-compressed matrices, specifically targeting scenarios where the uncompressed matrix exceeds device memory. By leveraging a directed acyclic graph (DAG) structure and a streaming evaluation method, the proposed engine achieves significant reductions in memory footprint—4 to 8 times smaller than traditional cuSPARSE CSR implementations—while maintaining competitive performance. The approach not only optimizes space and energy usage but also generalizes to evaluate any monoid homomorphism, showcasing its versatility across large-scale applications like the Software Heritage graph.
Achieving a 4 to 8 times reduction in memory footprint for matrix operations on GPUs could revolutionize how we handle large-scale data in constrained environments.
Grammar-compressed matrices (the mm-repair family) store a matrix's non-zero structure as a RePair straight-line program (SLP), supporting matrix-vector products in time and space proportional to the compressed size. We target the regime where this is decisive on a GPU: when the uncompressed matrix exceeds device memory, so footprint (not floating-point throughput) is the binding constraint. Our SLP is a directed acyclic graph (DAG) of out-degree 2, and the right product $y=Mx$ is a single bottom-up sweep (leaves to roots): a conflict-free gather. We make the grammar properly layered (every nonterminal child one level below its parent) via pass-through completion, which inserts identity nodes to carry values upward until consumed. This yields a streaming evaluation in which each level reads only the level below and writes the next, so the live set fits in two alternating read-only/write-only buffers instead of scaling with the whole grammar; the per-level width equals the live set. On genotype matrices, where a polygenic score is exactly the right product $y=G\beta$, a CUDA implementation shows a clear space advantage: a device footprint 4 to 8 times smaller than a materialized cuSPARSE CSR baseline, single-vector times within a small factor of cuSPARSE, and consistently lower energy. Because the sweep needs only an associative combine, the same engine and schedule evaluate any monoid homomorphism over the grammar by swapping a small leaf/combine/emit policy; the same reachability sweep then scales to the billion-edge Software Heritage graph ($261$ TB dense and unmaterializable, $21\times$ smaller serialized than CSR), where the memory argument holds. We frame this as an algorithm-engineering case study: structural metrics (depth, live-set width, completion cost) are measured, architecture-independent grammar properties, whereas time and energy are profiled on a single board.
