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


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.