Flash-KMeansが登場: GPUでFAISSより200倍速いK-Means

k-meansは数十年にわたりオフラインツールとして使用されてきました。データを前処理するために一度実行し、その後は別の作業に移ります。しかし、UCバークレーとUTオースティンの研究チームは、異なる設定をターゲットにした新しいオープンソースライブラリ、Flash-KMeansを発表しました。現代のAIパイプラインでは、トレーニングや推論ループの中でk-meansを呼び出すことが増えています。この頻度では、呼び出しごとの遅延が理論的な計算速度よりも重要です。Flash-KMeansは、標準的なLloydのk-meansのIO（入出力）を意識した実装です。数学を変更せず、近似も行いません。アルゴリズムがGPU上でデータを移動する方法を再構築するだけです。NVIDIA H200上で、研究チームは最高で17.9倍のエンドツーエンドの速度向上を報告しました。NVIDIA cuMLに対しては33倍、FAISSに対しては200倍以上の速度向上が見られました。Flash-KMeansは、Triton GPUカーネルで書かれたバッチ処理のk-meansライブラリです。Apache 2.0の下で提供され、pip install flash-kmeansでインストールできます。出力は数学的に標準的なLloydのk-meansと同じです。速度向上はカーネルレベルのデータフローから生じており、作業を省略することからではありません。これは、三角不等式プルーニングやコアセットサンプリングのようなアルゴリズム的手法とは異なります。標準のLloyd反復には2つのステージがあります。割り当てステージでは、各ポイントの重心までの距離を計算し、最も近いものを選びます。更新ステージでは、各クラスター内のポイントを平均して新しい重心を形成します。両方のステージは単純な算術です。GPU上では、両方のステージが計算ではなくメモリによってボトルネックになります。彼らが攻撃する2つのボトルネックのうち、最初のボトルネックは割り当てステージです。標準のコードは、形状N×Kの完全距離行列Dを高帯域幅メモリ（HBM）に構築します。行列を書き込み、その後argminを実行するために読み戻します。N=65536、K=1024、d=128、B=32の場合、距離計算には2.6msかかります。Dの書き込みと消費には約23msかかります。行列がコストであり、算術計算ではありません。Flash-KMeansはこれをFlashAssignで置き換えます。この設計はFlashAttentionから借用しています。FlashAssignは、HBMからオンチップSRにポイントと重心のタイルをストリーミングします。