Boolean Matrix Logic Programming on the GPU
This work addresses scalability and efficiency issues in logic programming for researchers and practitioners dealing with large-scale inference tasks, representing a novel paradigm shift rather than an incremental improvement.
The paper tackled the performance limitations of traditional logic programming for large-scale inference by introducing Boolean Matrix Logic Programming (BMLP) for GPU acceleration, achieving 1-4 orders of magnitude speed up over state-of-the-art systems on tasks like reachability queries in large graphs and the Freebase 15K dataset.
Traditional logic programming relies on symbolic computation on the CPU, which can limit performance for large-scale inference tasks. Recent advances in GPU hardware enable high-throughput matrix operations, motivating a shift toward parallel logic inference. Boolean Matrix Logic Programming (BMLP) introduces a novel approach to datalog query evaluation using Boolean matrix algebra, well-suited to GPU acceleration. Building on this paradigm, we present two GPU-accelerated BMLP algorithms for bottom-up inference over linear dyadic recursive datalog programs. We further extend the BMLP theoretical framework to support general linear recursion with binary predicates. Empirical evaluations on reachability queries in large directed graphs and the Freebase 15K dataset show that our methods achieve 1-4 orders of magnitude speed up over state-of-the-art systems. These results demonstrate that Boolean matrix-based reasoning can significantly advance the scalability and efficiency of logic programming on modern hardware. Source code is available on https://github.com/lun-ai/BMLP.git.