Um Sistema baseado na Separação de Ambientes para Execução Distribuída de Prolog

Rolando Martins

July 2003

---

Abstract

Prolog is one of the major languages used by researchers in the areas of Artificial Intelligence, specially in areas such us Machine Learning and Natural Language Processing. This is explained by the excellent sequential performance of Prolog systems. The development of parallel Prolog systems have further contributed to excel the language speed. These systems exploit implicit parallelism within the language and have the advantage of not requiring extra work in program development.
The main goal of this work is to design and implement a parallel Prolog system, capable of exploiting Or-parallelism on low cost distributed memory parallel architectures, such us the beowulf clusters. The system, named YapDss, builds on the work of the YapOr system, an or-parallel system for shared memory architectures, and uses the distributed stack-splitting binding model to represent computation state and work sharing among the parallel computational agents.
The development of YapDss required the analysis and understanding of the systems YAP and YapOr, in order to identify and modify the data structures and mechanisms necessary to schedule work in a distributed environment. Some of the contributions of YapDss are: a mechanism to share program code among the computing agents; techniques to minimize the scheduling information necessary for work sharing; a protocol for workload propagation that keeps the number of messages to a minimum to avoid communication overheads; and a communication interface using MPI to support distributed computations.
Lastly, we present an initial performance study of YapDss using a set of benchmark Prolog programs commonly used in the evaluation of similar systems. The YapDss system shows excellent performance on programs with reasonably large amounts of large-grain parallelism. The main limiting factor so far is that YapDss lacks support for the cut predicate.

Bibtex

@MastersThesis{martins-msc,
  author =  {R. Martins},
  title =   {{Um Sistema baseado na Separação de Ambientes para Execução Distribuída de Prolog}},
  school =  {University of Porto},
  address = {Portugal},
  month =   {July},
  year =    {2003},
  type =    {{MSc Thesis}},
  note =    {In Portuguese},
}

Download Thesis

PDF file