Computing transitive closure on systolic arrays of fixed size

DOI10.1007/BF02252956zbMath0731.68087OpenAlexW2051233862MaRDI QIDQ808290

Björn Lisper

Publication date: 1991

Published in: Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

shortest pathtransitive closuresystolic arrayarray partitioning

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35) Discrete mathematics in relation to computer science (68R99) Distributed algorithms (68W15)

Related Items (1)

Mapping dynamic programming onto modular linear systolic arrays

Cites Work

• Synthesis of a new systolic architecture for the algebraic path problem
• A systolic array algorithm for the algebraic path problem (shortest paths; matrix inversion)
• Transitive closure and related semiring properties via eliminants
• The space complexity of pebble games on trees
• Parallel computation and conflicts in memory access
• Synthesizing synchronous systems by static scheduling in space-time
• An orthogonal systolic array for the algebraic path problem
• Partitioning and Mapping Algorithms into Fixed Size Systolic Arrays
• Synthesizing linear array algorithms from nested FOR loop algorithms
• Parallel Matrix and Graph Algorithms
• On the Analysis and Synthesis of VLSI Algorithms
• Asymptotically tight bounds on time-space trade-offs in a pebble game
• A transitive closure algorithm
• A Theorem on Boolean Matrices
• A block algorithm and optimal fixed-size systolic array processor for the algebraic path problem

This page was built for publication: Computing transitive closure on systolic arrays of fixed size