Technical Report: DCC-97-6

Or-Parallel Prolog on a Distributed Memory Architecture

Departamento de Ciência de Computadores & LIACC
Faculdade de Ciências, Universidade do Porto
Rua do Campo Alegre, 823 4150 Porto, Portugal

July 1997

We present the design and study the performance of the Dorpp or-parallel Prolog system on the EDS parallel machine. This is basically a distributed memory machine except for one interesting and novel feature - access to non-local memory is supported, and copied data is cached locally, though there is no built-in memory coherence scheme. Dorpp uses a novel distributed shared memory model for implicitly exploiting or-parallelism in Prolog programs. It attempts to exploit locality and reduce communication overheads through its scheduling mechanisms and by caching accesses to remote shared data. The specific problems of memory coherency for or-parallel Prolog are discussed and novel solutions are proposed.

We present detailed performance analysis of the behaviour of Dorpp on a parallel simulator of the EDS machine. This analysis shows that the design is efficient and highlights some general results which are relevant to all implementations of or-parallel prolog on distributed memory systems.

Keywords: Or-Parallel Prolog, Distributed Memory, Memory Coherency, Scheduling.