Scaling Behaviors of Evolutionary Algorithms on GPUs: When Does Parallelism Pay Off?

• URL: http://arxiv.org/abs/2601.18446v2
• Date: Tue, 27 Jan 2026 09:01:53 GMT
• Title: Scaling Behaviors of Evolutionary Algorithms on GPUs: When Does Parallelism Pay Off?
• Authors: Xinmeng Yu, Tao Jiang, Ran Cheng, Yaochu Jin, Kay Chen Tan,
• Abstract summary: Evolutionary algorithms (EAs) are increasingly implemented on graphics processing units (GPUs) to leverage parallel processing capabilities for enhanced efficiency.<n>We investigate how GPU parallelism alters the behavior of EAs beyond simple acceleration metrics.<n>Our results reveal that the impact of GPU acceleration is highly heterogeneous and depends strongly on algorithmic structure.
• Score: 43.96509049196842
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Evolutionary algorithms (EAs) are increasingly implemented on graphics processing units (GPUs) to leverage parallel processing capabilities for enhanced efficiency. However, existing studies largely emphasize the raw speedup obtained by porting individual algorithms from CPUs to GPUs. Consequently, these studies offer limited insight into when and why GPU parallelism fundamentally benefits EAs. To address this gap, we investigate how GPU parallelism alters the behavior of EAs beyond simple acceleration metrics. We conduct a systematic empirical study of 16 representative EAs on 30 benchmark problems. Specifically, we compare CPU and GPU executions across a wide range of problem dimensionalities and population sizes. Our results reveal that the impact of GPU acceleration is highly heterogeneous and depends strongly on algorithmic structure. We further demonstrate that conventional fixed-budget evaluation based on the number of function evaluations (FEs) is inadequate for GPU execution. In contrast, fixed-time evaluation uncovers performance characteristics that are unobservable under small or practically constrained FE budgets, particularly for adaptive and exploration-oriented algorithms. Moreover, we identify distinct scaling regimes in which GPU parallelism is beneficial, saturates, or degrades as problem dimensionality and population size increase. Crucially, we show that large populations enabled by GPUs not only improve hardware utilization but also reveal algorithm-specific convergence and diversity dynamics that are difficult to observe under CPU-constrained settings. Consequently, our findings indicate that GPU parallelism is not strictly an implementation detail, but a pivotal factor that influences how EAs should be evaluated, compared, and designed for modern computing platforms.

Related papers

• GPU-Accelerated Algorithms for Graph Vector Search: Taxonomy, Empirical Study, and Research Directions [54.570944939061555]
  We present a comprehensive study of GPU-accelerated graph-based vector search algorithms.<n>We establish a detailed taxonomy of GPU optimization strategies and clarify the mapping between algorithmic tasks and hardware execution units.<n>Our findings offer clear guidelines for designing scalable and robust GPU-powered approximate nearest neighbor search systems.
  arXiv  Detail & Related papers  (2026-02-10T16:18:04Z)
• Multi-GPU Quantum Circuit Simulation and the Impact of Network Performance [0.7340017786387767]
  We present the introduction of MPI into the QED-C Application-Oriented Benchmarks to facilitate benchmarking on HPC systems.<n>We benchmark using a variety of interconnect paths, including the recent NVIDIA Grace Blackwell NVL72 architecture.<n>We show that while improvements to GPU architecture have led to speedups of over 4.5X, advances in interconnect performance have had a larger impact with over 16X performance improvements in time to solution.
  arXiv  Detail & Related papers  (2025-11-18T17:04:28Z)
• Investigating Matrix Repartitioning to Address the Over- and Undersubscription Challenge for a GPU-based CFD Solver [0.688204255655161]
  Existing approaches either fully or use plugin-based GPU solvers, each facing trade-offs between performance and development effort.<n>We propose a repartitioning strategy that better balances CPU matrix assembly and GPU-based linear solves.<n>Our results show that the proposed method significantly mitigates oversubscription issues, improving solver performance and resource utilization.
  arXiv  Detail & Related papers  (2025-10-09T17:53:12Z)
• A GPU Implementation of Multi-Guiding Spark Fireworks Algorithm for Efficient Black-Box Neural Network Optimization [2.9608128305931825]
  This paper presents a GPU-accelerated version of the Multi-Guiding Spark Fireworks Algorithm (MGFWA)<n>We demonstrate its superior performance in terms of both speed and solution quality.<n>The proposed implementation offers a promising approach to accelerate swarm intelligence algorithms.
  arXiv  Detail & Related papers  (2025-01-07T17:09:07Z)
• GPU Based Differential Evolution: New Insights and Comparative Study [7.5961910202572644]
  This work reviews the main architectural choices made in the literature for GPU based Differential Evolution algorithms. It introduces a new GPU based numerical optimisation benchmark to evaluate and compare GPU based DE algorithms.
  arXiv  Detail & Related papers  (2024-05-26T12:40:39Z)
• AcceleratedLiNGAM: Learning Causal DAGs at the speed of GPUs [57.12929098407975]
  We show that by efficiently parallelizing existing causal discovery methods, we can scale them to thousands of dimensions. Specifically, we focus on the causal ordering subprocedure in DirectLiNGAM and implement GPU kernels to accelerate it. This allows us to apply DirectLiNGAM to causal inference on large-scale gene expression data with genetic interventions yielding competitive results.
  arXiv  Detail & Related papers  (2024-03-06T15:06:11Z)
• Adaptive Elastic Training for Sparse Deep Learning on Heterogeneous Multi-GPU Servers [65.60007071024629]
  We show that Adaptive SGD outperforms four state-of-the-art solutions in time-to-accuracy. We show experimentally that Adaptive SGD outperforms four state-of-the-art solutions in time-to-accuracy.
  arXiv  Detail & Related papers  (2021-10-13T20:58:15Z)
• Providing Meaningful Data Summarizations Using Examplar-based Clustering in Industry 4.0 [67.80123919697971]
  We show, that our GPU implementation provides speedups of up to 72x using single-precision and up to 452x using half-precision compared to conventional CPU algorithms. We apply our algorithm to real-world data from injection molding manufacturing processes and discuss how found summaries help with steering this specific process to cut costs and reduce the manufacturing of bad parts.
  arXiv  Detail & Related papers  (2021-05-25T15:55:14Z)
• Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
  Kernel methods provide an elegant and principled approach to nonparametric learning, but so far could hardly be used in large scale problems. Recent advances have shown the benefits of a number of algorithmic ideas, for example combining optimization, numerical linear algebra and random projections. Here, we push these efforts further to develop and test a solver that takes full advantage of GPU hardware.
  arXiv  Detail & Related papers  (2020-06-18T08:16:25Z)
• Heterogeneous CPU+GPU Stochastic Gradient Descent Algorithms [1.3249453757295084]
  We study training algorithms for deep learning on heterogeneous CPU+GPU architectures. Our two-fold objective -- maximize convergence rate and resource utilization simultaneously -- makes the problem challenging. We show that the implementation of these algorithms achieves both faster convergence and higher resource utilization than on several real datasets.
  arXiv  Detail & Related papers  (2020-04-19T05:21:20Z)
• MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models [96.1052289276254]
  This work introduces a new MAP-solver, based on the popular Dual Block-Coordinate Ascent principle. Surprisingly, by making a small change to the low-performing solver, we derive the new solver MPLP++ that significantly outperforms all existing solvers by a large margin.
  arXiv  Detail & Related papers  (2020-04-16T16:20:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.