Logic Programming Research
Last Parallel Call Optimization and Fast Backtracking
in And-Parallel Logic Programming Systems
Author(s)
Manuel Carro,
DonXing Tang,
Gopal Gupta,
Enrico Pontelli
Abstract
In this paper we present a novel optimization called Last Parallel Call
Optimization. The last parallel call optimization can be regarded as an
extension of last call optimization, found in sequential systems,
to and-parallel systems.
The
last parallel call optimization leads to improved time and space performance
for a majority of
and-parallel programs. The last parallel call optimization is presented in detail
in this paper and its advantages discussed at length. The last parallel call optimization
can be incorporated in a parallel system (such as RAPWAM) through relatively minor
modifications to the runtime machinery.
We also present some experimental results from a limited
implementation of last parallel call operation done on the DDAS System.
These experimental results prove that last parallel call optimization is
indeed effective and
produces better speed-ups with respect to an unoptimized implementation.
We also discuss the problem of
efficiently performing the kill operation in and-parallel systems.
We present two approaches for efficiently
propagating the kill signal to other parallel
calls subsumed by the subgoal that received the kill signal.
The first approach,
implemented in the and-parallel component of
the ACE system, propagates the kill lazily while the second one propagates the
kill signal eagerly. The advantages and disadvantages of both these approaches are
presented. The implementation and optimization techniques presented in this paper
are very pragmatic and we believe that they
will be of considerable utility to implementors of and-parallel
systems.
The whole paper
can be downloaded from our
server.
Logic Prog. Page Research Page Lab Home Page