e-boost: Schnellere E‑Graph‑Extraktion mit adaptiven Heuristiken

In einer kürzlich veröffentlichten Arbeit auf arXiv wird das neue Framework e‑boost vorgestellt, das das langjährige Problem der E‑Graph‑Extraktion – ein NP‑schweres Optimierungsproblem – effizienter löst. Durch die Kombination von schnellen Heuristiken und exakten Verfahren schafft e‑boost einen Mittelweg zwischen Geschwindigkeit und optimaler Lösung, der bisherige Ansätze deutlich übertrifft.

Der Ansatz beruht auf drei Kerninnovationen. Erstens nutzt er eine parallelisierte Heuristik, die dank schwacher Datenabhängigkeiten die Kosten von DAG‑Knoten gleichzeitig berechnet und damit die Mehrkernleistung voll ausschöpft. Zweitens reduziert ein adaptives Pruning‑Schema die Suchmenge, indem es mit einem anpassbaren Schwellenwert nur vielversprechende Kandidaten beibehält. Drittens wird das verkleinerte Problem als Integer‑Linear‑Programm formuliert und mit einer Warm‑Start‑Strategie an einen ILP‑Solver übergeben, wodurch die Lösung schneller in hoher Qualität gefunden wird.

Die Ergebnisse sind beeindruckend: Im Vergleich zu klassischen ILP‑Methoden erzielt e‑boost einen Laufzeit‑Speedup von 558‑fach, während es gegenüber dem aktuellen Standard‑Framework SmoothE eine Leistungssteigerung von 19,04 % erzielt. Diese Verbesserungen wurden über eine breite Palette an Benchmarks aus den Bereichen formale Verifikation und Logik‑Synthese bestätigt.

Mit diesen Fortschritten eröffnet e‑boost neue Möglichkeiten für die Praxis, etwa bei der Optimierung von Schaltkreisen und der Verifikation komplexer Systeme. Die Kombination aus Parallelität, adaptivem Pruning und exaktem ILP‑Lösen stellt einen bedeutenden Schritt dar, der die Grenzen der E‑Graph‑Extraktion neu definiert und zukünftige Entwicklungen in der Optimierungsforschung inspiriert.