DocumentCode
983357
Title
A modular systolic linearization of the Warshall-Floyd algorithm
Author
Myoupo, Jean Frédéric ; Fabret, Anne Cécile
Author_Institution
LaRI, Univ. de Picardie Jules Verne, Amiens, France
Volume
7
Issue
5
fYear
1996
fDate
5/1/1996 12:00:00 AM
Firstpage
449
Lastpage
455
Abstract
In this paper, we use a variant of the geometric method to derive efficient modular linear systolic algorithms for the transitive closure and shortest path problems. Furthermore, we show that partially-pipelined modular linear systolic algorithms with an output operation, for matrix multiplication, can be as fast as the fully-pipelined existing ones and, moreover, they need less cells
Keywords
matrix multiplication; parallel algorithms; systolic arrays; Warshall-Floyd algorithm; geometric method; linear systolic algorithms; matrix multiplication; modular linear systolic algorithms; partially-pipelined modular linear systolic algorithms; shortest path problems; systolic linearization; transitive closure; Algorithm design and analysis; Clocks; Computer Society; Computer architecture; Computer networks; Hardware; Partitioning algorithms; Shortest path problem; Systolic arrays; Very large scale integration;
fLanguage
English
Journal_Title
Parallel and Distributed Systems, IEEE Transactions on
Publisher
ieee
ISSN
1045-9219
Type
jour
DOI
10.1109/71.503769
Filename
503769
Link To Document