SoberDSE: Sample-Efficient Design Space Exploration via Learning-Based Algorithm Selection

Het SoberDSE-framework lost het probleem van de enorme ontwerpruimte in High-Level Synthesis op door een leermodel te gebruiken dat per geval de meest geschikte algoritme selecteert, wat resulteert in aanzienlijk betere prestaties dan bestaande methoden, vooral in scenario's met beperkte data.

De kern

Stel je voor dat je een enorme bibliotheek hebt vol met verschillende recepten om een perfecte taart te bakken. Je hebt een recept voor een snelle taart, een voor een taart die heel lang meegaat, en een voor een taart die er prachtig uitziet. Het probleem is: je hebt geen idee welk recept het beste is voor jouw specifieke situatie (bijvoorbeeld: heb je maar 10 minuten, of heb je alleen maar bloem en geen suiker?).

In de wereld van chipontwerp (de hersenen van je computer of telefoon) gebeurt precies hetzelfde. Dit heet High-Level Synthesis (HLS). Ontwerpers moeten kiezen uit duizenden mogelijke instellingen om een chip te maken die snel is, weinig energie verbruikt en niet te groot is. Dit zoeken noemen ze Design Space Exploration (DSE).

Het probleem is dat de bibliotheek van mogelijke combinaties zo gigantisch groot is, dat het zoeken naar het perfecte recept duurt tot wel dagen of weken. En er is nog een vervelende regel: er bestaat geen één super-recept dat voor elke situatie het beste is. Soms werkt het snelle recept goed, soms het dure, en soms het simpele.

Wat is SoberDSE?

De auteurs van dit paper hebben een slimme oplossing bedacht genaamd SoberDSE. Je kunt het zien als een slimme kok die een "recepten-adviseur" is.

In plaats van dat de kok zelf urenlang probeert om de beste taart te bakken (wat de oude methodes deden), kijkt SoberDSE eerst even naar de ingrediënten en de tijd die je hebt (de kenmerken van het probleem). Vervolgens zegt hij: "Ah, voor deze specifieke taart is recept nummer 7 het beste!" en geeft hij dat recept direct door aan de bakker.

Hoe werkt het? (De Creatieve Analogie)

Stel je voor dat SoberDSE twee helpers heeft die samenwerken:

1. De Ervaren Opa (Supervised Learning):
   Deze helper heeft duizenden kookboeken gelezen. Hij kan snel een goed advies geven op basis van ervaring. "Als je bloem en eieren hebt, kies dan voor recept X."
   Het nadeel: Als je hem een heel nieuw type taart geeft waar hij nooit over gelezen heeft, raakt hij in de war en maakt hij fouten (dit heet overfitting).

2. De Jonge Leerling (Reinforcement Learning):
   Deze helper is nieuwsgierig en leert door te proberen. Hij probeert verschillende recepten, ziet wat er gebeurt, en leert van zijn fouten.
   Het nadeel: Hij is erg traag. Hij moet duizenden taarten bakken voordat hij echt goed wordt, en dat kost te veel tijd en energie.

De Magische Combinatie:
SoberDSE laat de Opa eerst een voorspelling doen. Die voorspelling gebruikt hij als startpunt voor de Leerling.

• De Leerling hoeft niet meer bij nul te beginnen; hij begint al met een goed idee dankzij de Opa.
• Hierdoor leert de Leerling veel sneller en maakt hij minder fouten, zelfs als er niet veel voorbeelden (data) zijn.

Waarom is dit zo belangrijk?

De onderzoekers hebben getest of hun systeem beter werkt dan de beste methodes die er nu zijn. De resultaten zijn indrukwekkend:

• Snelheid: SoberDSE is tot 5,7 keer sneller dan de beste traditionele methodes. Het is alsof je van een fiets op een raket zit.
• Kwaliteit: De taarten (de chipontwerpen) die SoberDSE oplevert, zijn van hogere kwaliteit dan die van de andere methodes.
• Slimme Keuze: Waar andere systemen vaak vastlopen in een lokaal optimum (een goed, maar niet perfect antwoord), vindt SoberDSE het echte beste antwoord door het juiste gereedschap voor de juiste klus te kiezen.

Samenvatting in één zin

SoberDSE is een slimme systeem dat niet zelf de hele wereld probeert te veroveren, maar juist weet welk bestaand gereedschap het beste werkt voor een specifieke klus, waardoor je veel tijd en energie bespaart en een beter resultaat krijgt.

Het is een bewijs dat je niet altijd een nieuw gereedschap hoeft uit te vinden; soms is het slimmer om te weten welk van de bestaande gereedschappen je moet pakken.

Technische samenvatting

Probleemstelling

High-Level Synthesis (HLS) is een cruciale technologie in Electronic Design Automation (EDA) die hardwarecircuits genereert vanuit hoog-niveau taalbeschrijvingen. Een fundamentele stap hierin is Design Space Exploration (DSE), waarbij het doel is om de beste hardware-architectuur te vinden onder gegeven constraints (zoals vermogen, prestaties en oppervlakte, oftewel PPA).

De uitdagingen zijn als volgt:

1. Explosieve zoekruimte: De configuratieruimte groeit exponentieel met het aantal compiler-directives (pragmas), waardoor een exhaustieve zoektocht computationally onmogelijk is voor complexe ontwerpen.
2. Geen "Free Lunch": Volgens de No Free Lunch (NFL) theorie bestaat er geen enkele DSE-algoritme dat op alle probleeminstances optimaal presteert. Experimenten tonen aan dat verschillende algoritmen (zoals NSGA-II, Simulated Annealing, ACO, PSO) op verschillende benchmarks uitblinken, maar geen enkele algoritme domineert alle benchmarks.
3. Data-schaarste: Het verzamelen van trainingsdata voor DSE is duur en tijdrovend, wat leidt tot een beperkt aantal voorbeelden (small-sample scenario's). Bestaande methoden, zoals puur toezicht-geleerd (supervised) of puur versterkingsleren (reinforcement learning), kampen hiermee respectievelijk met overfitting of lage sample-efficiëntie.

Methodologie: SoberDSE

De auteurs stellen SoberDSE voor, een raamwerk dat algoritme-selectie toepast om het beste DSE-algoritme automatisch te kiezen op basis van de kenmerken van een specifieke benchmark. Het raamwerk bestaat uit de volgende componenten:

1. Dataset Generator:

   • Er wordt een suite van 10 DSE-algoritmen geïmplementeerd (7 heuristische methoden zoals NSGA-II, SA, ACO, en 3 Reinforcement Learning-methoden zoals AC, PG, QL-MOEA).
   • Deze worden uitgevoerd op 20 trainingsbenchmarks. De prestaties worden gemeten met de Average Distance to Reference Set (ADRS) metric, waarbij een lagere waarde beter is.
   • De "ground truth" is het algoritme dat de laagste ADRS behaalt voor een specifieke benchmark.

2. Benchmark Feature Graph Generator (BFGG):

   • Om de kenmerken van de benchmarks effectief te vertegenwoordigen, wordt de C-broncode omgezet in een Control and Data Flow Graph (CDFG).
   • Deze grafen worden verrijkt met HLS-directives (pragmas) en geconverteerd naar een Benchmark Feature Graph (BFG) met behulp van ProGraML en LLVM. Dit zorgt voor een semantische weergave van zowel controle- als data-afhankelijkheden.

3. Collaborative Recommendation Model (Hybride Aanpak):

   • Om het probleem van beperkte data op te lossen, combineert SoberDSE Supervised Learning (SL) en Reinforcement Learning (RL) in een synergetisch model:
     • Supervised Component: Een Graph Neural Network (GNN) encodeert de BFG en voorspelt via een MLP-head de waarschijnlijkheid dat een bepaald algoritme het beste is. Dit model dient als een "warm start" of prior.
     • Reinforcement Learning Component: Een PPO-agent (Proximal Policy Optimization) gebruikt de voorspellingen van het SL-model als deel van zijn toestandsrepresentatie ($s_t$). De agent leert door interactie met de omgeving, waarbij de beloning ($r_t$) gebaseerd is op de afwijking van de ADRS ten opzichte van de beste bekende oplossing.
   • Deze hybride aanpak verhelpt de overfitting van puur SL en de lage sample-efficiëntie van puur RL.

Belangrijkste Bijdragen

• Empirisch Bewijs: Uitgebreide experimenten bevestigen dat geen enkel DSE-algoritme universeel optimaal is, wat de noodzaak onderstreept van een dynamisch selectiemechanisme.
• Nieuw Onderzoeksparadigma: In plaats van het ontwerpen van één nieuw super-algoritme, verschuift de focus naar het automatisch aanbevelen van het juiste bestaande algoritme per geval.
• Hybride Lermodel: Een innovatieve combinatie van SL en RL die hoge nauwkeurigheid bereikt in small-sample scenario's, wat een groot probleem is in de EDA-domein.
• Open Source: De code en modellen zijn beschikbaar gesteld voor reproduceerbaarheid.

Resultaten

De prestaties van SoberDSE zijn getest op een inferentie-dataset van 9 benchmarks (waaronder grote matrices en complexe kernels) en vergeleken met state-of-the-art (SOTA) methoden:

• Aanbevelingsnauwkeurigheid: SoberDSE presteert significant beter dan traditionele classificatiemodellen (Random Forest, XGBoost, SVM, K-NN) en een puur supervised model (SFM). De gemiddelde verbetering in nauwkeurigheid is 35,57% ten opzichte van conventionele classifiers.
• DSE Prestaties (ADRS):
  • SoberDSE overtreft de beste heuristische DSE-algoritmen (zoals Lattice, HGBO-DSE, MOEDA) met een verbetering van 81,06% (tot wel 5,7x beter in specifieke gevallen).
  • Het overtreft SOTA RL-methoden (zoals IRONMAN-PRO en QL-MOEA) met een verbetering van 68,80% (tot wel 4,2x beter).
• Runtime: SoberDSE is aanzienlijk sneller dan de meeste geëvalueerde algoritmen. Het bereikt een totale runtime van 862s op de testset, wat een reductie van maximaal 75,63% betekent ten opzichte van langzamere methoden zoals PG (3538s) en SA (1742s).

Betekenis en Conclusie

SoberDSE biedt een krachtig alternatief voor het traditionele "vanaf nul ontwerpen" van nieuwe DSE-algoritmen. Door te focussen op algoritme-selectie gebaseerd op benchmark-kenmerken, kan het systeem de beperkingen van de No Free Lunch theorie omzeilen.

De belangrijkste implicatie is dat men niet per se een nieuw, complexer algoritme nodig heeft om betere resultaten te behalen; in plaats daarvan kan men bestaande algoritmen intelligenter combineren en selecteren. De hybride aanpak van SoberDSE lost het kritieke probleem van data-schaarste in de hardware-ontwerpruimte op, waardoor het een praktische en efficiënte oplossing biedt voor de toekomstige optimalisatie van FPGA- en ASIC-ontwerpen.