Parallel execution of logic programs on shared memory multiprocessors
Gopal Gupta · 1992
This dissertation addresses the problem of compiling parallelism present in logic languages for efficient execution on shared memory multiprocessors. We present 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 cross-product 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 'cross-product' node (for the cross-product of solutions from and-or parallel goals). An extension of the WAM, called AO-WAM, is also presented 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, (iii) novel optimizations which minimize the cost of binding-array updates in the presence of and-parallelism. Techniques are also presented for incorporating side-effects and extra-logical features in the and-or parallel model, so that real world logic programs can be run. The and-or model is further enhanced to incorporate stream-parallelism based on the Andorra Principle. Problems that can arise due to interaction of restricted and-parallelism with stream-parallelism are described and solutions presented. ftn*This research has been supported by grant DCR-8603609 from the National Science Foundation and partially by U.K. Science and Engineering Research Council grant GR/F 27420.