Technical reports

A distributed and-or parallel Prolog network

K.L. Wrench

December 1990, 82 pages

DOI: 10.48456/tr-212

Abstract

A model is proposed for the parallel execution of Prolog, exploiting both dependent and- and full or-parallelism. The model is implemented on a distributed network of loosely-coupled processors and has no need of shared memory nor multiprocessor hardware.

Known as APPNet, the model makes use of oracles to partition the search space dynamically, thereby enabling processing elements to be allocated a unique portion of the computation. No communication takes place between processing elements. In executing problems that do not exhibit any and-parallelism, all solutions found represent final answers to the query. When an and-parallel problem is executed, the solutions generated are only partial solutions. The sets of partial solution are then joined to produce consistent final solutions. Back-unification is the process whereby partial solutions are unified according to a template derived from the program.

Prolog source programs need not be modified by the user. Static analysis is, however, carried out automatically on all programs by a preprocessor before their execution in the APPNet to ensure that clauses are not distributed before it is feasible to do so. Side-effecting constructs are identified and the appropriate restrictions are placed on the parallel execution strategy.

Full text

PDF (4.7 MB)

BibTeX record

@TechReport{UCAM-CL-TR-212,
  author =	 {Wrench, K.L.},
  title = 	 {{A distributed and-or parallel Prolog network}},
  year = 	 1990,
  month = 	 dec,
  url = 	 {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-212.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-212},
  number = 	 {UCAM-CL-TR-212}
}