Title

Design Of Optimal Systolic Algorithms For The Transitive Closure Problem

Authors

Authors

D. Sarkar;A. Mukherjee

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abbreviated Journal Title

IEEE Trans. Comput.

Keywords

Data Dependency; Linear Arrays; Parallel Algorithms; Parallel Machines; Rct Diagram; Systolic Arrays; Transitive Closure Problem; Vlsi; Wsi; Computer Science, Hardware & Architecture; Engineering, Electrical &; Electronic

Abstract

We present new optimal systolic algorithms for the transitive closure problem on ring and linear array of processors. The data dependency of the Warshal-Floyd algorithm is exploited to obtain highly pipelined parallel algorithms. One of the algorithms is asymptotically seven times cost-effective than the existing algorithms for computing transitive closure problems. We introduce a new expository device, called the RCT diagram, that depicts simultaneous flow of data and computation for parallel algorithms.

Journal Title

Ieee Transactions on Computers

Volume

41

Issue/Number

4

Publication Date

1-1-1992

Document Type

Note

Language

English

First Page

508

Last Page

512

WOS Identifier

WOS:A1992HR64900013

ISSN

0018-9340

Share

COinS