在GPU上的快速Equi-Join算法:设计和实施
1Department of Computer Science and Engineering, University of South Florida, 4202 E. Fowler Ave., ENB 118, Tampa, Florida 33620, USA.
概括
新的GPU连接算法明显优于现有方法,在现代硬件上实现了哈希连接的14.6X加快和排序合并连接的4.9X加快. 这些进步优化了科学数据库引擎,以提高性能.
科学领域:
- 计算机科学 计算机科学
- 数据库系统 数据库系统
- 高性能计算 高性能计算
背景情况:
- 现代图形处理单元 (GPU) 提供了显著的并行处理能力.
- 现有的GPU连接算法通常对于当前的GPU架构和编程框架来说是不理想的.
- 有效的关系连接处理对于科学数据库引擎至关重要.
研究的目的:
- 为当代GPGPU环境设计和实施高性能GPU连接算法.
- 为了利用Nvidia最新的GPU架构和CUDA功能来优化连接处理.
- 为了提高G-SDMS科学数据库引擎的性能.
主要方法:
- 彻底修复了 radix 哈希连接算法.
- 重新设计了GPUs的排序合并合并算法.
- 应用了使用修订后的硬件 (注册表,共享内存),原子运算,动态并行和CUDA流的新技术.
- 扩展了对超出内存数据集的算法.
主要成果:
- 新的哈希连接算法比现有的GPU实现效率高2.0至14.6倍.
- 新的排序-合并连接算法实现了4.0X至4.9X的加快速度.
- 与CPU同行相比,优化的GPU算法显示高达10.5X (排序合并) 和5.5X (哈希连接) 的速度.
结论:
- 开发的GPU连接算法有效地利用现代硬件和CUDA功能.
- 与现有的GPU和CPU实现相比,表现出了显著的性能改进.
- 这些算法为连接处理提供了可扩展的解决方案,即使大型数据集超过了GPU内存.
相关概念视频
Parallel Processing
152
The brain processes sensory information rapidly due to parallel processing, which involves sending data across multiple neural pathways at the same time. This method allows the brain to manage various sensory qualities, such as shapes, colors, movements, and locations, all concurrently. For instance, when observing a forest landscape, the brain simultaneously processes the movement of leaves, the shapes of trees, the depth between them, and the various shades of green. This enables a quick and...
152
Vector Operations
1.3K
Vectors are physical quantities that have both magnitude and direction. The vector operations include addition, subtraction, and scalar multiplication.
A vector multiplied by a scalar value is called scalar multiplication. The result obtained is a new vector with a different magnitude. If the scalar is positive, the direction of the vector remains the same, but if it is negative, the direction of the vector is reversed. For example, the product of the mass and velocity yields the momentum.
A vector multiplied by a scalar value is called scalar multiplication. The result obtained is a new vector with a different magnitude. If the scalar is positive, the direction of the vector remains the same, but if it is negative, the direction of the vector is reversed. For example, the product of the mass and velocity yields the momentum.
1.3K
Vector Algebra: Graphical Method
12.2K
Vectors can be multiplied by scalars, added to other vectors, or subtracted from other vectors. The vector sum of two (or more) vectors is called the resultant vector or, for short, the resultant.
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...
12.2K
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
55
Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
55
Fast Fourier Transform
326
The Fast Fourier Transform (FFT) is a computational algorithm designed to compute the Discrete Fourier Transform (DFT) efficiently. By breaking down the calculations into smaller, manageable sections, the FFT significantly reduces the computational complexity involved. Direct computation of an N-point DFT requires N2 complex multiplications, whereas the FFT algorithm needs only (N/2)log2N multiplications, offering a much faster performance.
The computational efficiency of the FFT becomes...
The computational efficiency of the FFT becomes...
326
Fast Decoupled and DC Powerflow
192
The fast decoupled power flow method addresses contingencies in power system operations, such as generator outages or transmission line failures. This method provides quick power flow solutions, essential for real-time system adjustments. Fast decoupled power flow algorithms simplify the Jacobian matrix by neglecting certain elements, leading to two sets of decoupled equations:
192


