[논문] TC-MIS: Tensor 코어에서의 최대 독립 집합

Source: arXiv - 2605.29604v1

개요

논문 **“TC-MIS: Maximal Independent Set on Tensor‑cores”**는 최신 NVIDIA GPU에 탑재된 고처리량 Tensor Cores(TCs)를 고전적인 그래프 문제인 Maximal Independent Set(MIS) 계산에 재활용하는 방법을 보여준다. 알고리즘을 Tensor Core의 matrix‑multiply‑accumulate(WMMA) 모델에 맞는 일련의 sparse matrix‑vector multiplications (SpMV) 로 재구성함으로써, 저자들은 기존 GPU‑기반 MIS 솔버에 비해 해결 품질을 유지하면서도 dramatic speedups를 달성한다.

주요 기여

• TC‑centric 재구성: 핵심 MIS 연산을 텐서 코어의 WMMA로 실행 가능한 타일형 SpMV 커널로 변환하여, 불규칙한 그래프 탐색을 규칙적이고 밀집형 연산으로 전환합니다.
• Warp‑level 타일링 전략: 워프‑매트릭스 타일링 방식을 도입해 워프 간 부하를 균형 있게 배분하고, 매우 희소한 인접 행렬에서도 TC 점유율을 최대화합니다.
• 포괄적인 성능 평가: 네 세대의 텐서‑코어 GPU(Ampere, Ada Lovelace, Hopper, Blackwell)에서 TC‑MIS를 벤치마크하고, 기존 최고 GPU MIS 구현 대비 최대 44.38× 속도 향상을 보고합니다.
• 솔루션 품질 보존: TC 가속 휴리스틱이 최신 CPU/GPU 휴리스틱이 만든 독립 집합과 크기 면에서 동등함을 입증합니다.
• 오픈‑소스 레퍼런스 구현: 기존 그래프‑처리 파이프라인에 통합할 수 있는 CUDA 코드베이스( WMMA 커널 포함)를 제공합니다.

방법론

1. Graph → Sparse Matrix: 입력 그래프는 인접 행렬 A (크기 n × n) 로 표현됩니다.
2. MIS as SpMV: 고전적인 병렬 MIS 알고리즘은 후보 정점을 반복적으로 선택하고, 그들의 이웃을 제거하며, “status” 벡터 x 를 업데이트합니다. 각 반복은 x ← x ⊙ (1 – A·x) 로 표현될 수 있으며, 여기서 “·”는 희소 행렬‑벡터 곱셈, “⊙”는 원소별 곱셈을 의미합니다.
3. Tiling for Tensor Cores:
   • 인접 행렬을 16×16 타일(네이티브 WMMA 타일 크기) 로 분할합니다.
   • 각 워프는 타일을 공유 메모리로 로드하고, 현재 status 벡터와 함께 WMMA 기반 곱‑누적 연산을 수행한 뒤 부분 결과를 기록합니다.
   • 희소 타일 메타데이터(행/열 오프셋)는 비제로 타일만 처리하도록 보장하여 불필요한 작업을 방지합니다.
4. Load‑balancing: 동적 작업 큐가 타일을 실시간으로 워프에 할당하여 그래프 알고리즘에서 흔히 발생하는 작업 부하 불균형을 완화합니다.
5. Iterative convergence: 독립 집합에 더 이상 정점을 추가할 수 없을 때까지 과정을 반복하며, 실제 그래프에서는 보통 몇 번의 반복만에 수렴합니다.

전체 파이프라인은 CUDA 프로그래밍 모델 내에서 유지되며, 기존 GPU MIS 코드베이스에 약간의 수정만 필요합니다.

결과 및 발견

• 처리량: 대규모 합성 및 실제 그래프(최대 1억 정점, 10억 엣지)를 Hopper‑클래스 GPU에서 초단위 이하 지연 시간으로 처리했습니다.
• 품질: TC‑MIS가 생성한 MIS 크기는 최고의 휴리스틱 베이스라인과 1 % 미만의 차이만을 보였으며, 가속이 솔루션 최적성을 희생하지 않음을 확인했습니다.
• 확장성: 그래프 밀도가 높아질수록 더 많은 타일이 비제로가 되어 TC의 행렬 처리량을 더 잘 활용함에 따라 성능 향상이 증가했습니다.

Source: …

실용적 함의

• ML 파이프라인을 위한 더 빠른 전처리: 많은 그래프 기반 ML 모델(예: GNN)에서는 MIS 또는 관련 샘플링 단계가 필요합니다; TC‑MIS는 이러한 병목 현상을 크게 줄일 수 있습니다.
• 실시간 자원 할당: 무선 채널 할당, 작업 스케줄링, 혹은 충돌 없는 메모리 할당과 같은 애플리케이션이 이제 일반 GPU에서 거의 실시간에 가까운 MIS 기반 휴리스틱을 실행할 수 있습니다.
• Tensor‑Core GPU에서 새로운 그래프 워크로드 활성화: 개발자는 기존 WMMA 커널(원래 딥러닝용으로 작성된)을 그래프 분석에 재사용할 수 있어 CUDA 코어와 Tensor Core를 위한 별도 코드 경로를 유지할 필요가 줄어듭니다.
• 비용 효율적인 확장: Tensor Core는 더 높은 FLOP/Watt를 제공하므로 클라우드 제공자는 그래프 중심 워크로드에 대해 성능을 희생하지 않으면서 더 저렴한 GPU 인스턴스를 제공할 수 있습니다.

Limitations & Future Work

• Sparse‑tile overhead: 매우 희소한 그래프(평균 차수 < 2)의 경우 타일 기반 접근 방식이 추가 메타데이터 처리를 발생시켜 속도 향상이 감소한다.
• Memory footprint: 타일링 및 타일별 오프셋 저장으로 메모리 사용량이 증가하며, 이는 메모리가 제한된 GPU에서 제약이 될 수 있다.
• Algorithmic scope: 현재 공식은 고전적인 그리디 MIS 휴리스틱을 목표로 하며, TC‑centric 설계를 정확한 MIS 솔버나 다른 그래프 문제(예: 최대 매칭, 색칠)로 확장하는 것은 아직 미해결이다.
• Portability: 구현이 WMMA를 사용하는 NVIDIA GPU에서 동작하지만, AMD 또는 Intel GPU와 같이 다른 매트릭스‑가속 프리미티브를 가진 환경에 적용하려면 추가 엔지니어링이 필요하다.

전체적으로, TC‑MIS는 텐서 코어—전통적으로 딥러닝 분야에서 사용되던—를 활용하여 불규칙 그래프 알고리즘을 가속화하는 매력적인 새로운 방향을 제시한다. 이는 프로덕션 시스템에서 더 빠르고 에너지 효율적인 그래프 분석을 가능하게 한다.

저자

• Prajjwal Nijhara
• Dip Sankar Banerjee

논문 정보

• arXiv ID: 2605.29604v1
• Categories: cs.DC, cs.DS, cs.PF
• Published: 2026년 5월 28일
• PDF: PDF 다운로드