Search papers, labs, and topics across Lattice.
This paper introduces SHARDLP, a distributed GPU linear programming solver designed to handle large-scale linear programs that exceed the memory capacity of a single node. By partitioning the matrix and primal-dual state from sharded input through solution output, SHARDLP achieves significant performance improvements over traditional CPU solvers, completing a benchmark task with 1.185 billion variables in just 9.9 minutes compared to 21.06 hours on CPU. The method also demonstrates remarkable scalability, solving instances with up to 13.604 billion variables and optimizing communication to enhance efficiency by up to 1.52 times.
SHARDLP shatters previous performance records, solving a 1.185-billion-variable LP in under 10 minutes—21 times faster than CPU counterparts.
Large linear programs can exceed the memory of a single compute node. Although first-order methods replace sparse factorizations with GPU-suited matrix-vector products, other solver phases can reintroduce a single-node memory limit. We present SHARDLP, a distributed GPU LP solver that keeps the matrix and primal-dual state partitioned from sharded input through solution output. On the Google PDLP benchmark, SHARDLP reaches the published criterion on nine of eleven instances, compared with eight in the published CPU PDLP study. On the largest benchmark, eight H200 GPUs solve a 1.185-billion-variable, 6.338-billion-nonzero LP in 9.9 minutes; the published CPU experiment reports 21.06 hours on different hardware. Beyond this benchmark, separately checked multi-node solves reach up to 13.604 billion variables and 40.807 billion nonzeros, while validated executions span up to 76 GPUs across 29 compute nodes. For column-partitioned solves, support-aware communication skips GPUs that store no coefficients for a row; on an LP with 2.76 billion nonzeros, it cuts modelled communication by 92.97% and improves solver time by 1.27x-1.52x
