GPU 架构上的 Datalog 优化：内存访问模式与数据结构设计深度解析
近期在 Dangling Pointers 上读到一篇关于在 GPU 上优化 Datalog 执行的技术文章，其中介绍的 GPULog 系统采用了一种独特的 hash-indexed sorted array 数据结构来解决 GPU 并行计算中的关键挑战。这个设计不仅仅是一个数据结构的创新，更是对 GPU 内存层次结构和并行计算模型的深度理解和工程化应用。
核心挑战：GPU 上的半朴素求值
Datalog 的核心计算模式是通过半朴素求值（Semi-naïve Evaluation）来迭代执行规则直到达到不动点。在传统的 CPU 实现中，这涉及管理三个数据桶：new（当前轮次新发现的元组）、delta（上一轮次添加的元组）和 full（所有已发现的元组）。在 GPU 上实现这一算法面临独特挑战：
首先是内存带宽限制。GPU 计算单元的性能远超其内存子系统，而半朴素求值本质上是一个 I/O 密集型操作，不断在内存中读写大量元组数据。论文作者指出 GPULog 的性能主要受内存带宽限制而非计算能力限制，这凸显了内存访问优化在 GPU Datalog 实现中的关键重要性。
其次是并行性管理。GPU 上通常有数千个计算核心同时工作，而半朴素求值涉及复杂的依赖关系和数据流管理。如何在保证正确性的同时充分利用 GPU 的大规模并行能力，是系统设计必须解决的核心问题。
Hash-Indexed Sorted Array 的设计哲学
GPULog 引入的 hash-indexed sorted array 体现了对 GPU 架构特点的深度理解。该结构由三个组件构成：密集打包的数据数组、按连接键排序的索引数组，以及开放式寻址哈希表。
设计的关键洞察在于平衡了哈希表的快速查找能力与排序数组的高效范围扫描特性。哈希表提供 O (1) 时间复杂度的首元素查找，而排序后的索引数组使得具有相同连接键的所有元组能够连续存储，从而实现高效的批处理。
这种设计在 GPU 上具有天然优势。GPU 的内存控制器能够批量加载连续内存块，当线程束中的多个线程访问排序索引数组中相邻元素时，内存访问会自动合并成一次高效的内存事务。这种内存合并（memory coalescing）机制是 GPU 性能优化的核心，而 GPULog 的数据结构设计充分利用了这一特性。
内存访问模式的工程优化
从工程角度看，GPULog 最有价值的贡献在于其内存访问模式的系统性优化。在连接操作中，系统首先通过哈希表定位第一个匹配的元组，然后利用排序后的索引数组进行范围扫描。这种模式避免了传统的哈希连接中每个匹配元组都需要进行哈希查找的开销。
具体而言，当执行连接操作 A ⋈ B 时，算法对 A 的每个元组在哈希表中查找 B 中第一个匹配的元组，然后线性扫描所有匹配元组。这种方法将哈希查找的次数从匹配元组数量减少到 1，同时利用了 GPU 的批量内存访问优势。
对数据数组的访问虽然不能完全合并（因为元组可能分散存储），但访问模式仍然是相对规则的。考虑到现代 GPU 具有大容量且相对高带宽的全局内存，这种部分合并的访问模式在实际性能上是可以接受的。
GPU 并行模型与算法适配
GPULog 的设计还体现了对 GPU 并行计算模型的理解。传统的 CPU 优化技术如缓存友好的数据布局，在 GPU 上需要重新设计。GPU 的内存层次结构更浅，但带宽更高，这要求算法设计者从数据并行而非任务并行的角度思考问题。
hash-indexed sorted array 使得连接操作能够自然地映射到 GPU 的线程模型。每个 GPU 线程可以负责处理一个或多个输入元组，而连接查找和范围扫描操作能够充分利用 GPU 的大规模并行能力。同时，排序后的数据布局确保了不同线程之间的内存访问模式相对独立，减少了内存银行冲突。
性能权衡与架构通用性
从性能分析的角度，GPULog 的方法体现了内存密集型操作在现代处理器架构上的一般优化原则。虽然当前实现针对的是 GPU，但数据结构设计本身具有跨平台通用性。哈希表加排序数组的组合在 FPGA、SmartNIC 等其他并行架构上同样可能有效。
这种设计思想对于其他查询处理系统也具有启发意义。在数据密集型应用中，如何平衡查找效率与顺序访问优势，如何优化数据布局以适应目标硬件的内存访问特性，这些都是系统设计者需要持续思考的问题。
GPULog 的 hash-indexed sorted array 代表了对 GPU 架构特点的深度工程化理解，它不仅仅是一个数据结构的创新，更是对现代并行计算环境下数据处理算法设计的系统性思考。这种设计方法论对于构建高效的 GPU 加速数据库系统具有重要的参考价值。
基于 Dangling Pointers 对 "Optimizing Datalog for the GPU"（ASPLOS'25）的技术分析整理而成。