Technical Report: DCC-97-6

Or-Parallel Prolog on a Distributed Memory Architecture

 Fernando Silva      Paul Watson (*)

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

July 1997


Abstract

Whilst there has been much work over the last ten years on the parallel implementation of logic programming, the vast majority of it has been focused on shared memory multiprocessor systems. In this paper, however, we focus on the exploitation of the other major type of parallel architecture - distributed memory systems.

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. 



(*) Department of Computing Science, University of Newcastle upon-tyne, UK.