SOME ESSENTIAL SIDE-EFFECTS OF PROLOG ON A DISTRIBUTED IMPLEMENTATION

Abstract

This work describes an implementation of some essential side-effects of Prolog:  cut,  findall, and  input/output, on a distributed memory system. The techniques designed are advantageous when applied to parallel systems based on recomputation, such as PDP (Prolog Distributed Processor), a model for Independent_AND/OR parallel execution of Prolog. Nevertheless, they are also valid for any distributed memory system. The implementation of the cut predicate exploits as much parallelism as possible, including the parallel computation of branches of the search tree which depend on a cut. However, the computation of a branch which does not depend on a cut is never delayed to control computations depending on a cut. The model proposed for the  findall predicate reduces the communication as much as possible by distributing the control of the execution of findall, and takes advantage of the success paths used in the recomputation to perform the sorting of the solutions. The PDP model for the exploitation of combined parallelism has allowed a straightforward introduction of the input/output predicates. Results obtained with an implementation of the models on a network of workstations by means of the PVM (Parallel Virtual Machine) software package are presented.