Title:

Unification in a Parallel Environment

Author(s):

Taylor, Stephen
Tzoar, Daphne
Stolfo, Salvatore

Date:

1984

Type:

Technical reports

Department:

Computer Science

Permanent URL:

http://hdl.handle.net/10022/AC:P:11628

Series:

Columbia University Computer Science Technical Reports

Part Number:

CUCS-097-84

Publisher:

Department of Computer Science, Columbia University

Publisher Location:

New York

Abstract:

This paper presents a method which allows standard data structure sharing techniques to be applied in a parallel environment. The techniques used are explained in the context of many parallel processors executing the same unification algorithm on different data concurrently. This operation can create complex structures to be transmitted between processors and naive algorithms could take an exponential amount of time to achieve the communication. The approach is compared to that advocated for the FFP machine. To demonstrate the techniques, we describe how a linear unification algorithm may be executed locally at each parallel processor and a single chosen resolvent communicated through an interconnection network to other processors. The structures are transmitted without applying substitutions and can be recreated at the receiver. The algorithms were developed as part of basic research related to the parallel Logic Programming System (LPS) under design at Columbia University. They have been implemented on a working prototype parallel machine, DADO1.

Subject(s):

Computer science

Item views:

279

Metadata:

description

View | Download