Solving some combinatorial problems on arrays with one-way dataflow (Q1825042)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Solving some combinatorial problems on arrays with one-way dataflow
scientific article

    Statements

    Solving some combinatorial problems on arrays with one-way dataflow (English)
    0 references
    0 references
    0 references
    0 references
    1990
    0 references
    Among various systolic architectures the ones with unidirectional flow of data provide some advantage at least from hardware designer's point of view - see e.g. \textit{R. Buschke} and \textit{J. Vysko\v{v}} [Reasons, techniques and solutions for linear systolic systems with unidirectional data flow, CONPAR 88, Proc. Conf. (1988)]. The article reviewed considers design of linear systolic arrays of this type for the following problems: ranking the elements in a chain, rooting a spanning tree and computing biconnected components of a connected graph. It is shown that all these problems can be solved using one-dimensional systolic array with unidirectional dataflow. Moreover a chain ranking algorithm has an interesting property, i.e. input data enters the array in arbitrary order. Also a biconnectivity algorithm is a little bit unusual one - it reads the input twice, or reads two copies of the input data. It is not clear whether this property is proper for unidirectional flow of data in solving this problem.
    0 references
    parallel graph algorithms
    0 references
    systolic arrays
    0 references
    unidirectional dataflow
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references