A SHORTEST-PATH ALGORITHM FOR BANDED MATRICES BY A MESH CONNECTION WITHOUT PROCESSOR PENALTY

Authors
MEI A IGARASHI Y
Citation
A. Mei et Y. Igarashi, A SHORTEST-PATH ALGORITHM FOR BANDED MATRICES BY A MESH CONNECTION WITHOUT PROCESSOR PENALTY, IEICE transactions on fundamentals of electronics, communications and computer science, E78A(3), 1995, pp. 389-394
Citations number
NO
Categorie Soggetti
Engineering, Eletrical & Electronic","Computer Science Hardware & Architecture","Computer Science Information Systems
Journal title
IEICE transactions on fundamentals of electronics, communications and computer science → ACNP
ISSN journal
09168508
Volume
E78A
Issue
3
Year of publication
1995
Pages
389 - 394
Database
ISI
SICI code
0916-8508(1995)E78A:3<389:ASAFBM>2.0.ZU;2-Q
Abstract
We give an efficient shortest path algorithm on a mesh-connected proce ssor array for n x n banded matrices with bandwidth b. We use a [b/2xb /2] semisystolic processor array. The input data is supplied to the pr ocessor array from the host computer. The output from the processor ar ray can be also supplied to itself through the host computer. This alg orithm computes all pair shortest distances within the band in 7n-4[b/ 2]-1 steps.