DocumentCode :
3349073
Title :
Distributed termination detection of loosely synchronized computations
Author :
Xu, Chengzhong ; Lau, Francis C M
Author_Institution :
Dept. of Comput. Sci., Hong Kong Univ., Hong Kong
fYear :
1992
fDate :
1-4 Dec 1992
Firstpage :
196
Lastpage :
203
Abstract :
An efficient algorithm for termination detection of loosely synchronized computations is proposed. The proposed algorithm is fully symmetric in that all processes are syntactically identical and can detect global termination simultaneously. It is better in terms of the delay for termination detection than other related algorithms, and is optimal in a number of regular structures. For the hypercube structure of any dimension, the proposed algorithm takes two iteration steps to detect termination after global termination has occurred. In the chain, ring, mesh and torus structures, the improvement is about 50% over its principal competitor. The proposed algorithm requires that the graph be edge-colored and that the color-diameter be known to the processes in advance
Keywords :
delays; distributed processing; hypercube networks; program compilers; program verification; chain; color-diameter; delay; distributed termination detection; global termination; hypercube structure; loosely synchronized computations; mesh; ring; torus structures; Circuits; Computational modeling; Computer science; Concurrent computing; Delay; Detection algorithms; Distributed computing; Load management; Message passing; Signal processing algorithms;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel and Distributed Processing, 1992. Proceedings of the Fourth IEEE Symposium on
Conference_Location :
Arlington, TX
Print_ISBN :
0-8186-3200-3
Type :
conf
DOI :
10.1109/SPDP.1992.242744
Filename :
242744
Link To Document :
بازگشت