And-or parallelism on shared-memory multiprocessors

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, two succesful 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 cross product of the solutions from the and-or parallel goals rather than recomputing them. We extend the classical and-or tree with two new nodes: a "sequential" node (for RAPs sequencial goals), and a "cross-product" node (for the cross product 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: (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 solution sharing, and (iii) novel optimizations which minimize the cost of binding-array updates in the presence of and-parallelism.