Analysis of Dependent And-Parallelism

Laboratory for Logic, DBs, and Advanced Programming
Dept. of Computer Science
New Mexico State University
Las Cruces, NM 88003
{epontell,gupta}@cs.nmsu.edu

Abstract
We consider the problem of exploiting non-deterministic dependent and-parallelism (DAP) from Prolog programs. The main issues that arise in designing a parallel Prolog system for exploiting DAP are discussed. Three criteria that an ideal implementation of DAP should satisfy are developed. We prove that an ideal system that satisfies all three criteria cannot be constructed. These criteria are then used to evaluate and classify existing execution models proposed for exploiting DAP, and to inspire new schemes for exploiting DAP that are arguably better than the existing ones. One such scheme, termed the Filtered Binding Model is presented. The Filtered Binding model has been incorporated in the ACE and-or parallel Prolog system, running on a Sequent Symmetry and Sun Sparc Multiprocessors. Performance results from this implementation are presented and shown to be better than the results achieved by other systems.