DESIGNING TREE-BASED BARRIER SYNCHRONIZATION ON 2D MESH NETWORKS

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 interf ace, the scheme builds a collective synchronization (CS) tree among th e participating nodes using a distributed algorithm. When the routers are set up properly with the CS tree information, barrier synchronizat ion can be accomplished very efficiently by passing simple messages. P erformance evaluations show that our proposed method performs better t han previous path-based approaches and is less sensitive to variations in group size and startup delay. However, our scheme has the extra ov erhead of building the CS tree. Thus, it is more suitable for parallel iterative computations in which the same barrier is invoked repetitiv ely.