AN EXTENDED DOMINATING NODE APPROACH TO BROADCAST AND GLOBAL COMBINE IN MULTIPORT WORMHOLE-ROUTED MESH NETWORKS

A new approach to the design of collective communication operations in wormhole-routed mesh networks is described. The approach extends the concept of dominating sets in graph theory by accounting for the relat ive distance-insensitivity of the wormhole switching strategy and by t aking advantage of a multiport communication architecture, which allow s each node to simultaneously transmit messages on different outgoing channels. Collective communication operations are defined in terms of sets of extended dominating nodes (EDNs). The nodes in a set of EDNs c an deliver (receive) messages to (from) a different, larger set of nod es in a single message-passing step under dimension-ordered wormhole r outing and without channel contention among messages. The EDN model ca n be applied to different collective operations in 2D and 3D mesh netw orks. In this paper, we focus on EDN-based broadcast and global combin e operations. Performance evaluation results are presented that confir m the advantage of this approach over other methods.