Please use this identifier to cite or link to this item:
Title: A distributed-termination experiment on a mesh-connected array of processors
Authors: Song, J. 
Keywords: Asynchoronous iteration
distributed termination
finite element computation
hypercube computer
Issue Date: Jul-1992
Citation: Song, J. (1992-07). A distributed-termination experiment on a mesh-connected array of processors. Parallel Computing 18 (7) : 779-791. ScholarBank@NUS Repository.
Abstract: 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(√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. © 1992.
Source Title: Parallel Computing
ISSN: 01678191
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

checked on Oct 28, 2019

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.