Technical Summary: An Introduction and Tutorial of the Beagle Framework

Problem Statement

The primary challenge addressed by the Beagle framework is the computational inefficiency of traditional Genetic Programming (GP) when scaling to large population sizes. Standard CPU-based GP frameworks struggle to explore vast, complex search spaces within feasible timeframes, particularly for symbolic regression tasks. While GPU acceleration offers a potential solution, existing high-level GPU libraries often lack the low-level control necessary to fully exploit heterogeneous computing environments for evolutionary algorithms. Furthermore, standard GP implementations often suffer from performance degradation due to memory fragmentation and garbage collection overheads inherent in dynamic data structures like trees.

Methodology

Beagle is an open-source, GPU-accelerated symbolic regression framework designed to maximize efficiency through specific architectural and algorithmic choices:

• Hardware and Software Stack: Built on .NET 10 using the open-source ILGPU library, Beagle utilizes low-level CUDA kernel programming rather than high-level abstractions. It supports cross-platform deployment (Windows/Linux) on NVIDIA GPUs, automatically distributing workloads across available CPU and GPU resources.
• Genome Representation: Unlike traditional tree-based GP, Beagle employs a custom Linear Genetic Programming (LGP) language called Genome Computer Language (GCL). GCL is based on Reverse Polish Notation (RPN) with a fixed-size stack (default 32 elements). This linear, stack-based architecture avoids the heap and stack allocation issues common in tree-based structures, making it compatible with the static memory allocation requirements of GPU kernels.
• Execution Architecture:
  • CPU/GPU Division: The CPU handles genetic operations (mutation, initialization), while the GPU manages model and fitness function evaluations.
  • Batching: To minimize data transfer overhead, individuals are sent to the GPU once per generation to evaluate multiple fitness cases (batches of 512 or 1024).
  • Thread Divergence Mitigation: The framework maps one CUDA block to a single individual and one thread to a single fitness case. This ensures that threads within a warp process the same model, significantly reducing thread divergence penalties.
• Memory Management: On the CPU side, Beagle avoids standard memory deallocation for individuals. Instead, it utilizes a "dead pool" to recycle memory from deceased individuals, effectively eliminating garbage collection and memory fragmentation overheads common in evolutionary algorithms.
• Selection and Evolution:
  • Monte-Carlo Ranking: To avoid the computational cost of sorting massive populations (millions of individuals), Beagle uses a random sample of 100 individuals to estimate population percentiles, assigning breeding rights based on these estimates.
  • Dynamic Population Sizes: The framework supports both static and dynamic target population sizes, often starting large to promote exploration and shrinking over generations to focus on exploitation.
  • Stagnation Mitigation: If no fitness improvement occurs after a threshold number of births, the population is reset while preserving the best solution found to date.
• Fitness Evaluation: Beagle defaults to a correlation-based fitness function, which has shown performance benefits in GPU environments. It handles invalid numerical outputs (NaN, Inf) by rewarding models that produce invalid values in the same locations as the target data, rather than discarding them.

Key Contributions

1. High-Scale GPU GP: The framework enables the execution of GP with population sizes in the millions, a scale previously difficult to achieve with CPU-based systems.
2. Custom Kernel Design: By utilizing ILGPU and writing custom CUDA kernels, Beagle achieves superior performance compared to existing CPU-based frameworks, as demonstrated on the Feynman100 benchmark suite.
3. Novel Terminology and Taxonomy: Developed independently of the broader GP community, Beagle introduces its own terminology (e.g., "Colony" for Population, "Organism" for Individual) which is mapped to standard GP terms in the documentation.
4. Robustness Mechanisms: The inclusion of "Always Viable Mutations" ensures that invalid genomes are corrected before evaluation, and the specific handling of invalid data points in fitness functions ensures robustness in symbolic regression.
5. Open-Source Release: The framework is released under the Apache 2.0 license, providing the community with a fully functional, GPU-accelerated tool for symbolic regression.

Results

The paper cites a benchmarking study (Reference [3]) demonstrating that the Beagle GPU-accelerated framework achieves "substantially superior performance" compared to existing CPU-based frameworks when evaluated on the Feynman100 benchmark suite. The framework is designed to scale effectively with hardware, allowing users with High-Performance Computing (HPC) systems to explore massive search spaces, while also being optimized for modest hardware with small GPU memory via batch management.

Significance

The authors position Beagle as a significant step toward leveraging GPU capabilities for evolutionary computing, drawing a parallel to the transformative impact GPUs had on neural networks over the last decade. The paper claims that by removing CPU bottlenecks (garbage collection, memory fragmentation) and maximizing GPU parallelism, Beagle allows for the practical exploration of search spaces that were previously intractable.

The development of Beagle represents a convergence of independent derivation (e.g., adopting Linear Genetic Programming) and novel contributions (e.g., Monte-Carlo Ranking selection for massive populations). The authors express the hope that the community will adopt Beagle for both practical symbolic regression problems and as a platform for future research, potentially yielding new theoretical insights and methodological advancements in genetic programming. The paper serves as both a technical introduction and a tutorial, guiding users through installation, configuration, and the use of the GCL language.