TL;DR
This paper introduces WarpCore (WC), a highly efficient and flexible GPU library for hash tables. WC significantly outperforms existing GPU hash table solutions, especially at high load factors, by leveraging novel parallel probing schemes and device-side operations. It also introduces multi-GPU support and demonstrates its utility in accelerating a real-world bioinformatics application.
What Problem Does This Paper Address?
Hash tables are fundamental data structures used across many fields, including bioinformatics and deep learning, due to their efficient key-value storage and retrieval. However, traditional CPU-based hash table implementations struggle with the massive datasets and parallel processing demands of modern applications. While GPUs offer high bandwidth and parallelism, existing GPU hash table solutions often suffer from limitations such as static table construction, poor performance at high load factors, or memory overhead. This paper addresses the need for a flexible, high-performance, and scalable hash table library specifically designed for GPUs.
Methods
WarpCore (WC) is a library that provides a set of optimized GPU implementations for various hash table data structures. Its core innovations include:
- Cooperative Probing Scheme (COPS): A hybrid probing strategy that combines an intra-warp linear probing scheme with an outer double hashing scheme. This ensures data locality within warps while maintaining good overall slot utilization.
- Sub-warp Tiling with Cooperative Groups (CGs): WC utilizes CUDA's Cooperative Groups feature to manage thread execution within warps, allowing for efficient parallel processing of individual elements and batch operations.
- Memory Layout Abstractions: The library supports flexible memory layouts (AOS, SOA, packed AOS) to optimize for different key-value types and access patterns.
- Device-Sided and Host-Sided Interfaces: WC offers both fine-grained device-side operations for integration into CUDA kernels and high-throughput host-side batch operations.
- Memory-Compact Bucket List Hash Table: For multi-value scenarios where memory efficiency is critical, WC introduces a novel bucket list hash table that stores values in linked lists of contiguous memory chunks, with a dynamic growth scheme.
- Multi-GPU Support: WC supports both distributed and independent modes for scaling hash tables across multiple GPUs, leveraging NVLink for efficient communication.
Datasets
The paper does not explicitly list specific datasets used for training. However, it describes the evaluation using:
- Synthetic Datasets: For performance benchmarks, synthetic datasets of 228 unique 4-byte keys with 4-byte values were used, with varying storage densities. For multi-value benchmarks, datasets with varying average numbers of values per key were generated.
- Real-world Bioinformatics Data: For the metagenomic classification use case, datasets consisting of 18 GB of bacterial reference genomes were used for single-GPU benchmarks, and a larger dataset of ~120 GB of bacterial, viral, archaeal, and animal genomes was used for multi-GPU benchmarks.
Key Insights and Ideas
- The power of cooperative probing: The COPS scheme effectively balances intra-warp data locality with global table efficiency, leading to significant performance gains, especially at high load factors where traditional methods falter.
- Flexibility is key: By providing modular building blocks and supporting various memory layouts, WarpCore can be adapted to a wide range of applications and data types, a significant advantage over more rigid existing solutions.
- Multi-value handling is a major bottleneck: Existing solutions struggle with multi-value hash tables, especially when keys have many associated values. WarpCore's bucket list approach offers a robust solution, maintaining performance where others degrade.
- GPU-native operations unlock performance: By enabling operations directly within CUDA kernels, WarpCore avoids costly data transfers and allows for the creation of highly optimized data processing pipelines.
- Multi-GPU scaling is achievable and impactful: The library's support for distributed and independent multi-GPU configurations demonstrates a viable path for handling extremely large datasets that exceed single-GPU memory limits.
Key Results
- Single-Value Performance: WarpCore achieves up to 1.6 billion inserts and 4.3 billion retrievals per second on a GV100 GPU, outperforming cuDPP, SlabHash, and NVIDIA RAPIDS cuDF. This advantage becomes even more pronounced at storage densities above 70%.
- Multi-Value Performance: WarpCore's MultiValueHashTable (WC OA) and BucketListHashTable (WC BL) variants show comparable or superior performance to cuDF, especially for higher key multiplicities. WC BL, in particular, demonstrates strong performance for skewed key distributions.
- Bioinformatics Application: In metagenomic classification, WarpCore achieved speedups of over two orders of magnitude compared to state-of-the-art CPU-based solutions (Kraken2 and MetaCache).
- Multi-GPU Scalability: For large-scale metagenomic database construction on 8 GPUs, WarpCore achieved a speedup of 592x and 317x compared to Kraken2 and MetaCache, respectively.
Limitations and Future Work
- Limitations:
- The paper notes that not all operations on the same hash table can be safely executed concurrently, particularly write operations with other operations of a different kind, due to potential race conditions and ABA problems.
- While WarpCore supports 32-bit and 64-bit data types, the performance benefits are most pronounced when key-value pairs fit within 64-bit words for efficient atomic operations.
- Future Work:
- The authors plan to make the WarpCore library publicly available.
- They suggest that the concepts introduced in WarpCore could serve as a basis for efficient implementations on other accelerators like FPGAs.
- Extending the library to support GPU clusters is a potential future direction.
Summary updated