AI GPU Algorithms Performance

Flash-KMeans - GPU 加速精确 K-Means

⭐⭐⭐⭐⭐ (5星)

摘要

MIT/Stanford 研究团队提出 Flash-KMeans，GPU 上精确 K-Means 的高效实现。现有的 GPU K-Means 实现受限于底层系统约束而非理论算法复杂度。

问题分析

Assignment 阶段瓶颈

严重的 IO 瓶颈：大量显式物化 N × K 距离矩阵在高带宽内存 (HBM) 中

Centroid Update 阶段瓶颈

硬件级原子写竞争：由于不规则的 scatter-style token 聚合导致

核心创新

1. FlashAssign

• 融合距离计算与在线 argmin
• 完全绕过中间内存物化
• 避免显式距离矩阵存储

2. Sort-Inverse Update

• 显式构建逆映射
• 将高竞争原子 scatters 转换为高带宽、分段局部归约
• 消除写竞争

3. Algorithm-System Co-Design

• Chunked-stream overlap: 分块流重叠
• Cache-aware compile heuristics: 缓存感知编译启发式

评估

NVIDIA H200 GPU 评估结果：

• 端到端加速 17.9x vs 最佳基线
• 相比 cuML 加速 33x
• 相比 FAISS 加速 200x+

URL

来源: Hacker News | 发现日期: 2026-03-20