Parallel Interpretation of PROLOG on Transputer Networks

Occam and the transputer were chosen for the implementation of a parallel Prolog interpreter. The execution model exploits the full OR-parallelism paired with a restricted form of AND-parallelism (pipeline AND-parallelism). The depth-first, left-to-right search strategy of a sequential Prolog interpreter is preserved under the model. The interpreter is made up of a set of cooperating processes which explore different branches of the search space simultaneously. In the paper, an Occam description of processes is given along with the performance results obtained with a version of the interpreter running on a network of four transputers.