On Improving the Efficiency of Deterministic Calls and Answers in Tabled Logic Programs
Miguel Areias and Ricardo Rocha
October 2009
Abstract
The execution model on which most tabling engines are based allocates
a choice point whenever a new tabled subgoal is called. This happens
even when the call is deterministic. However, some of the information
from the choice point is never used when evaluating deterministic
tabled calls with batched scheduling. Moreover, when a deterministic
answer is found for a deterministic tabled call, the call can be
completed early and the corresponding choice point can be
removed. Thus, if applying batched scheduling to a long deterministic
computation, the system may end up consuming memory and evaluating
calls unnecessarily. In this paper, we propose a solution that tries
to reduce this memory and execution overhead to a minimum. Our
experimental results show that, for deterministic tabled calls and
tabled answers with batched scheduling, it is possible not only to
reduce the memory usage overhead, but also the running time of the
execution.
Bibtex
@InProceedings{areias-epia09,
author = {M. Areias and R. Rocha},
title = {{On Improving the Efficiency of Deterministic Calls and Answers in Tabled Logic Programs}},
booktitle = {Proceedings of the 14th Portuguese Conference on Artificial Intelligence (EPIA 2009)},
pages = {113--125},
number = {5816},
series = {LNAI},
publisher = {Springer},
editor = {L. S. Lopes and N. Lau and P. Mariano and L. Rocha},
month = {October},
year = {2009},
address = {Aveiro, Portugal},
}
Download Paper
PDF file
Springer
Download Slides
PDF file