.png){kind=icon}
Return
Termination detection for parallel shortest path algorithms
.png){kind=icon}
PRE
AI
DOI：10.1006/jpdc.1998.1502.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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. (C) 1998 Academic Press.
Keywords:
parallel shortest path
idle time
synchronization
termination detection
Journal
IF:
4
Papers:
3.8K
Citations:
4.8K
Organization
No organization information available
Cited Papers
Similarity judgments and cortical visual responses reflect different properties of object and scene categories in naturalistic images.png)
NeuroImage
OAAI
NeuroImageIF0
OAAIShareSaveShareSaveShareSave no more
no more