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

Gopal Gupta, Bharat Jayaraman

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