Technical Report: DCC-97-14

YapOr: an Or-Parallel Prolog System based on Environment Copying

Ricardo Rocha, Fernando Silva and Vítor Santos Costa

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

December 1997

Abstract

Prolog compilers have proved to be highly efficient for standard sequential architectures. The efficiency of these implementations and the declarativeness of the Prolog language have kindled interest on implementations for parallel architectures. YapOr is an Or-parallel system that extends Yap's sequential execution model to exploit implicit or-parallelism in Prolog programs. YapOr is based on the environment copy model, as first implemented in Muse.

To develop YapOr, it was necessary to solve some important issues, such as the design of data structures to support parallel processing, the implementation of the incremental copying technique, the development of a memory organization able to answer with efficiency to parallel processing and to the incremental copying in particular, the implementation of the scheduling strategies, the design of an interface between the scheduler and the engine, the implementation of the sharing work process, and support for the cut builtin.

An initial evaluation of YapOr performance showed that it achieves very good performance on a large set of benchmark programs. Indeed, YapOr compares favorably with a mature parallel Prolog system such as Muse, both in terms of base speed and in terms of speedups.

Keywords: Parallel Logic Programming, Scheduling, Performance Evaluation.