Parallel Processing Research
Optimal Implementation of And-Or Parallel Prolog
Invited Paper, Future Generation Computer Systems,
Vol 10, No. 1, pp. 71-92,
Elsevier Science Publishers, Apr. 1994.
Author(s)
Gopal Gupta,
Vitor Santos Costa
Abstract
Most models that have been proposed, or implemented, so far for
exploiting both or-parallelism and independent and-parallelism have only
considered pure logic programs (pure Prolog).
We present an abstract model, called the Composition-Tree,
for representing and-or parallelism in full Prolog.
The Composition-Tree recomputes independent goals to ensure
that Prolog semantics is preserved. We combine the idea of
Composition-Tree
with ideas developed earlier, to develop an abstract execution
model that supports full Prolog semantics while at the same time
avoiding redundant inferences when computing solutions
to (purely) independent and-parallel goals. This is accomplished
by sharing solutions of independent goals when they are
pure (i.e. have no side-effects or cuts in them).
The Binding Array scheme is extended for and-or parallel
execution based on this abstract execution model. This extension
enables the Binding Array scheme to support or-parallelism in
the presence of independent and-parallelism, both when
solutions to independent goals are recomputed as well as when
they are shared.
We show how extra-logical predicates, such as cuts
and side-effects, are supported in this model.
The whole paper
can be downloaded from our
server.
Parallel Proc. Page Research Page Lab Home Page