[Paper] BLEST: Tensor Cores를 사용한 번개처럼 효율적인 BFS

Source: arXiv - 2512.21967v1

개요

이 논문은 BLEST라는 새로운 프레임워크를 소개합니다. 이 프레임워크는 NVIDIA의 Tensor Cores—원래 고밀도 행렬‑곱‑누적(MMA) 연산을 위해 설계된 하드웨어—를 활용하여 고전적인 Breadth‑First Search (BFS) 그래프 커널을 가속화합니다. BFS 파이프라인을 재구성하고 에지‑레벨 작업을 Tensor Cores의 비트 연산 능력에 정교하게 매핑함으로써, 저자들은 다양한 실제 그래프에서 최신 GPU BFS 라이브러리 대비 최대 5× speed‑up을 달성했습니다.

주요 기여

• 비트맵 기반 풀 기반 BFS: 컴팩트한 비트맵 프론티어를 사용해 BFS를 재구성함으로써 효율적인 워프 수준 병렬성을 가능하게 함.
• 이진화 가상 슬라이스 집합 (BVSS): 워프 수준에서 작업을 할당하는 로드 밸런싱 스킴으로, 프론티어와 무관한(즉, 불필요한) 작업을 제거함.
• 그래프 재배열 휴리스틱:
  • 압축 지향 순서는 소셜 네트워크와 같은 그래프(높은 지역성, 많은 소규모 차수 정점)에 적용.
  • 대역폭 감소 순서는 이질적이며 비소셜 그래프에 적용.
• 텐서 코어에서 배치된 SpMSpV: 비트 연산 텐서 코어 타일을 활용하는 희소 행렬‑희소 벡터 곱셈 패턴을 구현하여 MMA 호출 횟수를 크게 줄임.
• 커널 융합 + 지연 정점 업데이트: 여러 BFS 단계를 하나의 커널로 병합하고 정점 업데이트를 필요할 때까지 미루어 호스트‑GPU 동기화와 원자 연산 경쟁을 감소시킴.

Source: …

Methodology

1. Pull‑based BFS with bitmap frontier – 전통적인 푸시 모델(현재 프론티어에서 확장) 대신, BLEST는 모든 정점을 스캔하고 활성 프론티어 노드를 표시하는 비트맵을 확인함으로써 “풀” 방식으로 동작합니다. 이 표현은 비트 연산에 자연스럽게 적합합니다.

2. Warp‑level work slicing (BVSS) – 각 정점의 인접 리스트를 가상 슬라이스로 나누고, 각 워프는 활성 엣지 수가 대략 동일한 슬라이스를 처리하여 스레드 간 발산 없이 균형 잡힌 실행을 보장합니다.

3. Graph reordering –

   • Compression‑oriented: 고차수 노드들을 함께 클러스터하도록 정점을 재배열하여 비트맵의 밀도를 높이고 Tensor Core에서 더 나은 압축을 가능하게 합니다.
   • Bandwidth‑reducing: 클래식한 reverse‑Cuthill‑McKee 방식의 순서를 적용해 엣지‑컷 대역폭을 최소화함으로써 비정형 그래프에서 메모리 코얼레싱을 향상시킵니다.

4. Batched SpMSpV on Tensor Cores – 핵심 연산은 희소 인접 행렬 슬라이스와 프론티어 비트맵 사이의 일련의 비트 연산 도트‑프로덕트로 표현됩니다. 각 도트‑프로덕트는 TC 타일(예: 8×8 bits)에 매핑되어 단일 MMA 명령으로 실행되며, 그렇지 않으면 발생할 제로‑채워진 출력 항목 생성을 방지해 사이클을 절약합니다.

5. Kernel fusion & lazy updates – BFS의 “visit”, “update distance”, “frontier generation” 단계가 하나의 커널 실행으로 결합됩니다. 정점 거리 업데이트는 커널 끝까지 지연되어 원자적 쓰기 횟수를 줄이고 L2 캐시 재사용을 개선합니다.

결과 및 발견

• 30개 이상의 실제 그래프(소셜 네트워크, 웹 크롤링, 도로 지도, 합성 RMAT)에서 BLEST는 일관되게 베이스라인을 능가했으며, 재정렬 후 높은 차수 변동성을 보이는 그래프에서는 최대 6배 이상의 향상을 기록했습니다.
• 메모리 사용량은 비트맵 프론티어와 압축 지향 정렬 덕분에 약 30 % 감소했습니다.
• 커널 실행 오버헤드는 융합 전략으로 인해 약 45 % 감소했으며, 이로 인해 BFS 레벨당 호스트‑디바이스 동기화 횟수도 줄어들었습니다.

Practical Implications

• Faster graph analytics pipelines – Applications that repeatedly run BFS (e.g., shortest‑path, community detection, reachability queries) can see near‑linear reductions in runtime on modern NVIDIA GPUs equipped with Tensor Cores (e.g., A100, H100).
• Cost‑effective scaling – By extracting more performance per GPU, data‑center operators can handle larger graphs on fewer nodes, translating to lower electricity and hardware costs.
• Reusable primitives – The batched SpMSpV pattern and BVSS load‑balancing logic are generic enough to be adapted for other sparse linear algebra kernels (e.g., PageRank, label propagation) that also suffer from irregular memory access patterns.
• Integration path – Since BLEST builds on existing CUDA APIs (warp‑level primitives, __nv_bfloat16‑based MMA), it can be incorporated into existing graph libraries (Gunrock, cuGraph) as an optional “TC‑accelerated” backend without a complete rewrite.

제한 사항 및 향후 연구

• 하드웨어 의존성 – BLEST의 성능 향상은 고속 Tensor Core가 있는 경우에만 적용됩니다. 구형 GPU나 NVIDIA가 아닌 가속기는 이점을 얻을 수 없습니다.
• 재정렬 오버헤드 – 그래프 재정렬 단계는 전처리 비용을 추가하며, 이는 스트리밍이나 동적으로 변하는 그래프에서는 무시할 수 없을 정도가 될 수 있습니다.
• 희소 행렬 밀도 요구 – 평균 차수가 매우 낮은 극히 희소한 그래프는 비트 연산 TC 타일이 충분히 활용되지 않아 속도 향상이 제한적입니다.
• 향후 방향은 저자들이 제시한 바와 같이: 다중 GPU 클러스터로 접근 방식을 확장하고, 변화하는 그래프에 대해 실시간으로 업데이트되는 적응형 재정렬을 탐구하며, 가중치 엣지와 기타 세미링을 지원하도록 SpMSpV‑TC 파이프라인을 일반화하는 것을 포함합니다.

저자

• Deniz Elbek
• Kamer Kaya

논문 정보

• arXiv ID: 2512.21967v1
• Categories: cs.DC, cs.DS
• Published: December 26, 2025
• PDF: PDF 다운로드