Abstract

Abstract

Abstract

Abstract
Independent and-parallelism, dependent and-parallelism and or-parallelism are the three main forms of implicit parallelism present in logic programs. In this paper we present a model, IDIOM, which exploits all three forms of parallelism in a single framework. IDIOM is based on a combination of the Basic Andorra Model and the Extended And-Or Tree Model. Our model supports both Prolog as well as the flat concurrent logic languages. We discuss the issues that arise in combining the three forms of parallelism, and our solutions to them. We also present an implementation scheme, based on binding arrays, for implementing IDIOM.

Abstract

Abstract
Andorra-I is an experimental parallel Prolog system that transparently exploits both dependent and-parallelism and or-parallelism. It constitutes the first implementation of the Basic Andorra model, a parallel execution model for logic programs in which determinate goals are executed before other goals. This model, besides combining two of the most important forms of implicit parallelism in logic programs, also provides a form of implicit coroutining. This means that Andorra-I not only supports standard Prolog but also provides the capabilities of flat committed-choice languages. In this paper, we discuss the preprocessor which enables Andorra-I to support full Prolog, including cut, commit, meta-predicates and side-effect predicates. The main functions of the preprocessor are to perform a mode analysis of the program by abstract interpretation, to use this information to recognize procedures containing pruning operators that are potentially ``noisy'', to protect calls to such ``sensitive'' predicates by restricting certain conjunctions to be executed sequentially, and finally to generate for each predicate a routine which will determine when calls to that predicate become executable through becoming clause determinate.