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

VĂ­tor Santos Costa, Ricardo Rocha and Fernando Silva

September 1999


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.


  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