Automated Algorithm Design for Auto-Tuning Optimizers

Titel: Geautomatiseerd Algoritmisch Ontwerp voor Auto-Tuning Optimizers

Auteurs: Floris-Jan Willemsen, Niki van Stein, Ben van Werkhoven (Leiden University)

1. Het Probleem

Automatische prestatieoptimalisatie (auto-tuning) is essentieel voor hoogwaardige toepassingen zoals wetenschappelijke simulaties en AI, waarbij software moet worden geoptimaliseerd voor diverse hardware-architecturen.

• De Uitdaging: Auto-tuning vereist het verkennen van enorme, onregelmatige en ruisachtige zoekruimtes (bijv. thread-layouts, data-layouts, lus-transformaties). Handmatige exploratie is onmogelijk.
• Beperkingen van Bestaande Methoden: Traditionele benaderingen (zoals Evolutionary Algorithms, Simulated Annealing, Particle Swarm Optimization) worden vaak gebruikt, maar vereisen zorgvuldige handmatige hyperparameter-tuning en zijn niet specifiek ontworpen voor de unieke kenmerken van auto-tuning zoekruimtes.
• De Vraag: Kunnen Large Language Models (LLMs) worden ingezet om automatisch effectieve, op de specifieke problemen toegesneden optimalisatiealgoritmen te genereren, zonder dat menselijke experts heuristieken hoeven te ontwerpen?

2. Methodologie

De auteurs introduceren een nieuw paradigma waarbij LLMs worden gebruikt om optimalisatiealgoritmen te synthetiseren, geïntegreerd in een gesloten lus-framework.

• Framework Integratie:
  • Kernel Tuner: Een bestaand, open-source Python-framework voor het optimaliseren van computationele kernels (CUDA, OpenCL, etc.). Het definieert de zoekruimte en meet de prestaties.
  • LLaMEA (Large Language Model Evolutionary Algorithm): Een framework dat LLMs combineert met evolutionaire algoritmen om metaheuristieken te genereren.
• Het Proces (Closed-Loop):
  1. Generatie: De LLM genereert Python-code voor een nieuw optimalisatiealgoritme op basis van een prompt die de taakomschrijving en (optioneel) zoekruimtekenmerken bevat.
  2. Validatie & Selectie: De gegenereerde algoritmen worden uitgevoerd in Kernel Tuner. Algoritmen die niet werken of slecht presteren, worden verworpen. Alleen hoogpresterende algoritmen overleven de selectiefase.
  3. Evolutie: Een evolutionair algoritme (EA) selecteert de beste algoritmen en gebruikt LLM-gestuurde mutatie-operatoren om nieuwe varianten te creëren (bijv. "verfijn de strategie", "genereer een nieuw algoritme").
  4. Iteratie: Dit proces herhaalt zich over meerdere generaties totdat het evaluatiebudget is verbruikt.
• Evaluatiemethode:
  • Er wordt gebruikgemaakt van een gestandaardiseerde "performance score" ($P$) die de prestaties over de tijd meet ten opzichte van een baseline (willekeurige zoektocht) en een bekende optimum.
  • De score is gebaseerd op het gebied onder de prestatie-tijdcurve, genormaliseerd, wat zowel de snelheid van convergentie als de uiteindelijke kwaliteit van de oplossing meet.

3. Belangrijkste Bijdragen

1. Eerste Gesloten Llus: Introductie van het eerste framework dat LLM-genereren van optimalisatoren evolueert onder formele auto-tuning evaluatiemetrics.
2. Onafhankelijkheid van Doel: Het bewijs dat LLM-genereren van algoritmen kan presteren zonder dat de onderliggende applicatie of de zoekruimte zelf wordt herdefinieerd; alleen de zoekstrategie wordt gegenereerd.
3. Benchmarking: Een uitgebreide evaluatie tegen state-of-the-art menselijk ontworpen algoritmen (Genetische Algoritmen, Simulated Annealing) en andere frameworks (pyATF) over vier real-world applicaties en zes hardware-platforms.
4. Open Source: Alle code en data zijn beschikbaar gesteld via GitHub, inclusief de gegenereerde algoritmen die zijn geïntegreerd in Kernel Tuner.

4. Resultaten

De evaluatie omvatte vier applicaties (Dedispersion, 2D Convolutie, Hotspot, GEMM) op zes GPU's (AMD en Nvidia), resulterend in 24 unieke zoekruimtes.

• Invloed van Contextinformatie:
  • Het verstrekken van aanvullende informatie over de zoekruimte (parameterwaarden, constraints) aan de LLM leidde tot een gemiddelde prestatieverbetering van 14,6%.
  • Voor specifieke toepassingen (zoals Dedispersion en GEMM) was de verbetering zelfs 30,7% wanneer het algoritme specifiek op die taak was getuned.
• Vergelijking met Menselijke Algoritmen:
  • De beste door de LLM gegenereerde algoritmen (bijv. HybridVNDX en AdaptiveTabuGreyWolf) presteerden significant beter dan de beste menselijk ontworpen algoritmen.
  • Gemiddelde verbetering: De gegenereerde algoritmen behaalden een 72,4% hogere prestatiescore dan de state-of-the-art menselijke optimalisatoren (GA, SA, DE) over alle zoekruimtes.
  • Ze waren robuuster en vonden sneller hoogwaardige configuraties.
• Karakteristieken van Succesvolle Algoritmen:
  • De beste gegenereerde algoritmen combineerden elementen zoals Variable Neighborhood Descent, Tabu Search en Simulated Annealing, maar met een lichte, efficiënte controlelogica.
  • Ze benutten de API's van de zoekruimte om architectuur-agnostische bewegingen te maken terwijl ze constraints respecteren.

5. Betekenis en Conclusie

Dit onderzoek markeert een verschuiving in het veld van auto-tuning:

• Paradigmaverschuiving: In plaats van dat experts handmatig heuristieken ontwerpen, kunnen LLMs nu automatisch nieuwe, effectieve optimalisatiestrategieën synthetiseren die vaak beter zijn dan menselijke ontwerpen.
• Efficiëntie en Toegankelijkheid: Deze aanpak verlaagt de drempel voor het ontwerpen van geavanceerde auto-tuners en maakt het mogelijk om snel specifieke optimalisatoren te creëren voor nieuwe hardware of applicaties zonder uitgebreide menselijke inspanning.
• Toekomstperspectief: Hoewel de huidige resultaten veelbelovend zijn, hangt de kwaliteit af van het gebruikte LLM-model. Toekomstig werk kan gericht zijn op bredere validatie over meer domeinen en de integratie van deze generatieve capaciteiten in compilers en ML-deploymingsystemen voor zelf-adaptieve systemen.

Kortom, de paper bewijst dat LLM-gestuurde algoritmische ontwerpmethodes niet alleen haalbaar zijn, maar ook een aanzienlijke meerwaarde bieden ten opzichte van traditionele, handmatig ontworpen optimalisatiemethoden in complexe auto-tuning scenario's.