On Applying Or-Parallelism and Tabling to Logic Programs
Ricardo Rocha
Departamento de Ciência de Computadores & LIACC
Faculdade de Ciências, Universidade do Porto
Rua do Campo Alegre, 823 4150 Porto, Portugal
November 2001
Abstract
Logic programming languages, such as Prolog, provide a high-level,
declarative approach to programming. They offer a great potential for
implicit parallelism and thus allow parallel systems to automatically
reduce a program's execution time without any programmer
intervention. For complex applications that take several hours, if not
days, to return an answer, even modest parallel execution speedups can
be directly translated to very significant productivity gains.
Despite the power, flexibility and good performance that Prolog has
achieved, the past years have seen wide effort at increasing Prolog's
declarativeness and expressiveness. Unfortunately, some deficiencies
in Prolog's evaluation strategy - SLD resolution - limit the potential
of the logic programming paradigm. Tabling has proved to be a viable
technique to efficiently overcome SLD's susceptibility to infinite
loops and redundant subcomputations.
With this research we aim at demonstrating that implicit
or-parallelism is a natural fit for logic programs with tabling. To
substantiate this belief, we propose novel computational models that
integrate tabling with or-parallelism, we design and implement an
or-parallel tabling engine - OPTYap - and we use a shared memory
parallel machine to evaluate its performance. To the best of our
knowledge, OPTYap is the first implementation of a parallel tabling
engine for logic programming systems. OPTYap builds on Yap's efficient
sequential Prolog engine. Its execution model is based on the SLG-WAM
for tabling, and on the environment copying for or-parallelism.
The results in this thesis make it clear that the mechanisms proposed
to parallelize search in the context of SLD resolution can indeed be
effectively and naturally generalized to parallelize tabled
computations, and that the resulting systems can achieve good
performance on shared memory parallel machines. More importantly, it
emphasizes our belief that through applying or-parallelism and tabling
to logic programs we can contribute to increase the range of
applications for Logic Programming.
