Donald Bren School of Information and Computer Sciences

Current techniques for interpretation of logic programs involve a sequential search of a global tree of procedure invocations. This dissertation introduces the AND/OR Process Model, a method for interpretation by a system of asychronous, independent processes that communicate only by messages. The method makes it possible to exploit two distinct forms of parallelism. OR parallelism is obtained from evaluating nondeterministic choices in parallel. AND parallelism arises in the execution of deterministic fuctions, such as matrix multiplication of divide and conquer algorithms, that are inherently parallel. The two forms of parallelism can be exploited at the same time. This means AND parallelism can be applied to clauses that are composed of several nondeterministic components, and it can recover from incorrect choices in the solution of these components. In addition to defining parallel computations, the model provides a more defined procedural semantics for logic programs; that is, parallel interpreters based on this model are able to generate answers to queries that cause standard interpreters to go into an infinite loop. The interpretation method is intended to form the theoretical framework of a highly parallel non von Neumann computer architecture; the dissertation concludes with a discussion of issues involved in implementing the abstract interpreter on a multiprocessor.