CS Paper Radar

Parallel Computing Systems for the Optimal Selection of Process Equipment

Andrey B. Borisenko

cs.DC ·submitted 2026-11-12 04:43 UTC · v1
published

Abstract

This monograph addresses the optimal selection of equipment for chemical-engineering systems of multiproduct batch plants, a large-scale NP-hard discrete optimization problem in which, for each processing stage, a unit of standard size must be chosen so that the total capital cost of the equipment is minimized while the system remains operable and produces the required products within a given time horizon. We present the mathematical model of system operation and analyze its computational properties. We then develop a sequential branch-and-bound algorithm and its parallel versions for shared-memory systems (OpenMP), distributed-memory clusters (MPI, master-worker), and graphics processing units (CUDA), including recursive and iterative tree traversal, shared-memory optimization, and branch-divergence reduction. To overcome the exponential growth of the run time, we propose a hybrid metaheuristic in which Ant Colony Optimization finds a feasible initial solution and Simulated Annealing improves it, and we implement it on GPUs with thousands of independent threads. Finally, we propose random, constant, and multi-constant approaches to tuning the parameters of the ant colony algorithm based on statistical analysis of many parallel runs, and we study the program on GPUs of three generations and on nodes with several GPUs. Computational experiments on multi-core processors, clusters, and GPUs show that the parallel hybrid algorithm finds solutions within 0.01% of the branch-and-bound optimum in tens of seconds instead of tens of hours.

Comment
99 pages, 29 figures, 9 tables, 18 listings. English translation, by the author, with minor corrections, of the monograph originally published in Russian (Tambov, 2026)

Closest papers

Nearest neighbours by meaning across the whole index.

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.63
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.24

A Metaheuristic Optimization Framework for Discrete Optimization under Strict Time Limits

cs.NE ·2026-09-16 ·Umut Çalıkyılmaz, Nitin Nayak, Sven Groppe
benchmarkunusual similarity 0.63
Abstract

Real-time applications often rely on optimization approaches that can find high-quality solutions to hard problems on the order of milliseconds. Metaheuristic optimization frameworks (MOFs) are useful tools for such tasks, as they provide large sets of general-purpose search mechanisms that can return solutions under different computational budgets. However, existing work largely overlooks the available computation time as an explicit dimension of analysis. In this work, we introduce STILO, a MOF specifically designed for optimization under strict time limits. STILO integrates fine-grained configuration spaces for ant colony optimization (ACO), genetic algorithm (GA), and simulated annealing (SA), combining existing and novel operators. We performed experiments using both synthetic and benchmark instances of various discrete optimization problems. The results indicate that the proposed discrete distance calculation mechanism for SA is useful for optimization under strict time limits. They also show that the relative effectiveness of the proposed problem-independent graph structures for ACO can vary across time limits, even for the same instance characteristics. More generally, the results demonstrate that the effectiveness of algorithm families and operators depends not only on the problem type, but also on the characteristics of the instance and the available computational budget.

0.29

Fine-Grain GPU Parallelization of the Generalized Partition Crossover for Large-Scale Traveling Salesman Problems

cs.AI cs.NE ·2026-08-21 ·Swetha Varadarajan, Darrell Whitley
publishedbenchmark similarity 0.62
Abstract · accepted to NiHPC, PPSN 2026. Draft in preparation for a journal article

The Traveling Salesman Problem (TSP) is one of the most extensively studied NP-hard optimization problems. Genetic Algorithm (GA)-based solvers, such as the Edge Assembly Crossover (EAX), achieve state-of-the-art performance on many benchmark instances. However, the scalability of these approaches in massively parallel architectures remains limited because crossover operations involve irregular memory access patterns, graph traversals, and sequential dependencies. Existing GPU-based TSP solvers primarily exploit population-level parallelism and are limited to relatively small problem sizes. This work presents a fine-grain GPU implementation of the partition phase of the Generalized Partition Crossover (GPX) operator for large-scale TSP instances. The proposed approach reformulates GPX partitioning as a graph-parallel problem using coalesced memory layouts, ghost-node transformations, and connected-component analysis. The im- plementation parallelizes the union of parent tours, the splitting of degree- four vertices, the deletion of common edges, and the identification of recombining components using CUDA. Experimental results on instances ranging from 10,000 to 2 million cities demonstrate substantial acceleration over a naive sequential CPU imple- mentation. The proposed GPU partitioning achieves speedups between 48x and 625x while significantly reducing memory overhead. The re- sults demonstrate that operator-level parallelism can substantially im- prove the scalability of GA-based TSP solvers on modern many-core architectures.

0.29

PaNGEA: Parallel Node Generation and Exploration Algorithm on GPU

cs.DC math.OC ·2026-10-02 ·Jean Pauphilet, Yupeng Wu
similarity 0.62
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%.

0.22

On the Structural Optimization of Industrial Control Systems Using Metaheuristic Algorithms

eess.SY ·2026-10-10 ·Ruslan Zakirzyanov
published similarity 0.61
Abstract

The paper addresses the synthesis of a cost-optimal hardware architecture of the automated process control system (APCS) for continuous processes. The problem is formalized as the search for a minimum-cost rooted tree of devices subject to constraints on the number of I/O channels, the types and number of communication interfaces, the information capacity of processors, the regulation time and the reliability. The signals are grouped by control rooms. The problem is NP-hard, and a hybrid method is proposed that combines a deterministic hierarchy construction with a modified ant colony optimization (ACO) for device-type selection, enhanced by an adaptive heuristic. On ten instances the method is compared with a genetic algorithm (GA), particle swarm optimization (PSO), simulated annealing (SA) and CP-SAT over 30 runs each. By the best found cost the hybrid ACO outperforms GA, PSO and SA on all instances with more than 100 IOs (by 14-38 %) and runs 9-14 times faster. By the median cost, however, the deterministic-greedy baselines are more reliable (GA attains the best Friedman rank) because the cost of the ACO runs is highly variable. All differences are confirmed by the Friedman and Wilcoxon tests. The method targets the early-design search for the cheapest feasible architecture and synthesizes one within minutes at industrial scale (A up to 1086).

0.34

Heddle: Learning Structural Templates for Parallelism Planning on Heterogeneous GPU Clusters

cs.DC ·2026-09-28 ·Taeyoon Kim, Yonguk Song, Seoyeong Choy, Hexiao Duan, Dong Li +2 more
similarity 0.57
Abstract

Training large machine learning models on shared GPU infrastructures faces two challenges: (1) GPU availability shifts dynamically with varying resource demands from tenants, and (2) hardware heterogeneity accumulates as datacenters continuously adopt new GPU generations. Due to the vast search space induced by heterogeneous GPU types and node sizes, training planners must prune it aggressively to remain tractable, yet must also derive high-throughput plans promptly as cluster configurations change. Heddle achieves this goal through a learning-based planner that reduces the full planning problem to a search over pipeline structures. Heddle encapsulates planning decisions in a structural template and learns to construct plans from templates over diverse cluster configurations offline. This design is effective because structural decisions constitute the performancecritical core of a parallelism plan, while the rest follows by rule or from a small priced candidate set once the plan structure is fixed. Evaluation shows that Heddle matches or exceeds the best plan found by five existing planners across clusters with varying GPU types and node sizes for three models of different sizes by up to 84.5% in throughput on dense models and 4.6x on MoE models.

0.33

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

cs.DC ·2026-10-30 ·Lin Meng, Yuzhong Sun, Jie Zhu
similarity 0.57
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

CMD: An Integrated CGRA Framework with Cluster-Based Distributed Memory Design

cs.AR ·2026-09-05 ·Shangkun Li, Cheng Tan, Zeyu Li, Jinming Ge, Jiawei Liang +4 more
published similarity 0.56
Abstract · Accepted by ICCD 2026

Coarse-Grained Reconfigurable Arrays (CGRAs) are a promising solution for achieving high energy efficiency and reconfigurability across various application domains, but their performance is often crippled by rigid memory architectures that limit the number and location of tiles that can access data memory. This creates a significant bottleneck for kernels with intensive memory accesses. To address this, we propose CMD, an integrated CGRA framework featuring cluster-based distributed memory design with a co-designed compilation toolchain. The compiler includes a novel memory-aware mapper and a design space exploration (DSE) mechanism that identifies the optimal memory architecture design for specific kernels. Experimental results show that our post-DSE CMD CGRAs achieve an average speedup of $1.39\times$ over a conventional CGRA while simultaneously reducing the total area to an average of $0.912\times$ of the conventional CGRA.

0.20