Leitura de Artigo｜HM-ANN: Quando ANNS Encontra Memória Heterogênea
HM-ANN: Busca eficiente de vizinhos mais próximos em escala de bilhões de pontos em memória heterogênea é um artigo de pesquisa que foi aceito na Conferência de 2020 sobre Sistemas de Processamento de Informação Neural (NeurIPS 2020). Neste artigo, é proposto um novo algoritmo para busca de similaridade baseada em grafos, chamado HM-ANN. Esse algoritmo considera tanto a heterogeneidade da memória quanto a heterogeneidade dos dados em uma configuração de hardware moderna. O HM-ANN permite a busca de similaridade em escala de bilhões em uma única máquina sem tecnologias de compressão. Memória heterogênea (HM) representa a combinação de memória dinâmica de acesso aleatório (DRAM) rápida, porém pequena, e memória persistente (PMem) lenta, porém grande. O HM-ANN alcança baixa latência de busca e alta precisão de busca, especialmente quando o conjunto de dados não cabe na DRAM. O algoritmo tem uma vantagem distinta sobre as soluções de busca de vizinhos mais próximos aproximados (ANN) do estado da arte.
Motivação
Desde sua criação, os algoritmos de busca ANN têm apresentado um compromisso fundamental entre a precisão da consulta e a latência da consulta devido à capacidade limitada da DRAM. Para armazenar índices na DRAM para acesso rápido às consultas, é necessário limitar o número de pontos de dados ou armazenar vetores comprimidos, ambos os quais prejudicam a precisão da busca. Índices baseados em grafos (por exemplo, Hierarchical Navigable Small World, HNSW) têm desempenho superior de tempo de execução de consulta e precisão de consulta. No entanto, esses índices também podem consumir DRAM em nível de 1 TiB ao operar em conjuntos de dados em escala de bilhões.
Existem outras soluções alternativas para evitar que a DRAM armazene conjuntos de dados em escala de bilhões em formato bruto. Quando um conjunto de dados é grande demais para caber na memória em uma única máquina, abordagens comprimidas, como a quantização de produto dos pontos do conjunto de dados, são usadas. Mas a revocação desses índices com o conjunto de dados comprimido normalmente é baixa devido à perda de precisão durante a quantização. Subramanya et al. [1] exploram o aproveitamento de unidade de estado sólido (SSD) para alcançar busca ANN em escala de bilhões usando uma única máquina com uma abordagem chamada Disk-ANN, na qual o conjunto de dados bruto é armazenado no SSD e a representação comprimida na DRAM.
Introdução à memória heterogênea
Nome da imagemHierarquia de memória/armazenamento com HMxx
Nome da imagemHierarquia de memória/armazenamento com HMxx
Fonte: http://nvmw.ucsd.edu/nvmw2021-program/nvmw2021-data/nvmw2021-paper63-presentation_slides.pdf
Memória heterogênea (HM) representa a combinação de DRAM rápida, porém pequena, e PMem lenta, porém grande. DRAM é um hardware normal que pode ser encontrado em todos os servidores modernos, e seu acesso é relativamente rápido. Novas tecnologias de PMem, como Intel® Optane™ DC Persistent Memory Modules, preenchem a lacuna entre flash baseada em NAND (SSD) e DRAM, eliminando o gargalo de E/S. A PMem é durável como SSD e diretamente endereçável pela CPU, como memória. Renen et al. [2] descobrem que a largura de banda de leitura da PMem é 2,6× menor, e a largura de banda de escrita 7,5× menor, do que a DRAM no ambiente experimental configurado.
Design do HM-ANN
HM-ANN é um algoritmo de busca ANN em escala de bilhões preciso e rápido que roda em uma única máquina sem compressão. O design do HM-ANN generaliza a ideia do HNSW, cuja estrutura hierárquica se encaixa naturalmente na HM. O HNSW consiste em múltiplas camadas—apenas a camada 0 contém todo o conjunto de dados, e cada camada restante contém um subconjunto de elementos da camada diretamente abaixo dela.
Um exemplo de HNSW com 3 camadas
Fonte: https://arxiv.org/pdf/1603.09320.pdf
- Elementos nas camadas superiores, que incluem apenas subconjuntos do dataset, consomem uma pequena porção de todo o armazenamento. Essa observação os torna bons candidatos para serem colocados em DRAM. Dessa forma, espera-se que a maioria das buscas no HM-ANN aconteça nas camadas superiores, o que maximiza a utilização da característica de acesso rápido da DRAM. No entanto, nos casos do HNSW, a maioria das buscas acontece na camada inferior.
- A camada mais inferior carrega todo o dataset, o que a torna adequada para ser colocada em PMem. Como acessar a camada 0 é mais lento, é preferível que apenas uma pequena porção seja acessada por cada consulta e que a frequência de acesso seja reduzida.
Algoritmo de construção do grafo
Um exemplo de construção de grafo do HM-ANN
Fonte: http://nvmw.ucsd.edu/nvmw2021-program/nvmw2021-data/nvmw2021-paper63-poster.pdf
A ideia principal da construção do HM-ANN é criar camadas superiores de alta qualidade, a fim de fornecer melhor navegação para a busca na camada 0. Assim, a maior parte do acesso à memória acontece em DRAM, e o acesso em PMem é reduzido. Para tornar isso possível, o algoritmo de construção do HM-ANN tem uma fase de inserção top-down e uma fase de promoção bottom-up.
A fase de inserção top-down constrói um grafo small-world navegável à medida que a camada mais inferior é colocada na PMem.
A fase de promoção bottom-up promove pontos pivô da camada inferior para formar camadas superiores que são colocadas na DRAM sem perder muita precisão. Se uma projeção de alta qualidade dos elementos da camada 0 for criada na camada 1, a busca na camada 0 encontra os vizinhos mais próximos precisos da consulta com apenas alguns saltos.
- Em vez de usar a seleção aleatória do HNSW para promoção, o HM-ANN usa uma estratégia de promoção de alto grau para promover elementos com o maior grau na camada 0 para a camada 1. Para camadas superiores, o HM-ANN promove nós de alto grau para a camada superior com base em uma taxa de promoção.
- O HM-ANN promove mais nós da camada 0 para a camada 1 e define um número máximo maior de vizinhos para cada elemento na camada 1. O número de nós nas camadas superiores é decidido pelo espaço DRAM disponível. Como a camada 0 não é armazenada em DRAM, tornar cada camada armazenada em DRAM mais densa aumenta a qualidade da busca.
Algoritmo de busca em grafos
Um exemplo de busca em grafo do HM-ANN
Fonte: http://nvmw.ucsd.edu/nvmw2021-program/nvmw2021-data/nvmw2021-paper63-poster.pdf
O algoritmo de busca consiste em duas fases: busca em memória rápida e busca paralela na camada 0 com prefetching.
Busca em memória rápida
Assim como no HNSW, a busca em DRAM começa no ponto de entrada na camada mais alta e, em seguida, realiza busca 1-greedy do topo até a camada 2. Para estreitar o espaço de busca na camada 0, o HM-ANN realiza a busca na camada 1 com um orçamento de busca com efSearchL1, que limita o tamanho da lista de candidatos na camada 1. Esses candidatos da lista são usados como múltiplos pontos de entrada para a busca na camada 0, para melhorar a qualidade da busca na camada 0. Enquanto o HNSW usa apenas um ponto de entrada, a lacuna entre a camada 0 e a camada 1 é tratada de forma mais específica no HM-ANN do que as lacunas entre quaisquer outras duas camadas.
Busca paralela na camada 0 com prefetching
Na camada inferior, o HM-ANN particiona uniformemente os candidatos mencionados anteriormente da busca na camada 1 e os vê como pontos de entrada para realizar uma busca 1-greedy paralela multi-start com threads. Os principais candidatos de cada busca são coletados para encontrar os melhores candidatos. Como se sabe, descer da camada 1 para a camada 0 é exatamente ir para PMem. A busca paralela oculta a latência da PMem e aproveita ao máximo a largura de banda da memória, para melhorar a qualidade da busca sem aumentar o tempo de busca.
HM-ANN implementa um buffer gerenciado por software em DRAM para pré-buscar dados da PMem antes que o acesso à memória aconteça. Ao pesquisar a camada 1, o HM-ANN copia assincronamente os elementos vizinhos desses candidatos em efSearchL1 e as conexões dos elementos vizinhos na camada 1 da PMem para o buffer. Quando a busca na camada 0 acontece, uma parte dos dados a serem acessados já foi pré-buscada na DRAM, o que oculta a latência para acessar a PMem e leva a um tempo de consulta menor. Isso corresponde ao objetivo de design do HM-ANN, em que a maioria dos acessos à memória acontece na DRAM e os acessos à memória na PMem são reduzidos.
Avaliação
Neste artigo, é conduzida uma avaliação extensiva. Todos os experimentos são feitos em uma máquina com CPU Intel Xeon Gold 6252@2,3GHz. Ela usa DDR4 (96GB) como memória rápida e Optane DC PMM (1,5TB) como memória lenta. Cinco conjuntos de dados são avaliados: BIGANN, DEEP1B, SIFT1M, DEEP1M e GIST1M. Para testes em escala de bilhões, os seguintes esquemas são incluídos: métodos em escala de bilhões baseados em quantização (IMI+OPQ e L&C), os métodos não baseados em compressão (HNSW e NSG).
Comparação de algoritmos em escala de bilhões
Tabela 1.
Na tabela 1, o tempo de construção e o armazenamento de diferentes índices baseados em grafos são comparados. O HNSW leva o menor tempo de construção e o HM-ANN precisa de 8% de tempo adicional em relação ao HNSW. Em termos de uso total de armazenamento, os índices HM-ANN são 5–13% maiores que os HSNW, porque ele promove mais nós da camada 0 para a camada 1.
Figura 1.
Na Figura 1, o desempenho de consulta de diferentes índices é analisado. As Figuras 1 (a) e (b) mostram que o HM-ANN alcança recall top-1 de > 95% em 1ms. As Figuras 1 (c) e (d) mostram que o HM-ANN obtém recall top-100 de > 90% em 4 ms. O HM-ANN oferece o melhor desempenho de latência-vs-recall em comparação com todas as outras abordagens.
Comparação de algoritmos em escala de milhões
Figura 2.
Na Figura 2, o desempenho de consulta de diferentes índices é analisado em uma configuração puramente DRAM. HNSW, NSG e HM-ANN são avaliados com os três conjuntos de dados em escala de milhões cabendo na DRAM. O HM-ANN ainda alcança melhor desempenho de consulta do que o HNSW. A razão é que o número total de cálculos de distância do HM-ANN é menor (em média 850/consulta) do que o do HNSW (em média 900/consulta) para atingir a meta de 99% de recall.
Eficácia da promoção de alto grau
Na Figura 3, as estratégias de promoção aleatória e promoção de alto grau são comparadas na mesma configuração. A promoção de alto grau supera a linha de base. A promoção de alto grau é 1,8x, 4,3x e 3,9x mais rápida do que a promoção aleatória para atingir metas de recall de 95%, 99% e 99,5%, respectivamente.
Benefício de desempenho das técnicas de gerenciamento de memória
A Figura 5 contém uma série de etapas entre HNSW e HM-ANN para mostrar como cada otimização do HM-ANN contribui para suas melhorias. BP significa Bottom-up Promotion durante a construção do índice. PL0 representa Parallel layer-0 search, enquanto DP representa data prefetching da PMem para a DRAM. Passo a passo, o desempenho de busca do HM-ANN é impulsionado ainda mais.
Conclusão
Um novo algoritmo de indexação e busca baseado em grafos, chamado HM-ANN, mapeia o design hierárquico das ANNs baseadas em grafos com heterogeneidade de memória em HM. As avaliações mostram que o HM-ANN pertence aos novos índices de estado da arte em conjuntos de dados com bilhões de pontos.
Notamos uma tendência tanto na academia quanto na indústria, em que o foco está na construção de índices em dispositivos de armazenamento persistente. Para aliviar a pressão sobre a DRAM, Disk-ANN [1] é um índice construído em SSD, cujo throughput é significativamente menor que o da PMem. No entanto, a construção do HM-ANN ainda leva alguns dias, sem grandes diferenças estabelecidas em comparação com o Disk-ANN. Acreditamos que seja possível otimizar o tempo de construção do HM-ANN quando utilizamos as características da PMem com mais cuidado, por exemplo, estando cientes da granularidade da PMem (256 Bytes) e usando instruções de streaming para contornar as linhas de cache. Também acreditamos que mais abordagens com dispositivos de armazenamento durável serão propostas no futuro.
Referência
[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
Continue lendo
Introducing Zilliz Cloud Global Cluster: Region-Level Resilience for Mission-Critical AI
Zilliz Cloud Global Cluster delivers multi-region resilience, automatic failover, and fast global AI search with built-in security and compliance.
How to Build RAG with Milvus, QwQ-32B and Ollama
Hands-on tutorial on how to create a streamlined, powerful RAG pipeline that balances efficiency, accuracy, and scalability using the QwQ-32B and Milvus.
Vector Databases vs. Graph Databases
Use a vector database for AI-powered similarity search; use a graph database for complex relationship-based queries and network analysis.