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