Table Space Designs For Implicit and Explicit Concurrent Tabled Evaluation
Miguel Areias and Ricardo Rocha
2018
Abstract
One of the main advantages of Prolog is its potential for the implicit
exploitation of parallelism and, as a high-level language, Prolog is
also often used as a means to explicitly control concurrent
tasks. Tabling is a powerful implementation technique that overcomes
some limitations of traditional Prolog systems in dealing with
recursion and redundant sub-computations. Given these advantages, the
question that arises is if tabling has also the potential for the
exploitation of concurrency/parallelism. On one hand, tabling still
exploits a search space as traditional Prolog but, on the other hand,
the concurrent model of tabling is necessarily far more complex since
it also introduces concurrency on the access to the tables. In this
paper, we summarize Yap's main contributions to concurrent tabled
evaluation and we describe the design and implementation challenges of
several alternative table space designs for implicit and explicit
concurrent tabled evaluation which represent different trade-offs
between concurrency and memory usage. We also motivate for the
advantages of using fixed-size and lock-free data structures,
elaborate on the key role that the engine's memory allocator plays on
such environments, and discuss how Yap’s mode-directed tabling support
can be extended to concurrent evaluation. Finally, we present our
future perspectives towards an efficient and novel concurrent
framework which integrates both implicit and explicit concurrent
tabled evaluation in a single Prolog engine.
Bibtex
@Article{areias-tplp18,
author = {M. Areias and R. Rocha},
title = {{Table Space Designs For Implicit and Explicit Concurrent Tabled Evaluation}},
journal = {Journal of Theory and Practice of Logic Programming},
pages = {950--992},
volume = {18},
number = {5 \& 6},
month = {September},
year = {2018},
}
Download Paper
PDF file
Cambridge University Press
Computing Research Repository (CoRR)