Towards Iterative Relational Algebra on the GPU
Towards Iterative Relational Algebra on the GPU
复制标题
DOI：
--
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Ahmedur Rahman Shovon;Thomas Gilray;Kristopher K. Micinski;Sidharth Kumar
中科院分区：
文献类型：
--
作者：
Ahmedur Rahman Shovon;Thomas Gilray;Kristopher K. Micinski;Sidharth Kumar
迭代关系代数（定点循环中的 RA 内核）支持自下而上的逻辑编程语言，例如 Dat-alog。对于图挖掘、程序分析和社交媒体分析等领域的关系数据分析的高性能实现来说，此类声明性语言是有吸引力的目标。语言级构造是通过高性能关系代数原语（例如投影、重新排序和连接）来实现的。此类基元似乎是 GPU 的自然目标，可以在大型数据集上获得高吞吐量。然而，最先进的数据记录引擎仍然基于 CPU，在 8-16 个线程之间实现最佳扩展。虽然对 GPU 上的独立 RA 操作进行了很多探索，但相对较少的工作集中在迭代 RA 上，这暴露了新的挑战（例如，重复数据删除和内存管理）。在这篇简短的论文中，我们提出了一种基于 GPU 的哈希连接实现，利用 (a) 一种新颖的基于开放寻址的哈希表实现，(b) 运算符融合来优化内存访问，以及 (c) 两种重复数据删除的变体实现。为了评估我们的工作，我们使用基于哈希连接的 CUDA 库实现传递闭包，并将其性能与 cuDF（基于 GPU）和 Soufflé（基于 CPU）进行比较。我们对两者都显示出良好的结果，增益高达 10 。 8 × 对抗 cuDF 和 3 . 9 × 对阵舒芙蕾。
Iterative relational algebra (RA kernels in a fixed-point loop) enables bottom-up logic programming languages such as Dat-alog. Such declarative languages are attractive targets for high-performance implementations of relational data analytics in fields such as graph mining, program analysis, and social-media analytics. Language-level constructs are implemented via high-performance relational algebra primitives (e.g., projections, reorderings, and joins). Such primitives would appear a natural target for GPUs, obtaining high throughput on large datasets. However, state-of-the-art Datalog engines are still CPU-based, scaling best between 8–16 threads. While much has explored standalone RA operations on the GPU, relatively less work focuses on iterative RA, which exposes new challenges (e.g., deduplication and memory management). In this short paper, we present a GPU-based hash-join implementation, leveraging (a) a novel open-addressing-based hash table implementation, (b) operator fusing to optimize memory access and (c) two variant implementations of deduplication. To evaluate our work, we implement transitive closure using our hash-join-based CUDA library and compared its performance against cuDF (GPU-based) and Soufflé (CPU-based). We show favorable results against both, with gains up to 10 . 8 × against cuDF and 3 . 9 × against Soufflé.