acceptodds
Under review as a conference paper at ICLR 2027

D-PDLP: Scaling First-Order Primal–Dual Optimization to Distributed Multi-GPU Systems

Abstract

We present a distributed framework of the Primal-Dual Hybrid Gradient (PDHG) algorithm for solving massive-scale linear programming (LP) problems. Although PDHG-based solvers perform strongly on single GPUs, computational throughput can become a performance bottleneck for sufficiently high-workload instances. To overcome this bottleneck, we propose D-PDLP, a distributed PDLP framework and, to our knowledge, the first to accelerate the complete PDLP solver across multiple GPUs. By combining two-dimensional partitioning with our load-balancing strategy, D-PDLP distributes primal-dual computation across GPUs while maintaining efficient GPU execution. To understand how D-PDLP scales across GPUs, we derive a PDLP-specific cost model that relates computation and communication costs to the processor-grid configuration and GPU count. The model guides resource selection, with case studies on contrasting sparse workloads demonstrating its predictive value. Extensive experiments on standard LP benchmarks, including MIPLIB and Mittelmann instances, and huge-scale real-world datasets show that our implementation, built upon cuPDLPx, achieves approximately speedup on eight GPUs for computationally intensive instances while maintaining numerical accuracy. Our solver is released as open-source software.

Primary area:
optimization
Keywords:
Linear Programming, Optimization, GPU

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_6kTGOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper provides a scalable PDLP for the distributed multi-GPU system. The authors claim their work is the first work that design PDLP for multi-GPU acceleration and the results on eight GPU achieve 6 times speedup. Despite their results I have many concerns which need author reply.

Critical strengths
  • Brand-new framework to scale PDLP to the mulit-GPU systems.
  • Achieve remarkable performance improvement on multi-GPUs.
Critical weaknesses
  1. Novelty is limit. I not expert in this field but in HPC. To my current understanding the bottleneck of this operation is just two SpMV operation and the author just tile the operation across GPUs. But this operation is a well-known and commonly used approach in HPC field. And there is many optimized method in SpMM and SpMV operations, which achieve efficient computation-communication overlap. For example https://arxiv.org/abs/1510.00844. But the authors only use global allreduce.

  2. The authors introduce the THEORETICAL COST MODEL. But this section is somehow independent. This model is a performance model to predict the each step total runtime. But I don’t see it specific contribution. What is the contribution to your whole work? How to guide you design and optimization. As a reviewer, I prefer to see these questions. Please provide more claims.

  3. No further system level optimization. Did the author leverage further kernel tailoring? My current understanding is that the author just invoke the official CUPDLPX. Did the single step optimization contain other operations you have designed? Please provide more details.

  4. Provide more experiment insights. I m very happy to see detailed breakdown evaluations and the scalability evaluations when you scale more GPUs. But not just runtime evaluations.

Questions for authors

See weakness.

9 comments
AuthorsOpenReview ↗

Response to Reviewer 6kTG (Part 1/2)

We sincerely thank the reviewer for the constructive HPC perspective. With local computational primitives held fixed, D-PDLP improves complete-solver execution through state layout, grid selection, load balancing, and communication organization. Changes are highlighted in blue.

1. Solver-level contribution and communication design (W1)

Building on established sparse-linear-algebra techniques, our contribution is multi-GPU acceleration of the complete PDLP solver. One layout supports both SpMV directions, primal–dual and Halpern updates, convergence checks, restarts, and primal-weight updates. Section 1 and Appendix L.1 clarify this contribution and discuss the cited SpGEMM work.

Core AllReduces use grid-axis communicators—groups of two and four GPUs on a 2×42\times4 grid—while replication-aware scalar reductions support stopping and restart metrics (Section 3.2; Appendix E.2). The implementation is bulk-synchronous; finer-grained overlap offers a complementary optimization.

2. How the cost model guides execution (W2)

The model makes two decisions before execution. For a fixed GPU count, the dimension-dependent term n/∣C∣+m/∣R∣n/|C|+m/|R| guides the grid shape. The full model, including matrix work, vector work, collective payload, and latency, then compares GPU counts. Sections 3.3 and 4.1 describe how these decisions enter AUTO.

To validate the grid decision directly, we added an experiment with the hardware fixed at eight H100 GPUs. The model chooses before timing; we then compare its selection with the measured fastest and slowest candidates. This experiment is now in Section 5.3, “Direct Validation of Grid Selection.”

Table R1. Model-selected, measured fastest, and measured slowest process grids on eight H100 GPUs. All times are milliseconds per iteration.

InstanceModel-selected gridSelected timeMeasured fastest gridFastest timeMeasured slowest gridSlowest timeOverhead relative to fastestSpeedup over slowest
mcf_2500_100_5001×81\times81.403461×81\times81.403468×18\times18.825070.00%6.29×
zib032×42\times41.404492×42\times41.404498×18\times12.245240.00%1.60×
sdm_50k_500k_15_102×42\times41.328191×81\times81.260068×18\times11.814205.41%1.37×

For selected, fastest, and slowest times Ts,Tf,TwT_s,T_f,T_w, overhead is 100(Ts/Tf−1)%100(T_s/T_f-1)\% and speedup is Tw/TsT_w/T_s. The model selects the fastest grid on two instances and is only 5.41% slower on the third. Its 6.29× gain over the slowest layout on the same eight GPUs demonstrates both the importance of grid choice and the practical value of the model.

The choice has a clear structural interpretation. mcf_2500_100_500 has approximately 83.5 times as many variables as constraints. Its selected 1×81\times8 layout makes each GPU's portion of A⊤yA^\top y local and requires only a reduction of the shorter constraint-space vector in the core iteration. Thus, the model translates matrix shape into a favorable computation and communication layout.

GPU-count selection is supported separately by the existing Table 1, Section 5.2: AUTO achieves the best aggregate shifted geometric means among the tested fixed counts, 18.38 seconds on Mittelmann and 7.31 seconds on MIPLIB. The new grid experiment and existing benchmark comparison therefore validate both configuration decisions. Point 4 below further explains their effects through measured execution components.

AuthorsOpenReview ↗

Response to Reviewer 6kTG (Part 2/2)

3. Systems design with unchanged local primitives (W3)

We retain cuPDLPx's local computational primitives to isolate the gains from the distributed design, as clarified in Appendix L.1. The existing ablation (Table 10, Appendix J.1; Section 5.4) shows that block-wise permutation with nonzero-aware cuts reduces aggregate solving time by 13.8% relative to fully random permutation with the same cuts and by 4.6% relative to block-wise permutation with uniform cuts.

We also added a separate ten-setting permutation-seed sweep in Appendix M.2 to test whether the balance depends on a particular random permutation. These results demonstrate stable load balance and local SpMV performance across the tested seeds.

4. Component-level insights and larger systems (W4)

To explain performance beyond total solving time, we profiled the C/CUDA implementation on zib03 with Nsight Systems. Each window covers 999 complete Halpern-to-Halpern cycles, excluding initialization. We report the GPU timeline of rank 2 for four GPUs and rank 3 for both eight-GPU layouts. These measurements have been added to Appendix M.3.

Table R2. Per-cycle GPU-timeline breakdown for zib03, in milliseconds.

ConfigurationSparse matrix–vector multiplication: all callsNCCL collective kernelsOther GPU kernelsCopies and gapsTotal cycle time
1 GPU, 1×11\times1 grid2.4680.0001.3850.0313.885
4 GPUs, 2×22\times2 grid0.8360.7670.7160.0372.356
8 GPUs, 1×81\times8 grid0.5500.7190.6480.0361.954
8 GPUs, 2×42\times4 grid0.4780.7040.4840.0431.710

The sparse matrix–vector multiplication column includes all local calls in the window, including periodic convergence checks; NCCL includes collective execution and synchronization waiting. These per-cycle profiles are separate from the grid-selection timing measurements in Table R1.

From one GPU to the 2×42\times4 layout, sparse matrix–vector multiplication improves by 5.16×, while the full profiled cycle improves by 2.27×. NCCL occupies 41.2% of the eight-GPU timeline, showing the importance of collective execution and synchronization alongside local computation.

The grid comparison is especially informative. Changing 1×81\times8 to 2×42\times4 reduces cycle time by 12.5% and other GPU kernel time from 0.648 to 0.484 milliseconds (25.3%), accounting for about two-thirds of the time saved. The model's dimension-dependent workload term decreases by 26.6% for this change. These corresponding reductions support optimizing the complete solver layout, including vector operations, rather than considering matrix–vector kernels alone.

To test larger systems, we added multi-node experiments in Appendix M.4, summarized in Section 7. The MetaX C550 system has four physical nodes with eight fully interconnected GPUs each, linked through rail-only PCIe Fabric. We measured solving time on one, two, and four nodes.

Table R3. Solving times on the MetaX C550 system.

Instance8 GPUs / 1 node (seconds)16 GPUs / 2 nodes (seconds)32 GPUs / 4 nodes (seconds)Speedup from 8 to 32 GPUs
mcf_2500_100_50016407873984.12×
zib035925433391.75×

Scaling from eight to thirty-two GPUs gives 4.12× solving-time speedup on mcf_2500_100_500 and 1.75× on zib03, demonstrating acceleration across physical nodes on another accelerator platform.

We also scaled mcf_2500_100_500 on Hygon with eight GPUs per node, PCIe within nodes, and InfiniBand between nodes, using the same implementation and settings across GPU counts.

Table R4. Average iteration times for mcf_2500_100_500 on the Hygon cluster.

Number of GPUs1248163264128
Average time per iteration (milliseconds)38.423.610.35.12.81.81.51.28

Iteration time decreases from 38.4 to 1.28 milliseconds, giving approximately 30× per-iteration speedup across sixteen nodes. Crossing from one node to two reduces iteration time from 5.1 to 2.8 milliseconds. At 128 GPUs, the solver reaches optimal status in 427.13 seconds after 333,600 iterations. These results extend the evaluation from a single eight-H100 server to physical multi-node systems, while the component profiles explain how the distributed design affects solver execution.

Although the paper claims to be the first to scale the PDLP method, I still find its technical novelty and contributions limited.

  • the primary contribution lie in the NCCL-based communication design. However, the paper lacks sufficient technical details and in-depth explanations of the proposed system architecture, making it difficult to assess the significance of this contribution.

  • the performance-model-guided load-balancing strategy is a well-established technique in the HPC community. The authors do not provide sufficient technical depth or analysis to demonstrate how their approach differs from existing methods.

  • the paper does not present any substantial kernel-level optimizations, instead relying primarily on existing library implementations. This further limits the technical novelty and overall contribution of the work.

Reviewer_Ewg3OpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper presents D-PDLP, a distributed implementation of PDHG-based linear programming on a two-dimensional GPU grid. Primal and dual vectors are replicated along grid axes, and AxAx and A⊤yA^\top y are synchronized through orthogonal AllReduce operations. The method combines block-wise random permutation with nonzero-aware marginal partitioning to reduce sparse load imbalance. A cost model guides the processor-grid shape and an AUTO choice among 1, 2, 4, and 8 GPUs. The paper reports speedups of about 6×6\times on selected large LPs and additional results for diagonal-QP Lasso formulations.

Critical strengths
  1. The distributed PDHG design is described end to end. The paper includes the primal and dual updates, KKT evaluation, restart logic, and primal-weight updates.

  2. The load-balancing study is useful. In Table 9, Block Random with nonzero-aware partitioning reduces SGM10 from 220.08 s to 75.85 s on the selected instances.

  3. The evaluation includes large sparse problems and strict-accuracy checks. Appendix L.4 reports identical iteration counts across GPU counts for the tested sdm and neos cases.

Critical weaknesses
  1. Independent marginal cuts do not guarantee balanced 2D blocks. If nonzeros are concentrated in correlated row-column regions, some local blocks can remain much denser than others.
  2. Timing and implementation comparisons complicate attribution. The main LP results use Julia, while supplementary results use C. Appendix I shows that the C version can change both runtime and iteration count.
  3. The QP extension is limited to diagonal Q and transformed Lasso formulations. Table 3 does not establish performance for general convex QPs with non-diagonal structure.
Questions for authors
  1. How are infinite bounds handled in the residual normalizers and duality-gap computation in Appendix C.4?
  2. What are the maximum and median local nnz counts and SpMV times after partitioning?
  3. How does D-PDLP behave across multiple nodes or without NVLink?
2 comments
AuthorsOpenReview ↗

Response to Reviewer Ewg3 (Part 1/2)

We sincerely thank the reviewer for the careful assessment. In response, we clarified infinite-bound handling, implementation comparisons, and the diagonal-QP extension, and added local load-balance, permutation-seed, and multi-node experiments. These changes are incorporated in the revised paper and highlighted in blue.

1. Infinite bounds in the stopping criteria (Q1)

We have clarified the two conventions in Section 2.1 and Appendices C.4 and E.1.

Primal normalization. The normalizer uses finite constraint bounds only, with each equality bound counted once. If bfinb_{\mathrm{fin}} collects these entries, the denominator is 1+∥bfin∥21+\|b_{\mathrm{fin}}\|_2. Distributed evaluation counts each distinct vector block once, accounting for replication across the grid.

Bound-dependent objective term. With yi+=max⁡{yi,0}y_i^+=\max\{y_i,0\} and yi−=max⁡{−yi,0}y_i^-=\max\{-y_i,0\}, for y∈Yy\in Y we evaluate

=\sum_{i:(u_c)_i<+\infty}(u_c)_i y_i^- -\sum_{i:(\ell_c)_i>-\infty}(\ell_c)_i y_i^+.$$ An infinite endpoint is omitted from its sum and represented by a multiplier restriction: $(\ell_c)_i=-\infty$ requires $y_i\le0$, and $(u_c)_i=+\infty$ requires $y_i\ge0$. If both endpoints are infinite, $y_i=0$. These are precisely the restrictions defining $Y$ in the saddle-point formulation (2); outside this domain, $p(-y;\ell_c,u_c)=+\infty$. Thus, finite-bound summation and the multiplier domain implement the support function while avoiding undefined products such as $0\cdot\infty$. Infinite endpoints remain in projections to represent unrestricted directions. ### 2. Two-dimensional balance and local sparse matrix–vector times (W1/Q2) We agree that balancing row and column marginal counts alone does not guarantee balanced two-dimensional blocks. Our method therefore applies block-wise permutation before the cuts to disperse correlated concentrations of nonzeros. We clarified this design in **Section 4.3** and added direct measurements in **Appendix M.1**. To isolate the permutation's effect, we reproduced the solver's host-side partitioning on raw matrices using the same code path and default seed. We counted nonzeros in every local block and compared marginal cuts alone with block-wise permutation followed by the same cuts. **Table R1. Local nonzero counts before and after block-wise permutation.** | Instance | Process grid | Cuts alone: maximum / median nonzeros | Cuts alone: maximum / median ratio | Permutation and cuts: maximum / median nonzeros | Permutation and cuts: maximum / median ratio | | --- | --- | ---: | ---: | ---: | ---: | | `zib03` | $2\times2$ | 35.71 / 26.11 | 1.368 | 26.11 / 26.11 | 1.0003 | | `zib03` | $2\times4$ | 18.31 / 13.05 | 1.403 | 13.08 / 13.05 | 1.0021 | | `neos-3208254-reiu` | $4\times2$ | 5.35 / 3.14 | 1.705 | 3.14 / 3.14 | 1.0031 | Without permutation, the densest block is approximately **37–71% above the median**. With permutation, the maximum/median ratio is at most **1.0031** across these configurations. The comparison demonstrates that the permutation step makes axis-wise cuts effective at balancing individual two-dimensional blocks. To check whether this balance carries over to execution, we extracted complete Nsight Systems traces for `zib03` on **all eight H100 GPUs**, using the automatically selected $2\times4$ grid. Each GPU's local sparse matrix–vector multiplication (SpMV) time is averaged over **999 core iterations**, excluding initialization and communication. We then take the median and maximum across GPUs; combined time sums both directions on each GPU before aggregation. **Table R2. Local core sparse matrix–vector multiplication times for `zib03`.** | Local operation | Median across GPUs (milliseconds) | Maximum across GPUs (milliseconds) | Maximum / median ratio | | --- | ---: | ---: | ---: | | $A_{ij}^{\top}y_i$ | 0.18553 | 0.18650 | 1.00526 | | $A_{ij}\bar{x}_j$ | 0.24711 | 0.24780 | 1.00281 | | Combined time for both directions | 0.43277 | 0.43430 | 1.00354 | The maximum exceeds the median by only **0.53%** and **0.28%** for the two directions, and **0.35%** for their sum. Thus, the balanced nonzero counts are accompanied by closely matched local execution times. We also added a separate **ten-setting permutation-seed sweep** in **Appendix M.2** to test whether the balance depends on a particular random permutation. These results demonstrate stable load balance and local SpMV performance across the tested seeds. The existing solver-level ablation in **Table 10, Appendix J.1**, complements these measurements: block-wise permutation with nonzero-aware cuts improves aggregate solving time by **13.8%** over fully random permutation with the same cuts and by **4.6%** over block-wise permutation with uniform cuts.
AuthorsOpenReview ↗

Response to Reviewer Ewg3 (Part 2/2)

3. Separating distributed acceleration from implementation changes (W2)

We have clarified the comparison structure in Section 5.1 and Appendix I. The main LP benchmark speedups in Tables 1 and 3 compare GPU counts within Julia. The strict-accuracy experiments compare GPU counts within C/CUDA. Each distributed speedup therefore uses a matched implementation; Table 9, Appendix I, separately reports the Julia–C/CUDA comparison.

The C/CUDA results serve two purposes: to show that distributed acceleration persists across implementations and that C/CUDA can further reduce aggregate absolute solving times. The existing comparison reduces the shifted geometric mean from 101.2 to 86.1 seconds on four GPUs and from 77.7 to 62.2 seconds on eight GPUs.

The existing strict-accuracy test in Table 14, Appendix L.4, directly isolates execution speed. On raw sdm_50k_500k_15_10 at 10−810^{-8} tolerance, C/CUDA takes exactly 340,200 iterations on one, four, and eight GPUs, with solving times of 1368.142, 420.967, and 236.394 seconds. The 5.788× speedup therefore comes from executing the same optimization workload faster. Table 15 likewise reports identical iteration counts across GPU configurations for neos-3208254-reiu at each tested tolerance.

Solving time covers the iterative phase and excludes loading and one-time preprocessing. The existing Table 11, Appendix J.2, reports permutation and partitioning costs separately, making the timing convention explicit.

4. Scope of the quadratic-programming extension (W3)

The implemented extension targets convex quadratic programs with diagonal QQ, and we have made this scope explicit in Section 6 and Appendix L.7. Partitioning the diagonal alongside the primal variables keeps the update componentwise and local, preserving the LP communication pattern without additional collectives.

The existing comparison in Table 4, Section 6, gives all solvers the same lifted Lasso formulation at 10−610^{-6} tolerance. It reports up to 4.70× speedup over single-GPU PDHCG-II, demonstrating that the distributed layout also accelerates this class of quadratic programs. The revision ties the performance claim directly to this formulation and explains the local update that enables the extension.

5. Multiple nodes and interconnects other than NVLink (Q3)

To test execution beyond one NVLink server, we added experiments on a four-node MetaX C550 system, with eight fully interconnected GPUs per node and rail-only PCIe Fabric between nodes. We measured solving time with eight, sixteen, and thirty-two GPUs (Appendix M.4; Section 7).

Table R4. Solving times on the MetaX C550 system.

Instance8 GPUs / 1 node (seconds)16 GPUs / 2 nodes (seconds)32 GPUs / 4 nodes (seconds)Speedup from 8 to 32 GPUs
mcf_2500_100_50016407873984.12×
zib035925433391.75×

Both instances benefit from additional physical nodes: the eight-to-thirty-two-GPU speedups are 4.12× for mcf_2500_100_500 and 1.75× for zib03.

The cost model provides a structural explanation for the difference. mcf_2500_100_500 has approximately 83.5 times as many variables as constraints. Its aspect ratio favors column-only grids: each GPU computes its portion of A⊤yA^\top y locally, while the core iteration reduces only the shorter constraint-space vector. zib03 favors a two-dimensional layout with both reduction directions. Section 5.3 connects these matrix properties to grid selection.

We further tested mcf_2500_100_500 on Hygon with eight GPUs per node, PCIe within nodes, and InfiniBand between nodes, keeping the implementation and settings fixed across GPU counts.

Table R5. Average iteration times for mcf_2500_100_500 on the Hygon cluster.

Number of GPUs1248163264128
Average time per iteration (milliseconds)38.423.610.35.12.81.81.51.28

The average iteration time falls from 38.4 to 1.28 milliseconds, giving approximately 30× per-iteration speedup. Scaling continues across the first node boundary, from 5.1 milliseconds on eight GPUs to 2.8 milliseconds on sixteen. The 128-GPU run reaches optimal status in 427.13 seconds after 333,600 iterations. Together, the MetaX and Hygon results demonstrate distributed acceleration across physical nodes and interconnects beyond NVLink.

Reviewer_W9pvOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper introduces a multi-GPU distributed implementation of the PDLP first-order LP solver. The method is named D-PDLP and distributes constraint matrix over a two-dimensional GPU grid, with primal vectors replicated along columns and dual vectors along rows so that each device computes its local sparse matrix-vector products without communication. To handle irregular sparsity, D-PDLP combines adaptive grid selection, block-wise random permutation, and nonzero-aware partitioning along each axis. The authors derive a per-iteration cost model covering matrix and vector memory traffic, collective payload, and synchronization latency, and use it in an AUTO scheduler that chooses a GPU countand a grid shape before execution. Experiments show that PDLP reduces wall-clock solving time versus baselines up to about 6X while matching accuracy with identical optimization iteration counts.

Critical strengths
  1. T primal and dual replication are designed around the two SpMV operations, so local products require no inter-device communication and only two orthogonal AllReduce phases occur per iteration. This is a systems contribution with a clear reference point, and it demonstrates that distributed PDLP is feasible without redesigning the algorithm.

  2. The process that fully random permutation balances nonzeros but destroys local block structure is demonstrated by the ablation. This is a practical heuristic with a rationale and a well-isolated empirical contribution.

  3. Honest reporting of negative and mixed results. The paper does not hide that MIPLIB Small peaks at two GPUs and degrades at eight or that MIPLIB Overall at eight GPUs is worse than at one. This reporting disclose limitations and clarifies shortcoming.

  4. Because QQ is diagonal, the QP version adds no collectives to the LP communication pattern. D-PDHCG is fastest on every reported LASSO instance, often by large margins. This demonstrates that the framework transfers beyond LP with minimal new machinery.

  5. The paper specifies grid selection, block size, nonzero-aware cuts, solution mapping, collective payloads, and parameter values. This will make reproducing the results easier.

Critical weaknesses
  1. It looks like all experiments use eight H100s on one node, with no multi-node runs, no InfiniBand, and no larger NVLink domain. Framing the contribution as multi-GPU'' rather than multi-node'' is defensible, but the practical ceiling is eight devices.

  2. The method’s advantage is concentrated on very large, matrix-heavy instances, and a practitioner with mixed workloads cannot simply enable eight GPUs. Efficiency is below 75% even in the good cases.

  3. Partitioning is heuristic, one-dimensional, and single-seed. Nonzero-aware cuts balance row and column nonzero counts independently along each axis. The ablation uses one C implementation and a handful of instances. Given that load balance drives most of the gain, a stronger partitioner or a seed study could yield more improvements.

4.The main comparison is against single-GPU and internal configurations. More comparisons against wider baselines and setups are necessary.

  1. SOTA performance is supported narrowly. D-PDHCG is fastest on every LASSO instance against all listed QP solvers, and D-PDLP beats cuPDLPx, ABIP, and ABIP2, establishing SOTA within the first-order and PDLP families. It is not overall LP SOTA.
Questions for authors
  1. How does D-PDLP perform across multiple nodes, and where is the communication-dominated crossover?

  2. How sensitive are the results to permutation seed, block size, and partitioner choice?

  3. Does the Lasso-to-QP conversion and the diagonal-QQ restriction bias the QP comparison? How would D-PDHCG compare with general QP solvers operating on the compact Lasso form?

5 comments
AuthorsOpenReview ↗

Response to W1/Q1: Multi-node execution and scaling behavior

We sincerely thank the reviewer for the careful assessment. In response, we added multi-node, grid-selection, permutation-seed, and profiling experiments to complement the block-size and partitioning studies. We have incorporated these results in the revised paper. Changes are highlighted in blue.

To test scaling beyond eight GPUs, we ran mcf_2500_100_500 and zib03 on four MetaX C550 nodes. Each node has eight fully interconnected GPUs; nodes communicate through rail-only PCIe Fabric. We measured solving time on one, two, and four nodes (Appendix M.4; Section 7).

Table 1. Solving times on the MetaX C550 system.

Instance8 GPUs / 1 node (seconds)16 GPUs / 2 nodes (seconds)32 GPUs / 4 nodes (seconds)Speedup from 8 to 32 GPUs
mcf_2500_100_50016407873984.12×
zib035925433391.75×

The 4.12× and 1.75× speedups demonstrate acceleration across physical nodes without NVLink.

For the requested InfiniBand setting, we scaled mcf_2500_100_500 on a Hygon cluster with eight GPUs per node, PCIe within nodes, and InfiniBand between nodes. We kept the implementation and settings fixed across GPU counts (Appendix M.4).

Table 2. Average iteration times for mcf_2500_100_500 on the Hygon cluster.

Number of GPUs1248163264128
Average time per iteration (milliseconds)38.423.610.35.12.81.81.51.28

Iteration time falls from 38.4 to 1.28 milliseconds, giving 30× per-iteration speedup. The improvement continues across the first node boundary, from 5.1 milliseconds on eight GPUs to 2.8 milliseconds on sixteen. At 128 GPUs across sixteen nodes, the solver reaches optimal status in 427.13 seconds after 333,600 iterations.

To examine when additional nodes stop helping, we also compared eight and sixteen GPUs on a separate two-node MetaX C588 system (Appendix M.4).

Table 3. Solving times on the two-node MetaX C588 system.

Instance8 GPUs (seconds)16 GPUs (seconds)
mcf_2500_100_500793460
wil5048103

The additional node accelerates mcf_2500_100_500 but slows wil50. On Hygon, gains taper beyond thirty-two GPUs: doubling to sixty-four and then 128 GPUs gives 1.20× and 1.17× further speedups. These observations identify practical scaling limits and motivate resource selection based on the workload.

To examine iteration costs, we profiled C/CUDA on zib03 with Nsight Systems on H100 GPUs over 999 Halpern-to-Halpern cycles, excluding initialization. The reported timelines are rank 2 for four GPUs and rank 3 for both eight-GPU layouts (Appendix M.3).

Table 4. Per-cycle GPU-timeline breakdown for zib03, in milliseconds.

ConfigurationSparse matrix–vector multiplication: all callsNCCL collective kernelsOther GPU kernelsCopies and gapsTotal cycle time
1 GPU, 1×11\times1 grid2.4680.0001.3850.0313.885
4 GPUs, 2×22\times2 grid0.8360.7670.7160.0372.356
8 GPUs, 1×81\times8 grid0.5500.7190.6480.0361.954
8 GPUs, 2×42\times4 grid0.4780.7040.4840.0431.710

Sparse matrix–vector multiplication includes periodic convergence checks; NCCL time includes collective execution and synchronization waiting. From one GPU to the 2×42\times4 layout, matrix–vector multiplication improves by 5.16×, while the full profiled cycle improves by 2.27×. NCCL accounts for 41.2% of that eight-GPU timeline. This supports modeling sparse matrix work, vector operations, and communication jointly.

AuthorsOpenReview ↗

Response to W2: Mixed workloads and automatic resource selection

AUTO addresses mixed workloads by selecting the GPU count and grid for each instance before execution. The existing benchmark comparison in Table 1, Section 5.2 uses Julia on an eight-H100 NVLink server, a stopping tolerance of 10−410^{-4}, and time limits of 3600 seconds for Mittelmann and 1200 seconds for MIPLIB. It compares AUTO with fixed counts of one, two, four, and eight GPUs.

These results show why a single configuration is insufficient: smaller problems favor fewer GPUs, while eight GPUs reduce the MIPLIB Large aggregate time from 90.34 to 56.81 seconds and increase the solved count from 13 to 20. Across the full suites, AUTO achieves the best shifted geometric means: 18.38 seconds on Mittelmann and 7.31 seconds on MIPLIB. We have clarified this practical role in Appendix L.5.

To test the grid decision directly, we added a comparison with the GPU count fixed at eight H100 GPUs. The model chooses before execution; we then compare its selection with the measured fastest and slowest candidates. This experiment is now in Section 5.3, “Direct Validation of Grid Selection.”

Table R5. Model-selected, measured fastest, and measured slowest process grids on eight H100 GPUs. All times are milliseconds per iteration.

InstanceModel-selected gridSelected timeMeasured fastest gridFastest timeMeasured slowest gridSlowest timeOverhead relative to fastestSpeedup over slowest
mcf_2500_100_5001×81\times81.403461×81\times81.403468×18\times18.825070.00%6.29×
zib032×42\times41.404492×42\times41.404498×18\times12.245240.00%1.60×
sdm_50k_500k_15_102×42\times41.328191×81\times81.260068×18\times11.814205.41%1.37×

For selected, fastest, and slowest times Ts,Tf,TwT_s,T_f,T_w, overhead is 100(Ts/Tf−1)%100(T_s/T_f-1)\% and speedup is Tw/TsT_w/T_s. The model finds the fastest grid on two instances and is only 5.41% slower on the third. The 6.29× gain over the slowest grid on the same eight GPUs demonstrates both the importance of grid choice and the model's practical value.

The choice also has a clear structural explanation. mcf_2500_100_500 has 83.5 times as many variables as constraints (126,250,100 versus 1,512,600). Its selected 1×81\times8 layout partitions variables, computes each GPU's portion of A⊤yA^\top y locally, and reduces only the shorter constraint-space vector in each core iteration.

Regarding efficiency, the original Julia result for sdm_50k_500k_15_10 gives 6.18× eight-GPU speedup, or approximately 77% parallel efficiency (Table 3, Section 5.2). The existing strict-accuracy experiment in Table 14, Appendix L.4 further isolates execution speed: C/CUDA at 10−810^{-8} takes exactly 340,200 iterations on one, four, and eight GPUs, giving 5.788× eight-GPU speedup. Thus, the distributed implementation executes the same optimization workload faster.

AuthorsOpenReview ↗

Response to W3/Q2: Seed, block size, and partitioner sensitivity

Our layout is two-dimensional, with cut locations computed separately along each axis. Block-wise permutation precedes the cuts to disperse correlated concentrations of nonzeros while preserving local blocks. To measure its effect, we added a comparison using the solver's host-side partitioning on raw matrices with the default seed and counted nonzeros in every local block. Comparing marginal cuts alone with permutation followed by the same cuts isolates the permutation's effect (Section 4.3; Appendix M.1).

Table R6. Local nonzero counts before and after block-wise permutation. Counts are in millions; ratios are computed from the underlying unrounded counts.

InstanceProcess gridCuts alone: maximum / median nonzerosCuts alone: maximum / median ratioPermutation and cuts: maximum / median nonzerosPermutation and cuts: maximum / median ratio
zib032×22\times235.71 / 26.111.36826.11 / 26.111.0003
zib032×42\times418.31 / 13.051.40313.08 / 13.051.0021
neos-3208254-reiu4×24\times25.35 / 3.141.7053.14 / 3.141.0031

Without permutation, the densest block is approximately 37–71% above the median. With permutation, the maximum/median ratio is at most 1.0031. Permutation therefore enables balanced two-dimensional blocks after axis-wise cuts.

To check execution balance, we collected complete zib03 traces on all eight H100 GPUs with the selected 2×42\times4 grid. Each GPU's local time is averaged over 999 core iterations, excluding initialization and communication; the table then takes the median and maximum across GPUs. Combined time sums both directions per GPU before aggregation (Appendix M.1).

Table R7. Local core sparse matrix–vector multiplication times for zib03.

Local operationMedian across GPUs (milliseconds)Maximum across GPUs (milliseconds)Maximum / median ratio
Aij⊤yiA_{ij}^{\top}y_i0.185530.186501.00526
AijxˉjA_{ij}\bar{x}_j0.247110.247801.00281
Combined time for both directions0.432770.434301.00354

The combined maximum exceeds the median by only 0.35%, showing closely matched local execution times across all eight GPUs.

To test seed sensitivity, we added a separate ten-seed sweep (Appendix M.2). We measured local nonzero counts and both matrix–vector directions. Excess is 100(max⁡/median−1)%100(\max/\mathrm{median}-1)\% across GPUs; combined time again sums both directions per GPU first.

Table R8. Complete permutation-seed sensitivity results.

Permutation seedNonzero-count excess (%)Aij⊤yiA_{ij}^{\top}y_i time excess (%)AijxˉjA_{ij}\bar{x}_j time excess (%)Median combined time (milliseconds)Combined-time excess (%)
Default0.2143.0202.8350.397562.935
20.4661.3291.5810.396181.411
30.1450.7010.2040.396530.121
50.4570.7921.4600.394881.255
70.3462.6273.2240.397812.792
110.4170.2170.7280.395580.495
170.2390.5651.1050.395720.725
420.3540.5540.5990.395620.576
1010.3410.1730.6910.395410.347
20260.0580.4890.5700.395550.314

Across the ten settings, nonzero-count excess stays below 0.5% and combined-time excess below 3%. Median combined time ranges from 0.39488 to 0.39781 milliseconds, a spread of only 0.742% relative to the minimum. This demonstrates stable load balance and local execution across the tested seeds.

The original block-size study in Table 13, Appendix L.3 varies only B∈{4,32,128,256,1024}B\in\{4,32,128,256,1024\} on four instances, using C/CUDA, eight H100 GPUs, 10−610^{-6} tolerance, a common seed, and fixed CUDA kernels. All twenty runs reach optimal status. For B=32B=32–10241024, the shifted geometric mean remains within 1.4% of the best; the default B=256B=256 is within 0.9%. This broad plateau supports the default block size.

The existing ablation in Table 10, Appendix J.1, discussed in Section 5.4, compares all six combinations of three permutation schemes and two cutting strategies on nine instances, each on four and eight GPUs. Block-wise permutation with nonzero-aware cuts achieves the lowest aggregate time, 75.85 seconds: 13.8% below fully random permutation with nonzero-aware cuts and 4.6% below block-wise permutation with uniform cuts. These comparisons establish complementary gains from the two components; the new measurements above show that the resulting local balance is stable across seeds.

The preprocessing measurements already reported in Table 11, Appendix J.2 show that permutation and partitioning consume only 0.14%–4.47% of the solving-time saving from one to eight GPUs. The pipeline therefore delivers its gains at a small one-time cost.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.