Speculative Computations in Or-Parallel Tabled Logic Programs

Ricardo Rocha, Fernando Silva and VĂ­tor Santos Costa

September 2004


Abstract

Pruning operators, such as cut, are important to develop efficient logic programs as they allow programmers to reduce the search space and thus discard unnecessary computations. For parallel systems, the presence of pruning operators introduces the problem of speculative computations. A computation is named speculative if it can be pruned during parallel evaluation, therefore resulting in wasted effort when compared to sequential execution. In this work we discuss the problems behind the management of speculative computations in or-parallel tabled logic programs. In parallel tabling, not only the answers found for the query goal may not be valid, but also answers found for tabled predicates may be invalidated. The problem here is even more serious because to achieve an efficient implementation it is required to have the set of valid tabled answers released as soon as possible. To deal with this, we propose a strategy to deliver tabled answers as soon as it is found that they are safe from being pruned, and present its implementation in the OPTYap parallel tabling system.

Bibtex

@InProceedings{rocha-iclp04,
  author =    {R. Rocha and F. Silva and V. Santos Costa},
  title =     {{Speculative Computations in Or-Parallel Tabled Logic Programs}},
  booktitle = {Proceedings of the 20th International Conference on Logic Programming (ICLP 2004)},
  pages =     {254--268},
  number =    {3132},
  series =    {LNCS},
  publisher = {Springer},
  editor =    {B. Demoen and V. Lifschitz},
  month =     {September},
  year =      {2004},
  address =   {Saint-Malo, France},
}

Download Paper

PDF file
Springer

Download Slides

PDF file