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

Technische Samenvatting: GraphLeap

Probleemstelling
Vision Graph Neural Networks (ViGs) stellen afbeeldingen voor als grafen van patch-tokens, waarbij dynamische, kenmerkgedreven buurten worden gebruikt om concurrerende nauwkeurigheid te bereiken met een gunstige rekenefficiëntie in vergelijking met Vision Transformers (ViTs). Het kernmechanisme van ViGs—het reconstrueren van een $k$-naaste-buurten-graf ($k$NN) op elke laag op basis van huidige patch-kenmerken—creëert echter een ernstige prestatieknelpunt. Deze dynamische grafoptelling verbruikt 50–95% van de totale inferentietijd op CPU's en GPU's en schaalt kwadratisch ($O(N^2)$) met het aantal patches. Cruciaal is dat dit proces een strikte sequentiële afhankelijkheid oplegt: de graf voor laag $\ell$ moet volledig zijn opgebouwd voordat de kenmerkupdate (convolutie) voor die laag kan beginnen. Deze serialisatie verhindert efficiënte parallelisatie en belemmert realtime implementatie. Bovendien richten bestaande hardware-acceleratoren zich grotendeels op statische grafen of regelmatige rasterbewerkingen (CNN's/ViTs), waardoor de specifieke uitdagingen van dynamische afbeeldingsgrafoptelling en volledige ViG-pijplijnen onondersteund blijven.

Methodologie: GraphLeap-hervorming
De auteurs introduceren GraphLeap, een nieuwe algoritmische hervorming die grafoptelling ontkoppelt van kenmerkupdates over lagen om de sequentiële afhankelijkheid te doorbreken.

• Eén-laags vooruitkijken: In plaats van de graf voor laag $\ell$ te construeren met kenmerken van laag $\ell$ (wat moet wachten op de update van de vorige laag), construeert GraphLeap de graf voor laag $\ell+1$ met de kenmerken van de huidige laag $\ell$, terwijl gelijktijdig de kenmerkupdate voor laag $\ell$ wordt uitgevoerd met de graf die is opgebouwd uit de kenmerken van de vorige laag ($\ell-1$).
• Algoritmische verschuiving: In een standaard ViG geldt $G^{(\ell)} = G(U^{(\ell)})$. In GraphLeap gebruikt de berichtuitwisseling in blok $\ell$ $\hat{G}^{(\ell)} = G(U^{(\ell-1)})$, terwijl $U^{(\ell)}$ gelijktijdig wordt gebruikt om $\hat{G}^{(\ell+1)}$ te bouwen.
• Herstel van nauwkeurigheid: De auteurs erkennen dat het gebruik van "verouderde" grafen (van de vorige laag) een lichte afname in nauwkeurigheid kan veroorzaken. Zij tonen echter aan dat lichtgewicht fine-tuning (30 epochs) voldoende is om de oorspronkelijke nauwkeurigheid te herstellen, waarbij de prestaties vaak gelijk zijn aan of die van de baseline ViG overtreffen.

Systeemarchitectuur: End-to-end FPGA-accelerator
Op basis van het GraphLeap-algoritme presenteert het artikel de eerste end-to-end FPGA-accelerator voor Vision GNN's, geïmplementeerd op een AMD-Xilinx Alveo U280. Het ontwerp kenmerkt zich door een streaming, laag-gespijkerde architectuur die twee primaire engines overlapt:

1. Graph Construction Engine (GCE): Een engine met hoge doorvoer die gedilateerde $k$NN-grafen berekent. Deze verwerkt knopenkenmerken in tegels, gebruikt een mesh van verwerkingselementen (PE's) voor paarsgewijze afstandsberkening, en onderhoudt min-heaps om buren te extraheren. Cruciaal is dat deze engine burenindexen streamt naar de volgende fase zonder volledige randkenmerken in het extern geheugen te materialiseren.
2. Feature Update Engine (FUE): Deze engine consumeert de gestreamde graafdata en voert de ViG Grapher- en Feed-Forward Network (FFN)-bewerkingen uit. Deze omvat:
   • Gather Module (GM): Handelt onregelmatige toegangspatronen in het geheugen af via verweven banken en prefetching om burenkenmerken op te halen.
   • Graph Convolution Module (GCM): Implementeert max-relatieve aggregatie en lineaire transformaties met behulp van een systolisch array, waarbij expliciete concatenatie van knopenkenmerken en berichten wordt vermeden.
   • FFN Module (FM): Een gespecialiseerd MLP-datapad voor updates per knoop.

• Dataflow-strategie: De GCE werkt één laag vooruit op de FUE. Dit maakt het mogelijk dat het construeren van de graf voor laag $\ell+1$ parallel verloopt met de kenmerkupdate van laag $\ell$. Het ontwerp vermijdt expliciete materialisatie van $O(NK)$ randkenmerken en houdt alleen knopenkenmerken en kleine lijnbuffers on-chip.

Belangrijkste bijdragen

1. GraphLeap-algoritme: Een algemene hervorming die dynamische grafoptelling ontkoppelt van grafconvolutie, waardoor gelijktijdige uitvoering van grafbouw en kenmerkupdates mogelijk wordt.
2. Eerste end-to-end ViG-accelerator: De ontwikkeling van een streaming, gespijkerde FPGA-architectuur specifiek voor Vision GNN's, met een dedicate $k$NN-grafconstruktie-engine en een gespecialiseerde kenmerkupdate-engine.
3. Streaming $k$NN-construktie: Een hardware-ontwerp met hoge doorvoer voor gedilateerde $k$NN-afbeeldingsgraf die één laag vooruit werkt op kenmerkupdates en burenindexen direct naar de berekeningspijplijn streamt.
4. Efficiënte kenmerkupdate-pijplijn: Een hardware-engine die gedeelde systolische MLP-fabricen gebruikt voor zowel de Graph Convolution- als FFN-fasen, verbonden via streamingbuffers om gemengde onregelmatige en regelmatige werklasten te verwerken.

Experimentele resultaten
De auteurs hebben GraphLeap geëvalueerd op isotrope (Ti, S, B) en piramidale (Py-Ti, Py-S, Py-M, Py-B) ViG-modellen die zijn ingezet op de Alveo U280 FPGA.

• Snelheidswinst: De aanpak bereikt tot 95,7× snelheidswinst ten opzichte van een 64-core CPU-baseline en 8,5× snelheidswinst ten opzichte van een NVIDIA RTX A5000 GPU-baseline voor end-to-end inferentie.
• Latentie: Voor het ViG-B-model bij een resolutie van 224×224 bereikt de accelerator een end-to-end latentie van 2,77 ms.
• Vergelijking met SOTA: In vergelijking met state-of-the-art ViT-acceleratoren (DRViT, UbiMoE) op vergelijkbare FPGA-platforms bereikt GraphLeap 3× lagere latentie met vergelijkbare nauwkeurigheid.
• Nauwkeurigheid: Na fine-tuning herstellen GraphLeap-modellen zich tot binnen 1,4% van de oorspronkelijke ViG Top-1-nauwkeurigheid (bijvoorbeeld bereikt ViG-Py-B 82,34%).

Betekenis en claims
Het artikel stelt dat GraphLeap de haalbaarheid van realtime Vision GNN-inferentie aantoont door fundamenteel het sequentiële knelpunt van dynamische grafoptelling aan te pakken. De auteurs betogen dat hoewel de algoritmische hervorming slechts bescheiden winsten oplevert op conventionele CPU/GPU-architecturen (1,03–1,23×), het aanzienlijk potentieel voor prestaties ontsluit wanneer het wordt ontworpen in samenwerking met hardware die de resulterende producer-consumer streamingrelatie kan benutten. Het werk motiveert toekomstige hardware-algoritme co-design voor op grafen gebaseerde visiemodellen, en laat zien dat het ontkoppelen van construktie van convolutie efficiënte, lage-latentie inferentie mogelijk maakt zonder de voordelen van adaptieve buurten van ViGs op te offeren.