Title :
An extended dominating node approach to collective communication in all-port wormhole-routed 2D meshes
Author :
Tsai, Yih-Jia ; McKinley, Philip K.
Author_Institution :
Dept. of Comput. Sci., Michigan State Univ., East Lansing, MI, USA
Abstract :
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
Keywords :
graph theory; message passing; multiprocessor interconnection networks; parallel architectures; performance evaluation; scheduling; all-port communication architecture; all-port wormhole-routed 2D meshes; broadcast; collective communication; constituent unicast messages; distance-insensitivity; extended dominating node approach; graph theory; hardware support; matrix transposition; multiprocessor interconnection network; reduction; scheduling; simulation results; unicast; wormhole routed two dimensional meshes; Algorithm design and analysis; Broadcasting; Computational modeling; Computer architecture; Computer science; Hardware; Hypercubes; Network topology; Routing; Unicast;
Conference_Titel :
Scalable High-Performance Computing Conference, 1994., Proceedings of the
Conference_Location :
Knoxville, TN
Print_ISBN :
0-8186-5680-8
DOI :
10.1109/SHPCC.1994.296644
