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
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;
Conference_Titel :
Parallel and Distributed Processing, 1992. Proceedings of the Fourth IEEE Symposium on
Conference_Location :
Arlington, TX
Print_ISBN :
0-8186-3200-3
DOI :
10.1109/SPDP.1992.242744