Высокопроизводительная реализация CUDA структуры данных Cuckoo Filter, разработанная в рамках дипломной работы «Проектирование и оценка фильтра Cuckoo с графическим ускорением».
Эта библиотека предоставляет реализацию Cuckoo Filter с ускорением на графическом процессоре, оптимизированную для пакетных операций с высокой пропускной способностью. Фильтры кукушки — это вероятностные структуры данных с эффективным использованием пространства, которые поддерживают операции вставки, поиска и удаления с настраиваемой частотой ложных срабатываний.
- Пакетные операции вставки, поиска и удаления с ускорением CUDA.
- Настраиваемый размер отпечатка пальца и размер сегмента
- Множественные политики выселения (DFS, BFS)
- Режим отсортированной вставки для улучшения объединения памяти.
- Поддержка нескольких графических процессоров через слух
- Поддержка IPC для совместного использования фильтров между процессами
- Дизайн библиотеки только для заголовков
Тесты при коэффициенте загрузки 80 % на NVIDIA GH200 (H100 HBM3, 3,4 ТБ/с). Фильтр Cuckoo GPU сравнивается с:
| Сравнение | Вставлять | Запрос | Удалить |
|---|---|---|---|
| Графический процессор против процессора Cuckoo | На 360× быстрее | 973× быстрее | Н/Д |
| Кукушка против TCF | в 6 раз быстрее | в 42 раза быстрее | в 100 раз быстрее |
| Кукушка против GQF | 585× быстрее | в 6 раз быстрее | в 273× быстрее |
| Кукушка против Блум | 0,6× (медленнее) | в 1,4 раза быстрее | Н/Д |
| Сравнение | Вставлять | Запрос | Удалить |
|---|---|---|---|
| Графический процессор против процессора Cuckoo | 583× быстрее | 1504× быстрее | Н/Д |
| Кукушка против TCF | 1,9× быстрее | 11,3× быстрее | 35,3× быстрее |
| Кукушка против GQF | 9,6× быстрее | 2,6× быстрее | в 3,8× быстрее |
| Кукушка против Блум | 0,7× (медленнее) | 1,0× (равно) | Н/Д |
Примечание
Более полную оценку, включая дополнительные системы и анализ, см. в прилагаемом документе. диссертация.
- Инструментарий CUDA (>= 12,9)
- C++20-совместимый компилятор
- Система сборки Meson (>= 1.3.0)
meson setup build
meson compile -C build
Бенчмарки и тесты создаются по умолчанию. Чтобы отключить их:
meson setup build -DBUILD_BENCHMARKS=false -DBUILD_TESTS=false
#include <CuckooFilter.cuh>
// Configure the filter: key type, fingerprint bits, max evictions, block size, bucket size
using Config = CuckooConfig<uint64_t, 16, 500, 256, 16>;
// Create a filter with the desired capacity
CuckooFilter filter(1 << 20); // capacity for ~1M items
// Insert keys (d_keys is a device pointer)
filter.insertMany(d_keys, numKeys);
// Or use sorted insertion
filter.insertManySorted(d_keys, numKeys);
// Check membership
filter.containsMany(d_keys, d_results, numKeys);
// Delete keys
filter.deleteMany(d_keys, d_results, numKeys);
CuckooConfig шаблон принимает следующие параметры:
| Параметр | Описание | По умолчанию |
|---|---|---|
T |
Тип ключа | – |
bitsPerTag |
Размер отпечатка пальца в битах (8, 16, 32) | – |
maxEvictions |
Максимальное количество попыток выселения до неудачи | 500 |
blockSize |
Размер блока CUDA | 256 |
bucketSize |
Количество слотов в сегменте (должна быть степенью 2) | 16 |
AltBucketPolicy |
Альтернативная политика расчета сегментов | XorAltBucketPolicy |
evictionPolicy |
Стратегия выселения (DFS или BFS) | BFS |
WordType |
Атомный тип (uint32_t или uint64_t) | uint64_t |
Для рабочих нагрузок, превышающих мощность одного графического процессора:
КукушкаФильтрМультиГП
#include <CuckooFilterMultiGPU.cuh> CuckooFilterMultiGPUfilter(numGPUs, totalCapacity); filter.insertMany(h_keys, numKeys); filter.containsMany(h_keys, h_results, numKeys);
include/ - Header files
CuckooFilter.cuh - Main filter implementation
CuckooFilterMultiGPU.cuh - Multi-GPU implementation
CuckooFilterIPC.cuh - IPC support
bucket_policies.cuh - Alternative bucket policies
helpers.cuh - Helper functions
src/ - Example applications
benchmark/ - benchmarks
tests/ - Unit tests
scripts/ - Scripts for running/plotting benchmarks
