And-parallel implementation of Prolog on distributed memory machines

This research develops a scheme for the efficient execution of Prolog programs on a distributed memory parallel machine. Efficient schemes for the sequential execution of Prolog are generally based on the Warren Abstract Machine (WAM) [Warren 1983]; our execution scheme places an extended WAM on each processor which can receive tasks and spawn further tasks to other processors. The extended WAM supports independent and-parallel execution and intelligent backtracking at the clause level. An analysis of binding communication between processors is made to select the most efficient scheme. Additional run-time information can be derived from the communication of bindings at no additional overhead. An extended WAM instruction set is designed where information provided at compile-time is combined with information derived at run-time to dynamically determine the data-dependencies between subgoals. A scheme for intelligent backtracking in parallel clauses is developed which both `intelligently' selects the redo subgoal(s) and allows other execution in the clause to persist unless bindings are directly affected by the redo. Potentially, parallel execution can continue in a clause when backtracking occurs. The dynamic information is also used to prune unnecessary search space and an optimisation, `intelligent cutting' is introduced. A distributed Prolog executor has been implemented for an array of transputer processing elements. A complete analysis of the implementation is made for both sequential and parallel execution. Performance results are comparable with other results in the literature for shared memory architectures.