[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)