The SBA: Exploiting Orthogonality in AND-OR Parallel Systems

Manuel Correia

Vitor Santos Costa

Fernando Silva

One of the advantages of logic programming is the fact that one can exploit {\em 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 \emph{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.