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

Die Arbeit stellt SoberDSE vor, einen lernbasierten Rahmen zur automatischen Auswahl der optimalen Design-Space-Exploration-Algorithmen für High-Level-Synthesis-Probleme, der durch die Berücksichtigung von Benchmark-Charakteristika sowohl heuristische als auch andere lernbasierte Methoden in Bezug auf Effizienz und Genauigkeit bei kleinen Stichproben signifikant übertrifft.

Das Wesentliche

Stell dir vor, du bist ein Architekt, der ein riesiges, komplexes Gebäude entwerfen muss. Aber anstatt mit Bleistift und Papier zu arbeiten, nutzt du einen extrem mächtigen Computer, der aus deinem Entwurf eine funktionierende Hardware-Schaltung baut. Das nennt man High-Level Synthesis (HLS).

Das Problem ist: Es gibt nicht den einen perfekten Bauplan. Es gibt Millionen von Möglichkeiten, wie du deine Schaltung optimieren könntest (z. B. schneller machen, weniger Strom verbrauchen oder weniger Platz einnehmen). Diese riesige Menge an Möglichkeiten nennt man den Design Space (Entwurfsraum).

Das Problem: Die Suche nach der Nadel im Heuhaufen

Um das beste Ergebnis zu finden, müssen Ingenieure durch diesen riesigen Entwurfsraum suchen. Das ist wie die Suche nach der perfekten Nadel in einem Heuhaufen, der so groß ist wie ein ganzer Kontinent.

Früher haben die Ingenieure versucht, mit verschiedenen „Such-Strategien" (Algorithmen) durch diesen Heuhaufen zu laufen.

• Strategie A ist super im Suchen nach schnellen Nadeln, aber schlecht bei stromsparenden.
• Strategie B ist toll bei kleinen Heuhaufen, scheitert aber an riesigen.
• Strategie C ist sehr gründlich, dauert aber ewig.

Die Forscher haben herausgefunden: Es gibt keine einzelne Strategie, die bei jedem Heuhaufen die beste Nadel findet. Das ist wie ein berühmter Satz in der Mathematik besagt: „Es gibt kein kostenloses Mittagessen" (No Free Lunch Theorem). Was bei einem Problem hilft, schadet oft bei einem anderen.

Die Lösung: SoberDSE – Der kluge Wegweiser

Hier kommt SoberDSE ins Spiel. Stell dir SoberDSE nicht als einen neuen Sucher vor, sondern als einen super-intelligenten Wegweiser oder Taktiker.

Statt selbst den Heuhaufen zu durchsuchen, macht SoberDSE folgendes:

1. Es analysiert den Heuhaufen: Bevor die Suche beginnt, schaut sich SoberDSE den spezifischen Entwurf genau an. Ist er klein und kompakt? Ist er riesig und komplex? Hat er viele Verknüpfungen?
2. Es wählt den besten Sucher aus: Basierend auf dieser Analyse sagt SoberDSE: „Für diesen speziellen Heuhaufen ist Strategie A die beste Wahl!" oder „Für diesen hier brauchen wir Strategie B!"
3. Es kombiniert die Stärken: SoberDSE nutzt zwei Arten von „Intelligenz", um diese Entscheidung zu treffen:
   • Der erfahrene Mentor (Überwachtes Lernen): Dieser Teil hat schon viele Heuhaufen gesehen und kann aus Erfahrung raten, welche Strategie gut funktioniert.
   • Der neugierige Entdecker (Bestärkendes Lernen): Dieser Teil lernt durch Ausprobieren. Wenn der Mentor sich irrt, lernt der Entdecker daraus und passt seine Strategie an.

Das Besondere an SoberDSE ist, dass es besonders gut damit umgeht, wenn es wenige Daten gibt (wenige Beispiele von Heuhaufen, die man schon kennt). Herkömmliche Methoden brauchen oft Tausende von Beispielen, um zu lernen, aber SoberDSE kommt mit wenigen aus, weil es die beiden Intelligenzen kombiniert.

Warum ist das so wichtig?

Stell dir vor, du hast 10 verschiedene Aufgaben zu erledigen.

• Ohne SoberDSE würdest du für jede Aufgabe versuchen, die eine beste Methode zu finden, die für alle passt. Das funktioniert selten gut.
• Mit SoberDSE wählst du für jede Aufgabe individuell das perfekte Werkzeug aus deiner Werkzeugkiste aus.

Die Ergebnisse der Forscher zeigen:

• SoberDSE findet die besten Lösungen bis zu 5,7-mal besser als die besten herkömmlichen Suchmethoden.
• Es ist bis zu 4,2-mal besser als andere moderne, lernende Methoden.
• Es ist auch viel schneller. Während andere Methoden stundenlang suchen, findet SoberDSE das Ziel oft in einem Bruchteil der Zeit, weil es nicht blind sucht, sondern gezielt das richtige Werkzeug wählt.

Zusammenfassung in einem Satz

SoberDSE ist wie ein genialer Koch, der nicht versucht, ein einziges Rezept zu erfinden, das für alle Zutaten passt, sondern der für jeden einzelnen Einkaufszettel (den Entwurf) das perfekte Rezept (den Algorithmus) auswählt, um das leckerste Gericht (die beste Hardware) in kürzester Zeit zu zaubern.

Technische Zusammenfassung

1. Problemstellung

High-Level Synthesis (HLS) ist eine entscheidende Technologie im Bereich des Electronic Design Automation (EDA), die es ermöglicht, Hardware-Schaltungen aus hochsprachlichen Beschreibungen zu generieren. Ein kritischer Schritt dabei ist die Design Space Exploration (DSE), bei der unter gegebenen Constraints (Leistung, Fläche, Energie) die besten Hardware-Architekturen identifiziert werden müssen.

Die Hauptherausforderungen sind:

• Exponentieller Suchraum: Die Anzahl der möglichen Konfigurationen wächst exponentiell mit der Anzahl der Optimierungsanweisungen (Pragmas), was eine exhaustive Suche unmöglich macht.
• Kein „One-Size-Fits-All": Trotz zahlreicher vorgeschlagener Algorithmen (heuristisch oder lernbasiert) zeigt das „No-Free-Lunch"-Theorem (NFL), dass kein einzelner Algorithmus auf allen Probleminstanzen optimal performt. Experimente im Paper belegen, dass verschiedene Algorithmen (z. B. NSGA-II, SA, ACO, PSO) auf unterschiedlichen Benchmarks besser abschneiden.
• Datenknappheit: Das Training von reinen Reinforcement-Learning-Modellen für die DSE ist aufgrund der begrenzten Anzahl realer Benchmarks und der hohen Rechenkosten für Simulationen ineffizient und führt oft zu Überanpassung oder lokalen Optima.

2. Methodik: Das SoberDSE-Framework

SoberDSE löst das Problem nicht durch die Entwicklung eines neuen, überlegenen Suchalgorithmus, sondern durch Algorithmus-Auswahl (Algorithm Selection). Das Framework wählt basierend auf den Merkmalen eines spezifischen Benchmarks den besten DSE-Algorithmus aus einem vordefinierten Pool aus.

Der Workflow besteht aus folgenden Komponenten:

• Datengenerierung (Dataset Generator):

  • Es werden 10 Algorithmen implementiert (7 heuristisch: NSGA-II, SA, ACO, PSO, Lattice, HGBO-DSE, MOEDA; 3 RL-basiert: AC, PG, QL-MOEA).
  • Diese werden auf 20 Trainings-Benchmarks ausgeführt. Die Ergebnisse werden mittels eines vortrainierten QoR-Vorhersagemodells (ECoGNN) bewertet, um die „Ground Truth" (den besten Algorithmus pro Benchmark) zu ermitteln.
  • Als Metrik dient der Average Distance to Reference Set (ADRS), wobei niedrigere Werte eine bessere Annäherung an die Pareto-Front bedeuten.

• Benchmark-Feature-Graph-Generator (BFGG):

  • Um die Charakteristika der Benchmarks zu erfassen, wird der C-Code in eine Intermediate Representation (IR) umgewandelt und mittels ProGraML in einen Control and Data Flow Graph (CDFG) überführt.
  • Dieser Graph wird durch HLS-Direktiven (Pragmas) angereichert, um semantische Informationen für das Lernen zu nutzen.

• Kollaboratives Empfehlungsmodell (Hybrid-Ansatz):

  • Um das Problem der kleinen Stichprobengröße (Small-Sample Learning) zu lösen, kombiniert SoberDSE überwachtes Lernen mit Reinforcement Learning (RL).
  • Schritt 1 (Supervised): Ein Graph Neural Network (GNN) kodiert den Feature-Graph und ein MLP-Head gibt eine initiale Wahrscheinlichkeitsverteilung für die Algorithmus-Auswahl aus. Dies dient als Vorwissen.
  • Schritt 2 (Reinforcement Learning): Ein PPO-Agent (Proximal Policy Optimization) nutzt die Ausgabe des überwachten Modells als Teil seines Zustandsvektors ($s_t$). Der Agent interagiert mit der Umgebung, erhält Belohnungen basierend auf der Leistungsdifferenz zum besten Algorithmus und optimiert seine Strategie.
  • Inferenz: Das trainierte Modell empfiehlt für einen neuen Benchmark den optimalen Algorithmus, der dann ausgeführt wird, um die Pareto-Front zu finden.

3. Wichtige Beiträge

1. Empirische Validierung der NFL-Theorie: Durch die Implementierung und den Vergleich von 10 State-of-the-Art (SOTA) DSE-Algorithmen wurde nachgewiesen, dass kein einzelner Algorithmus universell überlegen ist.
2. Paradigmenwechsel: Die Forschung konzentriert sich nicht auf die Verbesserung eines einzelnen Suchalgorithmus, sondern auf die automatische, datengetriebene Auswahl des besten Algorithmus für einen spezifischen Fall.
3. Hybride Lernarchitektur: Entwicklung eines kollaborativen Modells, das die Stärken von überwachtem Lernen (schnelle Initialisierung, Feature-Extraktion) und RL (Adaptivität, Exploration) vereint, um die Effizienz bei kleinen Datensätzen zu maximieren.
4. Open Source: Bereitstellung von Code und Modellen für die Reproduzierbarkeit.

4. Ergebnisse

Die Evaluierung erfolgte auf 9 Inference-Benchmarks (u. a. aus MachSuite und Polyhedral), die von den Trainingsdaten getrennt waren.

• Vorhersagegenauigkeit: SoberDSE erreicht eine signifikant höhere Genauigkeit bei der Algorithmus-Empfehlung als klassische Klassifikationsmodelle (Random Forest, XGBoost, SVM, K-NN).
  • Verbesserung: Durchschnittlich +35,57% gegenüber konventionellen Klassifikatoren.
  • Ein reines überwachtes Modell (ohne RL) zeigte vergleichbare Ergebnisse wie die Baseline, was die Notwendigkeit des RL-Komponenten zur Vermeidung von Überanpassung unterstreicht.
• DSE-Leistung (ADRS):
  • SoberDSE übertrifft die besten heuristischen Algorithmen (Lattice, HGBO-DSE, MOEDA) um durchschnittlich 81,06% (gemessen an der ADRS-Verbesserung).
  • Gegenüber SOTA RL-Methoden (IRONMAN-PRO, QL-MOEA) wurde eine Verbesserung von 68,80% erzielt.
  • Konkret: SoberDSE ist im Durchschnitt 5,7-mal besser als heuristische und 4,2-mal besser als lernbasierte DSE-Methoden.
• Laufzeit:
  • SoberDSE ist deutlich schneller als viele Baseline-Algorithmen (z. B. 75,63% schneller als PG und QL-MOEA), da es den Suchraum durch die korrekte Vorauswahl des Algorithmus effizienter durchsucht. Die Gesamtlaufzeit betrug 862 Sekunden im Vergleich zu über 3500 Sekunden bei PG.

5. Bedeutung und Ausblick

SoberDSE demonstriert, dass die Optimierung von Design Space Exploration nicht zwingend durch das Erfinden neuer, komplexerer Suchalgorithmen erreicht werden muss. Stattdessen bietet der Ansatz der intelligenten Algorithmus-Auswahl eine leistungsfähige Alternative, die:

• Die Grenzen des No-Free-Lunch-Theorems umgeht.
• Mit begrenzten Trainingsdaten (Small-Sample) robust funktioniert.
• Einen signifikanten Gewinn in Qualität (PPA-Metriken) und Effizienz (Laufzeit) bietet.

Dieser Ansatz verschiebt den Fokus in der EDA-Forschung von der Entwicklung einzelner Suchstrategien hin zur Entwicklung robuster Meta-Lernsysteme, die den richtigen Werkzeugkasten für jedes spezifische Designproblem auswählen. Zukünftige Arbeiten planen die Erweiterung des Algorithmus-Pools und das Training auf weiteren Benchmarks.