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.

Abstract

Abstract
Prolog programs have explicit parallelism, that is, parallelism which can be exploited by a machine with minimal user effort. Or-parallelism is one such form of parallelism, and is particularly useful in that it is present in the many Prolog applications where several alternatives need to be considered. Or-parallelism has been exploited successfully in several systems, and especially in the Aurora and Muse systems. In this paper we analyze the portability of these two parallel systems onto a commercial shared memory parallel computer, a Sun SPARCcenter 2000 with 8 processors, running the Solaris 2.2 Operating System. We also analyze both systems' performance for classical benchmark programs and for two large Prolog applications.

Abstract

Abstract

Abstract