In this paper, we consider a tree-based routing scheme for supporting barrier synchronization on scalable parallel computers with a 2D mesh network. Based on the characteristics of a standard programming interface, the scheme builds a collective synchronization (CS) tree among the participating nodes using a distributed algorithm. When the routers are set up properly with the CS tree information, barrier synchronization can be accomplished very efficiently by passing simple messages. Performance evaluations show that our proposed method performs better than previous path-based approaches and is less sensitive to variations in group size and startup delay. However, our scheme has the extra overhead of building the CS tree. Thus, it is more suitable for parallel iterative computations in which the same barrier is invoked repetitively.

In this paper, we consider a hardware scheme for supporting barrier synchronization on scalable systems with a 2D mesh network. Our design takes into account of the program execution path in such systems-from programming interfaces down to routers. The hardware router design will be based on the MPI-1 standard. A distributed algorithm is proposed to construct a collective synchronization tree (CS tree) from the nodes participating in the barrier based upon the CS tree, the status registers in the routers are set up and synchronization messages are transmitted along the paths set by the status registers. Performance evaluations show that our proposed method has better performance for barrier synchronization and is less sensitive to variations in group size and startup delay than previous approaches. However our scheme has the extra overhead of building the CS tree. Thus it is more suitable for parallel iterative computations, in which the same barrier is invoked repetitively.