A Parallel Execution Model for Prolog

Barry Steven Fagin

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-87-380
November 1987

As single computer systems approach the technological limits of their performance, computer scientists are turning to multiprocessing as a means of solving computationally difficult problems. In addition, symbolic computing has emerged as a promising field of scientific endeavor. These two fields have recently combined into a new area of research: parallel symbolic computing.

One candidate language for parallel symbolic computing is Prolog. Numerous ways for executing Prolog in parallel have been proposed, but current efforts suffer from several deficiencies. Many cannot support fundamental types of concurrency in Prolog. Other models are of purely theoretical interest, ignoring implementation costs. Detailed simulation studies of execution models are scarce; at present, little is known about the costs and benefits of executing Prolog in parallel.

In this thesis, a new parallel execution model for Prolog is presented: the PPP model, or Parallel Prolog Processor. The PPP supports AND-parallelism, OR-parallelism, and intelligent backtracking. An implementation of the PPP is described, through the extension of an existing Prolog abstract machine architecture. Several examples of PPP execution are presented, and compilation to the PPP abstract instruction set is discussed. The performance effects of this model are reported, based on a simulation of a large benchmark set. The implications of these results for parallel Prolog systems are discussed, and directions for future work are indicated.

Advisor: Alvin M. Despain


BibTeX citation:

@phdthesis{Fagin:CSD-87-380,
    Author = {Fagin, Barry Steven},
    Title = {A Parallel Execution Model for Prolog},
    School = {EECS Department, University of California, Berkeley},
    Year = {1987},
    Month = {Nov},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/6221.html},
    Number = {UCB/CSD-87-380},
    Abstract = {As single computer systems approach the technological limits of their performance, computer scientists are turning to multiprocessing as a means of solving computationally difficult problems. In addition, symbolic computing has emerged as a promising field of scientific endeavor. These two fields have recently combined into a new area of research: parallel symbolic computing. <p> One candidate language for parallel symbolic computing is Prolog. Numerous ways for executing Prolog in parallel have been proposed, but current efforts suffer from several deficiencies. Many cannot support fundamental types of concurrency in Prolog. Other models are of purely theoretical interest, ignoring implementation costs. Detailed simulation studies of execution models are scarce; at present, little is known about the costs and benefits of executing Prolog in parallel. <p> In this thesis, a new parallel execution model for Prolog is presented: the PPP model, or Parallel Prolog Processor. The PPP supports AND-parallelism, OR-parallelism, and intelligent backtracking.  An implementation of the PPP is described, through the extension of an existing Prolog abstract machine architecture. Several examples of PPP execution are presented, and compilation to the PPP abstract instruction set is discussed. The performance effects of this model are reported, based on a simulation of a large benchmark set. The implications of these results for parallel Prolog systems are discussed, and directions for future work are indicated.}
}

EndNote citation:

%0 Thesis
%A Fagin, Barry Steven
%T A Parallel Execution Model for Prolog
%I EECS Department, University of California, Berkeley
%D 1987
%@ UCB/CSD-87-380
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/6221.html
%F Fagin:CSD-87-380