Citation
Li, Peyyun Peggy (1986) A Parallel Execution Model for Logic Programming. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/2ngs-bp80. https://resolver.caltech.edu/CaltechETD:etd-03192008-143903
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: | 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): |
| ||||||
Thesis Committee: |
| ||||||
Defense Date: | 24 April 1986 | ||||||
Funders: |
| ||||||
Record Number: | CaltechETD:etd-03192008-143903 | ||||||
Persistent URL: | https://resolver.caltech.edu/CaltechETD:etd-03192008-143903 | ||||||
DOI: | 10.7907/2ngs-bp80 | ||||||
Default Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||
ID Code: | 1023 | ||||||
Collection: | CaltechTHESIS | ||||||
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. 8MB |
Repository Staff Only: item control page