A Parallel Execution Model for Prolog
Fagin, Barry Steven
Technical Report Identifier: 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.
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.