GPU Filters · SALT Systems Lab

Overview

Filters store a set approximately, giving up a little accuracy for a lot of space efficiency. That trade-off matters on accelerators like GPUs, where memory is limited. Most filter research has focused on CPUs, though, so there were few fast, full-featured GPU filters.

This project explores the design space of GPU filters and introduces two new ones. The Two-Choice Filter (TCF) provides fast set membership. The GPU Quotient Filter (GQF) adds counting at some performance cost. Both have point and bulk APIs, and they are up to 4.4× and 1.4× faster than earlier GPU filters.

Key features

Two-Choice Filter (TCF)

Template components for point key-value structures, with configurable layout, access pattern, and false-positive rate.

Bulk TCF

A TCF optimized for bulk data that groups keys with Thrust.

GPU Quotient Filter (GQF)

Inserts, queries, deletes, counting, and key-value association, with a reduction scheme for Zipfian workloads.

Easy integration

Add the library with CPM in one CMake snippet.

Add to CMake

include(cmake/CPM.cmake)

CPMAddPackage(
  NAME gpu-filters
  GITHUB_REPOSITORY saltsystemslab/gpu-filters
  GIT_TAG origin/main
)

Citation

@inproceedings{mccoy2023gpufilters,
  author    = {McCoy, Hunter and Hofmeyr, Steven and Yelick, Katherine and Pandey, Prashant},
  title     = {High-Performance Filters for GPUs},
  booktitle = {Proceedings of the 28th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP)},
  year      = {2023},
  doi       = {10.1145/3572848.3577507}
}