Lecture d’article｜HM-ANN: Quand ANNS rencontre la mémoire hétérogène
HM-ANN : recherche efficace du plus proche voisin parmi des milliards de points sur mémoire hétérogène est un article de recherche qui a été accepté à la conférence 2020 sur les systèmes de traitement de l'information neuronale (NeurIPS 2020). Dans cet article, un nouvel algorithme de recherche de similarité fondée sur les graphes, appelé HM-ANN, est proposé. Cet algorithme prend en compte à la fois l’hétérogénéité de la mémoire et l’hétérogénéité des données dans un environnement matériel moderne. HM-ANN permet une recherche de similarité à l’échelle du milliard sur une seule machine sans technologies de compression. La mémoire hétérogène (HM) représente la combinaison d’une mémoire vive dynamique (DRAM) rapide mais de petite taille et d’une mémoire persistante (PMem) lente mais de grande capacité. HM-ANN atteint une faible latence de recherche et une grande précision de recherche, en particulier lorsque le jeu de données ne peut pas tenir dans la DRAM. L’algorithme présente un avantage distinct par rapport aux solutions de recherche approximative du plus proche voisin (ANN) de pointe.
Motivation
Depuis leur apparition, les algorithmes de recherche ANN posent un compromis fondamental entre la précision des requêtes et la latence des requêtes en raison de la capacité limitée de la DRAM. Pour stocker les index dans la DRAM afin d’obtenir un accès rapide aux requêtes, il est nécessaire de limiter le nombre de points de données ou de stocker des vecteurs compressés, deux approches qui nuisent à la précision de la recherche. Les index fondés sur les graphes (par exemple Hierarchical Navigable Small World, HNSW) offrent des performances d’exécution des requêtes et une précision des requêtes supérieures. Toutefois, ces index peuvent également consommer de la DRAM à l’échelle de 1 Tio lorsqu’ils opèrent sur des jeux de données à l’échelle du milliard.
Il existe d’autres solutions de contournement pour éviter de laisser la DRAM stocker des jeux de données à l’échelle du milliard au format brut. Lorsqu’un jeu de données est trop volumineux pour tenir en mémoire sur une seule machine, des approches compressées telles que la quantification de produit des points du jeu de données sont utilisées. Mais le rappel de ces index avec le jeu de données compressé est normalement faible en raison de la perte de précision lors de la quantification. Subramanya et al. [1] explorent l’utilisation d’un disque SSD (solid-state drive) pour réaliser une recherche ANN à l’échelle du milliard à l’aide d’une seule machine avec une approche appelée Disk-ANN, où le jeu de données brut est stocké sur SSD et la représentation compressée dans la DRAM.
Introduction à la mémoire hétérogène
Nom de l’imageHiérarchie mémoire/stockage avec HMxx
Nom de l’imageHiérarchie mémoire/stockage avec HMxx
Source : http://nvmw.ucsd.edu/nvmw2021-program/nvmw2021-data/nvmw2021-paper63-presentation_slides.pdf
La mémoire hétérogène (HM) représente la combinaison d’une DRAM rapide mais de petite taille et d’une PMem lente mais de grande capacité. La DRAM est un matériel courant que l’on trouve dans tous les serveurs modernes, et son accès est relativement rapide. Les nouvelles technologies PMem, telles que les modules de mémoire persistante Intel® Optane™ DC, comblent l’écart entre la mémoire flash basée sur NAND (SSD) et la DRAM, éliminant le goulot d’étranglement des E/S. La PMem est durable comme un SSD, et directement adressable par le CPU, comme la mémoire. Renen et al. [2] découvrent que la bande passante de lecture de la PMem est 2,6× inférieure, et la bande passante d’écriture 7,5× inférieure, à celles de la DRAM dans l’environnement expérimental configuré.
Conception de HM-ANN
HM-ANN est un algorithme de recherche ANN précis et rapide à l’échelle du milliard qui s’exécute sur une seule machine sans compression. La conception de HM-ANN généralise l’idée de HNSW, dont la structure hiérarchique s’intègre naturellement à la HM. HNSW se compose de plusieurs couches : seule la couche 0 contient l’ensemble du jeu de données, et chaque couche restante contient un sous-ensemble d’éléments de la couche située directement en dessous.
Un exemple de HNSW avec 3 couches
Source : https://arxiv.org/pdf/1603.09320.pdf
- Les éléments des couches supérieures, qui n’incluent que des sous-ensembles du jeu de données, consomment une petite partie de l’ensemble du stockage. Cette observation en fait de bons candidats pour être placés en DRAM. Ainsi, la majorité des recherches sur HM-ANN devraient se produire dans les couches supérieures, ce qui maximise l’utilisation de la caractéristique d’accès rapide de la DRAM. Cependant, dans le cas de HNSW, la plupart des recherches se produisent dans la couche inférieure.
- La couche la plus basse contient l’ensemble du jeu de données, ce qui la rend adaptée à un placement en PMem. Étant donné que l’accès à la couche 0 est plus lent, il est préférable que seule une petite partie soit consultée par chaque requête et que la fréquence d’accès soit réduite.
Algorithme de construction du graphe
Un exemple de construction de graphe de HM-ANN
Source : http://nvmw.ucsd.edu/nvmw2021-program/nvmw2021-data/nvmw2021-paper63-poster.pdf
L’idée clé de la construction de HM-ANN est de créer des couches supérieures de haute qualité, afin de fournir une meilleure navigation pour la recherche dans la couche 0. Ainsi, la plupart des accès mémoire se produisent en DRAM, et l’accès en PMem est réduit. Pour rendre cela possible, l’algorithme de construction de HM-ANN comporte une phase d’insertion descendante et une phase de promotion ascendante.
La phase d’insertion descendante construit un graphe de petit monde navigable, tandis que la couche la plus basse est placée sur la PMem.
La phase de promotion ascendante promeut des points pivots depuis la couche inférieure afin de former des couches supérieures placées en DRAM sans perdre beaucoup de précision. Si une projection de haute qualité des éléments de la couche 0 est créée dans la couche 1, la recherche dans la couche 0 trouve les plus proches voisins précis de la requête avec seulement quelques sauts.
- Au lieu d’utiliser la sélection aléatoire de HNSW pour la promotion, HM-ANN utilise une stratégie de promotion à haut degré pour promouvoir les éléments ayant le degré le plus élevé dans la couche 0 vers la couche 1. Pour les couches supérieures, HM-ANN promeut les nœuds à haut degré vers la couche supérieure en fonction d’un taux de promotion.
- HM-ANN promeut davantage de nœuds de la couche 0 vers la couche 1 et définit un nombre maximal de voisins plus élevé pour chaque élément dans la couche 1. Le nombre de nœuds dans les couches supérieures est déterminé par l’espace DRAM disponible. Comme la couche 0 n’est pas stockée en DRAM, rendre chaque couche stockée en DRAM plus dense augmente la qualité de la recherche.
Algorithme de recherche du graphe
Un exemple de recherche de graphe de HM-ANN
Source : http://nvmw.ucsd.edu/nvmw2021-program/nvmw2021-data/nvmw2021-paper63-poster.pdf
L’algorithme de recherche se compose de deux phases : recherche en mémoire rapide et recherche parallèle dans la couche 0 avec préchargement.
Recherche en mémoire rapide
Comme dans HNSW, la recherche en DRAM commence au point d’entrée dans la couche la plus élevée, puis effectue une recherche 1-greedy du haut vers la couche 2. Pour réduire l’espace de recherche dans la couche 0, HM-ANN effectue la recherche dans la couche 1 avec un budget de recherche avec efSearchL1, qui limite la taille de la liste de candidats dans la couche 1. Ces candidats de la liste sont utilisés comme plusieurs points d’entrée pour la recherche dans la couche 0, afin d’améliorer la qualité de la recherche dans la couche 0. Alors que HNSW n’utilise qu’un seul point d’entrée, l’écart entre la couche 0 et la couche 1 est traité plus spécifiquement dans HM-ANN que les écarts entre deux autres couches quelconques.
Recherche parallèle dans la couche 0 avec préchargement
Dans la couche inférieure, HM-ANN partitionne uniformément les candidats susmentionnés issus de la recherche dans la couche 1 et les considère comme des points d’entrée pour effectuer une recherche 1-greedy parallèle à démarrages multiples avec des threads. Les meilleurs candidats de chaque recherche sont collectés pour trouver les meilleurs candidats. Comme on le sait, descendre de la couche 1 à la couche 0 revient exactement à aller vers la PMem. La recherche parallèle masque la latence de la PMem et exploite au mieux la bande passante mémoire, afin d’améliorer la qualité de la recherche sans augmenter le temps de recherche.
HM-ANN implémente un tampon géré par logiciel dans la DRAM afin de précharger les données depuis la PMem avant que l’accès mémoire ne se produise. Lors de la recherche dans la couche 1, HM-ANN copie de manière asynchrone les éléments voisins de ces candidats dans efSearchL1 ainsi que les connexions des éléments voisins dans la couche 1 depuis la PMem vers le tampon. Lorsque la recherche dans la couche 0 a lieu, une partie des données devant être consultées est déjà préchargée dans la DRAM, ce qui masque la latence d’accès à la PMem et conduit à un temps de requête plus court. Cela correspond à l’objectif de conception de HM-ANN, selon lequel la plupart des accès mémoire se produisent dans la DRAM et les accès mémoire dans la PMem sont réduits.
Évaluation
Dans cet article, une évaluation approfondie est menée. Toutes les expériences sont effectuées sur une machine équipée d’un processeur Intel Xeon Gold 6252 CPU@2.3GHz. Elle utilise de la DDR4 (96GB) comme mémoire rapide et de l’Optane DC PMM (1.5TB) comme mémoire lente. Cinq jeux de données sont évalués : BIGANN, DEEP1B, SIFT1M, DEEP1M et GIST1M. Pour les tests à l’échelle du milliard, les schémas suivants sont inclus : méthodes à l’échelle du milliard basées sur la quantification (IMI+OPQ et L&C), les méthodes sans compression (HNSW et NSG).
Comparaison des algorithmes à l’échelle du milliard
Tableau 1.
Dans le tableau 1, le temps de construction et le stockage de différents index basés sur des graphes sont comparés. HNSW prend le temps de construction le plus court et HM-ANN nécessite 8 % de temps supplémentaire par rapport à HNSW. En termes d’utilisation totale du stockage, les index HM-ANN sont 5 à 13 % plus grands que HSNW, car il promeut davantage de nœuds de la couche 0 vers la couche 1.
Figure 1.
Dans la figure 1, les performances de requête de différents index sont analysées. Les figures 1 (a) et (b) montrent que HM-ANN atteint un rappel top-1 de > 95 % en moins de 1 ms. Les figures 1 (c) et (d) montrent que HM-ANN obtient un rappel top-100 de > 90 % en moins de 4 ms. HM-ANN offre les meilleures performances latence-vs-rappel par rapport à toutes les autres approches.
Comparaison des algorithmes à l’échelle du million
Figure 2.
Dans la figure 2, les performances de requête de différents index sont analysées dans un environnement purement DRAM. HNSW, NSG et HM-ANN sont évalués avec les trois jeux de données à l’échelle du million tenant dans la DRAM. HM-ANN atteint toujours de meilleures performances de requête que HNSW. La raison est que le nombre total de calculs de distance de HM-ANN est inférieur (en moyenne 850/requête) à celui de HNSW (en moyenne 900/requête) pour atteindre un objectif de rappel de 99 %.
Efficacité de la promotion à haut degré
Dans la figure 3, les stratégies de promotion aléatoire et de promotion à haut degré sont comparées dans la même configuration. La promotion à haut degré surpasse la référence. La promotion à haut degré est 1,8x, 4,3x et 3,9x plus rapide que la promotion aléatoire pour atteindre des objectifs de rappel de 95 %, 99 % et 99,5 %, respectivement.
Gain de performance des techniques de gestion de la mémoire
La figure 5 contient une série d’étapes entre HNSW et HM-ANN pour montrer comment chaque optimisation de HM-ANN contribue à ses améliorations. BP signifie Bottom-up Promotion lors de la construction de l’index. PL0 représente Parallel layer-0 search, tandis que DP désigne le préchargement des données depuis la PMem vers la DRAM. Étape par étape, les performances de recherche de HM-ANN sont encore améliorées.
Conclusion
Un nouvel algorithme d’indexation et de recherche basé sur des graphes, appelé HM-ANN, fait correspondre la conception hiérarchique des ANN basés sur des graphes avec l’hétérogénéité de la mémoire dans HM. Les évaluations montrent que HM-ANN appartient aux nouveaux index à l’état de l’art pour les jeux de données comportant un milliard de points.
Nous observons une tendance dans le monde académique ainsi que dans l’industrie, où l’accent est mis sur la construction d’index sur des dispositifs de stockage persistants. Pour alléger la pression sur la DRAM, Disk-ANN [1] est un index construit sur SSD, dont le débit est nettement inférieur à celui de la PMem. Cependant, la construction de HM-ANN prend encore quelques jours, sans qu’une grande différence par rapport à Disk-ANN soit établie. Nous pensons qu’il est possible d’optimiser le temps de construction de HM-ANN, lorsque nous utilisons plus soigneusement les caractéristiques de la PMem, par exemple en tenant compte de la granularité de la PMem (256 octets) et en utilisant des instructions de streaming pour contourner les lignes de cache. Nous pensons également que davantage d’approches avec des dispositifs de stockage durables seront proposées à l’avenir.
Référence
[1]: Suhas Jayaram Subramanya and Devvrit and Rohan Kadekodi and Ravishankar Krishaswamy and Ravishankar Krishaswamy: DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node, NIPS, 2019
DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node - Microsoft Research
DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node
[2]: Alexander van Renen and Lukas Vogel and Viktor Leis and Thomas Neumann and Alfons Kemper: Persistent Memory I/O Primitives, CoRR & DaMoN, 2019
Continuer à lire
Why We Built Vector Lakebase: Rethinking Unstructured Data Architecture for AI
Vector Lakebase: a unified, lake-native data foundation for AI workloads — and an answer to what happens after vector databases succeed.
Why Context Engineering Is Becoming the Full Stack of AI Agents
Discover how context engineering unifies prompts, RAG, and tools to build smarter, production-ready AI agents powered by Milvus.
Democratizing AI: Making Vector Search Powerful and Affordable
Zilliz democratizes AI vector search with Milvus 2.6 and Zilliz Cloud for powerful, affordable scalability, cutting costs in infrastructure, operations, and development.