Title

Design Of Optimal Systolic Algorithms For The Transitive Closure Problem

Keywords

Data dependency; linear arrays; parallel algorithms; parallel machines; RCT diagram; systolic arrays; transitive closure problem; VLSI; WSI

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. © 1992 IEEE

Publication Date

1-1-1992

Publication Title

IEEE Transactions on Computers

Volume

41

Issue

4

Number of Pages

508-512

Document Type

Article

Identifier

scopus

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/12.135564

Socpus ID

0026853564 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0026853564

This document is currently not available here.

Share

COinS