PATH-BASED MULTICAST COMMUNICATION IN WORMHOLE-ROUTED UNIDIRECTIONAL TORUS NETWORKS

This paper addresses the problem of one-to-many or multicast, communic ation in wormhole-routed, n-dimensional torus networks, The proposed m ethods are designed for systems that support intermediate reception, w hich permits multidestination messages to be pipelined through several nodes, depositing a copy at each node, A key issue in the design of s uch systems is the routing function, which must support both unicast a nd multifast traffic while preventing deadlock among messages, An effi cient, deadlock-free routing function is developed and used as a basis for a family of multicast algorithms. The S-torus multicast algorithm uses a single multidestination message to perform an arbitrary multic ast operation, The M-torus algorithm is a generalized multiphase multi cast algorithm, in which a combination of multidestination messages is used to perform a multicast in one or more communication steps. Two s pecific instances of the M-torus algorithm, the M-d-torus and M-u-toru s multicast algorithms, are presented, These algorithms product conten tion-free multicast operations and are deadlock-free under all combina tions of network traffic. A simulation study compares the performance of the different multicast algorithms, and implementation issues are d iscussed. The results of this research are applicable to the design of architectures for both wormhole-routed massively parallel computers a nd high-speed local area networks with wormhole-routed switch fabrics. (C) 1997 Academic Press.