The Sync Model: A Parallel Execution Method for Logic Programming

Abstract

The Sync Model, a parallel execution method for logic programming, is preposed. 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 ordering algorithm and the merge algorithm are described. The merge algorithm is proved to be correct and therefore, the Sync Model is proved complete, i.e., the execution of a logic program under the Sync Model generates all the solutions.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1986
Accession Number
ADA442971

Entities

People

  • Alain J. Martin
  • Pey-yun P. Li

Organizations

  • California Institute of Technology

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Availability
  • Classification
  • Computer Programming
  • Computing-Related Activities
  • Contracts
  • Information Operations
  • Instructions
  • Monitoring
  • Multiprocessors
  • Security
  • Software Development
  • Standards

Fields of Study

  • Computer science

Readers

  • Computational Linguistics
  • Computer Science/Computer Engineering/Data Science/Digital Signal Processing.
  • Parallel and Distributed Computing.