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
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