Modern Datalog on the GPU

2023年11月03日
  • 简介
    现代演绎数据库引擎(例如LogicBlox和Soufflé)使用户能够编写声明性查询,计算关于外延数据的递归推导,将高性能的操作(查询计划、半朴素求值和并行化)留给引擎。这些引擎是现代高吞吐量应用程序(如静态分析、安全审计、社交媒体挖掘和业务分析)的支柱。最先进的引擎基于显式表示(例如BTrees和tries)上的嵌套循环连接,并广泛使用范围索引来加速迭代连接。在这项工作中,我们介绍了GDlog:一种基于GPU的演绎分析引擎(实现为CUDA库),与先前系统相比实现了显着的性能提升(5-10倍或更多)。GDlog采用一种新颖的范围索引SIMD数据结构:哈希索引排序数组(HISA)。我们对GDlog进行了广泛的评估,将其与CPU和GPU基于哈希表和Datalog引擎进行比较,并使用它支持一系列大规模的演绎查询,包括可达性、同代、上下文敏感程序分析等。我们的实验表明,GDlog的性能与现代SIMD哈希表相当,并在运行时比以前的工作快一个数量级,同时提供更有利的内存占用。
  • 图表
  • 解决问题
    本论文旨在解决高吞吐量应用中的递归推断查询的性能问题。
  • 关键思路
    GDlog是一个基于GPU的推理分析引擎,使用哈希索引排序数组(HISA)数据结构实现高效的范围索引。
  • 其它亮点
    GDlog相较于现有系统具有更高的性能和更优秀的内存占用率。论文使用大规模的推理查询进行了广泛的评估,并与CPU和GPU的哈希表和Datalog引擎进行了比较。
  • 相关研究
    现有的推理引擎如LogicBlox和Soufflé都是基于显式表示的嵌套循环连接和范围索引加速迭代连接。
PDF
原文
点赞 收藏 评论 分享到Link

沙发等你来抢

去评论