Logic Programming 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
The whole paper
can be downloaded from our
server.
Logic Prog. Page
Research Page
Lab Home Page