Lectura de artículos｜HM-ANN: Cuando ANNS se encuentra con la memoria heterogénea
HM-ANN: Búsqueda eficiente de vecinos más cercanos entre mil millones de puntos en memoria heterogénea es un artículo de investigación que fue aceptado en la Conferencia de 2020 sobre Sistemas de Procesamiento de Información Neural (NeurIPS 2020). En este artículo, se propone un algoritmo novedoso para la búsqueda de similitud basada en grafos, llamado HM-ANN. Este algoritmo considera tanto la heterogeneidad de memoria como la heterogeneidad de datos en un entorno de hardware moderno. HM-ANN permite la búsqueda de similitud a escala de miles de millones en una sola máquina sin tecnologías de compresión. La memoria heterogénea (HM) representa la combinación de memoria dinámica de acceso aleatorio (DRAM) rápida pero pequeña y memoria persistente (PMem) lenta pero grande. HM-ANN logra una baja latencia de búsqueda y una alta precisión de búsqueda, especialmente cuando el conjunto de datos no cabe en DRAM. El algoritmo tiene una ventaja clara sobre las soluciones de búsqueda de vecinos más cercanos aproximados (ANN) de última generación.
Motivación
Desde sus inicios, los algoritmos de búsqueda ANN han planteado un compromiso fundamental entre la precisión de las consultas y la latencia de las consultas debido a la capacidad limitada de DRAM. Para almacenar índices en DRAM y lograr un acceso rápido a las consultas, es necesario limitar el número de puntos de datos o almacenar vectores comprimidos, lo cual perjudica la precisión de la búsqueda. Los índices basados en grafos (por ejemplo, Hierarchical Navigable Small World, HNSW) tienen un rendimiento superior en tiempo de ejecución de consultas y precisión de consultas. Sin embargo, estos índices también pueden consumir DRAM a nivel de 1 TiB cuando operan en conjuntos de datos a escala de miles de millones.
Existen otras soluciones alternativas para evitar que DRAM almacene conjuntos de datos a escala de miles de millones en formato sin procesar. Cuando un conjunto de datos es demasiado grande para caber en la memoria de una sola máquina, se utilizan enfoques comprimidos como la cuantización de producto de los puntos del conjunto de datos. Pero la recuperación de esos índices con el conjunto de datos comprimido normalmente es baja debido a la pérdida de precisión durante la cuantización. Subramanya et al. [1] exploran el aprovechamiento de una unidad de estado sólido (SSD) para lograr una búsqueda ANN a escala de miles de millones usando una sola máquina con un enfoque llamado Disk-ANN, donde el conjunto de datos sin procesar se almacena en SSD y la representación comprimida en DRAM.
Introducción a la memoria heterogénea
Nombre de la imagenJerarquía de memoria/almacenamiento con HMxx
Nombre de la imagenJerarquía de memoria/almacenamiento con HMxx
Fuente: http://nvmw.ucsd.edu/nvmw2021-program/nvmw2021-data/nvmw2021-paper63-presentation_slides.pdf
La memoria heterogénea (HM) representa la combinación de DRAM rápida pero pequeña y PMem lenta pero grande. DRAM es hardware normal que se puede encontrar en todos los servidores modernos, y su acceso es relativamente rápido. Las nuevas tecnologías PMem, como Intel® Optane™ DC Persistent Memory Modules, cierran la brecha entre la memoria flash basada en NAND (SSD) y DRAM, eliminando el cuello de botella de E/S. PMem es duradera como SSD y directamente direccionable por la CPU, como la memoria. Renen et al. [2] descubren que el ancho de banda de lectura de PMem es 2,6× menor, y el ancho de banda de escritura 7,5× menor, que DRAM en el entorno experimental configurado.
Diseño de HM-ANN
HM-ANN es un algoritmo de búsqueda ANN preciso y rápido a escala de miles de millones que se ejecuta en una sola máquina sin compresión. El diseño de HM-ANN generaliza la idea de HNSW, cuya estructura jerárquica encaja de forma natural en HM. HNSW consta de múltiples capas: solo la capa 0 contiene todo el conjunto de datos, y cada capa restante contiene un subconjunto de elementos de la capa directamente inferior.
Un ejemplo de HNSW con 3 capas
Fuente: https://arxiv.org/pdf/1603.09320.pdf
- Los elementos en las capas superiores, que incluyen solo subconjuntos del conjunto de datos, consumen una pequeña parte del almacenamiento total. Esta observación los convierte en candidatos adecuados para colocarse en DRAM. De esta manera, se espera que la mayoría de las búsquedas en HM-ANN ocurran en las capas superiores, lo que maximiza la utilización de la característica de acceso rápido de DRAM. Sin embargo, en los casos de HNSW, la mayoría de las búsquedas ocurren en la capa inferior.
- La capa más inferior contiene todo el conjunto de datos, lo que la hace adecuada para colocarse en PMem. Dado que acceder a la capa 0 es más lento, es preferible que cada consulta acceda solo a una pequeña porción y que se reduzca la frecuencia de acceso.
Algoritmo de construcción del grafo
Un ejemplo de construcción del grafo de HM-ANN
Fuente: http://nvmw.ucsd.edu/nvmw2021-program/nvmw2021-data/nvmw2021-paper63-poster.pdf
La idea clave de la construcción de HM-ANN es crear capas superiores de alta calidad, con el fin de proporcionar una mejor navegación para la búsqueda en la capa 0. Así, la mayor parte del acceso a memoria ocurre en DRAM, y se reduce el acceso en PMem. Para hacer esto posible, el algoritmo de construcción de HM-ANN tiene una fase de inserción de arriba hacia abajo y una fase de promoción de abajo hacia arriba.
La fase de inserción de arriba hacia abajo construye un grafo de mundo pequeño navegable a medida que la capa más inferior se coloca en la PMem.
La fase de promoción de abajo hacia arriba promueve puntos pivote desde la capa inferior para formar capas superiores que se colocan en DRAM sin perder mucha precisión. Si se crea una proyección de alta calidad de los elementos de la capa 0 en la capa 1, la búsqueda en la capa 0 encuentra los vecinos más cercanos precisos de la consulta con solo unos pocos saltos.
- En lugar de usar la selección aleatoria de HNSW para la promoción, HM-ANN usa una estrategia de promoción de alto grado para promover elementos con el grado más alto en la capa 0 hacia la capa 1. Para capas superiores, HM-ANN promueve nodos de alto grado a la capa superior en función de una tasa de promoción.
- HM-ANN promueve más nodos de la capa 0 a la capa 1 y establece un mayor número máximo de vecinos para cada elemento en la capa 1. El número de nodos en las capas superiores se decide por el espacio DRAM disponible. Dado que la capa 0 no se almacena en DRAM, hacer que cada capa almacenada en DRAM sea más densa aumenta la calidad de la búsqueda.
Algoritmo de búsqueda del grafo
Un ejemplo de búsqueda del grafo de HM-ANN
Fuente: http://nvmw.ucsd.edu/nvmw2021-program/nvmw2021-data/nvmw2021-paper63-poster.pdf
El algoritmo de búsqueda consta de dos fases: búsqueda en memoria rápida y búsqueda paralela en la capa 0 con prefetching.
Búsqueda en memoria rápida
Al igual que en HNSW, la búsqueda en DRAM comienza en el punto de entrada en la capa más alta y luego realiza una búsqueda 1-greedy desde la capa superior hasta la capa 2. Para reducir el espacio de búsqueda en la capa 0, HM-ANN realiza la búsqueda en la capa 1 con un presupuesto de búsqueda con efSearchL1, que limita el tamaño de la lista de candidatos en la capa 1. Esos candidatos de la lista se usan como múltiples puntos de entrada para la búsqueda en la capa 0, para mejorar la calidad de la búsqueda en la capa 0. Mientras que HNSW usa solo un punto de entrada, la brecha entre la capa 0 y la capa 1 se maneja de manera más especial en HM-ANN que las brechas entre cualquier otro par de capas.
Búsqueda paralela en la capa 0 con prefetching
En la capa inferior, HM-ANN particiona uniformemente los candidatos mencionados anteriormente de la búsqueda en la capa 1 y los considera como puntos de entrada para realizar una búsqueda 1-greedy paralela de múltiples inicios con hilos. Los mejores candidatos de cada búsqueda se recopilan para encontrar los mejores candidatos. Como se sabe, bajar de la capa 1 a la capa 0 es exactamente ir a PMem. La búsqueda paralela oculta la latencia de PMem y aprovecha al máximo el ancho de banda de memoria, para mejorar la calidad de la búsqueda sin aumentar el tiempo de búsqueda.
HM-ANN implementa un búfer gestionado por software en DRAM para precargar datos desde PMem antes de que ocurra el acceso a memoria. Al buscar en la capa 1, HM-ANN copia de forma asíncrona los elementos vecinos de esos candidatos en efSearchL1 y las conexiones de los elementos vecinos en la capa 1 desde PMem al búfer. Cuando ocurre la búsqueda en la capa 0, una parte de los datos que se van a acceder ya está precargada en DRAM, lo que oculta la latencia de acceso a PMem y conduce a un tiempo de consulta más corto. Coincide con el objetivo de diseño de HM-ANN, donde la mayoría de los accesos a memoria ocurren en DRAM y los accesos a memoria en PMem se reducen.
Evaluación
En este artículo, se lleva a cabo una evaluación exhaustiva. Todos los experimentos se realizan en una máquina con CPU Intel Xeon Gold 6252@2.3GHz. Usa DDR4 (96GB) como memoria rápida y Optane DC PMM (1.5TB) como memoria lenta. Se evalúan cinco conjuntos de datos: BIGANN, DEEP1B, SIFT1M, DEEP1M y GIST1M. Para pruebas a escala de miles de millones, se incluyen los siguientes esquemas: métodos basados en cuantización a escala de miles de millones (IMI+OPQ y L&C), los métodos sin compresión (HNSW y NSG).
Comparación de algoritmos a escala de miles de millones
Tabla 1.
En la tabla 1, se comparan el tiempo de construcción y el almacenamiento de diferentes índices basados en grafos. HNSW toma el menor tiempo de construcción y HM-ANN necesita un 8% más de tiempo que HNSW. En términos de uso total de almacenamiento, los índices HM-ANN son un 5–13% más grandes que HSNW, porque promueve más nodos de la capa 0 a la capa 1.
Figura 1.
En la Figura 1, se analiza el rendimiento de consulta de diferentes índices. La Figura 1 (a) y (b) muestran que HM-ANN logra un recall top-1 de > 95% en menos de 1ms. Las Figuras 1 (c) y (d) muestran que HM-ANN obtiene un recall top-100 de > 90% en menos de 4 ms. HM-ANN proporciona el mejor rendimiento de latencia frente a recall que todos los demás enfoques.
Comparación de algoritmos a escala de millones
Figura 2.
En la Figura 2, se analiza el rendimiento de consulta de diferentes índices en un entorno de DRAM pura. HNSW, NSG y HM-ANN se evalúan con los tres conjuntos de datos a escala de millones que caben en DRAM. HM-ANN aún logra un mejor rendimiento de consulta que HNSW. La razón es que el número total de cálculos de distancia de HM-ANN es menor (en promedio 850/consulta) que el de HNSW (en promedio 900/consulta) para alcanzar el objetivo de recall del 99%.
Efectividad de la promoción de alto grado
En la Figura 3, se comparan las estrategias de promoción aleatoria y promoción de alto grado en la misma configuración. La promoción de alto grado supera a la línea base. La promoción de alto grado funciona 1.8x, 4.3x y 3.9x más rápido que la promoción aleatoria para alcanzar objetivos de recall del 95%, 99% y 99.5%, respectivamente.
Beneficio de rendimiento de las técnicas de gestión de memoria
La Figura 5 contiene una serie de pasos entre HNSW y HM-ANN para mostrar cómo cada optimización de HM-ANN contribuye a sus mejoras. BP significa Bottom-up Promotion durante la construcción del índice. PL0 representa la búsqueda paralela en la capa 0, mientras que DP representa la precarga de datos desde PMem a DRAM. Paso a paso, el rendimiento de búsqueda de HM-ANN se impulsa aún más.
Conclusión
Un nuevo algoritmo de indexación y búsqueda basado en grafos, llamado HM-ANN, mapea el diseño jerárquico de los ANNs basados en grafos con la heterogeneidad de memoria en HM. Las evaluaciones muestran que HM-ANN pertenece a los nuevos índices de vanguardia en conjuntos de datos de miles de millones de puntos.
Observamos una tendencia tanto en el ámbito académico como en la industria, donde se centra la atención en construir índices en dispositivos de almacenamiento persistente. Para descargar la presión de la DRAM, Disk-ANN [1] es un índice construido sobre SSD, cuyo rendimiento es significativamente menor que el de PMem. Sin embargo, la construcción de HM-ANN aún tarda unos pocos días, donde no se establecen grandes diferencias en comparación con Disk-ANN. Creemos que es posible optimizar el tiempo de construcción de HM-ANN cuando utilizamos con más cuidado las características de PMem, por ejemplo, tener en cuenta la granularidad de PMem (256 Bytes) y usar instrucciones de streaming para evitar las líneas de caché. También creemos que en el futuro se propondrán más enfoques con dispositivos de almacenamiento duradero.
Referencia
[1]: Suhas Jayaram Subramanya and Devvrit and Rohan Kadekodi and Ravishankar Krishaswamy and Ravishankar Krishaswamy: DiskANN: Búsqueda rápida y precisa del vecino más cercano de mil millones de puntos en un solo nodo, NIPS, 2019
DiskANN: Búsqueda rápida y precisa del vecino más cercano de mil millones de puntos en un solo nodo
[2]: Alexander van Renen and Lukas Vogel and Viktor Leis and Thomas Neumann and Alfons Kemper: Primitivas de E/S de memoria persistente, CoRR & DaMoN, 2019
Sigue leyendo
Zilliz Cloud Now Available in AWS Asia Pacific (Seoul)
Zilliz Cloud is now available in AWS Seoul — low-latency vector search, in-country data residency, and one-step migration for Korean AI teams. 31 regions across 5 clouds.
Introducing Business Critical Plan: Enterprise-Grade Security and Compliance for Mission-Critical AI Applications
Discover Zilliz Cloud’s Business Critical Plan—offering advanced security, compliance, and uptime for mission-critical AI and vector database workloads.
Why Teams Are Migrating from Weaviate to Zilliz Cloud — and How to Do It Seamlessly
Explore how Milvus scales for large datasets and complex queries with advanced features, and discover how to migrate from Weaviate to Zilliz Cloud.