On Applying Or-Parallelism and Tabling to Logic Programs
Ricardo Rocha, Fernando Silva and VĂtor Santos Costa
2005
Abstract
Logic Programming languages, such as Prolog, provide a high-level,
declarative approach to programming. Logic Programming offers great
potential for implicit parallelism, thus allowing parallel systems to
often reduce a program's execution time without programmer
intervention. We believe that for complex applications that take
several hours, if not days, to return an answer, even limited speedups
from parallel execution can directly translate to very significant
productivity gains.
It has been argued that Prolog's evaluation strategy - SLD resolution
- often limits the potential of the logic programming paradigm. The
past years have therefore seen widening efforts at increasing Prolog's
declarativeness and expressiveness. Tabling has proved to be a viable
technique to efficiently overcome SLD's susceptibility to infinite
loops and redundant subcomputations.
Our research demonstrates that implicit or-parallelism is a natural
fit for logic programs with tabling. To substantiate this belief, we
have designed and implemented an or-parallel tabling engine - OPTYap -
and we used 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.
Preliminary results indicate 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 the range of applications for Logic Programming can
be increased.
Bibtex
@Article{rocha-tplp05,
author = {R. Rocha and F. Silva and V. Santos Costa},
title = {{On applying or-parallelism and tabling to logic programs}},
journal = {Journal of Theory and Practice of Logic Programming},
pages = {161--205},
volume = {5},
number = {1 \& 2},
year = {2005},
}
Download Paper
PDF file
Cambridge University Press
Computing Research Repository (CoRR)