Broadcast. The same message is delivered from the sender to all receivers.

 Scatter. The sender delivers different messages to different receivers. This is also referred to as personalized broadcast.

 Reduce. Different messages from different senders are combined together to form a single message for the receiver. The combining operator is usually commutative and associative, such as addition, multiplication, maximum, minimum, and the logical OR, AND, and exclusive OR operators. This service is also referred to as personalized combining or global combining.

 Gather. Different messages from different senders are concatenated together for the receiver. The order of concatenation is usually dependent on the ID of the senders.

 All-broadcast. All processes perform their own broadcast. Usually, the received n messages are concatenated together based on the ID of the senders. Thus, all processes have the same set of received messages. This service is also referred to as gossiping or total exchange.

 All-scatter. All processes perform their own scatter. The n concatenated messages are different for different processes. This service is also referred to as personalized all-to-all broadcast, index, or complete exchange.

 All combining. The result of a reduce operation is available to all processes. This is also referred to as a reduce and spread operation. The result may be broadcast to all processes after the reduce operation, or multiple reduce operations are performed with each process as a root.

 Barrier synchronization. A synchronization barrier is a logical point in the control flow of an algorithm at which all processes in a process group must arrive before any of the processes in the group are allowed to proceed further. Obviously, barrier synchronization involves a reduce operation followed by a broadcast operation.

 Scan. A scan operation performs a parallel prefix with respect to a commutative and associative combining operator on messages in a process group. Figure 5.5(a) shows a parallel prefix operation in a four-member process group with respect to the associative combining operator f. Apparently, a scan operation involves many reduce operations. The reverse (or downward) of parallel prefix is called parallel suffix, as shown in Figure 5.5(b).

Multicast Path Problem

In some communication mechanisms, replication of an incoming message in order to be forwarded to multiple neighboring nodes may involve too much overhead and is usually undesirable. Thus, the routing method does not allow each processor to replicate the message passing by. Also, a multicast path model provides better performance than the tree model (to be described below) when there is contention in the network. From a switching technology point of view, the multicast path model is more suitable for wormhole switching.

The multicast communication problem becomes the problem of finding a shortest path starting from u₀ and visiting all k destination nodes. This optimization problem is the finding of an optimal multicast path (OMP) and is formally defined below.

Multicast Cycle Problem

Reliable communication is essential to a message-passing system. Usually, a separate acknowledgment message is sent from every destination node to the source node on receipt of a message. One way to avoid the sending of |K| separate acknowledgment messages is to have the source node itself receive a copy of the message it initiated after all destination nodes have been visited. Acknowledgments are provided in the form of error bits flagged by intermediate nodes when a transmission error is detected. Thus, the multicast communication problem is the problem of finding a shortest cycle, called the optimal multicast cycle (OMC), for K.

Steiner Tree Problem

Both OMC and OMP assume that the message will not be replicated by any node during transmission. However, message replication can be implemented by using some hardware approach [197]. If the major concern is to minimize traffic, the multicast problem becomes the well-known Steiner tree problem [121]. Formally, we restate the Steiner tree problem as follows:

Multicast Tree Problem

In the Steiner tree problem, it is not necessary to use a shortest path from the source to a destination. If the distance between two nodes is not a major factor in the communication time, such as in VCT, wormhole, and circuit switching, the above optimization problem is appropriate. However, if the distance is a major factor in the communication time, such as in SAF switching, then we may like to minimize time first, then traffic. The multicast communication problem is then modeled as an optimal multicast tree (OMT). The OMT problem was originally defined in [195].

Apparently, the complexity of each of the above optimization problems is directly dependent on the underlying host graph. The above graph optimization problems for the popular hypercube and 2-D mesh topologies were studied in [210, 212], showing that the OMC and OMP problems are NP-complete for those topologies. Also, it was shown that the MST and OMT problems are NP-complete for the hypercube topology [60, 135]. The MST problem for the 2-D mesh topology is equivalent to the rectilinear Steiner tree problem, which is NP-complete [120].

The NP-completeness results indicate the necessity to develop heuristic multicast communication algorithms for popular interconnection topologies. Multicast communication may be supported in hardware, software, or both. Sections 5.5 and 5.7 will address hardware and software implementations, respectively, of multicast.

Broadcast Tree for Hypercube

Consider an n-cube topology. An original version of the following broadcast algorithm, which produces a spanning binomial tree based on the concept of recursive doubling, was proposed by Sullivan and Bashkow [334]. Each node in the system will receive the broadcast message exactly once and in no later than n time steps. Let s be the address of the source node and v be the node receiving a broadcast message. The broadcast algorithm is listed in Figure 5.10.

The function FirstOne(v) indicates the location of the least significant 1 in an n-bit binary number v. If v_k = 1 and v_j = 0 for all 0 ≤ j ≤ k − 1, then FirstOne(v) = k. If v = 0, then k = n.

Deadlock in Tree-Based Multicast Wormhole Switching

The spanning binomial tree is suitable for networks supporting SAF or VCT switching techniques. When combined with wormhole switching, tree-based multicast routing suffers from several drawbacks. Since there is no message buffering at routers, if one branch of the tree is blocked, then all are blocked (Figure 5.12). For the sake of clarity, input and output buffers in the figure have capacity for a single flit. Flit A at node N₅ cannot advance because the next requested channel is busy. As a consequence, flit C cannot be replicated and forwarded to node N₅. Blockage of any branch of the tree can prevent delivery of the message even to those destination nodes to which paths have been successfully established. For example, flits A and B at nodes N₃ and N₂ can advance and reach the destination node N₄. However, flits at node N₁ cannot advance. Tree-based multicast routing may cause a message to hold many channels for extended periods, thereby increasing network contention. Moreover, deadlock can occur using such a routing scheme. The nCUBE-2 [248], a wormhole-switched hypercube, uses a spanning binomial tree approach to support broadcast and a restricted form of multicast in which the destinations form a subcube.

Figure 5.13 shows a deadlocked configuration on a 3-cube. Suppose that nodes 000 and 001 simultaneously attempt to transmit broadcast messages A and B, respectively. The broadcast message A originating at host 000 has acquired channels [000, 001], [000, 010], and [000, 100]. The header flit has been duplicated at router 001 and is waiting on channels [001, 011] and [001, 101]. The B broadcast has already acquired channels [001, 011], [001, 101], and [001, 000] but is waiting on channels [000, 010] and [000, 100]. The two broadcasts will block forever.

In a similar manner, you may attempt to extend deadlock-free unicast routing on a 2-D mesh to encompass multicast. An extension of the XY routing method to include multicast is shown in Figure 5.14, in which the message is delivered to each destination in the manner described. As in the hypercube example, the progress of the tree requires that all branches be unblocked. For example, suppose that the header flit in Figure 5.14 is blocked due to the busy channel [(4, 2), (4, 3)]. Node (4, 2) cannot buffer the entire message. As a result of this constraint, the progress of messages in the entire routing tree must be stopped. In turn, other messages requiring segments of this tree are also blocked. Network congestion may be increased, thereby degrading the performance of the network. Moreover, this routing algorithm can lead to deadlock. Figure 5.15 shows a deadlocked configuration with two multicasts, A and B.

In Figure 5.15(a), A has acquired channels [(1, 1), (0, 1)] and [(1, 1), (2, 1)], and requests channel [(2, 1), (3, 1)], while B has acquired channels [(2, 1), (3, 1)] and [(2, 1), (1, 1)], and requests channel [(1, 1), (0, 1)]. Figure 5.15(b) shows the details of the situation for the nodes (0, 1), (1, 1), (2, 1), and (3, 1). Because neither node (1, 1) nor node (2, 1) buffers the blocked message, channels [(1, 1), (0, 1)] and [(2, 1), (3, 1)] cannot be released. Deadlock has occurred.

The next section presents a multicast wormhole routing algorithm based on the concept of network partitioning, which is equivalent to the concept of virtual networks presented in Section 4.4.3. A multicast operation is implemented as several submulticasts, each destined for a proper subset of the destinations and each routed in a different subnetwork. Because the subnetworks are disjoint and acyclic, no cyclic resource dependency can exist. Thus, the multicast routing algorithms are deadlock-free.

Double-Channel XY Multicast Wormhole Routing

The following double-channel XY multicast routing algorithm for wormhole switching was proposed by Lin, McKinley, and Ni [206] for 2-D mesh.

The algorithm uses an extension of the XY routing algorithm, which was shown above to be susceptible to deadlock. In order to avoid cyclic channel dependencies, each channel in the 2-D mesh is doubled, and the network is partitioned into four subnetworks, N_+X,+Y, N_+X,–Y, N_–X,+Y, and N_−X,–Y, as in Section 4.4.3. Subnetwork N_+X,+Y contains the unidirectional channels with addresses [(i, j), (i + 1, j)] and [(i, j), (i, j + 1)], subnetwork N_+X,–Y contains channels with addresses [(i, j), (i + 1, j)] and [(i, j), (i, j − 1)], and so on. Figure 5.16 shows the partitioning of a 3 × 4 mesh into the four subnetworks.

For a given multicast, the destination node set D is divided into at most four subsets, D_+X,+Y, D_+X,–Y, D_–X,+Y, and D_–X,–Y, according to the relative positions of the destination nodes and the source node u₀. Set D_+X,+Y contains the destination nodes to the upper right of u₀, D_+X,–Y contains the destinations to the lower right of u₀. and so on.

The multicast is thus partitioned into at most four submulticasts from u₀ to each of D_+X,+Y, D_+X–Y, D_–X,+Y, and D_–X,–Y. The submulticast to D_+X,+Y will be implemented in subnetwork N_+X,+Y using XY routing, D_+X,–Y in subnetwork N_+X,–Y, and so on. The message routing algorithm is given in Figure 5.17. Example 5.4 illustrates the operation of the algorithm.

While this multicast tree approach avoids deadlock, a major disadvantage is the need for double channels. It may be possible to implement double channels with virtual channels; however, the signaling for multicast communication is more complex. Moreover, the number of subnetworks grows exponentially with the number of dimensions of the mesh, increasing the number of channels between every pair of nodes accordingly.

Tree-Based Multicast with Pruning

Tree-based multicast routing is more suitable for SAF or VCT switching than for wormhole switching. The reason is that when a branch of the tree is blocked, the remaining branches cannot advance if wormhole switching is used. There is a special case in which tree-based multicast routing is suitable for networks using wormhole switching: the implementation of invalidation or update commands in DSMs with coherent caches [224]. Taking into account the growing interest in these machines, it is worth studying this special case.

Message data only require a few flits. Typically, a single 32-bit flit containing a memory address is enough for invalidation commands. The command itself can be encoded in the first flit together with the destination node address. An update command usually requires one or two additional flits to carry the value of the word to be updated. Hence, it is possible to design compact hardware routers with buffers deep enough to store a whole message. However, when multicast routing is considered, the message header must encode the destination addresses. As a consequence, message size could be several times the data size. Moreover, messages have a very different size depending on the number of destinations, therefore preventing the use of fixed-size hardware buffers to store a whole message. A possible solution consists of encoding destination addresses as a bit string (see Section 5.5.1) while limiting the number of destination nodes that can be reached by each message to a small value. This approach will be studied in Section 5.6 and applied to the implementation of barrier synchronization and reduction.

An alternative approach consists of using a fixed-size input buffer for flit pipelining (as in wormhole switching) and a small fixed-size data buffer to store the whole message data (as in VCT switching, except that destination addresses are not stored) [224]. This approach combines the advantages of wormhole switching and VCT switching. Its most important advantage is that a fixed and small buffer size is required for every channel, regardless of the number of destinations of the message. As a consequence, routers are compact and fast. As buffers are small, flits containing the destination addresses cannot be buffered at a single node, usually spanning several nodes. The main limitation of this mechanism is that it only works when message data can be completely buffered at each node.

In order to allow data flits to be buffered at a given node even when the next channel requested by the message is busy, a special message format is used. Figure 5.19 shows the format of a multicast message. The first flit of each message, d₁, encodes the first destination address. It is followed by the data flits of the message and the remaining destination addresses, d₂, d₃, …, d_n. As we will see, this message format will be kept while the message advances and produces new branches.

The architecture of a router supporting the message format described above is very similar to the one for tree-based multicast routing. However, it requires a few changes. When the first flit of a message reaches a node, it is routed as usual, reserving the requested output channel if it is free. The next few flits contain the message data. As these flits arrive, they are copied to the data buffer of the input channel and transferred across the switch. The remaining flits, if any, contain additional destination addresses. These flits are routed in the same way as the first flit of the message. If the output channel requested by a destination address flit d_i was already reserved by a previously routed flit d_j, 1 ≤ j ≤ i, then d_i is simply forwarded across the switch. Otherwise, d_i reserves a new output channel. In this case, d_i is forwarded across the switch, immediately followed by the message data flits previously stored in the data buffer. By doing so, the message forwarded across the new branch conforms to the format indicated in Figure 5.19. While data flits are being appended to the new branch of the message, incoming address flits are stored in the input buffer. Note that data only require a few flits. Also, routing each additional destination address flit d_i can be done in parallel with the transmission of d_i–1 across the switch.

Tree-based multicast routing is susceptible to deadlock. However, when message data only require a few flits, deadlock can be recovered from by pruning branches from the tree when a branch is blocked [224]. This mechanism relies on the use of data buffers to hold the message data, as described above. As shown in Figure 5.12, when a channel is busy, flit buffers are filled and flow control propagates backward, reaching the source node n_b of the branch. When this occurs, flits cannot be forwarded across any branch of the tree starting at n_b. The pruning mechanism consists of pruning all the branches of the tree at n_b except the one that was blocked. Pruning is only performed at the source node of the blocked branch. However, if flow control continues stopping flits at other nodes, pruning is also performed at those nodes.

Note that when using the described pruning mechanism, each pruned branch contains a message according to the format described in Figure 5.19. In particular, that message carries one or more destination address flits and all the data flits. Also, after pruning a branch it is possible to resume message transmission toward the remaining destination nodes because the data buffer contains a copy of all the data flits of the message.

The basic idea behind the pruning mechanism is that, once a tree has been completely pruned, the corresponding multicast message becomes a set of multiple unicast messages. Assuming that the base routing function for unicast routing is deadlock-free, multicast routing is also deadlock-free. However, not all the branches of a blocked tree need to be pruned. A deadlocked configuration requires a set of messages, each one waiting for a resource held by another message in the set. Therefore, only branches that cannot forward flits need to be pruned. Note that a branch may be unable to forward flits because another branch was blocked (see Figure 5.12). Moreover, it is useless to prune a blocked branch because flits will not be able to advance. As a result, pruning is only performed on branches that cannot forward flits but will be able to forward them as soon as they are pruned. By doing so, pruned branches will advance, freeing resources that may be needed by blocked branches of other multicast messages.

Tree-Based Multicast on Multistage Networks

The most natural way of implementing multicast/broadcast routing in multistage interconnection networks (MINs) is by using tree-based routing. Multicast can be implemented in a single pass through the network by simultaneously forwarding flits to several outputs at some switches. Broadcast can be implemented in a single pass by simultaneously forwarding flits to all the outputs at all the switches traversed by a message.

The replication of messages at some switches can be synchronous or asynchronous. In synchronous replication, the branches of a multidestination message can only forward if all the requested output channels are available. Hence, at a given time, all the message headers are at different switches of the same stage of the network. Synchronous replication requires a complex hardware signaling mechanism, usually slowing down flit propagation. In asynchronous replication, each branch can forward independently without coordinating with other branches. As a consequence, hardware design is much simpler. However, bubbles may arise when some requested output channels are not available. The reason is that branches finding a free output channel are able to advance while branches finding a busy output channel are blocked. A similar situation for direct networks was shown in Figure 5.12.

The propagation of multidestination messages may easily lead to deadlock, regardless of whether synchronous or asynchronous message replication is performed, as shown in the following example.

The tree-based multicast mechanism with pruning described in the previous subsection and the associated message format also work on MINs. Indeed, that mechanism was first developed for MINs, and then adapted to direct networks. The behavior of the pruning mechanism is more intuitive when applied to a MIN, as can be seen in Example 5.7. Note that pruning a single branch from each deadlocked configuration is enough to recover from deadlock. However, switches would have to synchronize. Additionally, recovery from deadlock is faster if all the switches detecting blocked branches perform a pruning operation.

Alternative approaches have been proposed in [55, 322]. In [55], a scheme with synchronous replication of multidestination messages that uses a deadlock avoidance scheme at each intermediate switch has been proposed. This scheme is the only one up to now that has been developed for MINs using pure wormhole switching. However, this scheme is complex and requires considerable hardware support. In [322], deadlock is simply avoided by using VCT switching. However, this approach requires the use of buffers deep enough to store whole messages, including destination addresses. Therefore, this approach requires more buffering capacity than the pruning mechanism described in the previous subsection.

In order to alleviate the overhead of encoding many destination addresses, a multiport encoding mechanism has been proposed in [322]. In a MIN with n stages and k × k switches, this encoding requires n k-bit strings, one for each stage. Each k-bit string indicates the output ports to which the message must be forwarded at the corresponding switch. A 1 in the ith position of the k-bit string denotes that the message should be forwarded to output port i. Figure 5.23(b) shows an example of a message format using multiport encoding. Figure 5.23(a) shows the path followed by this message when it is injected at node 6.

The main drawback of this encoding scheme is that the same jth k-bit string must be used at all the switches in stage j that route the message. For example, in Figure 5.23(a), all the switches in stage G₂ forward the message to the lower output of the switch. As a consequence, several passes through the network are usually required to deliver a message to a given destination set. However, the number of passes decreases beyond a certain number of destinations [322]. In particular, broadcast requires a single pass. So, this encoding scheme and the multicast mechanism proposed in [322] are more appropriate when the number of destinations is very high. For a small number of destinations, the message format and the pruning mechanism described in the previous subsection usually perform better, also requiring smaller buffers. Anyway, the main limitation of both techniques is that message length is limited by the buffer capacity.

Routing Function Based on Hamiltonian Paths

A suitable network partitioning strategy for path-based routing is based on Hamiltonian paths. A Hamiltonian path visits every node in a graph exactly once [146]; a 2-D mesh has many Hamiltonian paths. Thus, each node u in a network is assigned a label, l(u). In a network with N nodes, the assignment of the label to a node is based on the position of that node in a Hamiltonian path, where the first node in the path is labeled 0 and the last node in the path is labeled N − 1. Figure 5.24(a) shows a possible labeling in a 4 × 3 mesh, in which each node is represented by its integer coordinate (x, y). The labeling effectively divides the network into two subnetworks. The high-channel subnetwork contains all of the channels whose direction is from lower-labeled nodes to higher-labeled nodes, and the low-channel subnetwork contains all of the channels whose direction is from higher-labeled nodes to lower-labeled nodes.

Unicast as well as multicast communication will use the labeling for routing. That is, a unicast message will follow a path based on the labeling instead of using X Y routing. If the label of the destination node is greater than the label of the source node, the routing always takes place in the high-channel network; otherwise, it will take place in the low-channel network.

The label assignment function l for an m × n mesh can be expressed in terms of the x and y coordinates of nodes as

Let V be the node set of the 2-D mesh. The first step in finding a deadlock-free multicast algorithm for the 2-D mesh is to define a routing function R : V × V → V that uses the two subnetworks in such a way as to avoid channel cycles. One such routing function, defined for a source node u and destination node v, is defined as R(u, v) = w, such that w is a neighboring node of u and

Given a source and a destination node, it can be observed from Figure 5.24 that a message is always routed along a shortest path. This is important because the same routing function is used for unicast and multicast communication. It was proved in [211] that for two arbitrary nodes u and v in a 2-D mesh, the path selected by the routing function R is a shortest path from u to v. Furthermore, if l(u) < l(v), then the nodes along the path are visited in increasing order. If l(u) > l(v), then the nodes along the path are visited in decreasing order. However, if the Hamiltonian path is defined in a different way, unicast communication may not follow shortest paths.

Next, two path-based multicast routing algorithms that use the routing function R are defined [211]. In these two algorithms, the source node partitions the set of destinations according to the subnetworks and sends one copy of the message into each subnetwork that contains one or more destinations. The message visits destination nodes sequentially according to the routing function R.

Dual-Path Multicast Routing

The first heuristic routing algorithm partitions the destination node set D into two subsets, DH and D_L, where every node in D_H has a higher label than that of the source node u₀, and every node in D_L has a lower label than that of u₀. Multicast messages from u₀ will be sent to the destination nodes in D_H using the high-channel network and to the destination nodes in D_L using the low-channel network.

The message preparation algorithm executed at the source node of the dual-path routing algorithm is given in Figure 5.25. The destination node set is divided into the two subsets, D_H and D_L, which are then sorted in ascending order and descending order, respectively, with the label of each node used as its key for sorting. Although the sorting algorithm may require O(|D| log |D|) time, it often need be executed only once for a given set of destinations, the cost being amortized over multiple messages. In fact, for algorithms with regular communication patterns, it may be possible to do the sorting at compile time. The path routing algorithm, shown in Figure 5.26, uses a distributed routing method. Upon receiving the message, each node first determines whether its address matches that of the first destination node in the message header. If so, the address is removed from the message header and the message is delivered to the host node. At this point, if the address field of the message header is not empty, the message is also forwarded toward the first destination node in the message header using the routing function R. It was proved in [211] that the dual-path multicast routing algorithm is deadlock-free.

The performance of the dual-path routing algorithm is dependent on the distribution of destination nodes in the network. The total number of channels used to deliver the message in Example 5.8 is 33 (18 in the high-channel network and 15 in the low-channel network). The maximum distance from the source to a destination is 18 hops. In order to reduce the average length of multicast paths and the number of channels used for a multicast, an alternative is to use a multipath multicast routing algorithm, in which the restriction of having at most two paths is relaxed.

Multipath Multicast Routing

In a 2-D mesh, most nodes have outgoing degree 4, so up to four paths can be used to deliver a message, depending on the locations of the destinations relative to the source node. The only difference between multipath and dual-path routing concerns message preparation at the source node. Figure 5.28 gives the message preparation of the multipath routing algorithm, in which the destination sets D_H and D_L of the dual-path algorithm are further partitioned. The set D_H is divided into two sets, one containing the nodes whose x coordinates are greater than or equal to that of u₀ and the other containing the remaining nodes in D_H. The set D_L is partitioned in a similar manner.

The rules by which ties are broken in partitioning the destination nodes depends on the location of the source node in the network and the particular labeling method used. For example, Figure 5.29(a) shows the partitioning of the destinations in the high-channel network when the source is the node labeled 15. When the node labeled 8 is the source, the high-channel network is partitioned as shown in Figure 5.29(b).

Example 5.9 shows that multipath routing can offer advantages over dual-path routing in terms of generated traffic and the maximum distance between the source and destination nodes. Also, multipath routing usually requires fewer channels than dual-path routing. Because the destinations are divided into four sets rather than two, they are reached more efficiently from the source, which is approximately centrally located among the sets. Thus, when the network load is not high, multipath routing offers slight improvement over dual-path routing due to the fact that multipath routing introduces less traffic to the network.

However, a potential disadvantage of multipath routing is not revealed until both the load and number of destinations are relatively high. When multipath routing is used to reach a relatively large set of destinations, the source node will likely send on all of its outgoing channels. Until this multicast transmission is complete, any flit from another multicast or unicast message that routes through that source node will be blocked at that point. In essence, the source node becomes a hot spot. In fact, every node currently sending a multicast message is likely to be a hot spot. If the load is very high, these hot spots may throttle system throughput and increase message latency. Hot spots are less likely to occur in dual-path routing, accounting for its stable behavior under high loads with large destination sets. Although all the outgoing channels at a node can be simultaneously busy, this can only result from two or more messages routing through that node. A detailed performance study can be found in [206, 208].

Multicast Channel Dependencies

As indicated in Section 3.1.3, there is a dependency between two channels when a packet or message is holding one of them, and then it requests the other channel. In path-based multicast routing, the delivery of the same message to several destinations may produce additional channel dependencies, as we show in the next example.

Let us consider a 2-D mesh using XY routing. This routing algorithm prevents the use of horizontal channels after using a vertical channel. Figure 5.31 shows an example of multicast routing on a 2-D mesh. A message is sent by node 0, destined for nodes 9 and 14. The XY routing algorithm first routes the message through horizontal channels until it reaches node 1. Then, it routes the message through vertical channels until the first destination is reached (node 9). Now, the message must be forwarded toward its next destination (node 14). The path requested by the XY routing algorithm contains a horizontal channel. So, there is a dependency from a vertical channel to a horizontal one. This dependency does not exist in unicast routing. It is due to the inclusion of multiple destinations in the message header. More precisely, after reaching an intermediate destination the message header is routed toward the next destination. As a consequence, it is forced to take a path that it would not follow otherwise. For this reason, this dependency is referred to as multicast dependency [90, 96].

We studied four particular cases of channel dependency (direct, direct cross-, indirect, and indirect cross-dependencies) in Sections 3.1.4 and 3.1.5. For each of them we can define the corresponding multicast dependency, giving rise to direct multicast, direct cross-multicast, indirect multicast, and indirect cross-multicast dependencies. The only difference between these dependencies and the dependencies defined in Chapter 3 is that multicast dependencies are due to multicast messages reaching an intermediate destination. In other words, there is an intermediate destination in the path between the reserved channel and the requested channel.

The extended channel dependency graph defined in Section 3.1.3 can be extended by including multicast dependencies. The resulting graph is the extended multicast channel dependency graph [90, 96]. Similarly to Theorem 3.1, it is possible to define a condition for deadlock-free multicast routing based on that graph.

Before proposing the condition, it is necessary to define a few additional concepts. The message preparation algorithm executed at the source node splits the destination set for a message into one or more destination subsets, possibly reordering the nodes. This algorithm has been referred to as a split-and-sort function SS [90, 96]. The destination subsets supplied by this function are referred to as valid.

A split-and-sort function SS and a connected routing function R form a compatible pair (SS, R) if and only if, when a given message destined for the destination set D is being routed, the destination subset containing the destinations that have not been reached yet is a valid destination set for the node containing the message header. This definition imposes restrictions on both SS and R because compatibility can be achieved either by defining SS according to this definition and/or by restricting the paths supplied by the routing function. Also, if (SS, R) is a compatible pair and R₁ is a connected routing subfunction of R, then (SS, R₁) is also a compatible pair.

The following theorem proposes a sufficient condition for deadlock-free, path-based multicast routing [90, 96]. Whether it is also a necessary condition for deadlock-free multicast routing remains as an open problem.

Adaptive Multicast Routing

This section describes two adaptive multicast routing functions based on the extension of the routing function presented in Section 5.5.3. The label-based dual-path (LD) adaptive multicast routing algorithm for 2-D meshes [205] is similar to the dual-path routing algorithm presented in Section 5.5.3. In addition to minimal paths between successive destination nodes, the LD algorithm also allows nonminimal paths as long as nodes are crossed in strictly increasing or decreasing label order.

The message preparation algorithm executed at the source node is identical to the one given in Figure 5.25 for the dual-path routing algorithm. The destination node set is divided into two subsets, D_H and D_L, which are then sorted in ascending order and descending order, respectively, with the label of each node used as its key for sorting. The LD algorithm for message routing is shown in Figure 5.32.

Another adaptive routing function was proposed in [90, 96]. It allows messages to use the alternative minimal paths between successive destinations offered by the interconnection network. This routing function can be used for meshes and hypercubes, once a suitable node-labeling scheme is defined. It will serve as an example of the application of Theorem 5.1.

It is possible to define dual-path and multipath routing algorithms based on the routing function described below. This can be easily done by using one of the message preparation algorithms presented in Figures 5.25 and 5.28. For the sake of brevity, we will focus on the dual-path algorithm.

Hamiltonian path-based routing can be made adaptive by following a methodology similar to the one proposed in Section 4.4.4. This design methodology supplies a way to add channels following a regular pattern, also deriving the new routing function from the old one.

The routing function defined on page 238 defines a minimal-path connected deterministic routing function R₁. It does not require virtual channels. From a logical point of view, we can consider that there is a single virtual channel per physical channel. Let C₁ be the set of (virtual) channels supplied by R₁. Now, each physical channel is split into two virtual channels. This is equivalent to adding one virtual channel to each physical channel. The additional virtual channels will be used for adaptive routing. Let C be the set of all the virtual channels in the network. Let C_1H be the set of virtual channels belonging to C₁ that connect lower-labeled nodes to higher-labeled nodes, and let C_1L be the set of virtual channels belonging to C₁ that connect higher-labeled nodes to lower-labeled nodes. Let C_xyH be the set of output virtual channels from node x such that each channel belongs to a minimal path from x to y and the label of its destination node is not higher than the label of y. Let C_xyL be the set of output virtual channels from node x such that each channel belongs to a minimal path from x to y and the label of its destination node is not lower than the label of y. The adaptive routing function R is defined as follows:

In other words, the adaptive routing function can use any of the additional virtual channels belonging to a minimal path between successive destinations, except when a node with a label higher (for l(x) < l(y)) or lower (for l(x) > l(y)) than the label of the destination node is reached. Alternatively, the channels supplied by R₁ can also be used. This routing function can be easily extended for n-dimensional meshes as well as to support nonminimal paths. The extension for 3-D meshes is presented in [216]. The higher the number of dimensions, the higher the benefits from using adaptivity.

Channels belonging to C₁ are used exactly in the same way by R and R₁. Therefore, there is not any cross-dependency between channels belonging to C₁. Let us analyze the indirect dependencies that appear in the example shown in Figure 5.34 by considering some paths supplied by R. For instance, if the header of the message destined for node 41 is at node 19, then is routed to node 28 using a channel of C₁, then to node 27 using a channel of C – C₁, and then to node 36 using a channel of C₁, there is an indirect dependency between the channels of C₁. This dependency arises because R may route a message destined for a node with a higher label value through nodes with decreasing label values. If node 28 were a destination node, this example would correspond to an indirect multicast dependency.

Also, some indirect multicast dependencies exist between horizontal and vertical channels, due to messages that come back over their way after reaching an intermediate destination node. An example can be seen in Figure 5.34, when the message header is at node 52, and for instance, it is routed to node 53 using a channel of C₁, then to nodes 52 and 51 using channels of C – C₁, and finally, to node 60 using a channel of C₁.

The indirect and indirect multicast dependencies shown in the previous examples cannot be obtained by composing other dependencies. However, some indirect and indirect multicast dependencies can also be obtained by composing other direct and/or direct multicast dependencies. These dependencies do not add information to the channel dependency graphs.

Taking into account the definition of the split-and-sort function SS (message preparation algorithm) for the dual-path algorithm, a valid destination set for a source node ns only contains nodes with label values higher (alternatively, lower) than l(n_s). When the next destination node has a label value higher (lower) than the current node, the routing function cannot forward the message to a node with a label value higher (lower) than the next destination node. Thus, the pair (SS, R) is compatible. However, if all the minimal paths between successive destination nodes were allowed, the pair would not be compatible. For instance, if after reaching node 41 the message of the example given in Figure 5.34 were allowed to reach node 54, the current destination set D_H1 – {52, 53, 62} would not be a valid destination set for node 54.

There is not any dependency between channels belonging to C_1H and channels belonging to C_1L. However, if all the minimal paths between successive destinations were allowed, such dependencies would exist. The extended multicast channel dependency graph for (SS, R₁) consists of two subgraphs, each one containing the dependencies between channels belonging to C_1H and C_1L, respectively. Figure 5.35 shows part of the extended multicast channel dependency graph for (SS, R₁) and a 4 × 4 mesh. For the sake of clarity, the dependencies that do not add information to the graph have been removed. Also, only the subgraph for C_1H is displayed. The subgraph for C_1L is identical, except for channel labeling. Channels have been labeled as H_s or V_s, where H and V indicate that the channel is horizontal and vertical, respectively, and s is the label assigned to the source node of the channel. It must be noted that there are two horizontal output channels belonging to C₁ for most nodes, but only one of them belongs to C₁H. The same consideration applies to vertical channels.

Solid arrows represent direct or direct multicast dependencies. Dashed arrows represent indirect or indirect multicast dependencies. Dotted arrows represent indirect multicast dependencies. The graph has been represented in such a way that it is easy to see that there are no cycles. Obviously, the routing subfunction R₁ is connected. As the pair (SS, R₁) has no cycles in its extended multicast channel dependency graph, by Theorem 5.1 the pair (SS, R) is deadlock-free.

Base Routing Conformed Path

Deadlock avoidance is considerably simplified if unicast and multicast routing use the same routing algorithm. Moreover, using the same routing hardware for unicast and multicast routing allows the design of compact and fast routers. The Hamiltonian path-based routing algorithms proposed in previous sections improve performance over multiple unicast routing. However, their development has been in a different track compared to e-cube and adaptive routing. Moreover, it makes no sense sacrificing the performance of unicast messages to improve the performance of multicast messages, which usually represent a much smaller percentage of network traffic. Thus, as indicated in [269], it is unlikely that a system in the near future will be able to take advantage of Hamiltonian path-based routing.

The base routing conformed path (BRCP) model [269] defines multicast routing algorithms that are compatible with existing unicast routing algorithms. This model also uses path-based routing. The basic idea consists of allowing a multidestination message to be transmitted through any path in the network as long as it is a valid path conforming to the base routing scheme. For example, on a 2-D mesh with XY routing, a valid path can be any row, column, or row-column.

It is important to note that the BRCP model, as defined, cannot be directly applied on top of adaptive routing algorithms that allow cyclic dependencies between channels, like the ones described in Section 4.4.4. These algorithms divide the virtual channels of each physical channel into two classes: adaptive and escape. Adaptive channels allow fully adaptive routing, while escape channels allow messages to escape from potential deadlocks. Escape channels can be selected by a message at any node. However, if the BRCP model allows all the valid paths conforming to the base routing scheme, destination nodes may be arranged along a path that can only be followed by using adaptive channels. As a consequence, messages may be forced to select adaptive channels to reach the next destination node, therefore preventing some messages from selecting escape channels to escape from a potential deadlock.

However, this does not mean that the BRCP model cannot be combined with fully adaptive routing algorithms that allow cyclic dependencies between channels. Simply, destination nodes should be arranged in such a way that multidestination messages could be transmitted through any valid path consisting of escape channels. It is not necessary to restrict multidestination messages to use only escape channels. Those messages are allowed to use adaptive channels. However, by arranging destinations as indicated above, we guarantee that any message can select an escape channel at any node. For example, consider a 2-D mesh using wormhole switching and the routing algorithm described in Example 3.8. In this algorithm, one set of virtual channels is used for fully adaptive minimal routing. The second set of virtual channels implements XY routing and is used to escape from potential deadlocks. The BRCP model can be applied to the second set of virtual channels exactly in the same way that it is applied to a 2-D mesh with XY routing. By doing so, multicast messages can take advantage of the BRCP model, while unicast messages can benefit from fully adaptive routing.

The main goal of the BRCP model is providing support for multidestination messages without introducing additional channel dependencies with respect to the base routing algorithm used for unicast routing [269]. As indicated in Theorem 5.1, a compatible pair (SS, R) is deadlock-free if there exists a connected routing subfunction R₁ and the pair (SS, R₁) has no cycles in its extended multicast channel dependency graph. Instead of restricting the routing function R to satisfy this condition, the BRCP model restricts the split-and-sort function SS (message preparation algorithm) so that multicast dependencies do not produce any new channel dependency. Therefore, the extended multicast channel dependency graph and the extended channel dependency graph (defined in Section 3.1.3) are identical, and the condition proposed by Theorem 5.1 for deadlock-free routing is identical to the one for unicast routing (Theorem 3.1). As a consequence, if the base routing algorithm is deadlock-free, the multicast routing algorithm is also deadlock-free. The BRCP model can be formally defined as follows:

The routing subfunction R₁ supplies the escape channels mentioned above. If the routing function R has no cyclic dependencies between channels, then R₁ is made equal to R. In this case, a multidestination message can be transmitted through any path in the network as long as it is a valid path conforming to the base routing scheme defined by R.

Once the set of valid paths for multidestination messages has been determined, it is necessary to define routing algorithms for collective communication. The hierarchical leader-based (HL) scheme has been proposed in [269] to implement multicast and broadcast. Given a multicast destination set, this scheme tries to group the destinations in a hierarchical manner so that the minimum number of messages is needed to cover all the destinations. Since the multidestination messages conform to paths supported by the base routing, the grouping scheme takes into account this routing scheme and the spatial positions of destination nodes to achieve the best grouping. Once the grouping is achieved, multicast and broadcast take place by traversing nodes from the source in a reverse hierarchy.

Consider a multicast pattern from a source s with a destination set D. Let L₀ denote the set D ∪ {s}. The hierarchical scheme, in its first step, partitions the set L₀ into disjoint subsets with a leader node representing each subset. The leader node is chosen in such a way that it can forward a message to the members of its set using a single multidestination message under the BRCP model. For example, if a 2-D mesh implements XY routing, then the partitioning is done such that the nodes in each set lie on a row, column, or row-column.

Let the leaders obtained by the above first-step partitioning be termed as level-1 leaders and identified by a set L₁. This set L₁ can be further partitioned into disjoint subsets with a set of level-2 leaders. This process of hierarchical grouping is continued as long as it is profitable, as indicated below. Assuming that the grouping is carried out for m steps, there will be m sets of leaders, satisfying that L_m ⊆L_m–1 ⊆ … ⊆L₁⊆ L₀.

After the grouping is achieved, the multicast takes place in two phases. In the first phase, the source node performs unicast-based multicast (see Section 5.7) to the set L_m. The second phase involves m steps of multidestination message passing. It starts with the leaders in the set L_m and propagates down the hierarchical grouping in a reverse fashion to cover the lower-level leaders and, finally, all the nodes in destination set D.

As mentioned above, the hierarchical grouping is continued as long as it is profitable in order to reduce the multicast latency. As start-up latency dominates communication latency in networks using pipelined data transmission, the minimum multicast latency is usually achieved by minimizing the number of communication steps. As will be seen in Section 5.7, unicast-based multicast requires [log₂ (|L_m| + 1)] steps to reach all the leaders in the set L_m, assuming that the source node does not belong to that set. Therefore, the size of the set L_m should be reduced. However, while going from L_m–1 to L_m, one additional step of multidestination communication is introduced into the multicast latency. Hence, it can be seen that when [log₂(|L_m–₁| + 1)] > [log₂(|L_m| + 1)] + 1, it is profitable to go through an additional level of grouping. The previous expression assumes that the source node does not belong to L_m–1. If the source node belongs to L_m–1 or L_m, then the cardinal of the corresponding set must be reduced by one unit.

As the degree of multicasting increases, better grouping can be achieved while reducing L₁ to L₂. The best case is achieved for broadcast, as shown in Figure 5.38. In this case, all the level-1 leaders are reduced to a single level-2 leader. This indicates that broadcast from any arbitrary source can be done in three steps. A more efficient scheme to perform broadcast in two steps in a 2-D mesh using XY routing is shown in Figure 5.39(a) [268]. The number of steps to perform broadcasting can be further reduced by using the nonminimal west-first routing algorithm as the base routing, as shown in Figure 5.39(b) [268]. In this case, the message is first routed to the lower-left corner of the network without delivering it to any destination. From that point the message crosses all the nodes in the network, delivering copies of the message as it advances. Although this scheme reduces the number of steps to one, the path traversed by the message is very long, usually resulting in a higher broadcast latency than two-step broadcast.

As defined, the HL scheme may produce considerable contention when several nodes send multicast messages concurrently. A method to reduce node contention is to make each multicast choose unique intermediate nodes, as different as possible from the rest. However, with dynamic multicast patterns, all concurrent multicasts are unaware of one another. This means that a multicast has no information whatsoever about the source and destinations of the other multicasts.

A good multicast algorithm should only use some local information to make its tree as unique as possible. A possible solution consists of using the position of the source node in the system [173]. This is unique for each multicast message. If each multicast constructs its tree based on the position of its corresponding source, then all the multicasts will end up with trees as unique as possible.

In the HL algorithm the multicast tree is generated using primarily the destination (distribution) information. It depends, to a very small degree, on the position of the source. So, it can be improved by choosing the leader sets for a multicast depending on the position of its source. In the source quadrant-based hierarchical leader (SQHL) scheme [173], groupings are done exactly as in the HL scheme. However, the leader nodes are chosen in a different way. Consider a k-ary n-mesh. Let s_i, be the ith coordinate of the source node s of a multicast. Consider the set of destinations or leaders of the previous level that only differ in the ith coordinate. They will be reached by a single multidestination message. If s_i ≤ k/2, then the leader node will be the one in the set with the lowest coordinate in dimension i. Otherwise, the leader node will be the one with the highest coordinate in dimension i. For example, when grouping is performed along a given row in a 2-D mesh, the leader will be the leftmost destination in that row if the source node is located in the left half of the network. Otherwise, the leader will be the rightmost destination in that row. The remaining steps are the same as in the original HL scheme. The SQHL scheme allows multicast messages from source nodes in different quadrants of a mesh to proceed concurrently with minimal interference.

In the source-centered hierarchical leader (SCHL) scheme [173], each group g from the HL scheme is partitioned into at most two groups g₁ and g₂ based on the coordinates of the source node. Let s_i be the ith coordinate of the source node s of a multicast. Let us assume that destination nodes in g only differ in the coordinate corresponding to dimension i. All the nodes in that group with an ith coordinate lower than or equal to si, will be in g₁. The remaining nodes will be in g₂. Leader nodes are chosen so that they have an ith coordinate as close as possible to s_i. Both the SQHL and SCHL schemes improve performance over the HL scheme, as will be seen in Chapter 9.

Deadlocks in Delivery Channels

Path-based multicast routing functions avoid deadlock by transmitting messages in such a way that nodes are crossed either in increasing or decreasing label order. However, deadlock is still possible because messages transmitted on the high-channel and low-channel subnetworks (see Figure 5.24) use the same delivery channels at every destination node [216, 269].

Figure 5.40 shows a deadlocked configuration in which two multidestination messages M1 and M2 are destined for nodes A and B. M1 and M2 are traveling in the high-channel and low-channel subnetworks, respectively. Assuming that l(A) < l(B), M1 first reached node A, then node B. Also, M2 first reached node B, then node A. As there is a single delivery channel at each node, each message has reserved one delivery channel and is waiting for the other delivery channel to become free. Note that M1 cannot be completely delivered to node A because wormhole switching is used.

Deadlocks may arise because messages traveling in the high-channel and low-channel subnetworks share the same delivery channels, thus producing cyclic dependencies between them. Effectively, message M1 in Figure 5.40 has reserved the delivery channel c_DA at node A, then requested the delivery channel c_DB at node B. As a consequence, there is a dependency from c_DA to c_DB Similarly, there is a dependency from c_DB to c_DA This cyclic dependency can be easily broken by using different delivery channels for each subnetwork. In this case, two delivery channels at each node are enough to avoid deadlocks.

This situation may also arise when multidestination routing is based on the BRCP model. Consider an n-dimensional mesh with dimension-order routing for unicast messages. In this case, multidestination messages conforming to the base routing may be destined for sets of nodes along any dimension. As a consequence, the situation depicted in Figure 5.40 may occur in all the dimensions simultaneously. Figure 5.41 shows a deadlocked configuration for a 2-D mesh using XY routing where each node has three delivery channels. Note that each node has four input channels, which allow up to four messages requesting delivery channels at the same time.

As indicated in [268], the basic idea to avoid deadlock is to consider a given topology and routing function R, and determine the maximum number of multidestination messages that can enter a node simultaneously under the BRCP model. For example, if a base routing function R in an n-dimensional mesh requires v virtual channels per physical channel to support deadlock-free unicast routing, then 2nv delivery channels per node are sufficient for deadlock-free multidestination communication [268]. Note that each node has 2n input physical channels. Thus, each input virtual channel is associated with a dedicated delivery channel, therefore breaking all the dependencies between delivery channels.

It should be noted that virtual channels can also be used to reduce congestion. In this case, they are usually referred to as virtual lanes. Virtual lanes do not require additional delivery channels. Instead, each set of virtual lanes shares a single delivery channel [268]. When a multidestination message arrives on a virtual lane and reserves a delivery channel, and another multidestination message arrives on another virtual lane in the same set, it must wait. This waiting cannot produce deadlock because both messages follow the same direction. Also, it should be noted that adaptive routing algorithms that allow cyclic dependencies between channels only require the escape channels to avoid deadlock. Since the BRCP model restricts routing for multidestination messages according to the paths defined by escape channels, only the escape channels need to be considered when computing the number of delivery channels required for those algorithms.

The high number of delivery channels required to implement deadlock-free multidestination communication under the BRCP model may restrict the applicability of this model. Fortunately, current trends in network topologies recommend the use of low-dimensional meshes or tori (two or three dimensions at most). Also, as shown in Sections 4.2 and 4.4.4, it is possible to design deterministic and fully adaptive routing algorithms with a very small number of virtual channels. One and two virtual channels per physical channel are enough for deterministic routing in n-dimensional meshes and k-ary n-cubes, respectively. For fully adaptive routing, the requirements for escape channels are identical to those for deterministic routing. As indicated in [268], four delivery channels are enough to support deadlock-free multidestination communication under the BRCP model in 2-D meshes when the base routing is either XY routing, nonminimal west-first, or fully adaptive routing based on escape channels (described in Section 4.4.4). Moreover, there is very little blocking probability with all delivery channels being accessed simultaneously. Hence, delivery channels can be implemented as virtual channels by multiplexing the available bandwidth at the network interface.

Architectural Support

In order to implement multidestination gather/broadcasting messages, some architectural support is required at the router interface. Similar to the concept of barrier registers [260], a set of buffers can be provided at each router interface of the system. Figure 5.43(a) shows a possible router interface organization with m buffers. Each buffer has a few bits for synchronization id, a flag participate/not participate (P), a flag arrived/not arrived (A), and some space for holding an incoming gather message. These buffers can be accessed by the associated processor. Note that by supporting m buffers at every router interface, a system can implement m concurrent barriers for an application at a given time.

Figure 5.43(b) shows a suitable format for gather/broadcasting messages. Each message carries a msg type field (2–3 bits) indicating whether it is a gather, broadcast, or unicast message. The width of the synchronization id field depends on how many buffers can be incorporated into the router interface. The destination addresses are encoded as a bit string (see Section 5.5.1). For the linear array example being considered, 6 bits are sufficient to encode the addresses. Assuming processor 0 is identified as bit 0 of this address, the destination bit string of the gather message initiated by P4 will be 000111. Similarly, the broadcast message initiated by P0 will have a bit string of 010110.

Communication Sequence

Let us consider the communication sequence for the processors participating in a barrier using gather and broadcast messages. We assume static barriers [260] so that the processors participating in a barrier are known at compile time and the associated communication sequence can be generated before the program execution. A split-phase synchronization scheme [141, 261] with separate report and wake-up phases is assumed. Figure 5.44 shows the communication sequence to implement a barrier on a linear array. Before the execution of barrier x, 0 ≤ x <m, each intermediate processor specifies its desire for participating in the barrier by grabbing buffer x at its router interface, setting the associated participate flag to 1 and resetting the arrived flag to 0. These flags are reset by default, indicating that the associated processor does not participate. The arrived flag of buffer x at an intermediate router is set to 1 when the associated processor reaches its barrier point after computation.

The rightmost participating processor initiates a gather message with synchronization id = x. This gather message, while passing through the router of an intermediate destination, checks for the participate and arrived flags of the associated buffer x. If the processor is not participating, then the message keeps on moving ahead. If the processor is participating and it has already arrived at the barrier, then the message also proceeds. If the processor is participating and it has not arrived at the barrier, then the message gets blocked at the router interface. In this case, the message is stored in the message field of buffer x until the arrived flag is set to 1 by the processor. Then, the gather message is forwarded again into the network. Finally, this gather message is consumed by the leftmost participating processor. Note that gather messages require the use of VCT switching. When a gather message is stored in the corresponding buffer at the router interface, it is removed from the network. This is required to avoid deadlock and to reduce network contention because a gather message may be waiting for a long time until a given processor reaches the barrier.

After the gather phase is over, the leftmost processor initiates a broadcast message to the rightmost processor with intermediate processors as intermediate destinations. This message, as it passes through the routers of intermediate destinations, wakes up the associated processors, also resetting the participate and arrived flags of buffer x. The leftmost processor is done with the synchronization after sending the broadcast message. Similarly, the rightmost processor is done when it receives the broadcast message.

Complete Barrier Synchronization

Consider a k × k mesh as shown in Figure 5.45. Complete barrier synchronization can be achieved by considering the mesh as a set of linear arrays [265]. A basic scheme using four steps is shown in Figure 5.45(a). The first step uses a gather message in all rows to collect information toward the first column. The second step uses a gather message on the first column. At the end of these two steps, the upper-left corner processor has information that all other processors have arrived at the barrier. Now it can initiate a broadcast message along the first column. During the final step, the nodes in the first column initiate broadcast messages along their respective rows. This requires four communication steps to implement barrier synchronization on a k × k mesh. For any k-ary n-cube system, similar dimensionwise gather and broadcast can be done to implement barrier synchronization with 2n communication steps. Note that under this basic scheme, the multidestination gather and broadcast messages need to move along a single dimension of the system only. As each multidestination message is destined for the nodes in a row or column, destination addresses can be encoded as a bit string of k bits. Hence, using 16-bit or 32-bit flits, destination addresses can be encoded into a few (1–3) flits for current network sizes.

An enhancement to this basic scheme can be done as shown in Figure 5.45(b). The gather message initiated by the bottom row does not stop at the leftmost node of this row but continues along the first column to gather information from the leftmost leaders of all other rows. This will combine the first two gather steps into a single one. Hence, using such a multidimensional gather message, complete barrier synchronization can be implemented on a 2-D mesh in three steps. This enhancement can be easily extended to a higher number of dimensions. Note that such a multidimensional message conforms to the BRCP model discussed in Section 5.5.3. The headers of such multidimensional messages are longer in size because they need to carry more destinations in their headers. Although such a scheme is feasible, it requires additional logic at a router interface to wait for the arrival of multiple gather messages.

Arbitrary Set Barrier Synchronization

Consider a subset of nodes in a 2-D mesh trying to barrier-synchronize, as shown in Figure 5.46. If all processors belong to a single task, then this subset barrier can be implemented as a complete barrier by forcing all processors to participate in each barrier. However, such an assumption is very restrictive. In this section, we describe a general scheme that allows for multiple subset barriers to be executed concurrently in a system, and the operation for a given barrier involves only the processors participating in that barrier [265].

For a 2-D mesh, the scheme uses six phases as shown in Figure 5.46. The first phase consists of using gather messages within rows. For every row having at least two participating processors, a gather message is initiated by the rightmost participating processor and is consumed by the leftmost participating one. Let us designate the leftmost participating processors as row leaders. Now for every column having at least two row leaders, a gather message can be initiated by the bottom row leader to gather information along that column and finally be consumed by the top row leader. Let these top row leaders be designated as column leaders. After these two phases, information needs only to be gathered from the column leaders. It can be easily seen that these column leaders fall into disjoint rows and columns based on the grouping done. Hence no further reduction can be achieved with multidestination messages on systems supporting XY routing. If the base routing algorithm supports adaptivity, then further reduction can still be achieved by using adaptive paths.

The third phase consists of unicast-based message passing. This phase implements gather among column leaders in a tree-like manner using unicast-based message passing in every step. Once this reduction phase is over, the participating upper-left corner processor has information that all other processors have reached their respective barriers. This completes the report phase of barrier synchronization. Now the wake-up phase of barrier synchronization can be achieved by a series of broadcast phases. The fourth phase involves broadcast from the upper-left corner processor to column leaders in a tree-like manner using unicast-based multicast (see Section 5.7). The fifth phase involves broadcast by column leaders to row leaders using multidestination messages. During the final step, the row leaders use broadcast messages in their respective rows to wake up the associated processors.

In this six-phase scheme, every phase except the third and the fourth needs only one communication step. The number of communication steps needed in the third and the fourth phases depends on the number of column leaders involved. This issue was discussed in Section 5.5.3.

1. No local processors other than the source and destination processors should be involved in the implementation of the multicast tree.

2. The implementation should exploit the small distance sensitivity of wormhole switching.

3. The height of the multicast tree should be minimal. Specifically, for m − 1 destination nodes, the minimum height is k = [log₂(m)].

4. There should be no channel contention among the constituent messages of the multicast. In other words, the unicast messages involved should not simultaneously require the same channel. Note that this feature does not eliminate contention with other unicast or multicast messages.

Exercises

Problems