dorsal/arxiv
View SchemaBeyond Single-GPU: Scaling PDLP to Distributed Multi-GPU Systems
| Authors | Hongpei Li, Yicheng Huang, Huikang Liu, Dongdong Ge, Yinyu Ye |
|---|---|
| Categories | |
| ArXiv ID | 2601.07628vv1 |
| URL | https://arxiv.org/abs/2601.07628 |
| License | http://creativecommons.org/licenses/by/4.0/ |
Abstract
In this work, we present a distributed implementation of the Primal-Dual Hybrid Gradient (PDHG) algorithm for solving massive-scale linear programming (LP) problems. Although PDHG-based solvers have shown strong performance on single-node GPU architectures, their applicability to industrial-scale instances is often limited by GPU memory capacity and computational throughput. To overcome these challenges, we extend the PDHG framework to a distributed-memory setting via a practical two-dimensional grid partitioning of the constraint matrix, enabling scalable execution across multiple GPUs. Our implementation leverages the NCCL communication backend to efficiently synchronize primal-dual updates across devices. To improve load balance and computational efficiency, we introduce a block-wise random shuffling strategy combined with nonzero-aware data distribution, and further accelerate computation through fused CUDA kernels. By distributing both memory and computation, the proposed framework not only overcomes the single-GPU memory bottleneck but also achieves substantial speedups by exploiting multi-GPU parallelism with relatively low communication overhead. Extensive experiments on standard LP benchmarks, including MIPLIB and Hans' instances, as well as large-scale real-world datasets, show that our distributed implementation, built upon cuPDLPx, achieves strong scalability and high performance while preserving full FP64 numerical accuracy.
{
"annotation_id": "22283269-df1c-4ba4-b282-40759ff0b67f",
"date_created": "2026-02-17T05:53:11.619000Z",
"date_modified": "2026-02-17T05:53:11.619000Z",
"file_hash": "a3f9589b3e0f1ccfd6b14dc7bb98cf29e1289ea9d5e2bf526cf9060286c913db",
"private": false,
"record": {
"abstract": "In this work, we present a distributed implementation of the Primal-Dual Hybrid Gradient (PDHG) algorithm for solving massive-scale linear programming (LP) problems. Although PDHG-based solvers have shown strong performance on single-node GPU architectures, their applicability to industrial-scale instances is often limited by GPU memory capacity and computational throughput. To overcome these challenges, we extend the PDHG framework to a distributed-memory setting via a practical two-dimensional grid partitioning of the constraint matrix, enabling scalable execution across multiple GPUs. Our implementation leverages the NCCL communication backend to efficiently synchronize primal-dual updates across devices. To improve load balance and computational efficiency, we introduce a block-wise random shuffling strategy combined with nonzero-aware data distribution, and further accelerate computation through fused CUDA kernels. By distributing both memory and computation, the proposed framework not only overcomes the single-GPU memory bottleneck but also achieves substantial speedups by exploiting multi-GPU parallelism with relatively low communication overhead. Extensive experiments on standard LP benchmarks, including MIPLIB and Hans\u0027 instances, as well as large-scale real-world datasets, show that our distributed implementation, built upon cuPDLPx, achieves strong scalability and high performance while preserving full FP64 numerical accuracy.",
"arxiv_id": "2601.07628",
"authors": [
"Hongpei Li",
"Yicheng Huang",
"Huikang Liu",
"Dongdong Ge",
"Yinyu Ye"
],
"categories": [
"math.OC",
"cs.DC"
],
"license": "http://creativecommons.org/licenses/by/4.0/",
"title": "Beyond Single-GPU: Scaling PDLP to Distributed Multi-GPU Systems",
"url": "https://arxiv.org/abs/2601.07628",
"version": "v1"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "f7e6d060-8826-42b8-8b83-6b2352963b9c",
"id": "arXiv Dataset",
"type": "Model",
"variant": "snapshot-2026-01-17",
"version": "0.1.0"
},
"user_id": 1000002
}