Um Sistema Baseado na Cópia de Ambientes para a Execução de Prolog em Paralelo

Ricardo Rocha

July 1996

---

Abstract

Prolog is a popular programming language that is particularly important in Artificial Intelligence applications. Traditionally, Prolog has been implemented in the common, sequential general-purpose computers. More recently, Prolog implementations have also been proposed for parallel architectures where several processors work together to speedup the execution of a program. By giving better speedups, parallel implementations of Prolog should enable better performance for current problems, and expand the range of applications we can solve with Prolog.
This work addresses the issues of the design, implementation and performance evaluation of YapOr, an Or-parallel Prolog system. YapOr extends Yap's sequential execution model to exploit implicit Or-parallelism in Prolog programs. It is based on the environment copy model and implements most of the ideas introduced in Muse system.
To develop YapOr, it was necessary to solve some important issues, such as, design of data structures to support parallel process, implement the incremental copy technique, develop a memory organisation able to answer with efficiency to the parallel process and to the incremental copy in particular, implement the scheduling strategies, design an interface between the scheduler and the engine, implement the sharing work process, handle cut predicate with care and develop a scheme to support solutions that potentially correspond to speculative work.
An initial evaluation of the performance of YapOr showed that it achieves very good performance on a large set of benchmark programs. It also showed that YapOr compares favourably with Muse.

Bibtex

@MastersThesis{rocha-msc,
  author =  {R. Rocha},
  title =   {{Um Sistema Baseado na Cópia de Ambientes para a Execução de Prolog em Paralelo}},
  school =  {University of Minho},
  address = {Portugal},
  month =   {July},
  year =    {1996},
  type =    {{MSc Thesis}},
  note =    {In Portuguese},
}

Download Thesis

PDF file