TY - JOUR
T1 - Scalability of parallel algorithms for the all-pairs shortest-path problem
AU - Kumar, Vipin
AU - Singh, Vineet
PY - 1991/10
Y1 - 1991/10
N2 - This paper uses the isoefficiency metric to analyze the scalability of several parallel algorithms for finding shortest paths between all pairs of nodes in a densely connected graph. Parallel algorithms analyzed in this paper either have been previously presented elsewhere or are small variations of them. Scalability is analyzed with respect to mesh, hypercube, and shared-memory architectures. We demonstrate that isoefficiency functions are a compact and useful predictor of performance. In fact, previous comparative predictions of some of the algorithms based on experimental results are shown to be incorrect whereas isoefficiency functions predict correctly. We find the classic trade-offs of hardware cost vs time and memory vs time to be represented here as trade-offs of hardware cost vs scalability and memory vs scalability.
AB - This paper uses the isoefficiency metric to analyze the scalability of several parallel algorithms for finding shortest paths between all pairs of nodes in a densely connected graph. Parallel algorithms analyzed in this paper either have been previously presented elsewhere or are small variations of them. Scalability is analyzed with respect to mesh, hypercube, and shared-memory architectures. We demonstrate that isoefficiency functions are a compact and useful predictor of performance. In fact, previous comparative predictions of some of the algorithms based on experimental results are shown to be incorrect whereas isoefficiency functions predict correctly. We find the classic trade-offs of hardware cost vs time and memory vs time to be represented here as trade-offs of hardware cost vs scalability and memory vs scalability.
UR - http://www.scopus.com/inward/record.url?scp=0026237768&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0026237768&partnerID=8YFLogxK
U2 - 10.1016/0743-7315(91)90083-L
DO - 10.1016/0743-7315(91)90083-L
M3 - Article
AN - SCOPUS:0026237768
VL - 13
SP - 124
EP - 138
JO - Journal of Parallel and Distributed Computing
JF - Journal of Parallel and Distributed Computing
SN - 0743-7315
IS - 2
ER -