DocumentCode
2370130
Title
A shortest path algorithm for banded matrices by a mesh connection without processor penalty
Author
Mei, Aohan ; Igarashi, Yoshihide
Author_Institution
Dept. of Comput. Sci., Gunma Univ., Japan
fYear
1994
fDate
14-16 Dec 1994
Firstpage
159
Lastpage
166
Abstract
We give an efficient shortest path algorithm on a mesh-connected processor array for n×n banded matrices with bandwidth b. We use a [b/2]×[b/2] semisystolic processor array. The input data is supplied to the processors array from the host computer. The output from the processor array can be also supplied to itself through the host computer. This algorithm computes all pair shortest distances within the band in 7n-4[b/2]-1 steps
Keywords
computational complexity; directed graphs; parallel algorithms; systolic arrays; all pair shortest distances; banded matrices; mesh connection; processor penalty; semisystolic processor array; shortest path algorithm; Bandwidth; Clocks; Computational modeling; Computer science; Concurrent computing; Parallel algorithms; Parallel architectures; Phase change random access memory; Pipeline processing; Shortest path problem;
fLanguage
English
Publisher
ieee
Conference_Titel
Parallel Architectures, Algorithms and Networks, 1994. (ISPAN), International Symposium on
Conference_Location
Kanazawa
Print_ISBN
0-8186-6507-6
Type
conf
DOI
10.1109/ISPAN.1994.367151
Filename
367151
Link To Document