Technical Report: DCC-97-3
The SBA: Exploiting Orthogonality in AND-OR Parallel Systems
Manuel Eduardo Correia, Fernando Silva e Vítor Santos Costa
Departamento de Ciência de Computadores & LIACC
Faculdade de Ciências, Universidade do Porto
Rua do Campo Alegre, 823 4150 Porto, Portugal
April 1997
Abstract
One of the advantages of logic programming is the fact that one can
exploit
implicit parallelism in logic programs, such as
and-parallelism and or-parallelism. Recently, research has been
concentrated on integrating the different forms of parallelism into a
single combined system. In this work we concentrate on the problem of
integrating or-parallelism and independent and-parallelism for
parallel Prolog systems. We contend that previous data structures
require
pure recomputation and therefore do not allow for
orthogonality between and-parallelism and or-parallelism. In contrast,
we submit that a simpler solution, the sparse binding array, does
guarantee this goal, and explain in detail how independent
and-parallelism and or-parallelism can thus be efficiently combined.
