Termination Detection for Parallel Shortest Path Algorithms

The full text article is not available for purchase.

The publisher only permits individual articles to be downloaded by subscribers.


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. Copyright 1998 Academic Press.

Document Type: Research Article

Affiliations: 1: ECE Department, Northwestern University, 2145 Sheridan Road, Evanston, Illinois, 60208-3118 2: Department of Civil and Materials Engineering, University of Illinois at Chicago, 842 West Taylor Street, Chicago, Illinois, 60607-7023

Publication date: December 1, 1998

Related content



Share Content

Access Key

Free Content
Free content
New Content
New content
Open Access Content
Open access content
Subscribed Content
Subscribed content
Free Trial Content
Free trial content
Cookie Policy
Cookie Policy
ingentaconnect website makes use of cookies so as to keep track of data that you have filled in. I am Happy with this Find out more