ACE: And/Or-parallel Copying-based Execution of Logic Programs

In this paper we present a novel execution model for parallel implementation of logic programs which is capable of exploiting both independent and-parallelism and or-parallelism in an efficient way.This model extends the stack copying approach, which has been successfully applied in the Muse system to implement or-parallelism, by integrating it with proven techniques used to support independent and-parallelism.We show how all solutions to non-deterministic andparallel goals are found without repetitions.This is done through recomputation as in Prolog (and in various and-parallel systems, like &-Prolog and DDAS), i.e., solutions of and-parallel goals are not shared.We propose a scheme for the efficient management of the address space in a way that is compatible with the apparently incompatible requirements of both and-and or-parallelism.We also show how the full Prolog language, with all its extra-logical features, can be supported in our and-or parallel system so that its sequential semantics is preserved.The resulting system retains the advantages of both purely or-parallel systems as well as purely and-parallel systems.The stack copying scheme together with our proposed memory management scheme can also be used to implement models that combine dependent and-parallelism and or-parallelism, such as Andorra and Prometheus.