One of the advantages of logic programming is that it offers several sources of implicit parallelism, such as and-parallelism (ANDP) and or-parallelism (ORP). Recent research has concentrated on integrating the different forms of parallelism into a single combined system. In this work we deal with the problem of integrating ORP and independent and-parallelism (IAP), the two forms of parallelism most suitable for parallel Prolog systems. We contend that previous data structures do not allow for orthogonality between ANDP and ORP, leading to overly complex and inefficient designs. Our first major contribution thus includes the first complete analysis of the problem, from which we derive (i) a novel data-structure, the SBA (Sparse Binding Array), that does guarantee memory independence between the two forms of a parallelism thus leading to a more orthogonal integration, and (ii) detailed mechanisms for the efficient combination of IAP and ORP.

We then proceed to apply these mechanisms in the integration of a RAP-WAM derived IAP system with a SRI based ORP system. Several difficulties found in the process lead us to the conclusion that traditional designs for the implementation of IAP are more complex than what one needs, thus difficulting integration with or-work. As a case in point, backtracking in the presence of IAP is very complex and will interfere badly with existing or-parallel systems.

Our second major contribution is a novel model for IAP execution, fully supporting backtracking and memory reuse. This new model, LGSATS, learns from experience in previous ORP and IAP systems and is arguably much more amenable to be integrated with a SBA based ORP system. Our novel design is based on the following main guidelines: (i) And-agents perform as sequential engines for the most part of their execution; (ii) we follow a lazy work-publishing strategy in order to induce large grain and-tasks for parallel execution; iii) we re-utilize WAM data-structures wherever possible; (iv) we initialize and-parallel data structures only when they are publicized. Our contributions simplify system implementation, and facilitate integration between the two forms of parallelism.