On a Tabling Engine That Can Exploit Or-Parallelism
Ricardo Rocha, Fernando Silva and VĂtor Santos Costa
November 2001
Abstract
Tabling is an implementation technique that improves the
declarativeness and expressiveness of Prolog by reusing solutions to
goals. Quite a few interesting applications of tabling have been
developed in the last few years, and several are by nature
non-deterministic. This raises the question of whether parallel search
techniques can be used to improve the performance of tabled
applications.
In this work we demonstrate that the mechanisms proposed to
parallelize search in the context of SLD resolution naturally
generalize to parallel tabled computations, and that resulting systems
can achieve good performance on multi-processors. To do so, we present
the OPTYap parallel engine. In our system individual SLG engines
communicate data through stack copying. Completion is detected
through a novel parallel completion algorithm that builds upon the
data structures proposed for or-parallelism. Scheduling is simplified
by building on previous research on or-parallelism. We show initial
performance results for our implementation. Our best result is for an
actual application, model checking, where we obtain linear speedups.
Bibtex
@InProceedings{rocha-iclp01,
author = {R. Rocha and F. Silva and V. Santos Costa},
title = {{On a Tabling Engine That Can Exploit Or-Parallelism}},
booktitle = {Proceedings of the 17th International Conference on Logic Programming (ICLP 2001)},
pages = {43--58},
number = {2237},
series = {LNCS},
publisher = {Springer},
editor = {P. Codognet},
month = {November/December},
year = {2001},
address = {Paphos, Cyprus},
}
Download Paper
PDF file
Springer
Download Slides
PDF file