Achieving Scalability in Parallel Tabled Logic Programs
Ricardo Rocha, Fernando Silva and VĂtor Santos Costa
April 2002
Abstract
Tabling or memoing is a technique where one stores intermediate
answers to a problem so that they can be reused in further calls.
Tabling is of interest to logic programming because it addresses some
of most significant weaknesses of Prolog. Namely, it can guarantee
termination for programs with the bounded term-size property. Tabled
programs exhibit a more complex execution mechanism than traditional
Prolog's left-to-right search with backtracking. The reason is that
Prolog programs are highly recursive and generate multiple
answers. This rather involved execution mechanism requires a more
complex implementation than traditional Prolog.
The declarative nature of tabled logic programming suggests that it
might be amenable to parallel execution. On the other hand, the
complexity of the tabling mechanism, and the existence of a shared
resource, the table, argues that parallelism might be limited, and
that performance for real applications might never scale. In this work
we prove that parallel tabling is indeed scalable for real
applications by experimenting the OPTYap parallel tabled system on a
scalable shared-memory machine.
Bibtex
@InProceedings{rocha-ipdps02,
author = {R. Rocha and F. Silva and V. Santos Costa},
title = {{Achieving Scalability in Parallel Tabled Logic Programs}},
booktitle = {Proceedings of the 16th International Parallel and Distributed Processing
Symposium (IPDPS 2002)},
publisher = {IEEE Computer Society},
month = {April},
year = {2002},
address = {Fort Lauderdale, Florida, USA},
}
Download Paper
PDF file
IEEE Computer Society