Implementing a parallel PROLOG interpreter by using OCCAM and transputers

occam is a message-based parallel language that allows programs to be written with a large number of living processes. The transputer, which supports occam very efficiently, allows parallel systems to be built in a simple and modular way. occam and the transputer were chosen for the implementation and evaluation of a parallel prolog interpreter made up of a set of parallel processes communicating according to a message-passing protocol. The parallel execution model adopted exploits full OR parallelism and pipeline AND parallelism, while preserving the depth-first search technique of the classical sequential model. The aim of the implementation was to evaluate the actual degree of parallelism exploited by the execution model, and the efficiency of the used resolution algorithm. The number of living processes was found to be consistent with the number of processors in the architecture used (four), and the additional workload produced by the message exchanges between processes was found not to be excessively time consuming.