Enabling Population-Level Parallelism in Tree-Based Genetic Programming for GPU Acceleration

• URL: http://arxiv.org/abs/2501.17168v5
• Date: Fri, 10 Oct 2025 16:54:22 GMT
• Title: Enabling Population-Level Parallelism in Tree-Based Genetic Programming for GPU Acceleration
• Abstract summary: Tree-based Genetic Programming (TGP) is a widely used evolutionary computation algorithm for tasks such as symbolic regression, classification, and robotic control.<n>EvoGP is a high-performance framework tailored for GPU acceleration of TGP via population-level parallel execution.
• Score: 9.421242935448722
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Tree-based Genetic Programming (TGP) is a widely used evolutionary algorithm for tasks such as symbolic regression, classification, and robotic control. Due to the intensive computational demands of running TGP, GPU acceleration is crucial for achieving scalable performance. However, efficient GPU-based execution of TGP remains challenging, primarily due to three core issues: (1) the structural heterogeneity of program individuals, (2) the complexity of integrating multiple levels of parallelism, and (3) the incompatibility between high-performance CUDA execution and flexible Python-based environments. To address these issues, we propose EvoGP, a high-performance framework tailored for GPU acceleration of TGP via population-level parallel execution. First, EvoGP introduces a tensorized representation that encodes variable-sized trees into fixed-shape, memory-aligned arrays, enabling uniform memory access and parallel computation across diverse individuals. Second, EvoGP adopts an adaptive parallelism strategy that dynamically combines intra- and inter-individual parallelism based on dataset size, ensuring high GPU utilization across a broad spectrum of tasks. Third, EvoGP embeds custom CUDA kernels into the PyTorch runtime, achieving seamless integration with Python-based environments such as Gym, MuJoCo, Brax, and Genesis. Experiments show that EvoGP attains a peak throughput exceeding $10^{11}$ GPops/s, with speedups of up to $528\times$ over GPU-based TGP implementations and $18\times$ over the fastest CPU-based libraries, while maintaining comparable accuracy and improved scalability across large population sizes. EvoGP is open source and accessible at: https://github.com/EMI-Group/evogp.

Related papers

• Fine-Grain GPU Parallelization of the Generalized Partition Crossover for Large-Scale Traveling Salesman Problems [1.160208922584163]
  The Traveling Salesman Problem (TSP) is one of the most extensively studied NP-hard optimization problems.<n>The proposed approach reformulates GPX as a graph-parallel problem using coalesced memory layouts, ghost-node transformations, and connected-node analysis.<n>The proposed GPU achieves speedups between 48x and 625x while significantly reducing memory overhead.
  arXiv  Detail & Related papers  (2026-08-21T15:42:05Z)
• GRAB-ANNS: High-Throughput Indexing and Hybrid Search via GPU-Native Bucketing [39.763467046232584]
  We present GRAB-ANNS, a GPU-native graph index for dynamic hybrid search.<n>We show that GRAB-ANNS achieves up to 240.1 times higher query throughput and 12.6 times faster index construction than state-of-the-art CPU-based systems.
  arXiv  Detail & Related papers  (2026-03-31T11:00:10Z)
• ParEVO: Synthesizing Code for Irregular Data: High-Performance Parallelism through Agentic Evolution [13.109726609738749]
  ParEVO is a framework designed to synthesize high-performance parallel algorithms for irregular data.<n>On the ParEval benchmark, ParEVO achieves an average 106x speedup, and a robust 13.6x speedup on complex irregular graph problems.
  arXiv  Detail & Related papers  (2026-03-03T01:41:07Z)
• GSPN-2: Efficient Parallel Sequence Modeling [101.33780567131716]
  Generalized Spatial Propagation Network (GSPN) addresses this by replacing quadratic self-attention with a line-scan propagation scheme.<n>GSPN-2 establishes a new efficiency frontier for modeling global spatial context in vision applications.
  arXiv  Detail & Related papers  (2025-11-28T07:26:45Z)
• Scalable GPU-Accelerated Euler Characteristic Curves: Optimization and Differentiable Learning for PyTorch [0.0]
  We present optimized GPU kernels for the Euler Characteristic Curve (ECC) achieving 16-2000"O speedups over prior GPU implementations on synthetic grids.<n>We introduce a differentiable PyTorch layer enabling end-to-end learning.
  arXiv  Detail & Related papers  (2025-10-23T06:59:07Z)
• HiGP: A high-performance Python package for Gaussian Process [13.127443064937735]
  HiGP is a high-performance Python package designed for efficient Gaussian Process regression (GPR) and classification (GPC) It implements various effective matrix-vector (MatVec) and matrix-matrix (MatMul) multiplication strategies specifically tailored for kernel matrices. With a user-friendly Python interface, HiGP integrates seamlessly with PyTorch and other Python packages, allowing easy incorporation into existing machine learning and data analysis.
  arXiv  Detail & Related papers  (2025-03-04T04:17:36Z)
• Systems and Algorithms for Convolutional Multi-Hybrid Language Models at Scale [68.6602625868888]
  We introduce convolutional multi-hybrid architectures, with a design grounded on two simple observations.<n>Operators in hybrid models can be tailored to token manipulation tasks such as in-context recall, multi-token recall, and compression.<n>We train end-to-end 1.2 to 2.9 times faster than optimized Transformers, and 1.1 to 1.4 times faster than previous generation hybrids.
  arXiv  Detail & Related papers  (2025-02-25T19:47:20Z)
• Memory-Efficient Gradient Unrolling for Large-Scale Bi-level Optimization [71.35604981129838]
  Bi-level optimization has become a fundamental mathematical framework for addressing hierarchical machine learning problems.<n>Traditional gradient-based bi-level optimization algorithms are ill-suited to meet the demands of large-scale applications.<n>We introduce $(textFG)2textU$, which achieves an unbiased approximation of the meta gradient for bi-level optimization.
  arXiv  Detail & Related papers  (2024-06-20T08:21:52Z)
• Scaling Tractable Probabilistic Circuits: A Systems Perspective [53.76194929291088]
  PyJuice is a general implementation design for PCs that improves prior art in several regards.<n>It is 1-2 orders of magnitude faster than existing systems at training large-scale PCs.<n>PyJuice consumes 2-5x less memory, which enables us to train larger models.
  arXiv  Detail & Related papers  (2024-06-02T14:57:00Z)
• SymbolNet: Neural Symbolic Regression with Adaptive Dynamic Pruning for Compression [1.0356366043809717]
  We propose $ttSymbolNet$, a neural network approach to symbolic regression specifically designed as a model compression technique.<n>This framework allows dynamic pruning of model weights, input features, and mathematical operators in a single training process.
  arXiv  Detail & Related papers  (2024-01-18T12:51:38Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAE is a graph autoencoder framework that leverages transferability and stability of GNNs to achieve efficient network alignment without retraining. Our experiments demonstrate that T-GAE outperforms the state-of-the-art optimization method and the best GNN approach by up to 38.7% and 50.8%, respectively.
  arXiv  Detail & Related papers  (2023-10-05T02:58:29Z)
• INR-Arch: A Dataflow Architecture and Compiler for Arbitrary-Order Gradient Computations in Implicit Neural Representation Processing [66.00729477511219]
  Given a function represented as a computation graph, traditional architectures face challenges in efficiently computing its nth-order gradient. We introduce INR-Arch, a framework that transforms the computation graph of an nth-order gradient into a hardware-optimized dataflow architecture. We present results that demonstrate 1.8-4.8x and 1.5-3.6x speedup compared to CPU and GPU baselines respectively.
  arXiv  Detail & Related papers  (2023-08-11T04:24:39Z)
• Harnessing Deep Learning and HPC Kernels via High-Level Loop and Tensor Abstractions on CPU Architectures [67.47328776279204]
  This work introduces a framework to develop efficient, portable Deep Learning and High Performance Computing kernels. We decompose the kernel development in two steps: 1) Expressing the computational core using Processing Primitives (TPPs) and 2) Expressing the logical loops around TPPs in a high-level, declarative fashion. We demonstrate the efficacy of our approach using standalone kernels and end-to-end workloads that outperform state-of-the-art implementations on diverse CPU platforms.
  arXiv  Detail & Related papers  (2023-04-25T05:04:44Z)
• ParaGraph: Weighted Graph Representation for Performance Optimization of HPC Kernels [1.304892050913381]
  We introduce a new graph-based program representation for parallel applications that extends the Abstract Syntax Tree. We evaluate our proposed representation by training a Graph Neural Network (GNN) to predict the runtime of an OpenMP code region. Results show that our approach is indeed effective and has normalized RMSE as low as 0.004 to at most 0.01 in its runtime predictions.
  arXiv  Detail & Related papers  (2023-04-07T05:52:59Z)
• EvoX: A Distributed GPU-accelerated Framework for Scalable Evolutionary Computation [40.71953374838183]
  EvoX is a computing framework tailored for automated, distributed, and heterogeneous execution of EC algorithms. At the core of EvoX lies a unique programming model to streamline the development of parallelizable EC algorithms. EvoX offers comprehensive support for a diverse set of benchmark problems, ranging from dozens of numerical test functions to hundreds of reinforcement learning tasks.
  arXiv  Detail & Related papers  (2023-01-29T15:00:16Z)
• evosax: JAX-based Evolution Strategies [0.0]
  We release evosax: a JAX-based library of evolutionary optimization algorithms. evosax implements 30 evolutionary optimization algorithms including finite-difference-based, estimation-of-distribution evolution strategies and various genetic algorithms. It is designed in a modular fashion and allows for flexible usage via a simple ask-evaluate-tell API.
  arXiv  Detail & Related papers  (2022-12-08T10:34:42Z)
• A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking [124.21408098724551]
  Large-scale graph training is a notoriously challenging problem for graph neural networks (GNNs) We present a new ensembling training manner, named EnGCN, to address the existing issues. Our proposed method has achieved new state-of-the-art (SOTA) performance on large-scale datasets.
  arXiv  Detail & Related papers  (2022-10-14T03:43:05Z)
• Stochastic Gradient Descent without Full Data Shuffle [65.97105896033815]
  CorgiPile is a hierarchical data shuffling strategy that avoids a full data shuffle while maintaining comparable convergence rate of SGD as if a full shuffle were performed. Our results show that CorgiPile can achieve comparable convergence rate with the full shuffle based SGD for both deep learning and generalized linear models.
  arXiv  Detail & Related papers  (2022-06-12T20:04:31Z)
• Scaling Gaussian Process Optimization by Evaluating a Few Unique Candidates Multiple Times [119.41129787351092]
  We show that sequential black-box optimization based on GPs can be made efficient by sticking to a candidate solution for multiple evaluation steps. We modify two well-established GP-Opt algorithms, GP-UCB and GP-EI to adapt rules from batched GP-Opt.
  arXiv  Detail & Related papers  (2022-01-30T20:42:14Z)
• Accelerating Genetic Programming using GPUs [0.0]
  Genetic Programming (GP) has multiple applications in machine learning such as curve fitting, data modelling, feature selection, classification etc. This paper describes a GPU accelerated stack-based variant of the generational GP algorithm which can be used for symbolic regression and binary classification.
  arXiv  Detail & Related papers  (2021-10-15T06:13:01Z)
• 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)
• Incremental Ensemble Gaussian Processes [53.3291389385672]
  We propose an incremental ensemble (IE-) GP framework, where an EGP meta-learner employs an it ensemble of GP learners, each having a unique kernel belonging to a prescribed kernel dictionary. With each GP expert leveraging the random feature-based approximation to perform online prediction and model update with it scalability, the EGP meta-learner capitalizes on data-adaptive weights to synthesize the per-expert predictions. The novel IE-GP is generalized to accommodate time-varying functions by modeling structured dynamics at the EGP meta-learner and within each GP learner.
  arXiv  Detail & Related papers  (2021-10-13T15:11:25Z)
• Speed Benchmarking of Genetic Programming Frameworks [1.1470070927586016]
  Genetic Programming (GP) is known to suffer from the burden of being computationally expensive by design. In this work, we employ a series of benchmarks meant to compare both the performance and evolution capabilities of different vectorized and iterative implementation approaches.
  arXiv  Detail & Related papers  (2021-05-25T22:06:42Z)
• Predictive Coding Approximates Backprop along Arbitrary Computation Graphs [68.8204255655161]
  We develop a strategy to translate core machine learning architectures into their predictive coding equivalents. Our models perform equivalently to backprop on challenging machine learning benchmarks. Our method raises the potential that standard machine learning algorithms could in principle be directly implemented in neural circuitry.
  arXiv  Detail & Related papers  (2020-06-07T15:35:47Z)
• 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)
• Infinitely Wide Graph Convolutional Networks: Semi-supervised Learning via Gaussian Processes [144.6048446370369]
  Graph convolutional neural networks(GCNs) have recently demonstrated promising results on graph-based semi-supervised classification. We propose a GP regression model via GCNs(GPGC) for graph-based semi-supervised learning. We conduct extensive experiments to evaluate GPGC and demonstrate that it outperforms other state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-02-26T10:02:32Z)

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.