Multicasting in multistage interconnection networks
Chi-Ming Chiang · Michigan State University Libraries · 1995
Multicast communication, also known as multi-point communication, refers to the delivery of a message from a single source node to a number of destination nodes. It is a frequently used communication pattern in distributed-memory parallel computers and computer networks. Multistage interconnection networks (MINs) have resurged as another popular class of interconnection architecture for constructing scalable parallel computers and high speed network switches. While efficient implementation of multicast communication is critical to the performance of message-based scalable parallel computers and switch-based high speed networks, little research has been devoted to supporting multicast in MINs. Unlike unicast communication, the size of a header in a multicast message depends on the number of destinations, the distribution of destinations, and the multi-address encoding/decoding schemes. This research suggests and compares six different multi-address encoding/decoding schemes to shorten the header which is an overhead to the system. Each of them has its own advantages and disadvantages. An appropriate choice of the multi-address encoding scheme depends on the destination pattern and is detailed in this research. Several efficient multicast algorithms, both hardware and software implementations, for unidirectional wormhole-switched MINs are proposed in this research. The hardware implementation offers better performance than the software approach. Tree-based hardware approaches for wormhole-switched MINs, namely multi-head worms, require special mechanisms to avoid potential deadlocks when there are multiple multicasts. As shown in this research, the hardware approaches to support multicast should be considered in the design of high performance networks. In systems which do not support hardware multicast, multicast must be implemented atop existing unicast communications. This research proposes an efficient unicast-based multicast (or software multicast) algorithm for such systems. While Banyan MINs are limited to a unique routing path between any source and destination pair, an extra stage MIN can provide extra routing paths. Extra routing paths can reduce the message transmission blocking probability and allow additional flexibility in selecting a routing path. An algorithm to find a traffic-optimal multicast tree in such networks within polynomial time is proposed. Many new ideas and new algorithms are proposed to support efficient multicast communication in wormhole-switched MINs. Performance evaluation and comparison of different approaches are conducted through extensive simulation experiments. Research results obtained from this work will be extremely useful to parallel computer and network switch designers who wish to support multicast in their designs.