Distributed gpu solver handles massive linear programs faster than cpu
Distributed Linear Programming on GPU Clusters at Extreme Scale
Distributed, Parallel, and Cluster Computing
Summary
Some math problems called linear programs can get so big they don't fit in one computer's memory. The authors developed SHARDLP, a solver that breaks the problem into parts and runs them on multiple GPUs working together. This method solves huge problems much faster than traditional CPU methods and can handle much larger datasets. It also reduces the time spent communicating between GPUs by only sharing needed data.
What this means in practice
- •For operations teams: Solve extremely large linear optimization problems quickly using multiple GPUs working in parallel with efficient memory use.
- •For data center engineers: Deploy software that leverages GPU clusters to solve massive linear programs while minimizing inter-GPU communication overhead and memory limits.
Authors
Arnaud Deza, Santanu Dey, Pascal Van Hentenryck
Abstract
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