Technical reports

Exploiting OR-parallelism in Prolog using multiple sequential machines

Carole Susan Klein

250 pages

This technical report is based on a dissertation submitted October 1989 by the author for the degree of Doctor of Philosophy to the University of Cambridge, Wolfson College.

DOI: 10.48456/tr-216

Abstract

If the branches at each node of a tree are labelled, paths through the tree can be represented by a sequence of labels called an oracle. If an oracle leading to a node is followed, all of the bindings and other state information associated with a node will be recreated. Thus oracles are both a specification for a path through the tree and a concide format for representing the environment at a particular node.

This dissertation investigates the use of oracles for the parallel execution of Prolog programs. The execution of a Prolog program can be represented pictorially by an AND/OR tree. The branches of OR nodes within this tree have no binding dependencies so their evaluation can be performed on separate processors. If one of more of these OR branches is explored in parallel, OR-parallelism is exploited in the Prolog program.

A distributed system called the Delphi Machine has been designed and implemented to exploit the OR-parallelism inherent in Prolog programs. In the implementation described in this dissertation, Delphi runs on a group of uniprocessors connected by Ethernet. Various control strategies using oracles to control the parallel search are investigated. The execution times for Prolog programs run on the Delphi Machine are compared with those of a compiled and an interpreted sequential Prolog system. The results show that a distributed system using oracles to control the parallel search can be an efficient way to exploit OR parallelism in nondeterministic programs.

Because of overheads imposed by the Delphi algorithm, a program executed on a single processor Delphi machine runs at approximately one half the speed as the same program executed on the unmodified prolog system. For a twenty processor configuration, the speed ups obtained vary from approximately two to nine times depending on the amount of OR-parallelism which can be exploited by Delphi. Problems with large amounts of OR-parallelism show a nearly linear speedup.

Full text

PDF (20.6 MB)

BibTeX record

@TechReport{UCAM-CL-TR-216,
  author =	 {Klein, Carole Susan},
  title = 	 {{Exploiting OR-parallelism in Prolog using multiple
         	   sequential machines}},
  url = 	 {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-216.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-216},
  number = 	 {UCAM-CL-TR-216}
}