[HN Gopher] GDlog: A GPU-Accelerated Deductive Engine ___________________________________________________________________ GDlog: A GPU-Accelerated Deductive Engine Author : PaulHoule Score : 53 points Date : 2023-12-03 18:08 UTC (4 hours ago) (HTM) web link (arxiv.org) (TXT) w3m dump (arxiv.org) | westurner wrote: | "GDlog: A GPU-Accelerated Deductive Engine" (2023) | https://arxiv.org/abs/2311.02206 : | | > Abstract: _Modern deductive database engines (e.g., LogicBlox | and Souffle) enable their users to write declarative queries | which compute recursive deductions over extensional data, leaving | their high-performance operationalization (query planning, semi- | naive 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._ | convexstrictly wrote: | Github repo | | https://github.com/harp-lab/gdlog | convexstrictly wrote: | The paper claims it builds upon the concepts in HashGraph, an | efficient CUDA hashtable implementation. | | HashGraph (2019) https://arxiv.org/abs/1907.02900 | | Anyone know what the most performant CUDA hash table | implementations are these days? ___________________________________________________________________ (page generated 2023-12-03 23:00 UTC)