Logic Programming Research
AO-WAM: A WAM Extension for Compiled
And-Or Parallelism
Journal of Logic Programming
Vol.17,No. 1, Oct 1993, pp. 58-89
Author(s)
Gopal Gupta,
Bharat Jayaraman
Abstract
This paper presents an extended and-or tree and an extended WAM
(Warren Abstract Machine) for efficiently supporting both
and-parallel and or-parallel execution of logic
programs on shared-memory multiprocessors.
Our approach for exploiting both and- and or-parallelism
is based on the binding-arrays method for
or-parallelism and the RAP (Restricted And-Parallelism)
method for and-parallelism, the two most successful methods for
implementing or-parallelism and and-parallelism respectively.
Our combined and-or model avoids redundant computations
when goals exhibit both and- and or-parallelism, by
representing the crossproduct of the solutions from the
and-or parallel goals rather than re-computing them.
We extend the classical and-or tree with two new
nodes: a `sequential' node (for RAP's sequential goals), and a `crossproduct'
node (for the crossproduct of solutions from and-or-parallel goals).
The paper also presents an extension of the WAM, called AO-WAM, which is
used to compile logic programs for and-or parallel execution based on the
extended and-or tree. The AO-WAM incorporates a number of novel features:
to support the management of logical variable and the control of the
search space of the extended and-or tree model
(i) inclusion of a base array with each processor's binding-array
for constant-time access to variables in the presence of and-parallelism;
(ii) inclusion of new stack frames and instructions to express it solution
sharing, (iii) novel optimizations which minimize the cost of binding-array
updates in the presence of and-parallelism.
The whole paper
can be downloaded from our
server.
Logic Prog. Page Research Page Lab Home Page