A DISTRIBUTED-TERMINATION EXPERIMENT ON A MESH-CONNECTED ARRAY OF PROCESSORS

In totally asynchronous computation any number of processing elements (PEs) may start simultaneously. Termination detection for it is difficult because of asynchronousness and lack of single root (initiator) to accumulate termination information. This paper presents a symmetric, asynchronous, and distributed solution to the above problem for a mesh-connected array of PEs and its implementation and comparison on a parallel computer. Our algorithm produces less messages for termination purpose than the various counter token schemes. The worst time for it to finish is O(square-root n), where n is the number of PEs on a square mesh. An experiment on a 64-node NCUBE parallel computer showed that it was at least twice as fast as a centralized termination detection algorithm. The algorithm makes three assumptions: only nearest-neighbor communication exists; activation messages are always broadcast to all neighboring PEs to avoid deadlock; and any number of PEs can initiate the computation. It defines tokens and dependency arcs: tokens to collect termination states of regions of the mesh and dependency arcs to establish terminating precedence among connected PEs. They together reduce the number of messages for termination detection. Two sufficient conditions are shown to guarantee that any one of the PEs may detect termination. Although the algorithm was originated for use with totally asynchronous computations for the finite element analysis, it is applicable to any iterative computations on a mesh.