1. INTRODUCTION

The execution speed of sequential logic programming systems has been constantly improving since D.H.D. Warren's Prolog interpreter/compiler [61] for the DEC-System10 proved the usefulness of logic as a practical programming tool [37]. Yet, in order to meet the requirements of today's and tomorrow's applications, substantial improvements in performance are still needed. A promising approach is through the introduction of parallel evaluation strategies into the language executor. VLSI technology and parallel computer architecture advances also provide an opportunity for performance improvement. Investigations into this possibility have already led to the proposal of a number of schemes and machine architectures for parallel processing of logic programs [21, 36, 44].

The three major forms of parallelism exploitable in a logic program can be explained in terms of the structure of the program. Among these three forms of parallelism, low level parallelism, typically unification parallelism, may be obtained during the unification of a goal and a clause head. By executing a stream of intermediate instructions, the low level parallelism can also be exploited in a pipelined fashion [59]. A critical review on unification and its potential parallelism can be found in [35]. At a high level, when alternative clauses in a procedure are evaluated simultaneously, OR-parallelism is achieved [19]. OR-parallelism can also be exploited at a higher level in terms of the search tree, which represents the execution of the program [5, 63]. The unification of more than one clause head with a given goal is considered as separate branches of the search tree. Multiple such branches, each including the clause involved and its continuation, can be executed in parallel. AND-parallelism is exploited when more than one goal in a clause body are evaluated in parallel. Each goal in the body may include multiple OR branches.

In order to exploit AND/OR parallelism more efficiently through explicit language syntax and semantics, a number of new logic programming languages supporting concurrent processing have been proposed. This by itself is an interesting research area, and is out of the scope for the present review. We refer readers to Shapiro's comprehensive survey [53] and collected papers [52] on concurrent logic programming languages.

This paper presents a review on various models and systems proposed for exploiting OR-parallelism. It covers most of the important models and systems reported between early 1980s and 1992. The research in this area is still rapidly evolving and some mature systems are continuously been improved and new models are emerging. The trend has been to improve the existing working systems or to extend them for the support of both AND- and OR-parallelism. The review first introduces the basic concepts of OR- parallelism, potential difficulties for its exploitation and trade-offs for using various approaches. The review starts by looking at binding management approaches, followed by process control strategies used in various models for multiprocessor implementations. The performance of some working systems are then summarised and compared. The review concludes with an overall summary.

2. OR-PARALLELISM

2.1. Problems with exploitation

In terms of computation, OR-parallelism refers to a parallel search strategy. When a search process reaches a branch in the tree, it can start to search descendant branches in parallel. The name for OR- parallelism is based on the fact that in a non-deterministic program, a query is often satisfied by any answer. In other words, when any one of the searches starting from a choice point (non-leaf node on the