Home

Unification in a Parallel Environment

Stephen Taylor; Daphne Tzoar; Salvatore Stolfo

Title:
Unification in a Parallel Environment
Author(s):
Taylor, Stephen
Tzoar, Daphne
Stolfo, Salvatore
Date:
Type:
Technical reports
Department:
Computer Science
Permanent URL:
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:
296
Metadata:
View

In Partnership with the Center for Digital Research and Scholarship at Columbia University Libraries/Information Services.