An extended dominating node approach to collective communication in all-port wormhole-routed 2D meshes

A new model for the design of collective communication operations in wormhole-routed 20 mesh networks is introduced. While the resultant algorithms are unicast-based, in that they are implemented without special hardware support, they are designed to exploit both the distance-insensitivity of wormhole-routing and an all-port communication architecture, an which each node may simultaneously transmit (receive) messages on different channels. The method of defining and scheduling the constituent unicast messages is based on the identification and use of extended dominating nodes, which facilitate simultaneous transmission of many unicast messages in the network while avoiding contention among them. The method is used to develop new algorithms for broadcast, reduction and matrix transposition. Analysis and simulation results confirm the advantage of the new algorithms over other approaches