28741

GDlog: A GPU-Accelerated Deductive Engine

Yihao Sun, Ahmedur Rahman Shovon, Thomas Gilray, Kristopher Micinski, Sidharth Kumar
Syracuse University, Syracuse, USA
arXiv:2311.02206 [cs.DB], (3 Nov 2023)

@misc{sun2023gdlog,

   title={GDlog: A GPU-Accelerated Deductive Engine},

   author={Yihao Sun and Ahmedur Rahman Shovon and Thomas Gilray and Kristopher Micinski and Sidharth Kumar},

   year={2023},

   eprint={2311.02206},

   archivePrefix={arXiv},

   primaryClass={cs.DB}

}

Download Download (PDF)   View View   Source Source   

361

views

Modern deductive database engines (e.g., LogicBlox and Soufflé) enable their users to write declarative queries which compute recursive deductions over extensional data, leaving their high-performance operationalization (query planning, semi-naïve evaluation, and parallelization) to the engine. Such engines form the backbone of modern high-throughput applications in static analysis, security auditing, social-media mining, and business analytics. State-of-the-art engines are built upon nested loop joins over explicit representations (e.g., BTrees and tries) and ubiquitously employ range indexing to accelerate iterated joins. In this work, we present GDlog: a GPU-based deductive analytics engine (implemented as a CUDA library) which achieves significant performance improvements (5–10x or more) versus prior systems. GDlog is powered by a novel range-indexed SIMD datastructure: the hash-indexed sorted array (HISA). We perform extensive evaluation on GDlog, comparing it against both CPU and GPU-based hash tables and Datalog engines, and using it to support a range of large-scale deductive queries including reachability, same generation, and context-sensitive program analysis. Our experiments show that GDlog achieves performance competitive with modern SIMD hash tables and beats prior work by an order of magnitude in runtime while offering more favorable memory footprint.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2024 hgpu.org

All rights belong to the respective authors

Contact us: