TY - JOUR
T1 - Termination Detection for Parallel Shortest Path Algorithms
AU - Hribar, Michelle R.
AU - Taylor, Valerie E.
AU - Boyce, David E.
N1 - Funding Information:
Michelle Hribar was supported by a National Science Foundation Graduate Fellowship and the Department of Energy. Valerie Taylor is supported by NSF Young Investigator award under Grant CCR-9357781 and Allied Signal, Inc. David Boyce is supported by the National Science Foundation through Grant DMS-9313113 to the National Institute of Statistical Sciences.
PY - 1998/12/15
Y1 - 1998/12/15
N2 - Shortest path computation is required by a large number of applications such as VLSI, transportation, and communication networks. These applications, which are often very complex and have sparse networks, generally use parallel labeling shortest path algorithms. Such algorithms, when implemented on a distributed memory machine, require termination detection methods; these methods consist of some type of synchronization among all processors. Because global synchronization can be costly, it is assumed that the best termination detection methods synchronize as infrequently as possible. The frequency, however, can significantly impact the idle time of parallel labeling shortest path algorithms. In this paper we analyze the impact of this frequency on the performance, in particular the idle time, and identify when low versus high frequency detection is best. The analysis and results indicate that when the size of the subnetwork assigned to processor is small enough so that the computation time is less than or equal to the communication time within an iteration, high frequency termination detection methods should be used. Otherwise, low frequency methods should be used.
AB - Shortest path computation is required by a large number of applications such as VLSI, transportation, and communication networks. These applications, which are often very complex and have sparse networks, generally use parallel labeling shortest path algorithms. Such algorithms, when implemented on a distributed memory machine, require termination detection methods; these methods consist of some type of synchronization among all processors. Because global synchronization can be costly, it is assumed that the best termination detection methods synchronize as infrequently as possible. The frequency, however, can significantly impact the idle time of parallel labeling shortest path algorithms. In this paper we analyze the impact of this frequency on the performance, in particular the idle time, and identify when low versus high frequency detection is best. The analysis and results indicate that when the size of the subnetwork assigned to processor is small enough so that the computation time is less than or equal to the communication time within an iteration, high frequency termination detection methods should be used. Otherwise, low frequency methods should be used.
KW - Parallel shortest path; idle time; synchronization; termination detection
UR - http://www.scopus.com/inward/record.url?scp=0004250247&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0004250247&partnerID=8YFLogxK
U2 - 10.1006/jpdc.1998.1502
DO - 10.1006/jpdc.1998.1502
M3 - Article
AN - SCOPUS:0004250247
SN - 0743-7315
VL - 55
SP - 153
EP - 165
JO - Journal of Parallel and Distributed Computing
JF - Journal of Parallel and Distributed Computing
IS - 2
ER -