An efficient parallel termination detection algorithm

Abstract

In this paper, we present a new, easy to implement algorithm for detecting the termination of a parallel asynchronous computation on distributed-memory MIMD computers. We demonstrate that it operates concurrently with the main computation, adding minimal overhead, and we prove that it correctly detects termination when it occurs. Experimental results confirm that the termination detection routine imposes an overhead smaller than the experimental uncertainty.

Keywords:

• Termination detection
• Asynchronous termination
• Distributed computing

Keywords:

• D.1.3

Notes

^†Email: [email protected]. The work of this author was supported by the National Science Foundation under grant no. ACR-93-57812 while in residence at the University of Colorado. Portions of this work were performed under the auspices of the US Department of Energy by University of California Lawrence Livermore National Laboratory under contract No. W-7405-Eng-48.

^§Email: [email protected]. The work of this author was supported by the National Science Foundation under grant no. ACR-93-57812 and by the Department of Energy under grant no. DE-FG03-97ER25325.

^¶The work of this author was supported by the National Science Foundation under grant no. ACR-93-57812 and by the Department of Energy under grant no. DE-FG03-97ER25325.

Additional information

Notes on contributors

A. H. Baker

‡ †Email: [email protected]. The work of this author was supported by the National Science Foundation under grant no. ACR-93-57812 while in residence at the University of Colorado. Portions of this work were performed under the auspices of the US Department of Energy by University of California Lawrence Livermore National Laboratory under contract No. W-7405-Eng-48.

S. Crivelli

§ §Email: [email protected]. The work of this author was supported by the National Science Foundation under grant no. ACR-93-57812 and by the Department of Energy under grant no. DE-FG03-97ER25325.

E. R. Jessup

¶ ¶The work of this author was supported by the National Science Foundation under grant no. ACR-93-57812 and by the Department of Energy under grant no. DE-FG03-97ER25325.