Three Amigos: A Tale of Three Execution Models for Or-Parallelism

Vítor Santos Costa, Ricardo Rocha and Fernando Silva

September 1999

---

Abstract

One of the advantages of logic programming is the fact that it offers many sources of implicit parallelism, such as and-parallelism and or-parallelism. A major problem that a parallel model must address consists in represent the multiple values that shared variables can be binded to when exploited in parallel. Binding Arrays and Environment Copying are two or-parallel models that efficiently solve that problem. Recently, research in combining independent and-parallelism and or-parallelism within the same system has led to two new binding representation approaches: the Sparse Binding Array (an evolution of binding arrays) and the Copy-On-Write binding models.
In this paper, we investigate whether for or-parallelism the newer models are practical alternatives to copying. To address this question, we experimented with YapOr, an or-parallel copying system using the YAP Prolog engine, and we implemented the Sparse Binding Array (SBA) and the Copy-On-Write ($\alpha$COWL) over the original system. The three alternative systems share schedulers and the underlying engine; they differ only in their binding scheme. We compared their performance on a set of well-known all-solutions benchmarks.

Bibtex

@TechReport{santoscosta-dcc99-02,
  author =      {V. Santos Costa and R. Rocha and F. Silva},
  title =       {{Three Amigos: A Tale of Three Execution Models for Or-Parallelism}},
  institution = {DCC-FC \& LIACC, University of Porto},
  number =      {DCC-1999-02},
  month =       {September},
  year =        {1999},
}

Download Report

PDF file