A Caltech Library Service

A Parallel Execution Model for Logic Programming


Li, Peyyun Peggy (1986) A Parallel Execution Model for Logic Programming. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/2ngs-bp80.


The Sync Model, a parallel execution method for logic programming, is proposed. The Sync Model is a multiple-solution data-driven model that realizes AND-parallelism and OR-parallelism in a logic program assuming a message-passing multiprocessor system. AND parallelism is implemented by constructing a dynamic data flow graph of the literals in the clause body with an ordering algorithm. OR parallelism is achieved by adding special Synchronization signals to the stream of partial solutions and synchronizing the multiple streams with a merge algorithm.

The Sync Model is proved to be sound and complete. Soundness means it only generates correct solutions and completeness means it generates all the correct solutions. The soundness and completeness of the Sync Model are implied by the correctness of the merge algorithm.

A new class of interconnection networks, the Sneptree, is also presented. The Sneptree is an augmented complete binary tree which can simulate an unbounded complete binary tree optimally. Amongst different connection patterns of the Sneptree, some are regular and extensible so as to be well suited for VLSI implementation. A recursive method is presented to generate the H-structure layout of one type of the Sneptree, called the Cyclic Sneptree. A message routing algorithm between any two leaf nodes of the Cyclic Sneptree is also presented. The routing algorithm, which is of O(n) complexity, gives a good approximation to the shortest path.

The Sneptree is an ideal architecture for the Sync model, in which a dynamic process tree is constructed. With a simple mapping algorithm, the Sync Model can be mapped onto the Sneptree with highly-balanced load and low overhead.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Computer Science
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Martin, Alain J.
Thesis Committee:
  • Martin, Alain J. (chair)
  • Seitz, Charles L.
  • Abu-Mostafa, Yaser S.
  • Van de Snepscheut, Jan L. A.
  • Kechris, Alexander S.
Defense Date:24 April 1986
Funding AgencyGrant Number
Defense Advanced Research Projects Agency (DARPA)3771
Office of Naval Research (ONR)N00014-79-C-0597
Record Number:CaltechETD:etd-03192008-143903
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:1023
Deposited By: Imported from ETD-db
Deposited On:03 Apr 2008
Last Modified:16 Apr 2021 22:19

Thesis Files

PDF (Li_pp_1986.pdf) - Final Version
See Usage Policy.


Repository Staff Only: item control page