Uma implementação CUDA de alto desempenho da estrutura de dados do Filtro Cuckoo, desenvolvida como parte da tese “Projeto e Avaliação de um Filtro Cuckoo Acelerado por GPU”.
Esta biblioteca fornece uma implementação de filtro Cuckoo acelerada por GPU otimizada para operações em lote de alto rendimento. Filtros Cuckoo são estruturas de dados probabilísticas com uso eficiente de espaço que suportam operações de inserção, pesquisa e exclusão com uma taxa de falsos positivos configurável.
- Operações de inserção, pesquisa e exclusão em lote aceleradas por CUDA
- Tamanho configurável da impressão digital e tamanho do balde
- Múltiplas políticas de despejo (DFS, BFS)
- Modo de inserção classificado para melhor coalescência de memória
- Suporte multi-GPU via fofoca
- Suporte IPC para compartilhamento de filtro entre processos
- Design de biblioteca somente de cabeçalho
Benchmarks com fator de carga de 80% em um NVIDIA GH200 (H100 HBM3, 3,4 TB/s). O Filtro GPU Cuckoo é comparado com:
Residente L2 (4 milhões de itens, ~8 MiB)
| Comparação | Inserir | Consulta | Excluir |
|---|---|---|---|
| GPU vs CPU Cuco | 360× mais rápido | 973× mais rápido | N / D |
| Cuco vs TCF | 6× mais rápido | 42× mais rápido | 100× mais rápido |
| Cuco vs GQF | 585× mais rápido | 6× mais rápido | 273× mais rápido |
| Cuco vs Flor | 0,6× (mais lento) | 1,4× mais rápido | N / D |
Residente em DRAM (268 milhões de itens, ~512 MiB)
| Comparação | Inserir | Consulta | Excluir |
|---|---|---|---|
| GPU vs CPU Cuco | 583× mais rápido | 1504× mais rápido | N / D |
| Cuco vs TCF | 1,9× mais rápido | 11,3× mais rápido | 35,3× mais rápido |
| Cuco vs GQF | 9,6× mais rápido | 2,6× mais rápido | 3,8× mais rápido |
| Cuco vs Flor | 0,7× (mais lento) | 1,0× (igual) | N / D |
Observação
Para uma avaliação mais abrangente, incluindo sistemas e análises adicionais, consulte a tese anexa.
- Kit de ferramentas CUDA (>= 12,9)
- Compilador compatível com C++20
- Sistema de construção Meson (>= 1.3.0)
meson setup build
meson compile -C buildBenchmarks e testes são criados por padrão. Para desativá-los:
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); O CuckooConfig modelo aceita os seguintes parâmetros:
| Parâmetro | Descrição | Padrão |
|---|---|---|
T | Tipo de chave | – |
bitsPerTag | Tamanho da impressão digital em bits (8, 16, 32) | – |
maxEvictions | Máximo de tentativas de despejo antes do fracasso | 500 |
blockSize | Tamanho do bloco CUDA | 256 |
bucketSize | Slots por bucket (deve ter potência de 2) | 16 |
AltBucketPolicy | Política alternativa de cálculo de intervalo | XorAltBucketPolicy |
evictionPolicy | Estratégia de despejo (DFS ou BFS) | BFS |
WordType | Tipo atômico (uint32_t ou uint64_t) | uint64_t |
Para cargas de trabalho que excedem a capacidade de uma única GPU:
#include <CuckooFilterMultiGPU.cuh>
CuckooFilterMultiGPU filter(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
Fonte: theverge
