A fast tree-based barrier synchronization on switch-based irregular networks
Sangman Moh, Chansu Yu, HY Youn, Dohyung Han, B.Lee Lee, D.Lee Lee · 2000
Cooperating processes in different nodes of cluster systems exchange messages through the switch-based network of irregular topology, and the corresponding communication performance is the most critical factor in assessing the overall system performance. In particular, barrier synchronization among multiple processes in a process group usually constitutes the sequential or bottleneck part of a parallel program. In this paper, we propose a Barrier Tree for Irregular Networks (BTIN) and a barrier synchronization scheme using BTIN. The synchronization latency of the proposed BTIN scheme is asymptotically O(log n) while that of the fastest scheme reported in the literature is bounded by O(n), where n is the number of member nodes. Extensive simulation study shows that for the group size of 256 the BTIN scheme improves the synchronization latency by a factor of 3.3 3.8. It is also shown to be more scalable than conventional schemes with less network traffic. Index terms: Cluster systems, switch-based network, irregular topology, barrier synchronization, hardware-supported barriers, communication latency, wormhole routing, MPI. 1 1