Technical Report: DCC-99-2

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

Vítor Santos Costa, Ricardo Rocha and Fernando Silva

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

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 (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.