Design Of Optimal Systolic Algorithms For The Transitive Closure Problem

    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