An orthogonal systolic array for the algebraic path problem

DOI10.1007/BF02309554MaRDI QIDQ1822502zbMATH OpenOpenAlexFDO

Authors Yves Robert, Denis Trystram

Publication date 1987

Published in Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02309554

zbMATH Keywords

algebraic path problemhardware algorithmsorthogonal systolic arrayparallel algorithms

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Parallel numerical computation (65Y05) Analysis of algorithms and problem complexity (68Q25) Cellular automata (computational aspects) (68Q80)

Review text

This paper is devoted to the design of an orthogonal systolic array of \(n(n+1)\) elementary processors which can solve any instance of the Algebraic Path Problem within only 5n-2 time steps, and is compared with the 7n-2 time steps of the hexagonal systolic array of \textit{G. Rote} [Computing 34, 191-219 (1985; Zbl 0546.68047)].

Recommendations

• scientific article; zbMATH DE number 3954292
• scientific article; zbMATH DE number 4003535
• A block algorithm and optimal fixed-size systolic array processor for the algebraic path problem
• scientific article; zbMATH DE number 64177
• scientific article; zbMATH DE number 3870611

Cites work

• A systolic array algorithm for the algebraic path problem (shortest paths; matrix inversion)
• scientific article; zbMATH DE number 3856291 (Why is no real title available?)
• scientific article; zbMATH DE number 3628373 (Why is no real title available?)
• Linear and combinatorial optimization in ordered algebraic structures

Cited in

(16)

• Complexity of the pipeline computation of a family of inner products
• Synthesis of size-optimal toroïdal arrays for the algebraic path problem: A new contribution
• Geometrical tools to map systems of affine recurrence equations on regular arrays
• Derivation of systolic algorithms for the algebraic path problem by recurrence transformations
• scientific article; zbMATH DE number 3870611 (Why is no real title available?)
• scientific article; zbMATH DE number 3954292 (Why is no real title available?)
• scientific article; zbMATH DE number 4058886 (Why is no real title available?)
• A systolic array for the assignment problem
• scientific article; zbMATH DE number 64177 (Why is no real title available?)
• A family of efficient regular arrays for algebraic path problem
• scientific article; zbMATH DE number 4003535 (Why is no real title available?)
• A block algorithm and optimal fixed-size systolic array processor for the algebraic path problem
• An incremental mechanical development of systolic solutions to the algebraic path problem
• Towards systolizing compilation
• Computing transitive closure on systolic arrays of fixed size
• An orthogonal systolic design for the assignment problem

This page was built for publication: An orthogonal systolic array for the algebraic path problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1822502)