本文“为GPU优化Datalog”,介绍了GPULog系统,该系统旨在高效地在GPU上执行Datalog程序。Datalog程序通过显式元组和隐式规则定义关系,评估过程持续到达到不动点——本质上是重复的类似SQL的连接操作。作者利用半朴素评估算法,通过将元组分为“新”、“增量”和“全”三个桶来避免冗余计算,从而进行优化。 GPULog的核心创新是一种新型数据结构:哈希索引排序数组。该结构结合了紧凑的数据数组、用于高效查找的词法排序索引数组以及用于快速定位索引内起始点的哈希表。这使得能够实现连贯的内存访问模式,对于GPU性能至关重要。 结果表明,GPULog的性能显著优于最先进的CPU Datalog实现(Soufflé),即使后者通过HIP移植到相同的GPU硬件上也是如此。作者认为,内存带宽而非计算是主要的性能瓶颈,为未来研究减少带宽的Datalog算法开辟了道路。