Abstract
One of the advantages of logic programming in the fact that it offers many sources of implicit parallelism, 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.

Abstract
Parallel logic programming systems are sophisticated examples of symbolic computing systems. They address problems such as dynamic memory allocation, scheduling irregular execution patterns, and managing different types of implicit parallelism. Most parallel logic programming systems have been developed for bus-based shared-memory architectures. The complexity of parallel logic programming systems and the large amount of data they process raises the question of whether logic programming systems can still obtain good performance on scalable architectures, such as distributed shared-memory systems. In this work we use execution-driven simulation to investigate the access patterns and caching behaviour exhibited by a parallel logic programming system, Andorra-I. We show that the system obtains reasonable performance, but that it does not scale well. By studying the behaviour of the major data structures in Andorra-I in detail, we conclude that this result is largely a consequence of the scheduling and work manipulation implementation used in the system. We also show that the Andorra-I's data structures exhibit widely-varying memory access patterns and caching behaviour, which not only depend on the number of processors, but also on the amount and type of parallelism available in the application program. Some of these data structures clearly favour invalidate-based cache coherence protocols, while others favour update-based protocols. Since most of Andorra-I's data structures are common to other parallel logic programming systems, we believe that these systems can greatly benefit from flexible coherence schemes where either the compiler can specify the protocol to be used for each data structure or the protocol can adapt to varying memory access patterns.

Abstract

Abstract
One important problem in the design of novel logic programming systems is the support of several forms of implicit parallelism. A new binding model, the Sparse Binding Array (SBA), has been proposed for the efficient and simplified integration of Independent-And, Determinate-And and Or-parallelism. In this paper we report on the use of this model for pure Or-parallelism. The work discusses the major implementation issues in supporting this binding model for pure Or-parallelism. We show that an implementation based on this Binding model is more efficient then the original Aurora using tbe traditional Binding Array model [16]. Moreover, we explain how the notion of a variable level can be used to reduce overheads of the Orparallel system. Our results in supporting pure or-parallelism show that the approach is very promissing for combined paralell systems.

Abstract
Andorra-I is an experimental parallel Prolog system which transparently exploits both dependent and-parallelism and or-parallelism. One of the main components of Andorra-I is its preprocessor. In order to obtain efficient execution of programs in Andorra-I, the preprocessor includes a compiler for Andorra-I. The compiler includes a determinacy analyser and a clause compiler, and generates code for a specialised abstract machine. In this paper we discuss the main issues in the Andorra-I compiler, presenting its abstract instruction set and describing the algorithms used in its implementation.

Abstract
Practical Prolog programs usually contain extra-logical features like cuts, side-effects, and database manipulating predicates. In order to exploit implicit parallelism from real applications while preserving sequential Prolog semantics, a parallel logic programming system should necessarily support these features. In this paper we show how Prolog's extra-logical features can be supported in an and-or parallel logic programming system. We show that to support extra-logical features an and-or parallel logic programming system should recompute the solutions to independent goals instead of sharing them. We describe an abstraction called the composition tree for representing and-or parallel execution with recomputation. We introduce the notion of ''local-leftmostness'' in the composition tree and use it for deriving complete and efficient methods for supporting extra-logical predicates in and-or parallel logic programming systems based on the composition tree abstraction.