Designing tree-based barrier synchronization on 2D mesh networks
Authors:
- Jenq-Shyan YangJYJenq-Shyan Yang
- Chung-Ta KingCKChung-Ta King
- 1 June 1998
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 9 (6) , 526-534
Abstract
[[abstract]]©1998 IEEE-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[[department]]資訊工程學This publication has 13 references indexed in Scilit:
- The Network Architecture of the Connection Machine CM-5Journal of Parallel and Distributed Computing, 1996
- CCL: a portable and tunable collective communication library for scalable parallel computersIEEE Transactions on Parallel and Distributed Systems, 1995
- Deadlock-free multicast wormhole routing in 2-D mesh multicomputersIEEE Transactions on Parallel and Distributed Systems, 1994
- Unicast-based multicast communication in wormhole-routed networksIEEE Transactions on Parallel and Distributed Systems, 1994
- Notification and multicast networks for synchronization and coherenceJournal of Parallel and Distributed Computing, 1992
- Algorithms for scalable synchronization on shared-memory multiprocessorsACM Transactions on Computer Systems, 1991
- Deadlock-Free Message Routing in Multiprocessor Interconnection NetworksIEEE Transactions on Computers, 1987
- “Hot spot” contention and combining in multistage interconnection networksIEEE Transactions on Computers, 1985
- The NYU Ultracomputer—Designing an MIMD Shared Memory Parallel ComputerIEEE Transactions on Computers, 1983
- Virtual cut-through: A new computer communication switching techniqueComputer Networks (1976), 1979