Implementation and evaluation of OR parallel Prolog models on distributed systems

V. Benjumea, M. Roldan, J.M. Troya.


A Prolog parallel interpreter with which to evaluate several approaches in distributed OR parallel implementations is shown. Two execution models based on a process tree, which differ mainly in the process granularity, are considered. Furthermore, two memory management strategies based on a closed environment are examined. The evaluation method consists of comparing real results obtained after running four different versions which combine the different issues.

The interpreter has been implemented on a 16 Transputers Parsys Supernode, using Occam as the development language. The process and memory management have been implemented in a dynamic way, allowing improvement of the system's efficiency and reduction in memory waste. A dynamic load balancing mechanism has been implemented. Some statistics made using the interpreter show a speed-up of 3.75 for 4 processors and 12.57 for 16 processors.

Keywords: Parallel interpreter, logic programming, AND parallelism, OR parallelism, distributed memory systems, closed environment memory model