Technische Samenvatting: Een Introductie en Tutorial van het Beagle Framework

Probleemstelling

De primaire uitdaging die door het Beagle-framework wordt aangepakt, is de computationele inefficiëntie van traditionele Genetische Programmering (GP) bij het schalen naar grote populatiegroottes. Standaard CPU-gebaseerde GP-frameworks worstelen met het verkennen van enorme, complexe zoekruimtes binnen haalbare tijdskaders, met name voor taken op het gebied van symbolische regressie. Hoewel GPU-acceleratie een potentiële oplossing biedt, missen bestaande high-level GPU-bibliotheken vaak de lage-niveau controle die nodig is om heterogene computingomgevingen volledig te exploiteren voor evolutionaire algoritmen. Bovendien lijden standaard GP-implementaties vaak aan prestatievermindering door geheugenfragmentatie en overhead door garbage collection, die inherent zijn aan dynamische datastructuren zoals bomen.

Methodologie

Beagle is een open-source, GPU-versneld framework voor symbolische regressie dat ontworpen is om efficiëntie te maximaliseren door middel van specifieke architecturale en algoritmische keuzes:

• Hardware en Software Stack: Gebouwd op .NET 10 met behulp van de open-source ILGPU-bibliotheek, maakt Beagle gebruik van lage-niveau CUDA kernel-programmering in plaats van high-level abstracties. Het ondersteunt cross-platform deployment (Windows/Linux) op NVIDIA GPU's en verdeelt workloads automatisch over beschikbare CPU- en GPU-bronnen.
• Genoomrepresentatie: In tegenstelling tot traditionele boomgebaseerde GP, gebruikt Beagle een aangepaste Linear Genetic Programming (LGP) taal genaamd Genome Computer Language (GCL). GCL is gebaseerd op Reverse Polish Notation (RPN) met een vaste stack (standaard 32 elementen). Deze lineaire, stack-gebaseerde architectuur vermijdt de problemen met heap- en stackallocatie die gebruikelijk zijn bij boomstructuren, wat het compatibel maakt met de vereisten voor statische geheugenallocatie van GPU-kernels.
• Executiearchitectuur:
  • CPU/GPU Verdeling: De CPU handelt genetische operaties af (mutatie, initialisatie), terwijl de GPU de evaluatie van modellen en fitnessfuncties beheert.
  • Batching: Om de overhead van dataoverdracht te minimaliseren, worden individuen één keer per generatie naar de GPU gestuurd om meerdere fitnessgevallen te evalueren (batches van 512 of 1024).
  • Mitigatie van Thread Divergentie: Het framework mapt één CUDA-block aan één individu en één thread aan één fitnessgeval. Dit zorgt ervoor dat threads binnen een warp hetzelfde model verwerken, wat de penalties voor thread divergentie aanzienlijk vermindert.
• Geheugenbeheer: Aan de CPU-zijde vermijdt Beagle standaard geheugendeallocatie voor individuen. In plaats daarvan maakt het gebruik van een "dead pool" om geheugen van overleden individuen te recyclen, waardoor de overhead van garbage collection en geheugenfragmentatie die gebruikelijk is bij evolutionaire algoritmen effectief wordt geëlimineerd.
• Selectie en Evolutie:
  • Monte-Carlo Ranking: Om de computationele kosten van het sorteren van massieve populaties (miljoenen individuen) te vermijden, gebruikt Beagle een willekeurige steekproef van 100 individuen om populatiepercentielen te schatten, waarbij reproductierechten worden toegewezen op basis van deze schattingen.
  • Dynamische Populatiegroottes: Het framework ondersteunt zowel statische als dynamische doelpopulatiegroottes, waarbij vaak groot wordt gestart om exploratie te bevorderen en gedurende de generaties wordt afgeschaald om exploitatie te focussen.
  • Mitigatie van Stagnatie: Als er na een drempelwaarde van geboorten geen verbetering in fitness optreedt, wordt de populatie gereset, waarbij de tot nu toe gevonden beste oplossing behouden blijft.
• Fitness Evaluatie: Beagle gebruikt standaard een correlatiegebaseerde fitnessfunctie, die voordelen heeft getoond in GPU-omgevingen. Het gaat om met ongeldige numerieke outputs (NaN, Inf) door modellen te belonen die ongeldige waarden produceren op dezelfde locaties als de doeldata, in plaats van ze simpelweg te verwerpen.

Belangrijkste Bijdragen

1. High-Scale GPU GP: Het framework maakt de uitvoering van GP met populatiegroottes in de miljoenen mogelijk, een schaal die voorheen moeilijk te bereiken was met CPU-gebaseerde systemen.
2. Custom Kernel Design: Door ILGPU te gebruiken en aangepaste CUDA-kernels te schrijven, bereikt Beagle een superieur rendement vergeleken met bestaande CPU-gebaseerde frameworks, zoals aangetoond op de Feynman100 benchmark suite.
3. Nieuwe Terminologie en Taxonomie: Onafhankelijk ontwikkeld van de bredere GP-gemeenschap, introduceert Beagle zijn eigen terminologie (bijv. "Colony" voor Populatie, "Organism" voor Individu), die in de documentatie wordt gemapt naar standaard GP-termen.
4. Robuustheidsmechanismen: De inclusie van "Always Viable Mutations" zorgt ervoor dat ongeldige genomen worden gecorrigeerd vóór evaluatie, en de specifieke afhandeling van ongeldige datapunten in fitnessfuncties zorgt voor robuustheid in symbolische regressie.
5. Open-Source Release: Het framework wordt uitgebracht onder de Apache 2.0 licentie, waardoor de gemeenschap wordt voorzien van een volledig functionele, GPU-versnelde tool voor symbolische regressie.

Resultaten

Het artikel citeert een benchmarkingstudie (Referentie [3]) die aantoont dat het door Beagle versnelde GPU-framework "substantieel superieure prestaties" levert vergeleken met bestaande CPU-gebaseerde frameworks wanneer het wordt geëvalueerd op de Feynman100 benchmark suite. Het framework is ontworpen om effectief te schalen met hardware, waardoor gebruikers met High-Performance Computing (HPC) systemen enorme zoekruimtes kunnen verkennen, terwijl het ook geoptimaliseerd is voor bescheiden hardware met beperkt GPU-geheugen via batchbeheer.

Betekenis

De auteurs positioneren Beagle als een belangrijke stap naar het benutten van GPU-capaciteiten voor evolutionaire computing, waarbij ze een parallel trekken met de transformerende impact die GPU's hebben gehad op neurale netwerken in het afgelopen decennium. Het artikel stelt dat door het verwijderen van CPU-bottlenecks (garbage collection, geheugenfragmentatie) en het maximaliseren van GPU-parallellisme, Beagle de praktische exploratie van zoekruimtes mogelijk maakt die voorheen onbereikbaar waren.

De ontwikkeling van Beagle vertegenwoordigt een convergentie van onafhankelijke afleiding (bijv. het adopteren van Linear Genetic Programming) en nieuwe bijdragen (bijv. Monte-Carlo Ranking selectie voor massieve populaties). De auteurs hopen dat de gemeenschap Beagle zal adopteren voor zowel praktische problemen in symbolische regressie als voor een platform voor toekomstig onderzoek, wat potentieel nieuwe theoretische inzichten en methodologische vooruitgang kan opleveren. Het artikel dient zowel als een technische introductie als een tutorial, die gebruikers door installatie, configuratie en het gebruik van de GCL-taal leidt.