Titre du document / Document title

A modular systolic linearization of the Warshall-Floyd algorithm

Auteur(s) / Author(s)

MYOUPO J. F. ⁽¹⁾ ; FABRET A. C. ;

Affiliation(s) du ou des auteurs / Author(s) Affiliation(s)

⁽¹⁾ LaRIA, Faculté de Mathématique et d'Informatique, Université de Picardie Jules Verne, 33, rue Saint Leu, 80039, Amiens, FRANCE

Résumé / 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.

Revue / Journal Title

IEEE transactions on parallel and distributed systems   ISSN 1045-9219   CODEN ITDSEO 

Source / Source

1996, vol. 7, n^o5, pp. 449-455 (25 ref.)

Langue / Language

Anglais

Editeur / Publisher

IEEE Computer Society, Los Alamitos, CA, ETATS-UNIS  (1990) (Revue)

Mots-clés anglais / English Keywords

Linearization ; Algorithm ; Modular programming ; Transitive closure ; Shortest path ; Matrix product ;

Mots-clés français / French Keywords

Linéarisation ; Algorithme ; Programmation modulaire ; Fermeture transitive ; Plus court chemin ; Produit matrice ; Modular linear systolic algorithms ;

Mots-clés espagnols / Spanish Keywords

Linearización ; Algoritmo ; Programación modular ; Cerradura transitiva ; Camino más corto ; Producto matriz ;

Localisation / Location

INIST-CNRS, Cote INIST : 22203, 35400004420361.0010