Datalog 作为一种声明式的逻辑编程语言，长期以来主要在 CPU 上进行优化执行。然而，随着数据规模爆炸式增长和并行计算需求的提升，将 Datalog 迁移到 GPU 架构上成为必然趋势。ASPLOS'25 会议上发表的 GPULog 论文给出了答案：通过对核心数据结构和算法的深度优化，显著提升了 Datalog 在 GPU 上的执行性能。
核心创新：hash-indexed sorted array 三层架构
GPULog 的关键突破在于设计了专门适配 GPU 并行架构的 hash-indexed sorted array 数据结构。这个创新性设计采用三层结构来优化内存访问模式：
数据数组 (Data Array)：采用行主序 (row-major) 紧密存储的元组数据，这是基础的数据层。在 GPU 架构中，紧密存储模式能够最大化内存带宽利用率，减少缓存失效。
排序索引数组 (Sorted Index Array)：存储指向数据数组的指针，严格按照词法顺序排序，连接键 (join keys) 享有更高的排序优先级。这一层实现了高效的邻接访问模式，特别适合 GPU 的并行处理单元。
哈希表 (Hash Table)：采用开放地址法的哈希表，将连接键的哈希值映射到排序索引数组中匹配区域的起始位置。关键在于，哈希表不是存储实际数据，而是存储排序索引数组中的指针，从而实现 O (1) 的定位复杂度。
这种设计的精髓在于：将哈希表的快速查找能力与排序数组的内存局部性优势完美结合，在 GPU 的大规模并行环境下能够显著减少内存访问延迟。
半朴素评估的 GPU 实现
理解 GPULog 的性能优势，必须深入分析半朴素评估算法在 GPU 上的实现机制。传统半朴素评估将关系中的元组分为三个桶：
new 桶：存储当前迭代中新发现的元组
delta 桶：存储上轮迭代中添加的元组
full 桶：存储所有迭代中发现的所有元组
对于涉及两个关系 A 和 B 的连接操作，GPULog 实现了三阶段 JOIN 策略：
- delta (A) 与 full (B) 的连接
- full (A) 与 delta (B) 的连接
- delta (A) 与 delta (B) 的连接
核心优化在于：full (A) 与 full (B) 从不直接连接，这避免了大量的冗余计算。在 GPU 实现中，这种算法结构完美契合了并行化的需求，每个 GPU 线程可以独立处理一个连接操作，避免了锁竞争和同步开销。
性能瓶颈与优化策略
通过详细的性能分析，GPULog 团队发现：内存带宽而非计算能力是主要瓶颈。这一发现具有重要的工程指导意义。
在 GPU 架构中，单个算术逻辑单元 (ALU) 的计算能力远超内存带宽。传统的优化思路是提升算法复杂度来减少计算量，但在 GPU 环境下，更有效的策略是优化内存访问模式来减少内存流量。
hash-indexed sorted array 的内存访问模式优化体现在两个方面：
- 遍历排序索引数组时的内存访问是连贯的，避免了随机内存访问的性能损失
- 访问数据数组时的内存访问在元组元素数量范围内保持连贯，进一步提升了缓存利用率
论文实验数据显示，GPULog 相比最先进的 CPU 实现 Soufflé 有显著性能提升。特别值得注意的是，当算法移植到 AMD 的 HIP 运行时后，在相同的 NVIDIA GPU 上运行，仍然保持了优异的性能，这证明了算法设计的通用性和跨平台的可行性。
工程实践价值与未来展望
GPULog 的成功不仅在于算法创新，更重要的是它提供了 GPU 上执行逻辑编程的工程模板。核心数据结构的设计原理可以迁移到其他领域：
列式存储的推广：在 GPU 上处理关系数据时，采用列式存储结合 SIMD 并行指令，能够显著提升数据密集型应用的性能。
内存访问模式优化：对于任何需要频繁随机访问的数据结构，设计时都应该考虑内存访问的局部性，将快速查找与内存局部性结合。
跨硬件平台的算法设计：GPULog 在 NVIDIA 和 AMD GPU 上的良好性能表现表明，精心设计的算法可以突破特定硬件的局限，具备更广泛的适用性。
展望未来，随着 GPU 内存容量的增长和 HBM (高带宽内存) 技术的普及，GPULog 这类 GPU 加速的逻辑编程框架将在知识图谱推理、程序分析、数据库查询等领域发挥重要作用。关键在于持续优化内存访问模式，最大化利用 GPU 的并行计算能力。
参考资料来源：
- Optimizing Datalog for the GPU - ASPLOS'25 论文 - 对 GPULog 核心算法和数据结构的深入解析
- Semi-naïve Evaluation 算法详解 - 论文中引用的半朴素评估理论基础