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

기술 요약: GraphLeap

문제 정의
비전 그래프 신경망 (ViG) 은 이미지 패치 토큰의 그래프로 이미지를 표현하며, 동적이고 특징 기반의 이웃을 활용하여 Vision Transformers(ViT) 대비 경쟁력 있는 정확도와 유리한 계산 효율을 달성합니다. 그러나 ViG 의 핵심 메커니즘인 현재 패치 특징에 기반하여 모든 층에서 $k$-최근접 이웃 ($k$NN) 그래프를 재구성하는 과정은 심각한 성능 병목 현상을 초래합니다. 이 동적 그래프 구성은 CPU 및 GPU 에서 총 추론 시간의 50~95% 를 소비하며, 패치 수에 따라 2 차 ($O(N^2)$) 로 확장됩니다. 특히, 이 과정은 층 $\ell$의 그래프가 완전히 구성되어야만 해당 층의 특징 업데이트 (합성곱) 가 시작될 수 있도록 엄격한 순차적 종속성을 강제합니다. 이러한 직렬화는 효율적인 병렬화를 방해하고 실시간 배포를 저해합니다. 또한, 기존 하드웨어 가속기는 주로 정적 그래프 또는 정규 그리드 연산 (CNN/ViT) 을 대상으로 하여, 동적 이미지 그래프 구성 및 전체 ViG 파이프라인의 특정 과제는 지원되지 않고 있습니다.

방법론: GraphLeap 재형성
저자들은 순차적 종속성을 깨기 위해 그래프 구성과 층 간 특징 업데이트를 분리하는 새로운 알고리즘적 재형성인 GraphLeap을 소개합니다.

• 단일 층 미리보기 (One-Layer Lookahead): 이전 층의 업데이트를 기다려야 하는 층 $\ell$의 특징을 사용하여 층 $\ell$의 그래프를 구성하는 대신, GraphLeap 은 현재 층 $\ell$의 특징을 사용하여 층 $\ell+1$의 그래프를 구성하면서, 동시에 이전 층의 특징 ($\ell-1$) 으로 구성된 그래프를 사용하여 층 $\ell$의 특징 업데이트를 수행합니다.
• 알고리즘적 전환: 표준 ViG 에서 $G^{(\ell)} = G(U^{(\ell)})$인 반면, GraphLeap 에서는 블록 $\ell$의 메시지 전달에 $\hat{G}^{(\ell)} = G(U^{(\ell-1)})$를 사용하며, $U^{(\ell)}$는 동시에 $\hat{G}^{(\ell+1)}$를 구축하는 데 사용됩니다.
• 정확도 회복: 저자들은 "오래된" 그래프 (이전 층의 그래프) 를 사용하면 약간의 정확도 저하가 발생할 수 있음을 인정합니다. 그러나 경량 파인튜닝 (30 에포크) 만으로 원래 정확도를 회복할 수 있으며, 종종 기준 ViG 성능과 일치하거나 초과함을 입증했습니다.

시스템 아키텍처: 엔드투엔드 FPGA 가속기
GraphLeap 알고리즘을 기반으로, 이 논문은 AMD-Xilinx Alveo U280 에 구현된 Vision GNN 을 위한 최초의 엔드투엔드 FPGA 가속기를 제시합니다. 이 설계는 두 가지 주요 엔진을 중첩하는 스트리밍, 층 파이프라인 아키텍처를 특징으로 합니다.

1. 그래프 구성 엔진 (GCE): 확장된 $k$NN 그래프를 계산하는 고처리량 엔진입니다. 노드 특징을 타일로 처리하고, 쌍별 거리 계산을 위해 처리 요소 (PE) 의 메쉬를 사용하며, 이웃을 추출하기 위해 최소 힙을 유지합니다. 핵심적으로, 온칩 메모리에 전체 엣지 특징을 구체화하지 않고 이웃 인덱스를 다음 단계로 스트리밍합니다.
2. 특징 업데이트 엔진 (FUE): 이 엔진은 스트리밍된 그래프 데이터를 소비하여 ViG Grapher 및 피드포워드 네트워크 (FFN) 연산을 수행합니다. 여기에는 다음이 포함됩니다.
   • 수집 모듈 (GM): 이웃 특징을 검색하기 위해 인터리브 뱅킹 및 프리페칭을 통해 불규칙한 메모리 접근 패턴을 처리합니다.
   • 그래프 합성곱 모듈 (GCM): 노드 특징과 메시지의 명시적 연결을 피하면서 심스틱 어레이를 사용하여 최대 상대적 집계 및 선형 변환을 구현합니다.
   • FFN 모듈 (FM): 노드별 업데이트를 위한 전용 MLP 데이터 경로입니다.

• 데이터 흐름 전략: GCE 는 FUE 보다 한 층 앞서 작동합니다. 이를 통해 층 $\ell+1$의 그래프 구성이 층 $\ell$의 특징 업데이트와 병렬로 진행될 수 있습니다. 이 설계는 $O(NK)$ 엣지 특징의 명시적 구체화를 피하고, 노드 특징과 작은 라인 버퍼만 온칩에 유지합니다.

주요 기여

1. GraphLeap 알고리즘: 동적 그래프 구성을 그래프 합성곱에서 분리하여 그래프 구축과 특징 업데이트의 동시 실행을 가능하게 하는 일반적인 재형성입니다.
2. 최초의 엔드투엔드 ViG 가속기: 전용 $k$NN 그래프 구성 엔진과 전용 특징 업데이트 엔진을 갖춘 Vision GNN 을 위한 스트리밍 파이프라인 FPGA 아키텍처 개발입니다.
3. 스트리밍 $k$NN 구성: 특징 업데이트보다 한 층 앞서 작동하며 이웃 인덱스를 직접 계산 파이프라인으로 스트리밍하는 확장된 $k$NN 이미지 그래프를 위한 고처리량 하드웨어 설계입니다.
4. 효율적인 특징 업데이트 파이프라인: 혼합된 불규칙 및 정규 워크로드를 처리하기 위해 스트리밍 버퍼를 통해 연결된 Graph Convolution 및 FFN 단계 모두에 공유 심스틱 MLP 패브릭을 활용하는 하드웨어 엔진입니다.

실험 결과
저자들은 Alveo U280 FPGA 에 배포된 등방성 (Ti, S, B) 및 피라미드형 (Py-Ti, Py-S, Py-M, Py-B) ViG 모델에 대해 GraphLeap 을 평가했습니다.

• 속도 향상: 이 접근 방식은 엔드투엔드 추론에서 64 코어 CPU 기준 대비 최대 95.7 배의 속도 향상을 달성했으며, NVIDIA RTX A5000 GPU 기준 대비 8.5 배의 속도 향상을 달성했습니다.
• 지연 시간: 224×224 해상도의 ViG-B 모델의 경우, 가속기는 엔드투엔드 지연 시간을 2.77ms 로 달성했습니다.
• 최첨단 (SOTA) 대비 비교: 유사한 FPGA 플랫폼의 최첨단 ViT 가속기 (DRViT, UbiMoE) 와 비교하여 GraphLeap 은 동등한 정확도로 3 배 낮은 지연 시간을 달성했습니다.
• 정확도: 파인튜닝 후 GraphLeap 모델은 원래 ViG Top-1 정확도 내에서 1.4% 이내로 회복됩니다 (예: ViG-Py-B 는 82.34% 도달).

의의 및 주장
이 논문은 동적 그래프 구성의 순차적 병목 현상을 근본적으로 해결함으로써 실시간 Vision GNN 추론의 실현 가능성을 GraphLeap 이 입증했다고 주장합니다. 저자들은 알고리즘적 재형성이 기존 CPU/GPU 아키텍처에서는 1.03~1.23 배의 modest 한 이득만 가져오지만, 결과적인 생산자 - 소비자 스트리밍 관계를 활용할 수 있는 하드웨어와 공동 설계될 때 상당한 성능 잠재력을 unlocked 한다고 주장합니다. 이 연구는 그래프 기반 비전 모델을 위한 향후 하드웨어 - 알고리즘 공동 설계를 고무하며, 구성과 합성곱을 분리함으로써 ViG 의 적응형 이웃 혜택을 희생하지 않으면서도 효율적이고 지연 시간이 짧은 추론을 가능하게 함을 보여줍니다.