Path-Based Multicast Communication in Wormhole-Routed Unidirectional Torus Networks |
| |
Authors: | David F Robinson Philip K McKinley Betty HC Cheng |
| |
Affiliation: | aDepartment of Computer Science, Quincy University, Quincy, Illinois, 62301;bDepartment of Computer Science, Michigan State University, East Lansing, Michigan, 48824 |
| |
Abstract: | This paper addresses the problem of one-to-many, or multicast, communication in wormhole-routed,n-dimensional torus networks. The proposed methods are designed for systems that support intermediate reception, which permits multidestination messages to be pipelined through several nodes, depositing a copy at each node. A key issue in the design of such systems is the routing function, which must support both unicast and multicast traffic while preventing deadlock among messages. An efficient, deadlock-free routing function is developed and used as a basis for a family of multicast algorithms. TheS-torusmulticast algorithm uses a single multidestination message to perform an arbitrary multicast operation. TheM-torusalgorithm is a generalized multiphase multicast algorithm, in which a combination of multidestination messages is used to perform a multicast in one or more communication steps. Two specific instances of the M-torus algorithm, theMd-torusandMu-torusmulticast algorithms, are presented. These algorithms produce contention-free multicast operations and are deadlock-free under all combinations of network traffic. A simulation study compares the performance of the different multicast algorithms, and implementation issues are discussed. The results of this research are applicable to the design of architectures for both wormhole-routed massively parallel computers and high-speed local area networks with wormhole-routed switch fabrics. |
| |
Keywords: | multicast communication wormhole routing intermediate reception path-based routing collective communication |
本文献已被 ScienceDirect 等数据库收录! |
|