EXPLOITING AND-PARALLELISM AND COMBINED AND/OR-

PARALLELISM IN LOGIC PROGRAMS: A SURVEY

Kang Zhang
Department of Computing, School of MPCE
Macquarie University, NSW 2109, Australia

[ABSTRACT] Logic programs provide many opportunities for parallel execution. Among different forms of parallelism found in logic programs, AND-parallelism and OR-parallelism have shown to be most effective in speeding up the execution of logic programs. Research in the exploitation of AND-parallelism, OR-parallelism alone and combined AND/OR-parallelism has led to the proposals and implementations of various execution models and working systems. This paper offers a review of major activities in exploiting AND-parallelism and combined AND/OR- parallelism.

Keywords: Logic programming, Prolog, AND-parallelism, Combined AND/OR-parallelism

1. INTRODUCTION

There has been a flurry of research activities in parallel processing of logic programs in the last decade due to the growing demand for fast reasoning capabilities on the current parallel computers. Among different forms of parallelism inherent in logic programs, AND-parallelism and OR- parallelism have shown to be most effective in speeding up the program execution. OR-parallelism is achieved when multiple clauses belonging to a same procedure are executed in parallel, or when multiple OR-branches of the search tree, each including a clause and its continuation, are executed in parallel. The exploitation of OR-parallelism was reviewed in a previous paper [62].

AND-parallelism is the parallel execution of more than one goal in a clause body. It corresponds to parallel construction of a branch in the search tree. In other words, when an AND-parallel system knows a number of steps that must be done to complete a branch, it starts to perform those steps simultaneously. The name for AND-parallelism comes from the fact that all steps must succeed in order for a result to be produced. The central problem in implementing this form of parallelism is the producing of conflict bindings of variables which are shared among the parallel executed goals. As an example, consider the following simple program

<- p(X).
p(Y) :- q(Y), r(Y).
q(a).
q(b).
r(b).

In sequential Prolog (Figure 1a), when p is called, the subgoals1 q and r are evaluated from left to right. The evaluation of q binds a to Y. This value makes r fail. Then an alternative definition for q