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

Resumo Técnico: GraphLeap

Declaração do Problema
Redes Neurais em Grafos para Visão (ViGs) representam imagens como grafos de tokens de patch, utilizando vizinhanças dinâmicas e orientadas por características para alcançar precisão competitiva com eficiência computacional favorável em comparação com Transformers de Visão (ViTs). No entanto, o mecanismo central das ViGs — reconstruir um grafo de $k$-vizinhos mais próximos ($k$NN) em cada camada com base nas características atuais dos patches — cria um gargalo severo de desempenho. A construção dinâmica desse grafo consome 50–95% do tempo total de inferência em CPUs e GPUs e escala quadraticamente ($O(N^2)$) com o número de patches. Crucialmente, esse processo impõe uma dependência sequencial estrita: o grafo para a camada $\ell$ deve ser totalmente construído antes que a atualização de características (convolução) para essa camada possa começar. Essa serialização impede a paralelização eficiente e dificulta a implantação em tempo real. Além disso, aceleradores de hardware existentes visam majoritariamente grafos estáticos ou operações em grade regular (CNNs/ViTs), deixando os desafios específicos da construção dinâmica de grafos de imagem e de pipelines completos de ViG sem suporte.

Metodologia: Reformulação GraphLeap
Os autores introduzem o GraphLeap, uma reformulação algorítmica inovadora que desacopla a construção do grafo das atualizações de características entre camadas para quebrar a dependência sequencial.

• Antecipação de Uma Camada: Em vez de construir o grafo para a camada $\ell$ usando características da camada $\ell$ (o que exigiria aguardar a atualização da camada anterior), o GraphLeap constrói o grafo para a camada $\ell+1$ usando as características da camada atual $\ell$, enquanto simultaneamente realiza a atualização de características para a camada $\ell$ usando o grafo construído a partir das características da camada anterior ($\ell-1$).
• Mudança Algorítmica: No ViG padrão, $G^{(\ell)} = G(U^{(\ell)})$. No GraphLeap, a passagem de mensagens no bloco $\ell$ usa $\hat{G}^{(\ell)} = G(U^{(\ell-1)})$, enquanto $U^{(\ell)}$ é usada concorrentemente para construir $\hat{G}^{(\ell+1)}$.
• Recuperação de Precisão: Os autores reconhecem que o uso de grafos "desatualizados" (da camada anterior) pode introduzir uma degradação mínima de precisão. No entanto, demonstram que um ajuste fino leve (30 épocas) é suficiente para recuperar a precisão original, frequentemente igualando ou superando o desempenho do ViG de base.

Arquitetura do Sistema: Acelerador FPGA de Ponta a Ponta
Com base no algoritmo GraphLeap, o artigo apresenta o primeiro acelerador FPGA de ponta a ponta para GNNs de Visão, implementado em um AMD-Xilinx Alveo U280. O projeto apresenta uma arquitetura de fluxo de dados e pipeline de camadas que sobrepõe dois motores principais:

1. Motor de Construção de Grafos (GCE): Um motor de alto rendimento que computa grafos $k$NN dilatados. Ele processa características de nós em blocos, utiliza uma malha de elementos de processamento (PEs) para computação de distância par a par e mantém min-heaps para extrair vizinhos. Crucialmente, ele transmite índices de vizinhos para a próxima etapa sem materializar características de arestas completas na memória fora do chip.
2. Motor de Atualização de Características (FUE): Este motor consome os dados de grafos transmitidos e realiza as operações de Grapher e Rede Feed-Forward (FFN) do ViG. Inclui:
   • Módulo de Coleta (GM): Lida com padrões de acesso à memória irregulares por meio de bancadas intercaladas e pré-busca para recuperar características de vizinhos.
   • Módulo de Convolução em Grafo (GCM): Implementa agregação máxima relativa e transformações lineares usando uma matriz sístólica, evitando a concatenação explícita de características de nós e mensagens.
   • Módulo FFN (FM): Um caminho de dados MLP especializado para atualizações por nó.

• Estratégia de Fluxo de Dados: O GCE opera uma camada à frente do FUE. Isso permite que a construção do grafo para a camada $\ell+1$ prossiga em paralelo com a atualização de características da camada $\ell$. O projeto evita a materialização explícita de características de arestas $O(NK)$, mantendo apenas características de nós e pequenos buffers de linha no chip.

Principais Contribuições

1. Algoritmo GraphLeap: Uma reformulação geral que desacopla a construção dinâmica de grafos da convolução em grafos, permitindo a execução concorrente da construção de grafos e das atualizações de características.
2. Primeiro Acelerador End-to-End de ViG: O desenvolvimento de uma arquitetura FPGA de fluxo de dados e pipeline especificamente para GNNs de Visão, apresentando um motor dedicado de construção de grafos $k$NN e um motor especializado de atualização de características.
3. Construção de $k$NN em Fluxo: Um projeto de hardware de alto rendimento para grafos de imagem $k$NN dilatados que opera uma camada à frente das atualizações de características, transmitindo índices de vizinhos diretamente para o pipeline de computação.
4. Pipeline Eficiente de Atualização de Características: Um motor de hardware que utiliza malhas MLP sístólicas compartilhadas para as etapas de Convolução em Grafo e FFN, conectadas por meio de buffers de fluxo para lidar com cargas de trabalho mistas irregulares e regulares.

Resultados Experimentais
Os autores avaliaram o GraphLeap em modelos ViG isotrópicos (Ti, S, B) e piramidais (Py-Ti, Py-S, Py-M, Py-B) implantados no FPGA Alveo U280.

• Aceleração: A abordagem alcança até 95,7× de aceleração sobre uma linha de base de CPU de 64 núcleos e 8,5× de aceleração sobre uma linha de base de GPU NVIDIA RTX A5000 para inferência de ponta a ponta.
• Latência: Para o modelo ViG-B na resolução 224×224, o acelerador alcança uma latência de ponta a ponta de 2,77 ms.
• Comparação com o Estado da Arte: Comparado a aceleradores ViT de última geração (DRViT, UbiMoE) em plataformas FPGA semelhantes, o GraphLeap alcança 3× menor latência com precisão comparável.
• Precisão: Após o ajuste fino, os modelos GraphLeap recuperam-se para dentro de 1,4% da precisão Top-1 original do ViG (por exemplo, ViG-Py-B atinge 82,34%).

Significado e Alegações
O artigo afirma que o GraphLeap demonstra a viabilidade da inferência de GNNs de Visão em tempo real ao abordar fundamentalmente o gargalo sequencial da construção dinâmica de grafos. Os autores argumentam que, embora a reformulação algorítmica gere ganhos apenas modestos em arquiteturas convencionais de CPU/GPU (1,03–1,23×), ela libera um potencial de desempenho significativo quando co-projetada com hardware capaz de explorar a relação produtor-consumidor de fluxo de dados resultante. O trabalho motiva futuros projetos de co-design hardware-algoritmo para modelos de visão baseados em grafos, mostrando que o desacoplamento da construção da convolução permite inferência eficiente e de baixa latência sem sacrificar os benefícios de vizinhança adaptativa das ViGs.