Découvrez Flash-KMeans : un algorithme K-Means précis et optimisé pour les E/S, qui s'exécute plus de 200 fois plus vite que FAISS sur les GPU

Découvrez Flash-KMeans : un algorithme K-Means précis et optimisé pour les E/S, qui s’exécute plus de 200 fois plus vite que FAISS sur les GPU

par

Un acteur majeur du secteur vient de faire parler de lui.

Découvrez Flash-KMeans : un algorithme K-Means précis et optimisé pour les E/S, qui s’exécute plus de 200 fois plus vite que FAISS sur les GPU

Depuis des décennies, l’algorithme k-means est un outil utilisé hors ligne. On le lance une seule fois pour prétraiter les données, puis on passe à autre chose. Une équipe de chercheurs de l’université de Berkeley et de l’université du Texas à Austin a publié Flash-KMeans, une nouvelle bibliothèque open source conçue pour un autre type d’utilisation. Les pipelines d’IA modernes intègrent désormais l’algorithme k-means dans leurs boucles d’entraînement et d’inférence. À cette fréquence, la latence par appel est plus importante que le nombre théorique de FLOP.

Flash-KMeans est une implémentation du k-means standard de Lloyd tenant compte des opérations d’E/S. Elle ne modifie pas les calculs mathématiques et ne recourt pas à des approximations. Elle se contente de réorganiser la manière dont l’algorithme transfère les données sur un GPU. Sur une carte NVIDIA H200, l’équipe de recherche a rapporté un gain de vitesse de bout en bout pouvant atteindre 17,9 fois par rapport à la meilleure référence. Par rapport à NVIDIA cuML, elle fait état d’un gain de 33 fois. Par rapport à FAISS, elle fait état d’un gain de plus de 200 fois.

Parallèlement, flash-KMeans est une bibliothèque k-means par lots écrite en langages de noyaux GPU Triton. Elle est distribuée sous licence Apache 2.0 et s’installe à l’aide de la commande `pip install flash-kmeans`.

Le résultat est mathématiquement identique à celui de l’algorithme k-means standard de Lloyd. Le gain de vitesse provient du flux de données au niveau du noyau, et non d’une omission de calculs. C’est ce qui le distingue des méthodes algorithmiques telles que l’élagage par inégalité triangulaire ou l’échantillonnage par ensembles de cœurs.

Une itération de Lloyd classique comporte deux étapes. L’étape d’affectation calcule la distance de chaque point par rapport à chaque centroïde, puis sélectionne le plus proche. L’étape de mise à jour calcule la moyenne des points de chaque grappe pour former de nouveaux centroïdes. Ces deux étapes relèvent d’opérations arithmétiques simples. Sur les GPU, ce sont les capacités de mémoire, et non la puissance de calcul, qui constituent le goulot d’étranglement.

Le premier goulot d’étranglement se situe au niveau de la phase d’affectation. Le code standard construit une matrice de distances complète D de dimension N×K dans la mémoire à large bande passante (HBM). Il écrit la matrice, puis la relit pour exécuter argmin. Pour N=65536, K=1024, d=128, B=32, le calcul des distances prend 2,6 ms. L’écriture et la lecture de D prennent environ 23 ms. C’est la matrice qui représente le coût, et non le calcul arithmétique.

Flash-KMeans remplace cette approche par FlashAssign. Sa conception s’inspire de FlashAttention. FlashAssign transfère en continu des blocs de points et de centroïdes depuis la mémoire HBM vers la SRAM intégrée au circuit. Il combine le calcul des distances avec un argmin en ligne. La matrice N×K complète n’est jamais matérialisée. Cela réduit la complexité d’E/S dominante de O(NK) à O(Nd + Kd). Au niveau du noyau, FlashAssign atteint un gain pouvant aller jusqu’à 21,2 fois. Dans un cas précis, il a permis de réduire le temps d’affectation de 122,5 ms à 5,8 ms.

Le deuxième goulot d’étranglement se situe au niveau de la mise à jour du centroïde. Le code standard utilise des additions atomiques de type « scatter ». Chaque thread ajoute son point dans un tampon de somme partagé, indexé par l’identifiant du cluster. De nombreux threads accèdent simultanément au même cluster « grandement sollicité ». Cela entraîne des conflits d’accès atomiques et une sérialisation matérielle. L’équipe de recherche n’a mesuré ici qu’une bande passante effective de 50 Go/s sur un H200.

En quelques mots :

  • L’écriture et la lecture de D prennent environ 23 ms.
  • Au niveau du noyau, FlashAssign atteint un gain pouvant aller jusqu’à 21,2 fois.
  • Le code standard utilise des additions atomiques de type « scatter ».

Les prochaines semaines permettront d’en mesurer la portée réelle.

Pour aller plus loin :

Source originale : MarkTechPost : MarkTechPost