GraphLeap: Decoupling Graph Construction and Convolution for Vision GNN Acceleration on FPGA

Technischer Zusammenfassung: GraphLeap

Problemstellung
Vision Graph Neural Networks (ViGs) repräsentieren Bilder als Graphen von Patch-Token und nutzen dynamische, feature-getriebene Nachbarschaften, um im Vergleich zu Vision Transformern (ViTs) eine wettbewerbsfähige Genauigkeit bei günstiger Recheneffizienz zu erzielen. Der Kernmechanismus von ViGs – die Rekonstruktion eines $k$-nächste-Nachbarn-Graphen ($k$NN) in jeder Schicht basierend auf aktuellen Patch-Features – erzeugt jedoch einen schwerwiegenden Leistungsengpass. Dieser dynamische Graphenaufbau verbraucht 50–95 % der gesamten Inferenzzeit auf CPUs und GPUs und skaliert quadratisch ($O(N^2)$) mit der Anzahl der Patches. Entscheidend ist, dass dieser Prozess eine strikte sequenzielle Abhängigkeit erzwingt: Der Graph für Schicht $\ell$ muss vollständig aufgebaut sein, bevor das Feature-Update (Convolution) für diese Schicht beginnen kann. Diese Serialisierung verhindert eine effiziente Parallelisierung und behindert den Echtzeit-Einsatz. Darüber hinaus richten sich bestehende Hardware-Beschleuniger weitgehend auf statische Graphen oder regelmäßige Gitteroperationen (CNNs/ViTs) aus, sodass die spezifischen Herausforderungen des dynamischen Bildgraphenaufbaus und vollständiger ViG-Pipelines nicht unterstützt werden.

Methodik: GraphLeap-Reformulierung
Die Autoren stellen GraphLeap vor, eine neuartige algorithmische Reformulierung, die den Graphenaufbau von den Feature-Updates über die Schichten hinweg entkoppelt, um die sequenzielle Abhängigkeit zu durchbrechen.

• Ein-Schicht-Vorschau: Anstatt den Graphen für Schicht $\ell$ unter Verwendung der Features aus Schicht $\ell$ zu konstruieren (was auf das Update der vorherigen Schicht warten müsste), konstruiert GraphLeap den Graphen für Schicht $\ell+1$ unter Verwendung der Features der aktuellen Schicht $\ell$, während gleichzeitig das Feature-Update für Schicht $\ell$ unter Verwendung des Graphen durchgeführt wird, der aus den Features der vorherigen Schicht ($\ell-1$) konstruiert wurde.
• Algorithmischer Wandel: Im Standard-ViG gilt $G^{(\ell)} = G(U^{(\ell)})$. Bei GraphLeap verwendet das Message Passing im Block $\ell$ den Graphen $\hat{G}^{(\ell)} = G(U^{(\ell-1)})$, während $U^{(\ell)}$ gleichzeitig zur Konstruktion von $\hat{G}^{(\ell+1)}$ genutzt wird.
• Genauigkeitswiederherstellung: Die Autoren räumen ein, dass die Verwendung „veralteter" Graphen (aus der vorherigen Schicht) zu einer geringfügigen Genauigkeitsverschlechterung führen kann. Sie zeigen jedoch, dass ein leichtgewichtiges Fine-Tuning (30 Epochen) ausreicht, um die ursprüngliche Genauigkeit wiederherzustellen, wobei die Leistung oft mit der des Baseline-ViG übereinstimmt oder diese sogar übertrifft.

Systemarchitektur: End-to-End-FPGA-Beschleuniger
Aufbauend auf dem GraphLeap-Algorithmus stellt die Arbeit den ersten End-to-End-FPGA-Beschleuniger für Vision-GNNs vor, implementiert auf einem AMD-Xilinx Alveo U280. Das Design verfügt über eine Streaming-Architektur mit Schicht-Pipelining, die zwei Haupt-Engines überlappt:

1. Graph Construction Engine (GCE): Eine Hochdurchsatz-Engine, die dilatierte $k$NN-Graphen berechnet. Sie verarbeitet Node-Features in Kacheln, nutzt ein Mesh aus Verarbeitungselementen (PEs) zur Berechnung paarweiser Distanzen und unterhält Min-Heaps zur Extraktion von Nachbarn. Entscheidend ist, dass sie Nachbarindizes an die nächste Stufe streamt, ohne vollständige Kantenfeatures im Off-Chip-Speicher zu materialisieren.
2. Feature Update Engine (FUE): Diese Engine konsumiert die gestreamten Graphendaten und führt die ViG-Grapher- und Feed-Forward-Netzwerk-(FFN)-Operationen durch. Sie umfasst:
   • Gather Module (GM): Handhabt unregelmäßige Speicherzugriffsmuster durch interleaved Banking und Prefetching, um Nachbarfeatures abzurufen.
   • Graph Convolution Module (GCM): Implementiert maximale relative Aggregation und lineare Transformationen unter Verwendung eines systolischen Arrays, wodurch die explizite Konkatenation von Node-Features und Nachrichten vermieden wird.
   • FFN Module (FM): Eine spezialisierte MLP-Datenpfad für pro-Node-Updates.

• Datenflussstrategie: Die GCE arbeitet eine Schicht vor der FUE. Dies ermöglicht, dass der Aufbau des Graphen für Schicht $\ell+1$ parallel zum Feature-Update der Schicht $\ell$ fortschreitet. Das Design vermeidet die explizite Materialisierung von $O(NK)$ Kantenfeatures und hält nur Node-Features und kleine Zeilenpuffer on-Chip.

Hauptbeiträge

1. GraphLeap-Algorithmus: Eine allgemeine Reformulierung, die den dynamischen Graphenaufbau von der Graphenkonvolution entkoppelt und die gleichzeitige Ausführung von Graphenaufbau und Feature-Updates ermöglicht.
2. Erster End-to-End-ViG-Beschleuniger: Die Entwicklung einer Streaming-Pipelining-FPGA-Architektur speziell für Vision-GNNs mit einer dedizierten $k$NN-Graphkonstruktions-Engine und einer spezialisierten Feature-Update-Engine.
3. Streaming-$k$NN-Konstruktion: Ein Hochdurchsatz-Hardware-Design für dilatierte $k$NN-Bildgraphen, das eine Schicht vor den Feature-Updates arbeitet und Nachbarindizes direkt in die Berechnungspipeline streamt.
4. Effiziente Feature-Update-Pipeline: Eine Hardware-Engine, die gemeinsam genutzte systolische MLP-Strukturen sowohl für Graphenkonvolutions- als auch für FFN-Stufen nutzt und über Streaming-Puffer verbunden ist, um gemischte unregelmäßige und regelmäßige Workloads zu bewältigen.

Experimentelle Ergebnisse
Die Autoren evaluierten GraphLeap auf isotropen (Ti, S, B) und pyramidalen (Py-Ti, Py-S, Py-M, Py-B) ViG-Modellen, die auf dem Alveo U280-FPGA bereitgestellt wurden.

• Beschleunigung: Der Ansatz erzielt gegenüber einer 64-Kern-CPU-Baseline eine bis zu 95,7-fache Beschleunigung und gegenüber einer NVIDIA RTX A5000-GPU-Baseline eine 8,5-fache Beschleunigung für die End-to-End-Inferenz.
• Latenz: Für das ViG-B-Modell bei einer Auflösung von 224×224 erreicht der Beschleuniger eine End-to-End-Latenz von 2,77 ms.
• Vergleich mit SOTA: Im Vergleich zu fortschrittlichsten ViT-Beschleunigern (DRViT, UbiMoE) auf ähnlichen FPGA-Plattformen erzielt GraphLeap eine 3-fach geringere Latenz bei vergleichbarer Genauigkeit.
• Genauigkeit: Nach dem Fine-Tuning erreichen GraphLeap-Modelle eine Wiederherstellung auf 1,4 % der ursprünglichen ViG Top-1-Genauigkeit (z. B. erreicht ViG-Py-B 82,34 %).

Bedeutung und Behauptungen
Die Arbeit behauptet, dass GraphLeap die Machbarkeit einer Echtzeit-Vision-GNN-Inferenz demonstriert, indem es den sequenziellen Engpass des dynamischen Graphenaufbaus grundlegend adressiert. Die Autoren argumentieren, dass die algorithmische Reformulierung zwar auf konventionellen CPU/GPU-Architekturen nur moderate Gewinne erzielt (1,03–1,23-fach), aber erhebliches Leistungspotenzial freisetzt, wenn sie gemeinsam mit Hardware entwickelt wird, die die resultierende Producer-Consumer-Streaming-Beziehung ausnutzen kann. Die Arbeit motiviert zukünftige Hardware-Algorithmus-Co-Designs für graphbasierte Vision-Modelle und zeigt, dass die Entkoppelung des Aufbaus von der Konvolution eine effiziente, latenzarme Inferenz ermöglicht, ohne die Vorteile adaptiver Nachbarschaften von ViGs zu opfern.