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

Riepilogo Tecnico: GraphLeap

Enunciato del Problema
Le Reti Neurali a Grafo per la Visione (ViG) rappresentano le immagini come grafi di token di patch, sfruttando vicinaggi dinamici guidati dalle caratteristiche per ottenere accuratezza competitiva con un'efficienza computazionale favorevole rispetto ai Transformer per la Visione (ViT). Tuttavia, il meccanismo centrale delle ViG—ricostruire un grafo dei $k$-vicini più prossimi ($k$NN) a ogni livello basandosi sulle caratteristiche attuali delle patch—crea un grave collo di bottiglia nelle prestazioni. Questa costruzione dinamica del grafo consuma il 50–95% del tempo totale di inferenza su CPU e GPU e scala quadraticamente ($O(N^2)$) con il numero di patch. Crucialmente, questo processo impone una dipendenza sequenziale rigorosa: il grafo per il livello $\ell$ deve essere completamente costruito prima che l'aggiornamento delle caratteristiche (convoluzione) per quel livello possa iniziare. Questa serializzazione impedisce una parallelizzazione efficiente e ostacola il dispiegamento in tempo reale. Inoltre, gli acceleratori hardware esistenti mirano principalmente a grafi statici o operazioni su griglia regolare (CNN/ViT), lasciando senza supporto le sfide specifiche della costruzione dinamica di grafi per immagini e delle pipeline ViG complete.

Metodologia: Riformulazione GraphLeap
Gli autori introducono GraphLeap, una riformulazione algoritmica innovativa che disaccoppia la costruzione del grafo dagli aggiornamenti delle caratteristiche attraverso i livelli per rompere la dipendenza sequenziale.

• Anticipazione di un Livello: Invece di costruire il grafo per il livello $\ell$ utilizzando le caratteristiche del livello $\ell$ (che deve attendere l'aggiornamento del livello precedente), GraphLeap costruisce il grafo per il livello $\ell+1$ utilizzando le caratteristiche del livello corrente $\ell$, eseguendo simultaneamente l'aggiornamento delle caratteristiche per il livello $\ell$ utilizzando il grafo costruito dalle caratteristiche del precedente livello ($\ell-1$).
• Spostamento Algoritmico: Nella ViG standard, $G^{(\ell)} = G(U^{(\ell)})$. In GraphLeap, il passaggio di messaggi nel blocco $\ell$ utilizza $\hat{G}^{(\ell)} = G(U^{(\ell-1)})$, mentre $U^{(\ell)}$ è utilizzata concorrentemente per costruire $\hat{G}^{(\ell+1)}$.
• Recupero dell'Accuratezza: Gli autori riconoscono che l'uso di grafi "obsoleti" (dal livello precedente) può introdurre un lieve degrado dell'accuratezza. Tuttavia, dimostrano che un fine-tuning leggero (30 epoche) è sufficiente per recuperare l'accuratezza originale, spesso uguagliando o superando le prestazioni della ViG di base.

Architettura di Sistema: Acceleratore FPGA End-to-End
Basandosi sull'algoritmo GraphLeap, il paper presenta il primo acceleratore FPGA end-to-end per GNN per la Visione, implementato su un AMD-Xilinx Alveo U280. Il design presenta un'architettura a streaming e pipeline di livelli che sovrappone due motori principali:

1. Motore di Costruzione del Grafo (GCE): Un motore ad alta velocità di trasferimento che calcola grafi $k$NN dilatati. Elabora le caratteristiche dei nodi in mattonelle, utilizza una maglia di elementi di elaborazione (PE) per il calcolo delle distanze pairwise e mantiene heap minimi per estrarre i vicini. Crucialmente, trasmette gli indici dei vicini alla fase successiva senza materializzare le caratteristiche degli archi complete nella memoria fuori chip.
2. Motore di Aggiornamento delle Caratteristiche (FUE): Questo motore consuma i dati del grafo in streaming ed esegue le operazioni ViG Grapher e Feed-Forward Network (FFN). Include:
   • Modulo di Raccolta (GM): Gestisce i pattern di accesso alla memoria irregolari tramite bancatura intercalata e prefetching per recuperare le caratteristiche dei vicini.
   • Modulo di Convoluzione su Grafo (GCM): Implementa l'aggregazione massima-relativa e le trasformazioni lineari utilizzando un array sistolico, evitando la concatenazione esplicita delle caratteristiche dei nodi e dei messaggi.
   • Modulo FFN (FM): Un percorso dati MLP specializzato per gli aggiornamenti per nodo.

• Strategia di Flusso Dati: Il GCE opera un livello avanti rispetto all'FUE. Questo permette alla costruzione del grafo per il livello $\ell+1$ di procedere in parallelo con l'aggiornamento delle caratteristiche del livello $\ell$. Il design evita la materializzazione esplicita delle caratteristiche degli archi $O(NK)$, mantenendo solo le caratteristiche dei nodi e piccoli buffer di linea on-chip.

Contributi Chiave

1. Algoritmo GraphLeap: Una riformulazione generale che disaccoppia la costruzione dinamica del grafo dalla convoluzione su grafo, abilitando l'esecuzione concorrente della costruzione del grafo e degli aggiornamenti delle caratteristiche.
2. Primo Acceleratore ViG End-to-End: Lo sviluppo di un'architettura FPGA a streaming e pipeline specificamente per GNN per la Visione, dotata di un motore dedicato per la costruzione di grafi $k$NN e di un motore specializzato per l'aggiornamento delle caratteristiche.
3. Costruzione $k$NN in Streaming: Un design hardware ad alta velocità di trasferimento per grafi di immagini $k$NN dilatati che opera un livello avanti rispetto agli aggiornamenti delle caratteristiche, trasmettendo gli indici dei vicini direttamente alla pipeline di calcolo.
4. Pipeline di Aggiornamento delle Caratteristiche Efficiente: Un motore hardware che utilizza tessuti MLP sistolici condivisi per le fasi di Convoluzione su Grafo e FFN, collegati tramite buffer di streaming per gestire carichi di lavoro misti irregolari e regolari.

Risultati Sperimentali
Gli autori hanno valutato GraphLeap su modelli ViG isotropi (Ti, S, B) e piramidali (Py-Ti, Py-S, Py-M, Py-B) dispiegati sull'FPGA Alveo U280.

• Accelerazione: L'approccio raggiunge fino a 95,7× di accelerazione rispetto a una baseline CPU a 64 core e 8,5× di accelerazione rispetto a una baseline GPU NVIDIA RTX A5000 per l'inferenza end-to-end.
• Latenza: Per il modello ViG-B a risoluzione 224×224, l'acceleratore raggiunge una latenza end-to-end di 2,77 ms.
• Confronto con SOTA: Rispetto agli acceleratori ViT all'avanguardia (DRViT, UbiMoE) su piattaforme FPGA simili, GraphLeap raggiunge una latenza 3× inferiore con accuratezza comparabile.
• Accuratezza: Dopo il fine-tuning, i modelli GraphLeap recuperano entro il 1,4% dell'accuratezza Top-1 ViG originale (ad esempio, ViG-Py-B raggiunge l'82,34%).

Significato e Affermazioni
Il paper afferma che GraphLeap dimostra la fattibilità dell'inferenza GNN per la Visione in tempo reale affrontando fondamentalmente il collo di bottiglia sequenziale della costruzione dinamica del grafo. Gli autori sostengono che, mentre la riformulazione algoritmica produce guadagni modesti solo sulle architetture CPU/GPU convenzionali (1,03–1,23×), sblocca un potenziale di prestazioni significativo quando co-progettata con hardware in grado di sfruttare la relazione produttore-consumatore in streaming risultante. Il lavoro motiva il futuro co-design hardware-algoritmo per modelli di visione basati su grafi, mostrando che il disaccoppiamento della costruzione dalla convoluzione permette un'inferenza efficiente a bassa latenza senza sacrificare i benefici dei vicinaggi adattivi delle ViG.