Чтение статьи｜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
Читать далее
Notion's Vector Search Is Excellent. Their Next Problem Is Harder.
Notion solved vector search scaling in two years. The next bottleneck — offline context engineering, unified data, and the real-time/offline gap — is harder.
Zilliz Cloud Update: Tiered Storage, Business Critical Plan, Cross-Region Backup, and Pricing Changes
This release offers a rebuilt tiered storage with lower costs, a new Business Critical plan for enhanced security, and pricing updates, among other features.
DeepSeek-VL2: Mixture-of-Experts Vision-Language Models for Advanced Multimodal Understanding
Explore DeepSeek-VL2, the open-source MoE vision-language model. Discover its architecture, efficient training pipeline, and top-tier performance.