CS Paper Radar

PaNGEA: Parallel Node Generation and Exploration Algorithm on GPU

Jean Pauphilet, Yupeng Wu

cs.DC math.OC ·submitted 2026-10-02 10:09 UTC · v1

Abstract

Primal heuristics for finding high-quality feasible solutions are an important component in mixed-integer optimization (MIO) solvers. Recent advances in GPU-accelerated optimization algorithms show the potential of GPU acceleration for continuous optimization. In this paper, we introduce the Parallel Node Generation and Exploration Algorithm (PaNGEA), a GPU-friendly MIO primal heuristic. PaNGEA explores restricted subproblems by combining linear-relaxation solves with a local-search procedure designed for efficient batched execution on GPUs. In addition, instead of relying on a single heuristic for iterative variable fixing, we leverage GPU batching capabilities to generate and explore multiple subproblems in parallel. PaNGEA leverages GPU capabilities in two ways. First, on 283 MIPcc26 and MIPLIB instances, implementing a single-node primal heuristic on the GPU reduces the average gap integral by 8-18% relative to its CPU counterpart. Second, generating and exploring multiple nodes in parallel further reduces the average gap integral by 12-19%.

Closest papers

Nearest neighbours by meaning across the whole index.

A Per-Step Load-Balancing Engine for Expert-Parallel MoE Serving

cs.AR cs.DC ·2026-11-08 ·Jingyuan Li, Maolin Wang, Hayden So
code/data similarity 0.70
Abstract · An anonymous version of this manuscript was submitted to HPCA 2027 on August 1, 2026. The original submission PDF and its SHA-256 checksum a…

In expert-parallel Mixture-of-Experts serving, a layer finishes only when the most loaded GPU of its group does. Token routing shifts at every decode step and concentrates on a few experts, so most of the group's reserved GPU time waits on stragglers. Recovering that time means re-deciding, at every layer of every decode step, how each replicated expert's tokens divide between its copies. The exact linear-program solvers that make this decision optimally take longer than many of the layers they serve, and their working set outgrows GPU shared memory at deployment scale. We introduce Relief, a bidirectional pairwise relaxation that makes the linear program unnecessary, coming within a fraction of a point of the per-step optimum in a few passes of integer halving over the token counts. We build and measure three deployments, CUDA kernels on the serving GPU, the same verified engine on an FPGA over PCIe, and a fixed-function block beside the accelerator. On decode routing from three open MoE families, Relief holds the balance near the per-step optimum at every group size and layer time measured. Scored as effective utilization relative to that optimum, the kernel alone matches or exceeds every deployable scheme at every group size, from the hundred-microsecond layer on. The on-die engine widens that lead at every point, recovering up to 37.3 percentage points over the deployed static placement, while adding 0.02% of a current accelerator's transistors.

0.33

Speeding up Automated Algorithm Design by Batch Evaluation: A Case Study of Genetic Programming for Ant Colony Optimisation

cs.NE cs.DC ·2026-11-15 ·Bo-Cheng Lin, Yi Mei, Mengjie Zhang
similarity 0.68
Abstract

Evaluation is becoming the bottleneck of automated algorithm design, especially for iterative algorithms such as ant colony optimisation (ACO), which must run to completion on multiple instances. A transition rule designed by genetic programming reads the construction state of each ant and must be evaluated at every step. However, existing GPU methods for ACO precompute a fixed rule and parallelise the ants of one run. To address this issue, we propose BlockEval, a batch evaluation framework with GPU and CPU backends. The GPU backend executes many runs simultaneously, each as a whole in one thread block, and compiles one module per generation. When an ant has visited all its candidate cities, a warp-cooperative fallback stalls only its warp where possible. On travelling salesman problems with 50--1000 cities, the GPU backend is 4.1--16.5 times faster than the CPU backend on 32 cores and 11.2--17.8 times faster than EvoGP+TensorACO-CL.

0.30

Graph Coarsening Enables Escaping Local Optima in Compute-Constrained Nonconvex MAX-CUT

cs.LG cs.AIcs.CLmath.NA+1 ·2026-10-13 ·M. Harper Langston, Pierre-David Letourneau, Dalton Jones, Harris Teague, Peter Scott +5 more
publishedbenchmark similarity 0.67
Abstract

Because its binary optimization landscape contains exponentially many local optima, MAX-CUT is highly sensitive to initialization. We study Particle Polynomial Relaxation (PPR), a moment-based nonconvex continuous reformulation possessing an advantageous optimization landscape. We warm-start PPR with Combinatorial Multigrid (CMG), a spectral graph-coarsening method that produces structure-aware initial solutions in near-linear time without training data. On \texttt{t2g20} ($n=400$), benchmark instance with known exact optimum, the combined CMG+PPR pipeline reaches $97.5\%$ of optimum on average and $98.4\%$ on the best run. An extended variant with discrete local-search refinement reaches the published optimum on all sixty Biq Mac instances evaluated by a recent neural branch-and-bound method. Using a sparse CSR representation, the same approach scales to G-set instances with up to $20{,}000$ vertices reducing memory requirements by up to $3333\times$ while maintaining a consistent improvement over the CMG warm start. Gains are largest on sparse weighted graphs; on dense graphs we complement the pipeline with spectral sparsification.

0.31

MemX: Memory-Aware Automatic Parallelism for Cross-Vendor Heterogeneous GPU Training

cs.DC ·2026-10-30 ·Lin Meng, Yuzhong Sun, Jie Zhu
similarity 0.66
Abstract · 18 pages, 10 figures

Cross-vendor heterogeneous GPU clusters are increasingly used for large-scale model training. However, their GPUs differ substantially in compute power, memory capacity, and interconnect characteristics. Existing automatic parallelism training systems usually minimize iteration time while treating memory as a hard constraint, almost failing in resolving the compute--memory asymmetry of cross-vendor clusters regardless correlation between memory and throughput. In this paper, we present MemX, a new memory-aware automatic parallelism system that jointly optimizes iteration time, peak memory usage, and cross-GPU memory balance. MemX consists of a weighted-product objective function, heterogeneous recomputation strategies, a minimal-set profiler, interpolation-based data augmentation, a dual-output XGBoost predictor, and a hash-signature prediction cache, in order to accelerate search of large-scale auto-parallel best configurations at lower cost. We implement MemX on Megatron-LM and evaluate it against four automatic parallelism baselines on two heterogeneous clusters. MemX achieves the lowest prediction Mean Absolute Percentage Error (MAPE) of 12.17% and is the only method that identifies the real Top-1 configuration under both time-based and memory-balance rankings. In terms of search cost and search space, MemX searches 31,240 configurations in 26.5 seconds, while an end-to-end profiling baseline is extrapolated to require about 17 days at the same scale. The simulation study that extends the measured 20-GPU data to 40-GPU and 60-GPU clusters further illustrates the effectiveness of MemX at larger scales.

0.22

TrainBridge: Agentic NPU Training Optimization Guided by GPU Compilation Evidence

cs.CL cs.AI ·2026-10-21 ·Yupeng Chen, Kunxiang Zhao, Xingjian Wang, Yue Zhao, Yijing Wu +4 more
similarity 0.66
Abstract

We study how to improve training efficiency on Ascend NPUs. In the NPU training programs we study, framework-level compilation optimizations such as operator fusion are only partially applied, leaving fragmented computation and avoidable execution overheads. Profiling-guided tuning can address these inefficiencies, but it often requires costly trial and error. To make training on NPUs more efficient, we propose TrainBridge, an agentic approach for transferring GPU optimization guidance to NPU training. TrainBridge uses the highly optimized execution produced by mature GPU compilation stacks as a task-specific reference for NPU tuning. It extracts optimization intents from the GPU training execution to guide NPU program rewrites and further refines the rewritten program through iterative profiling. Our GPU-to-NPU migration experiments show that TrainBridge achieves an average 1.7x speedup across four workloads covering LLM pretraining, image classification, and vision-language training, and an average speedup of nearly 2.0x across 27 Modded-NanoGPT speedrun records with highly optimized GPU implementations.

0.16

Distributed Linear Programming on GPU Clusters at Extreme Scale

cs.DC math.OC ·2026-09-08 ·Arnaud Deza, Santanu S. Dey, Pascal Van Hentenryck
publishedbenchmarkcode/data similarity 0.65
Abstract · 21 pages, 5 figures. Accepted at the 18th Annual Workshop on Optimization for Machine Learning (OPT 2026), NeurIPS 2026

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 solves ten 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. The code for SHARDLP is available at https://github.com/ArnaudDeza/ShardLP.

0.76

HIERA: Workload-Aware Planning Across Implementation Spaces for GPU Kernel Optimization

cs.DC cs.AI ·2026-08-21 ·Jinghao Wang, Qiqi Gu, Chenpeng Wu, Jianguo Yao, Haibing Guan +1 more
similarity 0.65
Abstract

High-performance GPU kernels underpin modern deep learning and scientific computing. As workloads become increasingly diverse and GPU hardware evolves rapidly, developing efficient methods for automated GPU kernel generation and optimization has become increasingly important. Existing LLM-based methods typically optimize within a fixed implementation space, limiting either optimization flexibility or search efficiency. We propose \textsc{HIERA}, a hierarchical search-space planning framework for GPU kernel optimization. \textsc{HIERA} constructs contract-augmented task specifications, selects an appropriate implementation space across PyTorch operators, CUDA libraries, and custom CUDA kernels, and uses profiling feedback and expert knowledge to guide structured iterative refinement. Experiments on KernelBench across multiple various workload levels and base LLMs show that \textsc{HIERA} delivers stronger overall implementation validity, sample efficiency, and optimization performance than existing training-free methods, while remaining competitive with the training-based CUDA-L1 without additional model training. A case study on a specialized stencil operator from scientific computing further achieves a \(1.53\times\) speedup over cuDNN, demonstrating the potentiality of the general framework beyond standard machine-learning workloads.

0.39

Efficient Constant Optimization for Symbolic Regression with GPU-Accelerated Tree-Based Genetic Programming

cs.NE cs.DCcs.LGcs.MS ·2026-09-03 ·Hao Mao, Xu Tony Liu, Shuai Lu, Peng Zhao, Wenzheng Jiang +1 more
publishedbenchmarkcode/datahot direction similarity 0.65
Abstract · Accepted at the 30th Annual IEEE High Performance Extreme Computing Conference (HPEC 2026), 14-18 September 2026. To appear in IEEE Xplore

Constant optimization refines the numerical coefficients of candidate expressions in tree-based genetic programming for symbolic regression. But its per-generation cost has led modern GPU-accelerated frameworks to omit it or restrict it to lightweight forms. We present a GPU-resident, batched Levenberg--Marquardt solver that optimizes constants across a structurally heterogeneous population of expression trees using a fixed number of population-wide CUDA launches per iteration. Reverse-mode automatic differentiation assembles the per-tree Jacobian in one backward sweep, making the dominant per-iteration cost independent of the number of constants per tree, and a double-precision delivery guard guarantees that returned constants are never worse than their initial values. On early-generation populations, the solver sustains up to $5.1{\times}10^{5}$ trees per second on an NVIDIA A100; at a GPU-saturated benchmark configuration it delivers roughly $9.9{\times}$ the throughput of Operon running on a 64-core EPYC 7763, while matching fp64-reference quality. Integrated in-process into EvoGP, the solver enables end-to-end search to recover governing equations on $10$ of $18$ constructed problems versus 0 for stock EvoGP. Our code is at https://github.com/TensorConv/CuSR.

0.72