Чтение статьи｜HM-ANN: Когда ANNS встречается с гетерогенной памятью
HM-ANN: эффективный поиск ближайших соседей по миллиарду точек в гетерогенной памяти — это исследовательская статья, принятая на конференцию 2020 года по системам обработки нейронной информации (NeurIPS 2020). В этой статье предложен новый алгоритм графового поиска по сходству под названием HM-ANN. Этот алгоритм учитывает как гетерогенность памяти, так и гетерогенность данных в современной аппаратной среде. HM-ANN обеспечивает поиск по сходству в масштабе миллиардов на одной машине без технологий сжатия. Гетерогенная память (HM) представляет собой сочетание быстрой, но небольшой динамической памяти с произвольным доступом (DRAM) и медленной, но большой постоянной памяти (PMem). HM-ANN достигает низкой задержки поиска и высокой точности поиска, особенно когда набор данных не помещается в DRAM. Алгоритм имеет явное преимущество перед современными решениями поиска приближенных ближайших соседей (ANN).
Мотивация
С момента своего появления алгоритмы поиска ANN были связаны с фундаментальным компромиссом между точностью запроса и задержкой запроса из-за ограниченной емкости DRAM. Чтобы хранить индексы в DRAM для быстрого доступа к запросам, необходимо ограничивать количество точек данных или хранить сжатые векторы, и оба подхода снижают точность поиска. Графовые индексы (например, Hierarchical Navigable Small World, HNSW) обеспечивают превосходную производительность времени выполнения запросов и точность запросов. Однако эти индексы также могут потреблять DRAM уровня 1 ТиБ при работе с наборами данных масштаба миллиардов.
Существуют и другие обходные пути, позволяющие не хранить наборы данных масштаба миллиардов в DRAM в необработанном формате. Когда набор данных слишком велик, чтобы поместиться в памяти на одной машине, используются подходы со сжатием, такие как произведенное квантование точек набора данных. Но полнота таких индексов со сжатым набором данных обычно низкая из-за потери точности при квантовании. Subramanya et al. [1] исследуют использование твердотельного накопителя (SSD) для достижения ANN-поиска масштаба миллиардов на одной машине с помощью подхода под названием Disk-ANN, где необработанный набор данных хранится на SSD, а сжатое представление — в DRAM.
Введение в гетерогенную память
Название изображенияMemory/Storage Hierarchy with HMxx
Название изображенияMemory/Storage Hierarchy with HMxx
Источник: http://nvmw.ucsd.edu/nvmw2021-program/nvmw2021-data/nvmw2021-paper63-presentation_slides.pdf
Гетерогенная память (HM) представляет собой сочетание быстрой, но небольшой DRAM и медленной, но большой PMem. DRAM — это обычное аппаратное обеспечение, которое можно найти в каждом современном сервере, и доступ к ней относительно быстр. Новые технологии PMem, такие как Intel® Optane™ DC Persistent Memory Modules, закрывают разрыв между флеш-памятью на основе NAND (SSD) и DRAM, устраняя узкое место ввода-вывода. PMem долговечна, как SSD, и напрямую адресуется CPU, как память. Renen et al. [2] обнаружили, что в настроенной экспериментальной среде пропускная способность чтения PMem в 2,6 раза ниже, а пропускная способность записи в 7,5 раза ниже, чем у DRAM.
Проектирование HM-ANN
HM-ANN — это точный и быстрый алгоритм ANN-поиска масштаба миллиардов, который работает на одной машине без сжатия. Дизайн HM-ANN обобщает идею HNSW, чья иерархическая структура естественным образом вписывается в HM. HNSW состоит из нескольких слоев — только слой 0 содержит весь набор данных, а каждый оставшийся слой содержит подмножество элементов из слоя непосредственно под ним.
Пример HNSW с 3 слоями
Источник: https://arxiv.org/pdf/1603.09320.pdf
- Элементы в верхних слоях, которые включают только подмножества набора данных, занимают небольшую часть всего хранилища. Это наблюдение делает их подходящими кандидатами для размещения в DRAM. Таким образом, ожидается, что большинство поисков в HM-ANN будет происходить в верхних слоях, что максимизирует использование характеристики быстрого доступа DRAM. Однако в случаях HNSW большинство поисков происходит в нижнем слое.
- Самый нижний слой содержит весь набор данных, что делает его подходящим для размещения в PMem. Поскольку доступ к слою 0 медленнее, предпочтительно, чтобы каждый запрос обращался лишь к небольшой его части, а частота доступа была снижена.
Алгоритм построения графа
Пример построения графа HM-ANN
Источник: http://nvmw.ucsd.edu/nvmw2021-program/nvmw2021-data/nvmw2021-paper63-poster.pdf
Ключевая идея построения HM-ANN заключается в создании высококачественных верхних слоев, чтобы обеспечить лучшую навигацию для поиска на слое 0. Таким образом, большая часть обращений к памяти происходит в DRAM, а доступ к PMem сокращается. Чтобы сделать это возможным, алгоритм построения HM-ANN имеет фазу вставки сверху вниз и фазу продвижения снизу вверх.
Фаза вставки сверху вниз строит навигируемый граф малого мира, поскольку самый нижний слой размещается в PMem.
Фаза продвижения снизу вверх продвигает опорные точки из нижнего слоя для формирования верхних слоев, которые размещаются в DRAM без значительной потери точности. Если в слое 1 создана высококачественная проекция элементов из слоя 0, поиск в слое 0 находит точных ближайших соседей запроса всего за несколько переходов.
- Вместо использования случайного выбора HNSW для продвижения, HM-ANN использует стратегию продвижения с высокой степенью, чтобы продвигать элементы с наибольшей степенью в слое 0 в слой 1. Для более высоких слоев HM-ANN продвигает узлы с высокой степенью в верхний слой на основе коэффициента продвижения.
- HM-ANN продвигает больше узлов из слоя 0 в слой 1 и задает большее максимальное число соседей для каждого элемента в слое 1. Число узлов в верхних слоях определяется доступным пространством DRAM. Поскольку слой 0 не хранится в DRAM, повышение плотности каждого слоя, хранящегося в DRAM, увеличивает качество поиска.
Алгоритм поиска по графу
Пример поиска по графу HM-ANN
Источник: http://nvmw.ucsd.edu/nvmw2021-program/nvmw2021-data/nvmw2021-paper63-poster.pdf
Алгоритм поиска состоит из двух фаз: поиска в быстрой памяти и параллельного поиска на слое 0 с предварительной выборкой.
Поиск в быстрой памяти
Как и в HNSW, поиск в DRAM начинается с входной точки в самом верхнем слое, а затем выполняет 1-жадный поиск сверху до слоя 2. Чтобы сузить пространство поиска в слое 0, HM-ANN выполняет поиск в слое 1 с поисковым бюджетом efSearchL1, который ограничивает размер списка кандидатов в слое 1. Эти кандидаты из списка используются как несколько входных точек для поиска в слое 0, чтобы повысить качество поиска в слое 0. В то время как HNSW использует только одну входную точку, разрыв между слоем 0 и слоем 1 в HM-ANN обрабатывается более специально, чем разрывы между любыми другими двумя слоями.
Параллельный поиск на слое 0 с предварительной выборкой
В нижнем слое HM-ANN равномерно разделяет вышеупомянутых кандидатов, полученных при поиске в слое 1, и рассматривает их как входные точки для выполнения параллельного многозапускового 1-жадного поиска с помощью потоков. Лучшие кандидаты из каждого поиска собираются, чтобы найти наилучших кандидатов. Как известно, переход вниз со слоя 1 на слой 0 фактически означает переход к PMem. Параллельный поиск скрывает задержку PMem и максимально использует пропускную способность памяти, чтобы улучшить качество поиска без увеличения времени поиска.
HM-ANN реализует программно управляемый буфер в DRAM для предварительной выборки данных из PMem до того, как происходит доступ к памяти. При поиске на уровне 1 HM-ANN асинхронно копирует соседние элементы этих кандидатов в efSearchL1 и связи соседних элементов на уровне 1 из PMem в буфер. Когда происходит поиск на уровне 0, часть данных, к которым предстоит обратиться, уже предварительно загружена в DRAM, что скрывает задержку доступа к PMem и приводит к сокращению времени запроса. Это соответствует цели проектирования HM-ANN, при которой большая часть обращений к памяти происходит в DRAM, а обращения к памяти в PMem сокращаются.
Оценка
В этой статье проводится всесторонняя оценка. Все эксперименты выполняются на машине с Intel Xeon Gold 6252 CPU@2.3GHz. В ней используется DDR4 (96GB) в качестве быстрой памяти и Optane DC PMM (1.5TB) в качестве медленной памяти. Оцениваются пять наборов данных: BIGANN, DEEP1B, SIFT1M, DEEP1M и GIST1M. Для тестов миллиардного масштаба включены следующие схемы: методы миллиардного масштаба на основе квантования (IMI+OPQ и L&C), методы без сжатия (HNSW и NSG).
Сравнение алгоритмов миллиардного масштаба
Таблица 1.
В таблице 1 сравниваются время построения и объем хранилища различных графовых индексов. HNSW требует наименьшего времени построения, а HM-ANN требуется на 8% больше времени, чем HNSW. С точки зрения общего использования хранилища индексы HM-ANN на 5–13% больше, чем HSNW, поскольку он повышает больше узлов с уровня 0 до уровня 1.
Рисунок 1.
На рисунке 1 анализируется производительность запросов различных индексов. Рисунок 1 (a) и (b) показывают, что HM-ANN достигает top-1 recall > 95% в пределах 1 мс. Рисунки 1 (c) и (d) показывают, что HM-ANN достигает top-100 recall > 90% в пределах 4 мс. HM-ANN обеспечивает лучшую производительность задержка-vs-recall по сравнению со всеми другими подходами.
Сравнение алгоритмов миллионного масштаба
Рисунок 2.
На рисунке 2 анализируется производительность запросов различных индексов в конфигурации только с DRAM. HNSW, NSG и HM-ANN оцениваются на трех наборах данных миллионного масштаба, помещающихся в DRAM. HM-ANN по-прежнему достигает лучшей производительности запросов, чем HNSW. Причина в том, что общее число вычислений расстояния у HM-ANN ниже (в среднем 850/запрос), чем у HNSW (в среднем 900/запрос), для достижения целевого recall 99%.
Эффективность продвижения узлов с высокой степенью
На рисунке 3 сравниваются стратегии случайного продвижения и продвижения узлов с высокой степенью в одной и той же конфигурации. Продвижение узлов с высокой степенью превосходит базовый вариант. Продвижение узлов с высокой степенью работает в 1,8x, 4,3x и 3,9x быстрее, чем случайное продвижение, для достижения целевых значений recall 95%, 99% и 99,5% соответственно.
Преимущество производительности от методов управления памятью
Рисунок 5 содержит ряд шагов между HNSW и HM-ANN, чтобы показать, как каждая оптимизация HM-ANN способствует улучшениям. BP означает Bottom-up Promotion при построении индекса. PL0 обозначает Parallel layer-0 search, а DP — предварительную выборку данных из PMem в DRAM. Шаг за шагом производительность поиска HM-ANN повышается.
Заключение
Новый графовый алгоритм индексирования и поиска, называемый HM-ANN, сопоставляет иерархический дизайн графовых ANN с неоднородностью памяти в HM. Оценки показывают, что HM-ANN относится к новым индексам уровня state-of-the-art на наборах данных с миллиардом точек.
Мы наблюдаем тенденцию как в академической среде, так и в индустрии, где внимание сосредоточено на построении индексов на устройствах постоянного хранения данных. Чтобы снизить нагрузку на DRAM, Disk-ANN [1] представляет собой индекс, построенный на SSD, пропускная способность которого значительно ниже, чем у PMem. Однако построение HM-ANN всё ещё занимает несколько дней, при этом не выявлено существенных отличий по сравнению с Disk-ANN. Мы считаем, что можно оптимизировать время построения HM-ANN, если более тщательно использовать характеристики PMem, например учитывать гранулярность PMem (256 байт) и использовать потоковые инструкции для обхода cachelines. Мы также считаем, что в будущем будет предложено больше подходов с использованием устройств долговременного хранения данных.
Ссылки
[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
Читать далее
Expanding Our Global Reach: Zilliz Cloud Launches in Azure Central India
Zilliz Cloud expands to Azure Central India. This new region helps customers meet compliance, reduce latency, and optimize cloud costs when building AI applications.
Vector Databases vs. Object-Relational Databases
Use a vector database for AI-powered similarity search; use an object-relational database for complex data modeling with both relational integrity and object-oriented features.
Legal Document Analysis: Harnessing Zilliz Cloud's Semantic Search and RAG for Legal Insights
Enhance legal document analysis with Zilliz Cloud’s Semantic Search and RAG. Improve accuracy, efficiency, and scalability for contracts, case law, and compliance.