CaltechAUTHORS
  A Caltech Library Service

A Parallel Execution Model for Logic Programming

Li, Peyyun Peggy (1986) A Parallel Execution Model for Logic Programming. California Institute of Technology . (Unpublished) http://resolver.caltech.edu/CaltechCSTR:1986.5227-tr-86

[img]
Preview
Postscript
See Usage Policy.

10Mb
[img]
Preview
Other (Adobe PDF (9.5MB))
See Usage Policy.

9Mb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechCSTR:1986.5227-tr-86

Abstract

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:Report or Paper (Technical Report)
Group:Computer Science Technical Reports
Record Number:CaltechCSTR:1986.5227-tr-86
Persistent URL:http://resolver.caltech.edu/CaltechCSTR:1986.5227-tr-86
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26663
Collection:CaltechCSTR
Deposited By: Imported from CaltechCSTR
Deposited On:20 Apr 2001
Last Modified:26 Dec 2012 14:01

Repository Staff Only: item control page