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

Résumé Technique : GraphLeap

Énoncé du Problème
Les Réseaux de Neurones Graphiques pour la Vision (ViG) représentent les images sous forme de graphes de tokens de patches, en utilisant des voisinages dynamiques et pilotés par les caractéristiques pour atteindre une précision compétitive avec une efficacité de calcul favorable par rapport aux Transformers pour la Vision (ViT). Cependant, le mécanisme central des ViG — la reconstruction d'un graphe des $k$ plus proches voisins ($k$NN) à chaque couche basée sur les caractéristiques actuelles des patches — crée un goulot d'étranglement sévère pour les performances. Cette construction dynamique de graphes consomme 50 à 95 % du temps total d'inférence sur les CPU et les GPU et s'étend de manière quadratique ($O(N^2)$) avec le nombre de patches. Crucial, ce processus impose une dépendance séquentielle stricte : le graphe pour la couche $\ell$ doit être entièrement construit avant que la mise à jour des caractéristiques (convolution) pour cette couche ne puisse commencer. Cette sérialisation empêche une parallélisation efficace et entrave le déploiement en temps réel. De plus, les accélérateurs matériels existants ciblent principalement des graphes statiques ou des opérations de grille régulière (CNN/ViT), laissant sans soutien les défis spécifiques de la construction dynamique de graphes d'images et des pipelines ViG complets.

Méthodologie : Reformulation GraphLeap
Les auteurs introduisent GraphLeap, une reformulation algorithmique novatrice qui découple la construction du graphe des mises à jour des caractéristiques à travers les couches pour briser la dépendance séquentielle.

• Anticipation d'une couche : Au lieu de construire le graphe pour la couche $\ell$ en utilisant les caractéristiques de la couche $\ell$ (ce qui doit attendre la mise à jour de la couche précédente), GraphLeap construit le graphe pour la couche $\ell+1$ en utilisant les caractéristiques de la couche actuelle $\ell$, tout en effectuant simultanément la mise à jour des caractéristiques pour la couche $\ell$ en utilisant le graphe construit à partir des caractéristiques de la couche précédente ($\ell-1$).
• Changement Algorithmique : Dans un ViG standard, $G^{(\ell)} = G(U^{(\ell)})$. Dans GraphLeap, le passage de messages au bloc $\ell$ utilise $\hat{G}^{(\ell)} = G(U^{(\ell-1)})$, tandis que $U^{(\ell)}$ est simultanément utilisé pour construire $\hat{G}^{(\ell+1)}$.
• Récupération de la Précision : Les auteurs reconnaissent que l'utilisation de graphes « périmés » (de la couche précédente) peut introduire une légère dégradation de la précision. Cependant, ils démontrent qu'un réglage fin léger (30 époques) suffit à récupérer la précision originale, correspondant souvent ou dépassant les performances de base du ViG.

Architecture Système : Accélérateur FPGA de Bout en Bout
S'appuyant sur l'algorithme GraphLeap, l'article présente le premier accélérateur FPGA de bout en bout pour les GNN de Vision, implémenté sur une AMD-Xilinx Alveo U280. La conception présente une architecture de flux de données et de pipeline de couches qui chevauche deux moteurs principaux :

1. Moteur de Construction de Graphe (GCE) : Un moteur à haut débit qui calcule des graphes $k$NN dilatés. Il traite les caractéristiques des nœuds par tuiles, utilise une grille d'éléments de traitement (PE) pour le calcul des distances par paires, et maintient des tas min pour extraire les voisins. Crucial, il transmet les indices des voisins à l'étape suivante sans matérialiser les caractéristiques complètes des arêtes dans la mémoire hors puce.
2. Moteur de Mise à Jour des Caractéristiques (FUE) : Ce moteur consomme les données de graphe en flux et effectue les opérations ViG Grapher et du Réseau de Neurones Feed-Forward (FFN). Il comprend :
   • Module de Rassemblement (GM) : Gère les motifs d'accès mémoire irréguliers via un bancage entrelacé et une prélecture pour récupérer les caractéristiques des voisins.
   • Module de Convolution Graphique (GCM) : Implémente l'agrégation relative maximale et les transformations linéaires en utilisant un réseau systolique, évitant la concaténation explicite des caractéristiques des nœuds et des messages.
   • Module FFN (FM) : Un chemin de données MLP spécialisé pour les mises à jour par nœud.

• Stratégie de Flux de Données : Le GCE opère une couche en avance sur le FUE. Cela permet à la construction du graphe pour la couche $\ell+1$ de se poursuivre en parallèle avec la mise à jour des caractéristiques de la couche $\ell$. La conception évite la matérialisation explicite des caractéristiques des arêtes $O(NK)$, ne conservant que les caractéristiques des nœuds et de petits tampons de ligne sur puce.

Contributions Clés

1. Algorithme GraphLeap : Une reformulation générale qui découple la construction dynamique de graphes de la convolution graphique, permettant l'exécution concurrente de la construction de graphes et des mises à jour des caractéristiques.
2. Premier Accélérateur ViG de Bout en Bout : Le développement d'une architecture FPGA en flux de données et pipelinée spécifiquement pour les GNN de Vision, dotée d'un moteur de construction de graphes $k$NN dédié et d'un moteur de mise à jour des caractéristiques spécialisé.
3. Construction de $k$NN en Flux : Une conception matérielle à haut débit pour les graphes d'images $k$NN dilatés qui opère une couche en avance sur les mises à jour des caractéristiques, transmettant directement les indices des voisins au pipeline de calcul.
4. Pipeline de Mise à Jour des Caractéristiques Efficace : Un moteur matériel utilisant des tissus MLP systoliques partagés pour les étapes de Convolution Graphique et FFN, connectés via des tampons de flux pour gérer des charges de travail mixtes irrégulières et régulières.

Résultats Expérimentaux
Les auteurs ont évalué GraphLeap sur des modèles ViG isotropes (Ti, S, B) et pyramidales (Py-Ti, Py-S, Py-M, Py-B) déployés sur le FPGA Alveo U280.

• Accélération : L'approche atteint jusqu'à 95,7× d'accélération par rapport à une base de référence CPU à 64 cœurs et 8,5× d'accélération par rapport à une base de référence GPU NVIDIA RTX A5000 pour l'inférence de bout en bout.
• Latence : Pour le modèle ViG-B à une résolution de 224×224, l'accélérateur atteint une latence de bout en bout de 2,77 ms.
• Comparaison avec l'État de l'Art : Par rapport aux accélérateurs ViT de pointe (DRViT, UbiMoE) sur des plateformes FPGA similaires, GraphLeap atteint une latence 3× inférieure avec une précision comparable.
• Précision : Après réglage fin, les modèles GraphLeap récupèrent à moins de 1,4 % de la précision Top-1 ViG originale (par exemple, ViG-Py-B atteint 82,34 %).

Signification et Revendications
L'article affirme que GraphLeap démontre la faisabilité de l'inférence en temps réel des GNN de Vision en s'attaquant fondamentalement au goulot d'étranglement séquentiel de la construction dynamique de graphes. Les auteurs soutiennent que, bien que la reformulation algorithmique ne produise que des gains modestes sur les architectures CPU/GPU conventionnelles (1,03–1,23×), elle débloque un potentiel de performance significatif lorsqu'elle est co-conçue avec du matériel capable d'exploiter la relation producteur-consommateur en flux de données qui en résulte. Ce travail motive la future co-conception matériel-algorithme pour les modèles de vision basés sur les graphes, montrant que le découplage de la construction de la convolution permet une inférence efficace et à faible latence sans sacrifier les avantages des voisinages adaptatifs des ViG.