Date of Award

6-26-2026

Date Published

August 2026

Degree Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Electrical Engineering and Computer Science

Advisor(s)

Kristopher Micinski

Subject Categories

Computer Sciences | Physical Sciences and Mathematics

Abstract

Deductive logic reasoning has evolved from a theoretical symbolic artificial intelligence tool into a massive computational workload. Modern domains, ranging from static program analysis and binary reverse engineering to knowledge-graph reasoning, rely on Datalog, a logical query language, to express deeply recursive, declarative specifications. However, scaling logic reasoning to these industrial workload exposes two interlocking ceilings in traditional engines. Architecturally, the memory bandwidth and parallel throughput of single-node CPUs fall drastically short of the read- and write-heavy demands of semi-naive evaluation. Asymptotically, traditional query processing algorithms, such as binary join algorithms generate massive intermediate relations that exhaust device memory on the cyclic queries typical of real-world analyses. Lifting these ceilings requires a fundamental shift to High-Performance Computing (HPC) hardware. This dissertation bridges this gap, establishing modern GPU-accelerated HPC architectures as a viable, high-performance platform for scalable logic reasoning. It contributes four novel Datalog engines that progressively codesign storage layouts, indexing strategies, join algorithms, and inter-rule scheduling for the SIMT execution model. First, GDlog demonstrates that lock-free, GPU-native evaluation can decisively outperform state-of-the-art CPU baselines by utilizing a count-then-materialize pipeline and a novel Hash-Indexed Sorted Array (HISA). Second, \textbf{MNMG-Datalog} scales this foundation horizontally to supercomputing clusters, introducing the first multi-node multi-GPU Datalog engine using CUDA-aware MPI and monotonicity-aware recursive aggregation. Third, FVLog explores the storage axis, proving that flat, column-oriented data layouts combined with eager delta merging maximize GPU memory bandwidth on projection-heavy reasoning workloads. Finally, SRDatalog addresses the asymptotic algorithmic ceiling by introducing the first GPU implementation of worst-case optimal multi-way joins (WCOJ) for iterative recursive workloads. Utilizing histogram-guided load balancing and stream-parallel scheduling, SRDatalog successfully executes the deeply recursive, cyclic queries of production program analysis end-to-end, overcoming the memory exhaustion failures of prior binary-join engines. Collectively, these four engines articulate a coherent design discipline for scaling logic reasoning on modern accelerators: prioritizing memory bandwidth, flat storage, and bulk-synchronous phase alignment. By achieving speedups of an order of magnitude or more over gold-standard CPU baselines across industrial-scale workloads, this dissertation proves that hardware-software codesign can successfully push declarative logic reasoning to supercomputing scales.

Access

Open Access

Download

Share

COinS