Analysis of Or-Parallel Models for Logic Programs

Parallel Processing Research

Analysis of Or-Parallel Models for Logic Programs 

ACM Transactions On Programming Languages and Systems
ACM TOPLAS, Sept. 1993, Vol. 15, No. 4, pp. 659-680

Author(s)
Gopal Gupta, Bharat Jayaraman

Abstract
Exploiting or-parallelism is an important way of speeding up the execution of logic programs. Although several methods have been proposed to realize or-parallelism in an actual implementation, not much has been done to analyze the subject in a systematic way. This paper offers a framework for studying or-parallel execution models of logic programs. We propose three criteria that an ideal or-parallel execution model for logic programs should satisfy: constant-time access to variables, constant-time task creation, and constant-time task switching. We then prove that all three criteria cannot be simultaneously satisfied by any execution model for or-parallelism based on a finite number of processors but unbounded memory. Based on this result, we proceed to categorize the various or-parallel methods proposed in the literature.

The whole paper

can be downloaded from our

server.


 Parallel Proc. Page   Research Page   Lab Home Page