NVIDIA has detailed the multi-GPU Primal-Dual hybrid gradient (mPDLP) solver in NVIDIA cuOpt, designed to scale linear programming (LP) optimization problems across multiple GPUs connected via NVLink. The implementation distributes sparse matrix-vector multiplication (SpMV) operations using min-cut graph partitioning, allowing mathematical models with over 100 million variables to be solved within practical planning windows.
Min-Cut Graph Partitioning
The mPDLP solver addresses memory limits and convergence times in large optimization workloads by distributing operations across NVLink-connected GPUs. First-order Primal-Dual hybrid gradient methods rely on repeating SpMV calculations using a linear constraint matrix and its transpose. To distribute these steps without severe communication bottlenecks, cuOpt converts the constraint matrix into a bipartite graph and applies a min-cut partitioning algorithm.
This partitioning keeps tightly coupled variables and constraints on the same physical GPU. Computations are executed locally where possible, while cross-device data transfers over NVLink, NVSwitch, and NCCL libraries are confined to edges that cross partition boundaries.
Benchmark Speedups and Memory Savings
Distributing constraint matrices yields up to a 6x reduction in peak memory consumption per GPU for linear programs capped at 2.1 billion nonzeros compared to single-GPU implementations. Benchmark evaluations across more than 100 benchmark datasets demonstrated that performance scaling correlates with matrix density, showing significant speedups once problems exceed 10 million nonzeros.
In isolated iterative execution steps, mPDLP achieved up to an 11.4x speedup on the tsp-gaia-10m benchmark, translating to a 4.2x end-to-end runtime reduction. When evaluated against 2D-partitioned multi-GPU solvers like D-PDLP, mPDLP achieved speedups between 1.2x and 2.5x on the majority of tested large-scale instances.
Partner Testing and Workload Limitations
In corporate implementations, supply chain software provider Kinaxis reported a 3.3x speedup on a production planning model containing over 135 million variables running on eight NVIDIA H100 GPUs. Energy modeling company PSR achieved over a 5x speedup on an energy system capacity model featuring 185 million variables using eight NVIDIA B200 GPUs.
However, NVIDIA notes explicit performance boundaries. Small linear programs incur inter-GPU synchronization overhead that outweighs parallel execution benefits. Furthermore, optimization problems with sparsity patterns that yield high edge-cut ratios after partitioning trigger heavy cross-device communications, which can diminish or reverse multi-GPU speedups.
AI-generated editorial illustration; not a documentary photograph.
Source: Scaling Decision Optimization to 100 Million Variables and Beyond with mPDLP in NVIDIA cuOpt
SIGNAL TITANS
Leave a Reply