Fast Equi-Join Algorithms on GPUs: Design and Implementation.

Area of Science:

• Computer Science
• Database Systems
• High-Performance Computing

Background:

• Modern Graphics Processing Units (GPUs) offer significant parallel processing capabilities.
• Existing GPU join algorithms are often suboptimal for current GPU architectures and programming frameworks.
• Efficient relational join processing is crucial for scientific database engines.

Purpose of the Study:

• To design and implement high-performance GPU join algorithms for contemporary GPGPU environments.
• To leverage the latest Nvidia GPU architecture and CUDA features for optimized join processing.
• To enhance the performance of the G-SDMS scientific database engine.

Main Methods:

• Overhauled the radix hash join algorithm.
• Redesigned the sort-merge join algorithm for GPUs.
• Applied novel techniques utilizing revised hardware (registers, shared memory), atomic operations, dynamic parallelism, and CUDA Streams.
• Extended algorithms for out-of-memory datasets.

Main Results:

• The new hash join algorithm is 2.0 to 14.6 times more efficient than existing GPU implementations.
• The new sort-merge join algorithm achieves a speedup of 4.0X to 4.9X.
• Compared to CPU counterparts, optimized GPU algorithms show up to 10.5X (sort-merge) and 5.5X (hash join) speedup.

Conclusions:

• The developed GPU join algorithms effectively utilize modern hardware and CUDA features.
• Significant performance improvements over existing GPU and CPU implementations were demonstrated.
• The algorithms provide a scalable solution for join processing, even with large datasets exceeding GPU memory.