Lettura dell'articolo｜HM-ANN: Quando ANNS incontra la memoria eterogenea
HM-ANN: Ricerca efficiente del vicino più prossimo su miliardi di punti con memoria eterogenea è un articolo di ricerca accettato alla Conference on Neural Information Processing Systems del 2020 (NeurIPS 2020). In questo articolo viene proposto un nuovo algoritmo per la ricerca di similarità basata su grafi, chiamato HM-ANN. Questo algoritmo considera sia l’eterogeneità della memoria sia l’eterogeneità dei dati in un contesto hardware moderno. HM-ANN consente la ricerca di similarità su scala di miliardi su una singola macchina senza tecnologie di compressione. La memoria eterogenea (HM) rappresenta la combinazione di memoria dinamica ad accesso casuale (DRAM) veloce ma piccola e memoria persistente (PMem) lenta ma grande. HM-ANN ottiene bassa latenza di ricerca e alta accuratezza di ricerca, soprattutto quando il dataset non può essere contenuto nella DRAM. L’algoritmo presenta un vantaggio netto rispetto alle soluzioni all’avanguardia per la ricerca approssimata del vicino più prossimo (ANN).
Motivazione
Fin dalla loro nascita, gli algoritmi di ricerca ANN hanno posto un compromesso fondamentale tra accuratezza della query e latenza della query a causa della capacità limitata della DRAM. Per archiviare gli indici nella DRAM per un accesso rapido alle query, è necessario limitare il numero di punti dati oppure archiviare vettori compressi, entrambi fattori che danneggiano l’accuratezza della ricerca. Gli indici basati su grafi (ad es. Hierarchical Navigable Small World, HNSW) hanno prestazioni superiori in termini di tempo di esecuzione delle query e accuratezza delle query. Tuttavia, questi indici possono anche consumare DRAM a livello di 1 TiB quando operano su dataset su scala di miliardi.
Esistono altre soluzioni alternative per evitare che la DRAM archivi dataset su scala di miliardi in formato grezzo. Quando un dataset è troppo grande per entrare in memoria su una singola macchina, vengono utilizzati approcci compressi come la quantizzazione del prodotto dei punti del dataset. Ma il recall di quegli indici con il dataset compresso è normalmente basso a causa della perdita di precisione durante la quantizzazione. Subramanya et al. [1] esplorano l’uso di unità a stato solido (SSD) per ottenere la ricerca ANN su scala di miliardi usando una singola macchina con un approccio chiamato Disk-ANN, in cui il dataset grezzo è archiviato su SSD e la rappresentazione compressa nella DRAM.
Introduzione alla memoria eterogenea
Nome dell’immagineGerarchia di memoria/archiviazione con HMxx
Nome dell’immagineGerarchia di memoria/archiviazione con HMxx
Fonte: http://nvmw.ucsd.edu/nvmw2021-program/nvmw2021-data/nvmw2021-paper63-presentation_slides.pdf
La memoria eterogenea (HM) rappresenta la combinazione di DRAM veloce ma piccola e PMem lenta ma grande. La DRAM è hardware comune che si può trovare in ogni server moderno e il suo accesso è relativamente veloce. Le nuove tecnologie PMem, come Intel® Optane™ DC Persistent Memory Modules, colmano il divario tra flash basata su NAND (SSD) e DRAM, eliminando il collo di bottiglia I/O. La PMem è durevole come un SSD e direttamente indirizzabile dalla CPU, come la memoria. Renen et al. [2] scoprono che la larghezza di banda in lettura della PMem è 2,6× inferiore, e la larghezza di banda in scrittura 7,5× inferiore, rispetto alla DRAM nell’ambiente sperimentale configurato.
Progettazione di HM-ANN
HM-ANN è un algoritmo di ricerca ANN su scala di miliardi accurato e veloce che viene eseguito su una singola macchina senza compressione. La progettazione di HM-ANN generalizza l’idea di HNSW, la cui struttura gerarchica si adatta naturalmente alla HM. HNSW è composto da più livelli: solo il livello 0 contiene l’intero dataset, e ciascun livello rimanente contiene un sottoinsieme di elementi del livello immediatamente sottostante.
Un esempio di HNSW con 3 livelli
Fonte: https://arxiv.org/pdf/1603.09320.pdf
- Gli elementi nei livelli superiori, che includono solo sottoinsiemi del dataset, consumano una piccola porzione dell'intero spazio di archiviazione. Questa osservazione li rende candidati discreti per essere collocati in DRAM. In questo modo, ci si aspetta che la maggior parte delle ricerche su HM-ANN avvenga nei livelli superiori, il che massimizza l'utilizzo della caratteristica di accesso rapido della DRAM. Tuttavia, nei casi di HNSW, la maggior parte delle ricerche avviene nel livello inferiore.
- Il livello più basso contiene l'intero dataset, il che lo rende adatto a essere collocato in PMem. Poiché l'accesso al livello 0 è più lento, è preferibile che ogni query acceda solo a una piccola porzione e che la frequenza di accesso sia ridotta.
Algoritmo di costruzione del grafo
Un esempio di costruzione del grafo di HM-ANN
Fonte: http://nvmw.ucsd.edu/nvmw2021-program/nvmw2021-data/nvmw2021-paper63-poster.pdf
L'idea chiave della costruzione di HM-ANN è creare livelli superiori di alta qualità, al fine di fornire una migliore navigazione per la ricerca al livello 0. Pertanto, la maggior parte degli accessi alla memoria avviene in DRAM e l'accesso in PMem è ridotto. Per rendere ciò possibile, l'algoritmo di costruzione di HM-ANN ha una fase di inserimento top-down e una fase di promozione bottom-up.
La fase di inserimento top-down costruisce un grafo navigabile small-world mentre il livello più basso viene collocato sulla PMem.
La fase di promozione bottom-up promuove punti pivot dal livello inferiore per formare livelli superiori che vengono collocati su DRAM senza perdere molta accuratezza. Se viene creata una proiezione di alta qualità degli elementi dal livello 0 nel livello 1, la ricerca nel livello 0 trova i vicini più prossimi accurati della query con solo pochi salti.
- Invece di utilizzare la selezione casuale di HNSW per la promozione, HM-ANN utilizza una strategia di promozione ad alto grado per promuovere gli elementi con il grado più alto nel livello 0 al livello 1. Per i livelli superiori, HM-ANN promuove i nodi ad alto grado al livello superiore in base a un tasso di promozione.
- HM-ANN promuove più nodi dal livello 0 al livello 1 e imposta un numero massimo maggiore di vicini per ciascun elemento nel livello 1. Il numero di nodi nei livelli superiori è deciso dallo spazio DRAM disponibile. Poiché il livello 0 non è memorizzato in DRAM, rendere più denso ogni livello memorizzato in DRAM aumenta la qualità della ricerca.
Algoritmo di ricerca del grafo
Un esempio di ricerca del grafo di HM-ANN
Fonte: http://nvmw.ucsd.edu/nvmw2021-program/nvmw2021-data/nvmw2021-paper63-poster.pdf
L'algoritmo di ricerca consiste in due fasi: ricerca in memoria veloce e ricerca parallela nel livello 0 con prefetching.
Ricerca in memoria veloce
Come in HNSW, la ricerca in DRAM inizia dal punto di ingresso nel livello più alto e poi esegue una ricerca 1-greedy dall'alto fino al livello 2. Per restringere lo spazio di ricerca nel livello 0, HM-ANN esegue la ricerca nel livello 1 con un budget di ricerca con efSearchL1, che limita la dimensione della lista dei candidati nel livello 1. Questi candidati della lista vengono usati come punti di ingresso multipli per la ricerca nel livello 0, per migliorare la qualità della ricerca nel livello 0. Mentre HNSW utilizza un solo punto di ingresso, il divario tra il livello 0 e il livello 1 è gestito in modo più specifico in HM-ANN rispetto ai divari tra qualsiasi altra coppia di livelli.
Ricerca parallela nel livello 0 con prefetching
Nel livello inferiore, HM-ANN partiziona uniformemente i candidati menzionati in precedenza dalla ricerca nel livello 1 e li considera come punti di ingresso per eseguire una ricerca 1-greedy multi-start parallela con thread. I migliori candidati di ciascuna ricerca vengono raccolti per trovare i candidati migliori. Come noto, scendere dal livello 1 al livello 0 significa esattamente andare alla PMem. La ricerca parallela nasconde la latenza della PMem e sfrutta al meglio la larghezza di banda della memoria, per migliorare la qualità della ricerca senza aumentare il tempo di ricerca.
HM-ANN implementa un buffer gestito via software in DRAM per prefetchare i dati da PMem prima che avvenga l’accesso alla memoria. Durante la ricerca nel layer 1, HM-ANN copia in modo asincrono gli elementi vicini di quei candidati in efSearchL1 e le connessioni degli elementi vicini nel layer 1 da PMem al buffer. Quando avviene la ricerca nel layer 0, una parte dei dati da accedere è già stata prefetchedata in DRAM, il che nasconde la latenza di accesso a PMem e porta a un tempo di query più breve. Questo corrisponde all’obiettivo di progettazione di HM-ANN, in cui la maggior parte degli accessi alla memoria avviene in DRAM e gli accessi alla memoria in PMem sono ridotti.
Valutazione
In questo paper viene condotta una valutazione estesa. Tutti gli esperimenti sono eseguiti su una macchina con CPU Intel Xeon Gold 6252@2.3GHz. Utilizza DDR4 (96GB) come memoria veloce e Optane DC PMM (1.5TB) come memoria lenta. Vengono valutati cinque dataset: BIGANN, DEEP1B, SIFT1M, DEEP1M e GIST1M. Per i test su scala di miliardi, sono inclusi i seguenti schemi: metodi basati su quantizzazione su scala di miliardi (IMI+OPQ e L&C), metodi non basati su compressione (HNSW e NSG).
Confronto degli algoritmi su scala di miliardi
Tabella 1.
Nella tabella 1 vengono confrontati il tempo di costruzione e lo storage di diversi indici basati su grafi. HNSW richiede il tempo di costruzione più breve e HM-ANN necessita dell’8% di tempo aggiuntivo rispetto a HNSW. In termini di utilizzo complessivo dello storage, gli indici HM-ANN sono più grandi del 5–13% rispetto a HSNW, perché promuove più nodi dal layer 0 al layer 1.
Figura 1.
Nella Figura 1 viene analizzata la performance di query di diversi indici. La Figura 1 (a) e (b) mostrano che HM-ANN raggiunge una recall top-1 di > 95% entro 1ms. Le Figure 1 (c) e (d) mostrano che HM-ANN ottiene una recall top-100 di > 90% entro 4 ms. HM-ANN offre la migliore performance latenza-vs-recall rispetto a tutti gli altri approcci.
Confronto degli algoritmi su scala di milioni
Figura 2.
Nella Figura 2 viene analizzata la performance di query di diversi indici in un’impostazione puramente DRAM. HNSW, NSG e HM-ANN sono valutati con i tre dataset su scala di milioni che rientrano in DRAM. HM-ANN raggiunge comunque una performance di query migliore rispetto a HNSW. Il motivo è che il numero totale di calcoli di distanza di HM-ANN è inferiore (in media 850/query) rispetto a quello di HNSW (in media 900/query) per raggiungere l’obiettivo di recall del 99%.
Efficacia della promozione ad alto grado
Nella Figura 3, le strategie di promozione casuale e promozione ad alto grado sono confrontate nella stessa configurazione. La promozione ad alto grado supera il baseline. La promozione ad alto grado è 1.8x, 4.3x e 3.9x più veloce della promozione casuale nel raggiungere rispettivamente gli obiettivi di recall del 95%, 99% e 99.5%.
Beneficio prestazionale delle tecniche di gestione della memoria
La Figura 5 contiene una serie di passaggi tra HNSW e HM-ANN per mostrare come ciascuna ottimizzazione di HM-ANN contribuisca ai suoi miglioramenti. BP sta per Bottom-up Promotion durante la costruzione dell’indice. PL0 rappresenta Parallel layer-0 search, mentre DP indica il prefetching dei dati da PMem a DRAM. Passo dopo passo, la performance di ricerca di HM-ANN viene spinta oltre.
Conclusione
Un nuovo algoritmo di indicizzazione e ricerca basato su grafi, chiamato HM-ANN, mappa il design gerarchico delle ANN basate su grafi con l’eterogeneità della memoria in HM. Le valutazioni mostrano che HM-ANN appartiene ai nuovi indici state-of-the-art nei dataset da miliardi di punti.
Notiamo una tendenza sia nel mondo accademico sia nell'industria, in cui ci si concentra sulla costruzione di indici su dispositivi di archiviazione persistente. Per alleggerire la pressione sulla DRAM, Disk-ANN [1] è un indice costruito su SSD, il cui throughput è significativamente inferiore rispetto a PMem. Tuttavia, la costruzione di HM-ANN richiede ancora alcuni giorni, senza che siano stabilite grandi differenze rispetto a Disk-ANN. Riteniamo sia possibile ottimizzare il tempo di costruzione di HM-ANN, quando utilizziamo le caratteristiche di PMem con maggiore attenzione, ad esempio tenendo conto della granularità di PMem (256 Byte) e usando istruzioni di streaming per bypassare le cacheline. Riteniamo inoltre che in futuro verranno proposti altri approcci con dispositivi di archiviazione durevoli.
Riferimento
[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
Continua a leggere
Zilliz Cloud Just Landed in Claude Code
The Zilliz Cloud Plugin brings the full power of Zilliz Cloud directly into your Claude Code terminal as natural-language conversations.
Zilliz Cloud Introduces Advanced BYOC-I Solution for Ultimate Enterprise Data Sovereignty
Explore Zilliz Cloud BYOC-I, the solution that balances AI innovation with data control, enabling secure deployments in finance, healthcare, and education sectors.
Vector Databases vs. Hierarchical Databases
Use a vector database for AI-powered similarity search; use a hierarchical database for organizing data in parent-child relationships with efficient top-down access patterns.