Title :
Efficient termination detection for loosely synchronous applications in multicomputers
Author :
Xu, Chengzhong ; Lau, Francis C M
Author_Institution :
Dept. of Electr. & Comput. Eng., Wayne State Univ., Detroit, MI, USA
fDate :
5/1/1996 12:00:00 AM
Abstract :
We propose a simple algorithm which is based on edge-coloring of system graphs for termination detection of loosely synchronous computations. The proposed algorithm is fully symmetric in that all processors run syntactically identical code and can detect global termination at the same time. Under the 1-port communication model, the algorithm is optimal in terms of termination delay, the difference between the time when a global termination occurs and the time it is detected, in a number of structures-chain, ring of even number of nodes, k-ary n-cube and k-ary n-mesh of low degree, where k is even; and near-optimal for other cases. The optimality analysis is based on results from a related problem, periodic gossiping in edge-colored graphs. This algorithm has been applied to some practical cases in which the overhead due to its execution is found to be insignificant
Keywords :
graph colouring; multiprocessing systems; multiprocessor interconnection networks; parallel algorithms; system recovery; ata parallelism; distributed algorithms; edge-colored graphs; edge-coloring; efficient termination detection; global termination; interconnection networks; k-ary n-cube; k-ary n-mesh; loosely synchronous applications; loosely synchronous computations; multicomputers; one-port communication model; optimality analysis; periodic gossiping; system graphs; Computational modeling; Computer networks; Concurrent computing; Delay effects; Detection algorithms; Distributed algorithms; Distributed computing; Multiprocessor interconnection networks; Parallel processing; Peer to peer computing;
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on