svg-project/flash-kmeans

해결하는 문제

Flash-KMeans는 K-Means 클러스터링 알고리즘의 고성능 및 메모리 효율적인 구현을 제공합니다. GPU에서 대규모 데이터셋(대규모 N) 또는 고차원 데이터(대규모 D)를 처리할 때 흔히 발생하는 메모리 부족(OOM) 오류와 느린 계산 속도 문제를 해결하며, 큰 거리 행렬을 생성하지 않아 메모리 사용을 최소화합니다.

작동 방식

이 프로젝트는 Triton GPU 커널을 사용하여 IO에 민감한 배치 처리 K-Means를 구현합니다. 데이터 차원에 따라 두 가지 주요 실행 경로를 사용합니다:

• 작은-D 경로: 차원 수가 $\le 512$인 경우에 최적화되며, H200, H100, A100, GB10 등의 특정 GPU 아키텍처에 맞춰 수동으로 튜닝된 휴리스틱을 사용합니다.
• Split-D 경로: 차원 수가 $> 512$이거나 공유 메모리가 제한된 경우 사용되며, 차원 루프를 타일링하여 K-스트리밍 성질을 유지합니다.

단일 GPU에 수용할 수 없는 데이터셋의 경우, CPU에서 GPU로 데이터를 청크 단위로 전송하는 이중 버퍼링 스트리밍 설계를 구현합니다. 또한 데이터를 GPU 간에 분할하고, 중심점 업데이트를 위해 가벼운 수동 gather-reduce-broadcast 메커니즘을 사용하여 NCCL 종속성을 피하면서 멀티 GPU 확장도 지원합니다.

대상 사용자

대규모 클러스터링 작업을 수행하는 연구자 및 개발자에게 특별히 설계되었습니다. 특히 Sparse VideoGen2와 같은 시스템을 구현하는 사람이나, 여러 GPU에 걸쳐 확장 가능한 빠르고 정확한 K-Means 구현이 필요한 사용자에게 적합합니다.

주요 특징

• Triton 기반 가속: 표준 PyTorch 및 기타 Triton 구현보다 뚜렷한 성능 향상.
• 메모리 효율성: 전체 거리 행렬 생성을 피함으로써 OOM을 방지.
• 자동 디스패치: 입력 형태와 dtype에 따라 Small-D 및 Split-D 커널 간 자동 전환.
• 멀티 GPU 확장성: PCIe 대역폭의 선형 확장 및 H2D 전송과 중심점 감소의 겹침.
• 광범위한 하드웨어 지원: 최신 NVIDIA GPU용 튜닝된 설정을 포함하며, 알 수 없는 아키텍처에 대해 보수적인 백업을 제공합니다.