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

Resumen Técnico: GraphLeap

Enunciado del Problema
Las Redes Neuronales de Grafos para Visión (ViG) representan imágenes como grafos de tokens de parche, utilizando vecindarios dinámicos impulsados por características para lograr una precisión competitiva con una eficiencia de cálculo favorable en comparación con los Transformadores de Visión (ViT). Sin embargo, el mecanismo central de las ViG —reconstruir un grafo de $k$-vecinos más cercanos ($k$NN) en cada capa basándose en las características actuales de los parches— crea un cuello de botella severo en el rendimiento. Esta construcción de grafos dinámica consume entre el 50% y el 95% del tiempo total de inferencia en CPUs y GPUs, y escala cuadráticamente ($O(N^2)$) con el número de parches. Crucialmente, este proceso impone una dependencia estrictamente secuencial: el grafo para la capa $\ell$ debe construirse completamente antes de que pueda comenzar la actualización de características (convolución) para dicha capa. Esta serialización impide una paralelización eficiente y obstaculiza el despliegue en tiempo real. Además, los aceleradores de hardware existentes se dirigen principalmente a grafos estáticos u operaciones de cuadrícula regular (CNN/ViT), dejando sin soporte los desafíos específicos de la construcción de grafos de imágenes dinámicos y las pipelines completas de ViG.

Metodología: Reformulación de GraphLeap
Los autores introducen GraphLeap, una reformulación algorítmica novedosa que desacopla la construcción del grafo de las actualizaciones de características a través de las capas para romper la dependencia secuencial.

• Anticipación de una Capa: En lugar de construir el grafo para la capa $\ell$ utilizando características de la capa $\ell$ (lo cual debe esperar a la actualización de la capa anterior), GraphLeap construye el grafo para la capa $\ell+1$ utilizando las características de la capa actual $\ell$, mientras realiza simultáneamente la actualización de características para la capa $\ell$ utilizando el grafo construido a partir de las características de la capa anterior ($\ell-1$).
• Cambio Algorítmico: En una ViG estándar, $G^{(\ell)} = G(U^{(\ell)})$. En GraphLeap, el paso de mensajes en el bloque $\ell$ utiliza $\hat{G}^{(\ell)} = G(U^{(\ell-1)})$, mientras que $U^{(\ell)}$ se utiliza concurrentemente para construir $\hat{G}^{(\ell+1)}$.
• Recuperación de Precisión: Los autores reconocen que el uso de grafos "desactualizados" (de la capa anterior) puede introducir una degradación menor en la precisión. Sin embargo, demuestran que un ajuste fino ligero (30 épocas) es suficiente para recuperar la precisión original, a menudo igualando o superando el rendimiento de la ViG de referencia.

Arquitectura del Sistema: Acelerador FPGA de Extremo a Extremo
Basándose en el algoritmo GraphLeap, el artículo presenta el primer acelerador FPGA de extremo a extremo para GNN de Visión, implementado en un AMD-Xilinx Alveo U280. El diseño presenta una arquitectura de flujo de datos en streaming y con tubería por capas que superpone dos motores principales:

1. Motor de Construcción de Grafos (GCE): Un motor de alto rendimiento que calcula grafos $k$NN dilatados. Procesa las características de los nodos en baldosas, utiliza una malla de elementos de procesamiento (PE) para el cálculo de distancias por pares y mantiene montículos mínimos para extraer los vecinos. Crucialmente, transmite los índices de vecinos a la siguiente etapa sin materializar características de aristas completas en la memoria fuera del chip.
2. Motor de Actualización de Características (FUE): Este motor consume los datos de grafos transmitidos y realiza las operaciones de Grapher de ViG y de la Red de Alimentación Directa (FFN). Incluye:
   • Módulo de Recolección (GM): Gestiona patrones de acceso a memoria irregulares mediante bancada intercalada y prebúsqueda para recuperar características de vecinos.
   • Módulo de Convolución de Grafos (GCM): Implementa agregación máxima-relativa y transformaciones lineales utilizando una matriz sístólica, evitando la concatenación explícita de características de nodos y mensajes.
   • Módulo FFN (FM): Una ruta de datos MLP especializada para actualizaciones por nodo.

• Estrategia de Flujo de Datos: El GCE opera una capa por delante del FUE. Esto permite que la construcción del grafo para la capa $\ell+1$ proceda en paralelo con la actualización de características de la capa $\ell$. El diseño evita la materialización explícita de características de aristas $O(NK)$, manteniendo solo características de nodos y pequeños búferes de línea en el chip.

Contribuciones Clave

1. Algoritmo GraphLeap: Una reformulación general que desacopla la construcción de grafos dinámicos de la convolución de grafos, permitiendo la ejecución concurrente de la construcción de grafos y las actualizaciones de características.
2. Primer Acelerador de ViG de Extremo a Extremo: El desarrollo de una arquitectura FPGA en streaming y con tubería específicamente para GNN de Visión, que presenta un motor dedicado de construcción de grafos $k$NN y un motor especializado de actualización de características.
3. Construcción de $k$NN en Streaming: Un diseño de hardware de alto rendimiento para grafos de imágenes $k$NN dilatados que opera una capa por delante de las actualizaciones de características, transmitiendo índices de vecinos directamente a la pipeline de cálculo.
4. Pipeline de Actualización de Características Eficiente: Un motor de hardware que utiliza tejidos MLP sísticos compartidos tanto para las etapas de Convolución de Grafos como de FFN, conectados mediante búferes de streaming para manejar cargas de trabajo mixtas irregulares y regulares.

Resultados Experimentales
Los autores evaluaron GraphLeap en modelos ViG isotrópicos (Ti, S, B) y piramidales (Py-Ti, Py-S, Py-M, Py-B) desplegados en el FPGA Alveo U280.

• Aceleración: El enfoque logra una aceleración de hasta 95.7× sobre una línea base de CPU de 64 núcleos y una aceleración de 8.5× sobre una línea base de GPU NVIDIA RTX A5000 para inferencia de extremo a extremo.
• Latencia: Para el modelo ViG-B a una resolución de 224×224, el acelerador logra una latencia de extremo a extremo de 2.77 ms.
• Comparación con el Estado del Arte: En comparación con aceleradores de ViT de última generación (DRViT, UbiMoE) en plataformas FPGA similares, GraphLeap logra una latencia 3 veces menor con una precisión comparable.
• Precisión: Tras el ajuste fino, los modelos GraphLeap se recuperan hasta un 1.4% de la precisión Top-1 original de ViG (por ejemplo, ViG-Py-B alcanza un 82.34%).

Significado y Afirmaciones
El artículo afirma que GraphLeap demuestra la viabilidad de la inferencia de GNN de Visión en tiempo real al abordar fundamentalmente el cuello de botella secuencial de la construcción de grafos dinámicos. Los autores argumentan que, si bien la reformulación algorítmica produce ganancias modestas en arquitecturas convencionales de CPU/GPU (1.03–1.23×), desbloquea un potencial de rendimiento significativo cuando se diseña en conjunto con hardware que puede explotar la relación de flujo de datos productor-consumidor resultante. El trabajo motiva futuros diseños conjuntos de hardware y algoritmos para modelos de visión basados en grafos, mostrando que desacoplar la construcción de la convolución permite una inferencia eficiente y de baja latencia sin sacrificar los beneficios de vecindarios adaptativos de las ViG.