Bombyx: OpenCilk Compilation for FPGA Hardware Acceleration
Shahawy, de Castelnau, Ienne
Task-level parallelism (TLP) is a widely used approach in software where independent tasks are dynamically created and scheduled at runtime. Recent systems have explored architectural support for TLP on field-programmable gate arrays (FPGAs), often leveraging high-level synthesis (HLS) to create processing elements (PEs). In this paper, we present Bombyx, a compiler toolchain that lowers OpenCilk programs into a Cilk-1-inspired intermediate representation, enabling efficient mapping of CPU-oriented TLP applications to spatial architectures on FPGAs. Unlike OpenCilk's implicit task model, which requires costly context switching in hardware, Cilk-1 adopts explicit continuation-passing - a model that better aligns with the streaming nature of FPGAs. Bombyx supports multiple compilation targets: one is an OpenCilk-compatible runtime for executing Cilk-1-style code using the OpenCilk backend, and another is a synthesizable PE generator designed for HLS tools like Vitis HLS. Additionally, we introduce a decoupled access-execute optimization that enables automatic generation of high-performance PEs, improving memory-compute overlap and overall throughput.
academic
Bombyx: OpenCilk-Kompilierung für FPGA-Hardwarebeschleunigung
Dieser Artikel präsentiert Bombyx, eine Toolchain zur Kompilierung von OpenCilk-Programmen in FPGA-Hardwarebeschleuniger. Bombyx konvertiert das implizite Task-Parallelitätsmodell von OpenCilk in eine explizite Continuation-Passing-Zwischendarstellung im Cilk-1-Stil, die besser für die Stream-Charakteristiken von FPGAs geeignet ist. Die Toolchain unterstützt mehrere Kompilierungsziele: eine OpenCilk-kompatible Laufzeit zur Verifikation sowie synthetisierbare Processing-Unit-Generatoren für High-Level-Synthesis-Tools wie Vitis HLS. Darüber hinaus führt Bombyx die Decoupled-Access-Execute (DAE)-Optimierung ein, die automatisch hochperformante Processing Units generiert und die Speicher-Compute-Überlappung sowie den Gesamtdurchsatz verbessert.
Task-Level-Parallelität (TLP) ist eine weit verbreitete Parallelisierungstechnik in Software, die die dynamische Erstellung und Planung unabhängiger Tasks zur Laufzeit ermöglicht. Obwohl bereits Hardwarerahmen (wie ParallelXL und HardCilk) TLP auf FPGAs unterstützen, fehlt es an automatisierten Werkzeugen zur automatischen Extraktion und Kompilierung von Processing-Unit (PE)-Code aus Software-TLP-Frameworks. Bestehende Rahmen erfordern typischerweise, dass Benutzer PE-Code manuell bereitstellen, was sowohl mühsam als auch fehleranfällig ist.
Automatisierungsbedarf: Die Portierung von CPU-orientierten TLP-Anwendungen auf FPGAs erfordert umfangreiche manuelle Arbeit, einschließlich Code-Umstrukturierung, Hardware-Interface-Anpassung und Konfigurationsdateigenerierung
Leistungsoptimierung: Manuell geschriebener Code kann nur schwer fortgeschrittene Hardwareoptimierungen (wie Decoupled-Access-Execute) anwenden
Entwicklungseffizienz: Das Fehlen automatisierter Toolchains behindert die breite Anwendung von TLP bei der FPGA-Beschleunigung
Implizites OpenCilk-Modell: Das Fork-Join-Modell mit cilk_spawn und cilk_sync erfordert Kontextwechsel an Synchronisationspunkten. Die Implementierung von Kontextwechseln in Hardware erfordert das Speichern des gesamten Schaltungszustands, was von aktuellen HLS-Tools weder direkt unterstützt wird noch umfangreiche RTL-Entwicklung erfordert
TAPIR-Zwischendarstellung: Das von OpenCilk verwendete TAPIR nutzt Low-Level-Compiler-Konstrukte, die es schwierig machen, lesbaren C++-Code ähnlich dem Original für HLS zu generieren
Manuelle PE-Programmierung: Erfordert manuelle Behandlung von Closure-Ausrichtung, Write-Buffer-Interfaces, Konfigurationsdateigenerierung und anderen mühsamen Details
Das explizite Continuation-Passing-Modell von Cilk-1 ist besser für die Hardwareimplementierung geeignet, da es Funktionen an Synchronisationspunkten in Terminierungsfunktionen aufteilt (die atomar ausgeführt werden, ohne Kontextwechsel). Obwohl dieses Modell für die Software-Programmierung nicht intuitiv genug ist (und daher in der Cilk-Entwicklung aufgegeben wurde), ist es für die Hardwareimplementierung natürlich. Das Ziel von Bombyx ist es, die Konvertierung von OpenCilk zu explizitem TLP zu automatisieren und optimierte Hardware-PEs zu generieren.
Automatisierter Kompilierungsprozess: Präsentation einer vollständigen automatisierten Toolchain Bombyx von OpenCilk zu FPGA-Hardwarebeschleunigern
Explizite Zwischendarstellung: Entwurf einer auf Kontrollflussgraphen basierenden impliziten und expliziten IR, die die automatische Konvertierung vom Fork-Join-Modell zum Continuation-Passing-Modell ermöglicht
Multi-Target-Codegenerierung:
HardCilk-Backend: Automatische Generierung von synthetisierbarem C++ HLS-Code und Konfigurationsdateien
Cilk-1-Simulationsschicht: Verwendung der OpenCilk-Laufzeit zur Verifikation der Konvertierungskorrektheit
Decoupled-Access-Execute-Optimierung: Unterstützung der DAE-Optimierung durch Compiler-Direktiven (Pragmas), die Speicherzugriff und Berechnung in verschiedene Tasks aufteilen und die Hardwareleistung verbessern
Experimentelle Verifikation: DAE-Optimierung erreicht eine Laufzeitreduktion von 26,5% in Graph-Traversal-Benchmarks
Ein oder mehrere Ausgangsblöcke (keine ausgehenden Kanten)
Grundblöcke bestehen aus sequenziellen C-Anweisungen, die mit Kontrollflusanweisungen enden
Warum nicht TAPIR verwenden: TAPIR verwendet Low-Level-Konstrukte (wie φ-Knoten, alloca usw.), die es schwierig machen, lesbaren C++-Code ähnlich dem Original zu generieren. Die IR von Bombyx behält die ursprüngliche Codestruktur bei.
Dies ist der zentrale Konvertierungsschritt von Bombyx, der das implizite Synchronisationsmodell von OpenCilk in das explizite Continuation-Passing-Modell von Cilk-1 konvertiert.
Schlüsselkonzepte:
Closure: Eine Datenstruktur, die eine Task darstellt und Folgendes enthält:
Verfügbare Parameter
Platzhalter für wartende Abhängigkeiten
Rückgabezeiger
spawn_next: Erstellt eine Continuation-Task, die auf Abhängigkeiten wartet
send_argument: Schreibt explizit Argumente in einen wartenden Closure und benachrichtigt den Scheduler
Konvertierungsalgorithmus:
Pfadaufteilung: Durchlaufe den CFG und starte einen neuen Pfad, wenn Funktionsterminierungsblöcke (return) oder Sync-Operationen auftreten
Jeder Pfad wird zu einer in sich geschlossenen Terminierungsfunktion
Grau schattierte Bereiche in Abbildung 4(c) stellen zwei Pfade dar
Abhängigkeitserkennung: Analysiere Abhängigkeitsbeziehungen an Sync-Grenzen
Identifiziere Variablen, die nach Sync verwendet werden müssen (wie x und y in Abbildung 1)
Diese Variablen müssen explizit in Closure-Feldern gespeichert werden
Schlüsselwort-Ersetzung:
Einfügen von Closure-Deklarationen bei Spawn-Aufrufen
Ersetzen von Sync durch spawn_next-Aufrufe der Nachfolgerfunktion
Ändern von Spawn-Rückgabewerten in explizites Schreiben in Closure-Felder
Beibehaltung von Return-Anweisungen, die später in send_argument konvertiert werden können
Konvertierungsbeispiel (Abbildung 1 zu Abbildung 2):
// Implizit (OpenCilk)
int x = cilk_spawn fib(n-1);
int y = cilk_spawn fib(n-2);
cilk_sync;
return x + y;
// Explizit (Cilk-1)
cont int x, y;
spawn_next sum(k, ?x, ?y); // Erstelle Continuation-Task
spawn fib(x, n-1); // Schreibe in x-Platzhalter
spawn fib(y, n-2); // Schreibe in y-Platzhalter
// Funktion endet, kein Sync erforderlich
HardCilk ist ein Open-Source-FPGA-TLP-Architektur-Generator, der einen Hardware-Work-Stealing-Scheduler bereitstellt. Bombyx automatisiert die Generierung aller erforderlichen HardCilk-Komponenten:
In naiver PE-Implementierung ist eine einzelne Einheit für die Initiierung von Speicheranforderungen und die Ausführung von Berechnungen verantwortlich, was zu Folgendem führt:
Speicherstalls lassen die PE untätig werden
Verringerte Gesamtdurchsatzleistung
Traditionelle Pipelining in HLS-Tools (wie Vitis) ist begrenzt:
Kann Schleifen mit Datenabhängigkeiten an Schleifengrenzen nicht verarbeiten
Statischer Scheduler kann nicht bestimmen, wann Speicherzugriffe geplant werden sollen
Leistungs-Ressourcen-Kompromiss: Die 26,5%ige Leistungsverbesserung erfolgt auf Kosten eines Ressourcen-Overheads von etwa 50%, was für speicherintensive Anwendungen ein angemessener Kompromiss ist
PE-Größen-Analyse:
Spawner + Executor ≈ Größe der Non-DAE-Single-PE
Access-Task benötigt zusätzliche Ressourcen
Empfehlung: Verwendung von RTL-implementierten datenparallelen PEs kann Speicherzugriffs-Task-Kosten amortisieren
Optimierungspotenzial: Das Paper weist darauf hin, dass zukünftig Speicherzugriffs-Tasks als Black-Box-Primitive integriert werden könnten, anstatt sie mit HLS zu generieren
Einzigartige Konvertierungsstrategie: Geschickte Nutzung des expliziten Continuation-Passing-Modells von Cilk-1 zur Lösung des Hardware-Kontextwechsel-Problems
Automatisierungswert: Erste vollständige automatisierte Toolchain von OpenCilk zu FPGA-Hardwarebeschleunigung, füllt wichtige Lücke
Vernünftiges IR-Design: IR-Design, das die ursprüngliche Codestruktur beibehält, erzeugt lesbaren HLS-Code
Unvollständige Konvertierungsalgorithmen: Keine detaillierten Erklärungen von Abhängigkeitsanalyse, Closure-Feldauswahl und anderen Schlüsselalgorithmen
Korrektheitssicherung: Keine formalen Beweise oder systematische Verifikationsmethoden für Konvertierungskorrektheit
Grenzfälle: Keine Diskussion der Behandlung von Rekursion, Zeigern, komplexen Datenstrukturen usw.
Schlüsselliteratur, auf die sich dieses Paper bezieht:
2 OpenCilk (PPoPP'23): Neuestes Cilk-Framework, Eingabesprache von Bombyx
4 HardCilk (FCCM'24): Zielplattform von Bombyx, frühere Arbeit der Autoren
5 Cilk-1 (SIGPLAN'95): Klassisches explizites Continuation-Passing-TLP-System, theoretische Grundlage von Bombyx
6 Joerg-Dissertation (1996): Beweis der theoretischen Machbarkeit der implizit-zu-explizit-Konvertierung
Gesamtbewertung: Bombyx ist eine wertvolle Forschungsarbeit, die die Lücke in der automatisierten Toolchain von OpenCilk zu FPGA-Hardwarebeschleunigung füllt. Die Kerninnnovation liegt in der Nutzung des expliziten Continuation-Passing-Modells von Cilk-1 zur Vermeidung von Hardware-Kontextwechseln und der Bereitstellung eines vollständigen Kompilierungsprozesses. Als Anfangsarbeit weist das Paper jedoch offensichtliche Mängel in der Breite und Tiefe der experimentellen Bewertung auf, und die Halbautomatisierung der DAE-Optimierung begrenzt die Benutzerfreundlichkeit. Das Tool hat direkten Wert für HardCilk-Benutzer und TLP-Forscher, erfordert aber weitere Reifung für breite Anwendung. Empfohlene zukünftige Arbeiten sollten sich auf automatisierte Optimierungserkennung, erweiterte Benchmark-Bewertung und Open-Source-Veröffentlichung konzentrieren, um Community-Verifikation und Verbesserung zu fördern.