Browse Prior Art Database

The Sync Model: A Parallel Execution Method for Logic Programming

IP.com Disclosure Number: IPCOM000127952D
Original Publication Date: 1986-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 20 page(s) / 59K

Publishing Venue

Software Patent Institute

Related People

Pey-yun Peggy Li: AUTHOR [+4]

Abstract

The Sync Model, a parallel execution method for logic programming, is pro- posed. 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 mul- tiprocessor 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 algo- rithm 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. The research described in this paper was sponsored by the Defense Advanced Re-search Projects Adency, ARPA Order No. 3771, and monitored by the Office of Naval Research under contract number N00014-79-C-0597.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 6% of the total text.

Page 1 of 20

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

The Sync Model: A Parallel Execution Method for Logic Programming

Pey-yun Peggy Li and Alain J. Martin Computer Science California Institute of Technology Pasadena CA 91125

March 1980

5221 :TR : 86

Abstract

The Sync Model, a parallel execution method for logic programming, is pro- posed. 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 mul- tiprocessor 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 algo- rithm 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. The research described in this paper was sponsored by the Defense Advanced Re-search Projects Adency, ARPA Order No. 3771, and monitored by the Office of Naval Research under contract number N00014-79-C-0597.

1 Introduction

One way to improve the efficiency in the execution of a logic program is to exploit the potential parallelism, namely AND parallelism and OR parallelism, inherent to the program. In this paper, a method - called the "Sync Model" - is proposed for the parallel execution of logic programs on a message-passing multiprocessor system. The method realized both AND-parallelism and OR- parallelism. OR parallelism - the parallel execution of all clauses that are unifiable with the goal - is easier to realize than AND parallelism because the executions of OR clauses are independent of each other. On a message-passing system, the synchronization of the multiple solutions gener- ated by different processes is the major problem in the implementation of OR parallelism. AND parallelism-the parallel execution of AND literals in a clause body-may result in binding conflicts for a variable shared by several literals. Constructing a data flow graph is the most common approach for AND parallelism. By allowing exactly one producer for each shared variable, binding conflicts can be eliminated. One problem in the data flow approach is that the data flow graph is changed dynamically according to the binding q values transmitted within the graph. When a variable is bound to a partially instantiated term containing another variable, binding conflicts may occur. Therefore, the data flow graph needs to be modified to enforce the "one producer per variable" rule to the new variable. In most computation models for concurrent logic programming languages, the data flow graph of literals in a clause body is constructed by the programmer through variable annotations. Alternatively, t...