Bit reversal. The node with binary coordinates a_n−1, a_n−2, …,a₁, a₀ communicates with the node a₀, a₁, …, a_n−2, a_n−1.

 Perfect shuffle. The node with binary coordinates a_n−1, a_n−2, …, a₁, a₀ communicates with the node a_n−2, a_n−3, …, a₀, a_n−1 (rotate left 1 bit).

 Butterfly. The node with binary coordinates a_n−1, a_n−2, …, a₁, a₀ communicates with the node a₀, a_n−2, …, a₁, a_n−1 (swap the most and least significant bits).

 Matrix transpose. The node with binary coordinates a_n−1, a_n−2, …, a₁, a₀communicates with the node .

 Complement. The node with binary coordinates a_n−1, a_n−2, …, a₁, a₀ communicates with the node .

9.4.1 Performance under Uniform Traffic

In this section, we evaluate the performance of several routing algorithms by using a uniform distribution for message destinations.

9.4.2 Performance under Local Traffic

Figure 9.9 shows the average message latency versus normalized accepted traffic when messages are sent locally. In this case, message destinations are uniformly distributed inside a cube centered at the source node with each side equal to four channels.

The partially adaptive algorithm doubles throughput with respect to the deterministic one when messages are sent locally. The fully adaptive algorithm performs even better, reaching a throughput three times higher than the deterministic algorithm and 50% higher than the partially adaptive algorithm. Latency is also smaller for the full range of accepted traffic.

When locality increases even more, the benefits of using adaptive algorithms are smaller because the distance between source and destination nodes are short, and the number of alternative paths is much smaller. Figure 9.10 shows the average message latency versus normalized accepted traffic when messages are uniformly distributed inside a cube centered at the source node with each side equal to two channels. In this case, partially and fully adaptive algorithms perform almost the same. All the improvement with respect to the deterministic algorithm comes from a better utilization of virtual channels.

9.4.3 Performance under Nonuniform Traffic

As stated in [73], adaptive routing is especially interesting when traffic is not uniform. Figures 9.11 and 9.12 compare the performance of routing algorithms for the bit reversal and perfect shuffle communication patterns, respectively. In both cases, the deterministic and partially adaptive algorithms achieve poor performance because both of them offer a single physical path for every source/destination pair.

The fully adaptive algorithm increases throughput by a factor of 2.25 with respect to the deterministic algorithm when using the perfect shuffle communication pattern, and it increases throughput by a factor of 8 in the bit reversal communication pattern. Standard deviation of message latency is also much smaller for the fully adaptive algorithm. Finally, note that there is no significant performance degradation when the fully adaptive algorithm reaches the saturation point, especially for the perfect shuffle communication pattern.

9.7.1 Effect of the Number of Virtual Channels

Splitting each physical channel into several virtual channels increases the number of routing choices, allowing messages to pass blocked messages. On the other hand, flits from several messages are multiplexed onto the same physical channel, slowing down both messages. The effect of increasing the number of virtual channels has been analyzed in [72] for deterministic routing algorithms on a 2-D mesh topology.

In this section, we analyze the effect of increasing the number of virtual channels on all the algorithms under study, using a uniform distribution of message destinations. As in [72], we assume that the total buffer capacity associated with each physical channel is kept constant and is equal to 16 flits (15 flits and 18 flits for three and six virtual channels, respectively).

Figure 9.16 shows the behavior of the deterministic algorithm with two, four, six, and eight virtual channels per physical channel. Note that the number of virtual channels for this algorithm must be even. The higher the number of virtual channels, the higher the throughput. However, the highest increment is produced when changing from two to four virtual channels. Also, latency slightly increases when adding virtual channels. These results are very similar to the ones obtained in [72]. The explanation is simple: Adding the first few virtual channels allows messages to pass blocked messages, increasing channel utilization and throughput. Adding more virtual channels does not increase routing flexibility considerably. Moreover, buffer size is smaller, and blocked messages occupy more channels. As a result, throughput increases by a small amount. Adding virtual channels also has a negative effect [88]. Bandwidth is shared among several messages. However, bandwidth sharing is not uniform. A message may be crossing several physical channels with different degrees of multiplexing. The more multiplexed channel becomes a bottleneck, slightly increasing latency.

Figure 9.17 shows the behavior of the partially adaptive algorithm with two, four, six, and eight virtual channels. In this case, adding two virtual channels increases throughput by a small amount. However, adding more virtual channels increases latency and even reduces throughput. Moreover, the partially adaptive algorithm with two and four virtual channels achieves almost the same throughput as the deterministic algorithm with four and eight virtual channels, respectively. Note that the partially adaptive algorithm is identical to the deterministic one, except that it allows most messages to share all the virtual channels. Therefore, it effectively allows the same degree of channel multiplexing using half the number of virtual channels as the deterministic algorithm. When more than four virtual channels are used, the negative effects of channel multiplexing mentioned above outweigh the benefits.

Figure 9.18 shows the behavior of the fully adaptive algorithm with three, four, six, and eight virtual channels. Note that two virtual channels are used for deadlock avoidance and the remaining channels are used for fully adaptive routing. In this case, latency is very similar regardless of the number of virtual channels. Note that the selection function selects the output channel for a message in such a way that channel multiplexing is minimized. As a consequence, channel multiplexing is more uniform and channel utilization is higher, obtaining a higher throughput than the other routing algorithms. As indicated in Section 9.4.1, throughput decreases when the fully adaptive algorithm reaches the saturation point. This degradation can be clearly observed in Figure 9.18. Also, as indicated in [91], it can be seen that increasing the number of virtual channels increases throughput and even removes performance degradation.

9.7.2 Effect of the Number of Ports

Network hardware has become very fast. In some cases, network performance may be limited by the bandwidth available at the source and destination nodes to inject and deliver messages, respectively. In this section, we analyze the effect of that bandwidth. As fully adaptive algorithms achieve a higher throughput, this issue is more critical when adaptive routing is used. Therefore, we will restrict our study to fully adaptive algorithms. Injection and delivery channels are usually referred to as ports. In this study, we assume that each port has a bandwidth equal to the channel bandwidth.

Figure 9.19 shows the effect of the number of ports for a uniform distribution of message destinations. For the sake of clarity, we removed the part of the plots corresponding to the performance degradation of the adaptive algorithm close to saturation. As can be seen, the network interface is a clear bottleneck when using a single port. Adding a second port decreases latency and increases throughput considerably. Adding a third port increases throughput by a small amount, and adding more ports does not modify the performance. It should be noted that latency does not consider source queuing time. When a single port is used, latency is higher because messages block when the header reaches the destination node, waiting for a free port. Those blocked messages remain in the network, therefore reducing channel utilization and throughput.

As can be expected, more bandwidth is required at the network interface when messages are sent locally. Figure 9.20 shows the effect of the number of ports for local traffic with side = 2 (see Section 9.4.2). In this case, the number of ports has a considerable influence on performance. It has a stronger impact on throughput than the routing algorithm or even the topology used. The higher the number of ports, the higher the throughput. However, as the number of ports increases, adding more ports has a smaller impact on performance. Therefore, in order to avoid mixing the effect of different design parameters, we run all the simulations in the remaining sections of this chapter by using four ports.

Taking into account that the only way to make parallel machines really scalable is by exploiting locality, the effect of the number of ports is extremely important. However, most current multicomputers have a single port. In most cases, the limited bandwidth at the network interface does not limit the performance. The reason is that there is an even more important bottleneck in the network interface: the software messaging layer (see Section 9.12). The latency of the messaging layer reduces network utilization, hiding the effect of the number of ports. However, the number of ports may become the bottleneck in distributed, shared-memory multiprocessors.

9.7.3 Effect of Buffer Size

In this section, we analyze the effect of buffer size on performance. Buffers are required to allow continuous flit injection at the source node in the absence of contention, therefore hiding routing time and allowing windowing protocols between adjacent routers. Also, if messages are short enough, using deeper buffers allows messages to occupy a smaller number of channels when contention arises and buffers are filled. As a consequence, contention is reduced and throughput should increase. Finally, buffers are required to hold flits while a physical channel is transmitting flits from other buffers (virtual channels).

If buffers are kept small, buffer size does not affect clock frequency. However, using very deep buffers may slow down clock frequency, so there is a trade-off. Figure 9.21 shows the effect of input and output buffer size on performance using the fully adaptive routing algorithm with three virtual channels. In this case, no windowing protocol has been implemented. Minimum buffer size is two flits because flit transmission across physical channels is asynchronous. Using smaller buffers would produce bubbles in the message pipeline.

As expected, the average message latency decreases when buffer size increases. However, the effect of buffer size on performance is small. The only significant improvement occurs when the total flit capacity changes from 4 to 5 flits. Adding more flits to buffer capacity yields diminishing returns as buffer size increases. Increasing input buffer size produces almost the same effect as increasing output buffer size, as far as total buffer size remains the same. The reason is that there is a balance between the benefits of increasing the size of each buffer. On the one hand, increasing the input buffer size allows more data flits to make progress if the routing header is blocked for some cycles until an output channel is available. On the other hand, increasing the output buffer size allows more data flits to cross the switch while the physical channel is assigned to other virtual channels.

Moreover, when a message blocks, buffers are filled. In this case, it does not matter how total buffer capacity is split among input and output buffers. The only important issue is whether buffers are deep enough to allow the blocked message to leave the source node so that some channels are freed.

Note that the plots in Figure 9.21 correspond to short messages (16 flits). We also ran simulations for longer messages. In this case, buffer size has a more noticeable impact on performance. However, increasing buffer capacity does not increase performance significantly if messages are longer than the diameter of the network times the total buffer capacity of a virtual channel. The reason is that a blocked message keeps all the channels it previously reserved regardless of buffer size.

9.10.1 A Speed Model

Most network simulators written up to now for wormhole switching work at the flit level. Writing a simulator that works at the gate level or at the transistor level is a complex task. Moreover, execution time would be extremely high, considerably reducing the design space that can be studied. A reasonable approximation to study the effect of design parameters on the performance of the interconnection network consists of modeling the delay of each component of the router. Then, for a given set of design parameters, the delay of each component is computed, determining the critical path and the number of clock cycles required for each operation, and computing the clock frequency for the router. Then, the simulation is run using a flit-level simulator. Finally, simulation results are corrected by using the previously computed clock frequency.

Consider the router model described in Section 2.1. We assume that all the operations inside each router are synchronized by its local clock signal. To compute the clock frequency of each router, we will use the delay model proposed in [57]. It assumes 0.8 μm CMOS gate array technology for the implementation.

The deterministic and the partially adaptive routing algorithms require the same clock period of 6.74 ns. Although routing delay is greater in the latter case, channel delay dominates in both cases and is therefore the bottleneck. For the adaptive algorithm, clock period increases up to 7.49 ns, slowing down clock frequency by 10% with respect to the other algorithms. It should be noted that clock frequency would be the same if a single injection/delivery port were used.

The following sections show the effect of router delays on performance. Note that plots in those sections are identical to the ones shown in Sections 9.4.1, 9.4.2, and 9.4.3, except that plots for each routing algorithm have been scaled by using the corresponding clock period. As the deterministic and the partially adaptive algorithms have the same clock frequency, comments will focus on the relative performance of the fully adaptive routing algorithm. Finally, note that as VLSI technology improves, channel propagation delay is becoming the only bottleneck. As a consequence the impact of router complexity on performance will decrease over time, therefore favoring the use of fully adaptive routers.

9.10.2 Performance under Uniform Traffic

Figure 9.34 shows the average message latency versus accepted traffic when using a uniform distribution for message destinations. Latency and traffic are measured in ns and flits/node/μs, respectively. Note that, in this case, accepted traffic has not been normalized because the normalizing factor is different for each routing algorithm.

As expected, the lower clock frequency of the fully adaptive router produces a comparatively higher latency and lower throughput for the fully adaptive algorithm. Nevertheless, this algorithm still increases throughput by 103% and 28% with respect to the deterministic and the partially adaptive algorithms. However, for low loads, these algorithms achieve a latency up to 10% lower than the fully adaptive one. When the network is heavily loaded, the fully adaptive algorithm offers more routing options, achieving the lowest latency. Moreover, this algorithm also obtains a lower standard deviation of the latency (not shown) for the whole range of traffic.

9.10.3 Performance under Local Traffic

Figures 9.35 and 9.36 show the average message latency versus accepted traffic when message destinations are uniformly distributed inside a cube centered at the source node with each side equal to four and two channels, respectively.

The relative behavior of the routing algorithms heavily depends on the average distance traveled by messages. When side = 4, the fully adaptive routing algorithm increases throughput by a factor of 2.5 with respect to the deterministic algorithm. However, the fully adaptive algorithm only achieves the lowest latency when the partially adaptive algorithm is close to saturation. Here, the negative effect of the lower clock frequency on performance can be clearly observed.

When traffic is very local, the partially adaptive algorithm achieves the highest throughput, also offering the lowest latency for the whole range of traffic. Nevertheless, it only improves throughput by 32% with respect to the deterministic algorithm. The fully adaptive algorithm exhibits the highest latency until accepted traffic reaches 60% of the maximum throughput. In this case, the negative effect of the lower clock frequency on performance is even more noticeable. As a consequence, adaptive routing is not useful when most messages are sent locally.

9.10.4 Performance under Nonuniform Traffic

Figures 9.37 and 9.38 show the average message latency versus accepted traffic for the bit reversal and the perfect shuffle traffic patterns, respectively.

Despite the lower clock frequency, the fully adaptive algorithm increases throughput by a factor of 6.9 over the deterministic algorithm when the bit reversal communication pattern is used. For the perfect shuffle communication pattern, the fully adaptive algorithm doubles throughput with respect to the deterministic one. However, it only increases throughput by 35% over the partially adaptive algorithm. Also, this algorithm achieves a slightly lower latency than the fully adaptive one until it is close to the saturation point.

9.10.5 Effect of the Number of Virtual Channels

Section 9.7.1 showed that splitting physical channels into several virtual channels usually increases throughput but may increase latency when too many virtual channels are added. Also, it showed that virtual channels are more interesting for deterministic algorithms than for adaptive algorithms. In summary, the use of virtual channels has some advantages and some disadvantages. There is a trade-off.

In this section a more realistic analysis of the effect of adding virtual channels is presented. This study considers the additional propagation delay introduced by the circuits required to implement virtual channels. Note that increasing the number of virtual channels increases channel propagation delay. Moreover, it also increases the number of routing options and switch size, increasing routing delay and switch delay accordingly.

Assuming that all the operations are performed in a single clock cycle, Table 9.1 shows the clock period of the router as a function of the number of virtual channels per physical channel for the three routing algorithms under study. It has been computed according to the model presented in Section 9.10.1. For each value of the clock period, the slowest operation (t_r, t_s, or t_w) is indicated.

Figures 9.39, 9.40, and 9.41 show the effect of adding virtual channels to the deterministic, partially adaptive, and fully adaptive routing algorithms, respectively. Plots show the average message latency versus accepted traffic for a uniform distribution of message destinations.

For the deterministic algorithm there is a trade-off between latency and throughput. Adding virtual channels increases throughput, but it also increases latency. Therefore, depending on the requirements of the applications, the designer has to choose between achieving a lower latency or supporting a higher throughput. Anyway, changing from two to four virtual channels increases throughput by 52% at the expense of a small increment in the average latency. The standard deviation of latency is also reduced. The reason is that the additional channels allow messages to pass blocked messages. On the other hand, using eight or more virtual channels is not interesting at all because latency increases with no benefit.

However, adding virtual channels is not interesting at all for the partially adaptive and the fully adaptive routing algorithms. For the partially adaptive one, adding two virtual channels only increases throughput by 13%. Adding more virtual channels even decreases throughput. Moreover, the algorithm with the minimum number of virtual channels achieves the lowest latency except when the network is close to saturation. For the fully adaptive algorithm, adding virtual channels does not increase throughput at all.

Moreover, it increases latency significantly. Therefore, the minimum number of virtual channels should be used for both adaptive algorithms.

A similar study can be done for meshes. Although results are not shown, the conclusions are the same. For the deterministic routing algorithm, it is worth adding one virtual channel (for a total of two). Using three virtual channels increases throughput by a small amount, but it also increases latency. For the fully adaptive routing algorithm, using the minimum number of virtual channels (two channels) achieves the lowest latency. It is not worth adding more virtual channels.

9.11.1 Comparison with Separate Addressing

Figure 9.42 compares the measured performance of separate addressing and a multicast tree algorithm (specifically, the spanning binomial tree presented in Section 5.5.2) for subcubes of different sizes on a 64-node nCUBE-2. The message length is fixed at 100 bytes. The tree approach offers substantial performance improvement over separate addressing.

The U-mesh algorithm described in Section 5.7.4 was evaluated in [234]. The evaluation was performed on a 168-node Symult 2010 multicomputer, based on a 12 × 14 2-D mesh topology. A set of tests was conducted to compare the U-mesh algorithm with separate addressing and the Symult 2010 system-provided multidestination service Xmsend. In separate addressing, the source node sends an individual copy of the message to every destination. The Xmsend function was implemented to exploit whatever efficient hardware mechanisms may exist in a given system to accomplish multiple-destination sends. If there is no such mechanism, it is implemented as a library function that performs the necessary copying and multiple unicast calls.

Figure 9.43 plots the multicast latency values for implementations of the three methods. A large sample of destination sets was randomly chosen in these experiments. The message length was 200 bytes. The multicast latency with separate addressing increases linearly with the number of destinations. With the U-mesh algorithm, the latency increases logarithmically with the number of destinations. These experimental results demonstrate the superiority of the U-mesh multicast algorithm. Taking into account these results and that the U-mesh algorithm requires no hardware support, we can conclude that multicomputers should at least include a software implementation of multicast, regardless of how frequently this operation is performed.

9.11.2 Comparing Tree-Based and Path-Based Algorithms

This section compares the performance of the double-channel XY multicast routing algorithm presented in Section 5.5.2, and the dual-path and multipath multicast algorithms presented in Section 5.5.3. These results were presented in [208]. The performance of a multicast routing algorithm depends not only on the delay and traffic resulting from a single multicast message, but also on the interaction of the multicast message with other network traffic. In order to study these effects on the performance of multicast routing algorithms, some simulations were run on an 8 × 8 mesh network. The simulation program modeled multicast communication in 2-D mesh networks. The destinations for each multicast message were uniformly distributed. All simulations were executed until the confidence interval was smaller than 5% of the mean, using 95% confidence intervals, which are not shown in the figures.

In order to compare the tree-based and path-based algorithms fairly, each algorithm was simulated on a network that contained double channels. Figure 9.44 gives the plot of average network latency for various network loads. The average number of destinations for a multicast is 10, and the message size is 128 bytes. The speed of each channel is 20 Mbytes/s. All three algorithms exhibit good performance at low loads. The path-based algorithms, however, are less sensitive to increased load than the tree-based algorithm. This result occurs because in tree-based routing, when one branch is blocked, the entire tree is blocked, increasing contention considerably. This type of dependency does not exist in path-based routing. Multipath routing exhibits lower latency than dual-path routing because, as shown above, paths tend to be shorter, generating less traffic. Hence, the network will not saturate as quickly. Although not shown in the figure, the variance of message latency using multipath routing was smaller than that of dual-path routing, indicating that the former is also generally more fair.

The disadvantage of tree-based routing increases with the number of destinations. Figure 9.45 compares the three algorithms, again using double channels. The average number of destinations is varied from 1 to 45. In this set of tests, every node generates multicast messages with an average time between messages of 300 μs. The other parameters are the same as for the previous figure.

With larger sets of destinations, the dependencies among branches of the tree become more critical to performance and cause the delay to increase rapidly. The conclusion from Figures 9.44 and 9.45 is that tree-based routing is not particularly well suited for 2-D mesh networks when messages are relatively long. The path algorithms still perform well, however. Note that the dual-path algorithm results in lower latency than the multipath algorithm for large destination sets. The reason is somewhat subtle. 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.

Simulations were also run for multipath and dual-path routing with single channels and an average of 10 destinations. As the load increased, multipath routing offered slight improvement over dual-path routing. However, both routing algorithms saturated at a much lower load than with double channels (approximately for an average arrival time between messages of 350 μs), resulting in much lower performance than the tree-based algorithm with double channels. This result agrees with the performance evaluation presented in Section 9.4.1, which showed the advantage of using two virtual channels on 2-D meshes.

Finally, tree-based multicast with pruning (see Section 5.5.2) performs better than path-based multicast routing algorithms when messages are very short and the number of destinations is less than half the number of nodes in the network [224]. This makes tree-based multicast with pruning especially suitable for the implementation of cache-coherent protocols in distributed, shared-memory multiprocessors.

In summary, path-based multicast routing algorithms perform better than tree-based algorithms for long messages, especially for large destination sets. However, tree-based multicast performs better than path-based multicast when messages are very short. Finally, other design parameters like the number of virtual channels may have a stronger influence on performance than the choice of the multicast algorithm.

9.11.3 Performance of Base Routing Conformed Path Multicast

This section presents performance evaluation results for hardware-supported multicast operations based on the base routing conformed path (BRCP) model described in Section 5.5.3. For comparison purposes, the U-mesh and the Hamiltonian path-based routing algorithms are also evaluated. These results were presented in [268].

To verify the effectiveness of the BRCP model, single-source broadcasting and multicasting was simulated at the flit level. Two values for communication start-up time (t_s) were used: 1 and 10 μs. Link propagation time (t_p) was assumed to be 5 ns for a 200 Mbytes/s link. For unicast message passing, router delay (t_node) was assumed as 20 ns. For multidestination message passing a higher value of router delay, 40 ns, was considered. For a fair comparison, 2n consumption channels were assumed for both multidestination and unicast message passing, where n is the number of dimensions of the network. Each experiment was carried out 40 times to obtain average results.

Figures 9.46 and 9.47 compare the latency of single-source multicast on 2-D meshes for two network sizes and two t_s values. Four different schemes were considered: a hierarchical leader-based (HL) scheme using (R, C) and (R, C, RC) paths, U-mesh, and a Hamiltonian path-based scheme. The simulation results show that the BRCP model is capable of reducing multicast latency as the number of destinations participating in the multicast increases beyond a certain number. This cutoff number was observed to be 16 and 32 nodes for the two network sizes considered.

For a large number of destinations the HL schemes are able to reduce multicast latency by a factor of 2 to 3.5 compared to the U-mesh scheme. The Hamiltonian path-based scheme performs best for smaller system size, higher ts, and a smaller number of destinations per multicast. However, the HL schemes perform better than the Hamiltonian path-based scheme as the system size increases, t_s reduces, and the number of destinations per multicast increases.

For systems with higher t_s (10 μs), the HL scheme with RC paths was observed to implement multicast faster than using R and C paths. However, for systems with t_s = 1 μs, the scheme using R and C paths performed better. This is because a multidestination worm along an RC path encounters longer propagation delay (up to 2k hops in a k × k network) compared to that along an R/C path (up to k hops). The propagation delay dominates for systems with lower ts. Thus, the HL scheme with R and C paths is better for systems with a lower t_s value, whereas the RC path-based scheme is better for other systems.

9.11.4 Performance of Optimized Multicast Routing

This section evaluates the performance of several optimizations described in Chapter 5. In particular, the source-partitioned U-mesh (SPUmesh) algorithm, introduced in Section 5.7.4, and the source quadrant-based hierarchical leader (SQHL) and source-centered hierarchical leader (SCHL) schemes, described in Section 5.5.3, are compared to the U-mesh and hierarchical leader-based (HL) algorithms described in the same sections. The performance results presented in this section were reported in [173].

A flit-level simulator was used to model a 2-D mesh and evaluate the algorithms for multiple multicast. The parameters used were t_s (communication start-up time) = 5 μs, t_p (link propagation time) = 5 ns, t_node (router delay at node) = 20 ns, t_sw (switching time across the router crossbar) = 5 ns, t_inj (time to inject message into network) = 5 ns, and t_cons (time to consume message from network) = 5 ns. The message length was assumed to be a constant 50 flits, and a 16 × 16 mesh was chosen. Each experiment was carried out 30 times to obtain average results. For each simulation, destination sets were randomly generated for each multicast message. In Figure 9.48(a), multicast latency is plotted against the number of sources (s), while keeping the number of destinations (d) fixed. In Figure 9.48(b), multicast latency is plotted against d, while keeping s fixed. The former shows the effect of the number of multicasts on latency, while the latter shows the effect of the size of the multicasts on latency.

Figure 9.48(a) shows that the SPUmesh algorithm outperforms the U-mesh algorithm for large d by a factor of about 1.6. For small to moderate values of d, performance is similar. This is clear in Figure 9.48(b) where the U-mesh latency shoots up for larger d, whereas the SPUmesh latency remains more or less constant. The U-mesh algorithm behaves in this way because increasing d increases the number of start-ups the common center node will have to sequentialize. However, the SPUmesh algorithm performs equally well for both large and small d. This is because increasing d does not increase the node contention, as the multicast trees are perfectly staggered for identical destination sets.

It can be observed in Figure 9.49(a) that the SCHL scheme does about two to three times better than the SQHL scheme and about five to seven times better than the HL scheme. The HL scheme undergoes a large degree of node contention even for randomly chosen destinations. A property of the HL scheme observed in Section 9.11.3 is that latency reduces with increase in d. This basic property of the HL scheme is best exploited by the SCHL scheme. This can be noticed in Figure 9.49(b), where on increasing d the latency of SCHL drops. However, the SQHL scheme outperforms the SCHL scheme for small d, since the number of start-ups at the U-mesh stage of the multicast will be more for the SCHL scheme. There is a crossover point after which the SCHL scheme performs better. This can be seen Figure 9.49(b). The above results lead to the conclusion that node contention is one of the principal reasons for poor performance of existing multicast algorithms. Reducing node contention should be the primary focus while designing multicast algorithms.

9.11.5 Performance of Unicast- and Multidestination-Based Schemes

This section compares multicast algorithms using unicast messages with those using multidestination messages. This measures the potential additional benefits that a system provides if it supports multidestination wormhole routing in hardware. The multicast algorithms selected for comparison are the ones that achieved the best performance in Section 9.11.4 (the SPUmesh and the SCHL schemes), using the same parameters as in that section. The performance results presented in this section were reported in [173].

As expected, the SCHL scheme outperforms the SPUmesh algorithm for both large and small d. This can be seen in Figure 9.50. Since the destination sets are completely random, there is no node contention to degrade the performance of the SCHL scheme. There is a crossover point at around d = 100, after which the SCHL scheme keeps improving as d increases. The reason is that hierarchical grouping of destinations gives relatively large leader sets for small d. This is because the destinations are randomly scattered in the mesh. On the other hand, SPUmesh generates perfectly staggered trees for identical destination sets. But, as d increases, leader sets become smaller and the advantage of efficient grouping in the SCHL scheme overcomes the node contention. This results in a factor of about 4−6 improvement over the SPUmesh algorithm when the number of sources and destinations is very high.

These results lead to the conclusion that systems implementing multidestination message passing in hardware can support more efficient multicast than systems providing unicast message passing only. However, when the number of destinations for multicast messages is relatively small, the performance benefits of supporting multidestination message passing are small. So the additional cost and complexity of supporting multidestination message passing is only worth it if multicast messages represent an important fraction of network traffic and the average number of destinations for multicast messages is high.

9.11.6 Performance of Path-Based Barrier Synchronization

This section compares the performance of unicast-based barrier synchronization [355] and the barrier synchronization mechanism described in Section 5.6.2. These performance results were reported in [265].

A flit-level simulator was used to evaluate the algorithms for barrier synchronization. The following parameters were assumed: t_s (communication start-up time) as 1 and 10 μs, t_p (link propagation time) as 5 ns, and channel width as 32 bits. For multidestination gather and broadcast worms, bit string encoding was used. The node delay (t_node) was assumed to be 20 ns for unicast-based message passing. Although the node delay for multidestination worm (using bit manipulation logic) may be similar to that of unicast messages, three different values of node delay were simulated. In the simulation graphs, these values are indicated by 20 ns (1 × node delay), 30 ns (1.5 × node delay), and 40 ns (2 × node delay). The processors were assumed to be arriving at a barrier simultaneously. For arbitrary set barrier synchronization, the participating processors were chosen randomly. Each experiment was repeated 40 times, and the average synchronization latency was determined.

9.12.1 Overhead of the Software Messaging Layer

The overhead of the software messaging layer and its contribution to the overall communication latency has been evaluated by several researchers on different parallel computers [85, 170, 171, 214, 354]. Here we present some recent performance evaluation results obtained by running benchmarks on an IBM SP2. These results have been reported in [238]. In the next section, we will show the drastic reduction in latency that can be achieved by establishing virtual circuits between nodes before data are available and by reusing those circuits for all the messages exchanged between those nodes.

The SP2 communication subsystem is composed of the high-performance switch plus the adapters that connect the nodes to the switch [5, 329, 330]. The adapter contains an onboard microprocessor to off-load some of the work of passing messages from node to node and some memory to provide buffer space. DMA engines are used to move information from the node to the memory of the adapter and from there to the switch link.

Three different configurations of the communication subsystem of the IBM SP2 were evaluated. In the first configuration, the adapters were based on an Intel i860, providing a peak bandwidth of 80 Mbytes/s. The links connecting to the high-performance switch provided 40 Mbytes/s peak bandwidth in each direction, with a node-to-node latency of 0.5 μs for systems with up to 80 nodes. The operating system was AIX version 3, which included MPL, a proprietary message-passing library [324]. An implementation of the MPI interface [44] was available as a software layer over MPL. In the second configuration, the communication hardware was identical to the first configuration. However, the operating system was replaced by AIX version 4, which includes an optimized implementation of MPI. In the third configuration, the network hardware was updated, keeping AIX version 4. The new adapters are based on a PowerPC 601, achieving a peak transfer bandwidth of 160 Mbytes/s. The new switch offers 300 Mbytes/s peak bidirectional bandwidth, with latencies lower than 1.2 μs for systems with up to 80 nodes.

The performance of point-to-point communication was measured using the code provided in [85] for systems using MPI. The performance of the IBM SP2 is shown in Table 9.2 for the three configurations described above and different message lengths (L). The words “old” and “new” refer to the communications hardware, and “v3” and “v4” indicate the version of the operating system. As can be seen, software overhead dominates communication latency for very short messages. Minimum latency ranges from 40 to 60 μs while hardware latency is on the order of 1 μs. As a consequence, software optimization has a stronger effect on reducing latency for short messages than improving network hardware. This is the case for messages shorter than 4 Kbytes. However, for messages longer than 4 Kbytes the new version of the operating system performs worse. The reason is that for messages shorter than 4 Kbytes an eager protocol is used, sending messages immediately, while for longer messages a rendezvous protocol is used, sending a message only when the receiver node agrees to receive it. Switching to the rendezvous protocol incurs higher start-up costs but reduces the number of times information is copied when using the new hardware, thus reducing the cost per byte for the third configuration. Finally, the higher peak bandwidth of the new hardware can be clearly appreciated for messages longer than 10 Kbytes.

An interesting observation is that the message length required to achieve half the maximum throughput is approximately 3 Kbytes for the old hardware configuration and around 32 Kbytes for the new network hardware. Thus, improving network bandwidth without reducing software overhead makes it even more difficult to take advantage of the higher network performance. Therefore, the true benefits of improving network hardware will depend on the average message size.

Several parallel kernels have been executed on an IBM SP2 with 16 Thin2 nodes. These kernels include four benchmarks (MG, LU, SP, and BT) from the NAS Parallel Benchmarks (NPB) version 2 [14] and a shallow water modeling code (SWM) from the ParkBench suite of benchmarks [350]. Only the first and third configurations described above for the communication subsystem were evaluated (referred to as “old” and “new”, respectively).

Figure 9.53 shows the execution time in seconds and the average computation power achieved for the different benchmarks. It can be clearly seen that the performance of all the applications is almost the same for the old and new configurations because average message lengths are shorter than 10 Kbytes.

Therefore, software overhead has a major impact on the performance of parallel computers using message-passing libraries. Improving network hardware will have an almost negligible impact on performance unless the latency of the messaging layer is considerably reduced.

9.12.2 Optimizations in the Software Messaging Layer

In this section we present some performance evaluation results showing the advantages of establishing virtual circuits between nodes, and caching and reusing those circuits. This technique is referred to as virtual circuit caching (VCC). VCC is implemented by allocating buffers for message transmission at source and destination nodes before data are available. Those buffers are reused for all the subsequent transmissions between the same nodes, therefore reducing software overhead considerably. A directory of cached virtual circuits is kept at each node. The evaluation results presented in this section are based on [81].

The simulation study has been performed using a time-step simulator written in C. The simulated topology is a k-ary n-cube. A simulator cycle is normalized to the time to transmit one flit across a physical link. In addition, the size of one flit is 2 bytes. Since the VCC mechanism exploits communication locality, performance evaluation was performed using traces of parallel programs. Traces were gathered for several parallel kernels executing on a 256-processor system.

The communication traces were collected using an execution-driven simulator from the SPASM toolset [323]. The parallel kernels are the (1) broadcast-and-roll parallel matrix multiply (MM), (2) a NAS kernel (EP), (3) a fast Fourier transform (FFT), (4) a Kalman filter (Kalman), and (5) a multigrid solver for computing a 3-D field (MG). The algorithm kernels display different communication traffic patterns.

9.13.1 Software-Based Fault-Tolerant Routing

In this section we evaluate the performance of the software-based fault-tolerant routing protocols presented in Section 6.5.2. These techniques can be used on top of any deadlock-free routing algorithm, including oblivious e-cube routing and fully adaptive Duato’s protocol (DP). The resulting fault-tolerant routing protocols are referred to as e-sft and DP-sft, respectively.

The performance of e-sft and DP-sft was evaluated with flit-level simulation studies of message passing in a 16-ary 2-cube with 16-flit messages, a single-flit routing header, and eight virtual channels per physical channel. Message destination traffic was uniformly distributed. Simulation runs were made repeatedly until the 95% confidence intervals for the sample means were acceptable (less than 5% of the mean values). The simulation model was validated using deterministic communication patterns. We use a congestion control mechanism (similar to [36]) by placing a limit on the size of the buffer on the injection channels. If the input buffers are filled, messages cannot be injected into the network until a message in the buffer has been routed. Injection rates are normalized.

9.13.2 Routing Algorithms for PCS

This section evaluates the performance of two backtracking protocols using pipelined circuit switching (PCS) and compares them with three routing protocols using wormhole switching. Performance is analyzed both in fault-free networks and in the presence of static faults. The backtracking protocols analyzed in this section are exhaustive profitable backtracking (EPB) and misrouting backtracking with m misroutes (MB-m). These protocols were described in Section 4.7. The wormhole protocols analyzed here are Duato’s protocol (DP), dimension reversal routing (DR), and negative-first (NF). These protocols were described in Sections 4.4.4 and 4.3.2.

Given a source/destination pair (s, d), let s_i, d_i be the ith dimension coordinates for s and d, respectively. Let |s_i − d_i|_k denote the torus dimension distance from s_i to d_i defined by

We performed simulation studies on 16-ary 2-cubes to evaluate the performance of each protocol. Experiments were conducted with and without static physical link faults under a variety of network loads and message sizes. For all routing protocols except NF, a processor s was allowed to communicate to other processors in the subcube defined by {d : |s_i − d_i|_k ≤ 4, i = 1, …, n}. This corresponds to a neighborhood of about one-half the network diameter. Destinations were picked uniformly through this neighborhood. Since NF is not allowed to use end-around connections, the communication neighborhood was defined by {d : |s_i − d_i| ≤ 4, i − 1, …, n}. Thus, the diameter of the communication patterns was comparable for all routing protocols. A simulator cycle was normalized to the time to transmit one flit across a physical link. Each simulation was run for 30,000 global clock cycles, discarding information occurring during a 10,000-clock-cycle warm-up period. The transient start-up period was determined by monitoring variations in the values of performance parameters. We noted that after a duration of 10,000 network cycles, the computed parameter values did not deviate more than 2%. The recorded values in the start-up interval were discarded. In a moderately loaded network, in the 20,000 clock cycles over which statistics were gathered, over 800,000 flits were moved through the network. Each simulation was run repeatedly to obtain a sample mean and a sample variance for each measured value. Runs were repeated until the confidence intervals for the sample means were acceptable. The simulation model was validated using deterministic communication patterns. Simulations on single messages in traffic-free networks gave the theoretical latencies and setup times for wormhole and PCS messages. In addition, tests were performed on individual links to ensure that the simulated mechanisms for link arbitration in the presence of multiple virtual circuits over the link functioned correctly.

9.13.3 Routing Algorithms for Scouting

In this section we evaluate the performance of the two-phase (TP) routing protocol described in Section 6.6. When no faults are present in the network, TP routing uses K = 0 and the same routing restrictions as DP. This results in performance that is identical to that of DP. To measure the fault tolerance of TP, it is compared with misrouting backtracking with m misroutes (MB-m).

 Software messaging layer. A high percentage of the communication latency in multicomputers is produced by the overhead in the software messaging layer. Reducing or hiding this overhead is likely to have a higher impact on performance than the remaining design parameters, especially when messages are relatively short. The use of VCC can eliminate or hide most of the software overhead by overlapping path setup with computation, and caching and retaining virtual circuits for use by multiple messages. VCC complements the use of techniques to reduce the software overhead, like Active Messages. It should be noted that software overhead is so high in some multicomputers that it makes no sense improving other design parameters. However, once this overhead has been removed or hidden, the remaining design parameters become much more important.

 Software support for collective communication. Collective communication operations benefit considerably from using specific algorithms. Using separate addressing, latency increases linearly with the number of participating nodes. However, when algorithms for collective communication are implemented in software, latency is considerably reduced, increasing logarithmically with the number of participating nodes. This improvement is achieved with no additional hardware cost and no overhead for unicast messages.

 Number of ports. If the software overhead has been removed or hidden, the number of ports has a considerable influence on performance, especially when messages are sent locally. If the number of ports is too small, the network interface is likely to be a bottleneck for the network. The optimal number of ports heavily depends on the spatial locality of traffic patterns.

 Switching technique. Nowadays, most commercial and experimental parallel computers implement wormhole switching. Although VCT switching achieves a higher throughput, the performance improvement is small when virtual channels are used in wormhole switching. Additionally, VCT switching requires splitting messages into packets not exceeding buffer capacity. If messages are longer than buffer size, wormhole switching should be preferred. However, when messages are shorter than or equal to buffer size, VCT switching performs slightly better than wormhole switching, also simplifying deadlock avoidance. This is the case for distributed, shared-memory multiprocessors. VCT switching is also preferable when it is not easy to avoid deadlock in wormhole switching (multicast routing in multistage networks) or in some applications requiring real-time communication [294]. Finally, a combination of wormhole switching and circuit switching with wave-pipelined switches and channels has the potential to increase performance, especially when messages are very long [101].

 Packet size. For pipelined switching techniques, filling the pipeline produces some overhead. Also, routing a header usually takes longer than transmitting a data flit across a switch. Finally, splitting messages into packets and reassembling them at the destination node also produces some overhead. These overheads can be amortized if packets are long enough. However, once packets are long enough to amortize the overhead, it is not convenient to increase packet size even more because blocking time for some packets will be high. On the other hand, switching techniques like VCT may limit packet size, especially when packet buffers are implemented in hardware. Finally, it should be noted that this parameter only makes sense when messages are long. If they are shorter than the optimal packet size, messages should not be split into packets. This is the case for DSMs.

 Deadlock-handling technique. Current deadlock avoidance techniques allow fully adaptive routing across physical channels. However, some buffer resources (usually some virtual channels) must be dedicated to avoid deadlock by providing escape paths to messages blocking cyclically. On the other hand, progressive deadlock recovery techniques require a minimum amount of dedicated hardware to deliver deadlocked packets. Deadlock recovery techniques do not restrict routing at all and therefore allow the use of all the virtual channels to increase routing freedom, achieving the highest performance when packets are short. However, when packets are long or have very different lengths and the network approaches the saturation point, the small bandwidth offered by the recovery hardware may saturate. In this case, some deadlocked packets may have to wait for a long time, thus degrading performance and making latency less predictable. Also, recovery techniques require efficient deadlock detection mechanisms. Currently available detection techniques only work efficiently when all the packets are short and have a similar length. Otherwise, many false deadlocks are detected, quickly saturating the bandwidth of the recovery hardware. The poor behavior of current deadlock detection mechanisms considerably limits the practical applicability of deadlock recovery techniques unless all the packets are short. This may change when more accurate distributed deadlock detection mechanisms are developed.

 Routing algorithm. For regular topologies and uniform traffic, the difference between deterministic and fully adaptive routing algorithms is small. However, for switch-based networks with irregular topology and uniform traffic, adaptive routing algorithms considerably improve performance over deterministic or partially adaptive ones because the latter usually route many messages across nonminimal paths. Moreover, for nonuniform traffic patterns, adaptive routing considerably increases throughput over deterministic routing algorithms, regardless of network topology. On the other hand, adaptive routing does not reduce latency when traffic is low to moderate because contention is small and base latency is the same for deterministic and fully adaptive routing, provided that both algorithms only use minimal paths. So, for real applications, the best choice depends on the application requirements. If most applications exhibit a high degree of communication locality, fully adaptive routing does not help. If the traffic produced by the applications does not saturate the network (regardless of the routing algorithm) and latency is critical, then adaptive routing will not increase performance. However, when multiprocessors implement latency-hiding mechanisms and application performance mainly depends on the throughput achievable by the interconnection network, then adaptive routing is expected to achieve higher performance than deterministic routing. In the case of using adaptive routing, the additional cost of implementing fully adaptive routing should be kept small. Therefore, routing algorithms that require few resources to avoid deadlock or to recover from it, like the ones evaluated in this chapter, should be preferred. For these routing algorithms, the additional complexity of fully adaptive routing usually produces a small reduction in clock frequency.

 Number of virtual channels. In wormhole switching, when no virtual channels are used, blocked messages do not allow other messages to use the bandwidth of the physical channels they are occupying. Adding the first additional virtual channel usually increases throughput considerably at the expense of a small increase in latency. On the other hand, adding more virtual channels produces a much smaller increment in throughput while increasing hardware delays considerably. For deterministic routing in meshes, two virtual channels provide a good trade-off. For tori, the partially adaptive algorithm evaluated in this chapter with two virtual channels also provides a good trade-off, achieving the advantages of channel multiplexing without increasing the number of virtual channels with respect to the deterministic algorithm. If fully adaptive routing is preferred, the minimum number of virtual channels should be used. Fully adaptive routing requires a minimum of two (three) virtual channels to avoid deadlock in meshes (tori). Again, for applications that require low latency and produce a relatively small amount of traffic, adding virtual channels does not help. Virtual channels only increase performance when applications benefit from a higher network throughput.

 Hardware support for collective communication. Adding hardware support for multidestination message passing usually reduces the latency of collective communication operations with respect to software algorithms. However, this reduction is very small (if any) when the number of participating nodes is small. When many nodes participate and traffic is only composed of multidestination messages, latency reduction ranges from 2 to 7, depending on several parameters. In real applications, traffic for collective communication operations usually represents a much smaller fraction of network traffic. Also, the number of participating nodes may vary considerably from one application to another. In general, this number is small except for broadcast and barrier synchronization. In summary, whether adding hardware support for collective communication is worth its cost depends on the application requirements.

 Injection limitation mechanism. When fully adaptive routing is used, network interfaces should include some mechanism to limit the injection of new messages when the network is heavily loaded. Otherwise, increasing applied load above the saturation point may degrade performance severely. In some cases, the start-up latency is so high that it effectively limits the injection rate. When the start-up latency does not prevent network saturation, simple mechanisms like restricting injected messages to use some predetermined virtual channel(s) or waiting until the number of free output virtual channels at a node is higher than a threshold are enough. Injection limitation mechanisms are especially recommended when using routing algorithms that allow cyclic dependencies between channels, and to limit the frequency of deadlock when using deadlock recovery mechanisms.

 Buffer size. For wormhole switching and short messages, increasing buffer size above a certain threshold does not improve performance significantly. For long messages (or packets), increasing buffer size increases performance because blocked messages occupy fewer channels. However, when messages are very long, increasing buffer size only helps if buffers are deep enough to allow blocked messages to leave the source node and release some channels. It should be noted that communication locality may prevent most messages from leaving the source node before reaching their destination even when using deep buffers. Therefore, in most cases small buffers are enough to achieve good performance. However, this analysis assumes that flits are individually acknowledged. Indeed, buffer size in wormhole switching is mainly determined by the requirements of the flow control mechanism. Optimizations like block acknowledgments require a certain buffer capacity to perform efficiently. Moreover, when channels are pipelined, buffers must be deep enough to store all the flits in transit across the physical link plus the flits injected into the link during the propagation of the flow control signals. Some additional capacity is required for the flow control mechanism to operate without introducing bubbles in the message pipeline. Thus, when channels are pipelined, buffer size mainly depends on the degree of channel pipelining. For VCT switching, throughput increases considerably when moving from one to two packet buffers. Adding more buffers yields diminishing returns.

 Reliability/performance trade-offs. An interconnection network should be reliable. Depending on the intended applications and the relative value of MTBF and MTTR, different trade-offs are possible. When MTTR << MTBF, the probability of the second or the third fault occurring before the first fault is repaired is very low. In such environments, software-based rerouting is a cost-effective and viable alternative. This technique supports many fault patterns and requires minimum hardware support. However, performance degrades significantly when faults occur, increasing latency for messages that meet faults by a factor of 2–4. When faults are more frequent or performance degradation is not acceptable, a more complex hardware support is required. The fault tolerance properties of the routing algorithm are constrained by the underlying switching technique, as indicated in the next item.

 Switching technique. If performance is more important than reliability, fault tolerance should be achieved without modifying the switching technique. In this case, additional resources (usually virtual channels) are required to implement limited misrouting and route messages in the presence of faults. If reliability is more important than performance, PCS has the potential to increase fault tolerance considerably at the cost of some overhead in path setup. PCS can be combined with misrouting backtracking protocols, achieving an excellent level of tolerance to static faults. Finally, dynamically configurable flow control techniques, like scouting, offer an excellent performance/reliability trade-off at the expense of a more complex hardware support. This switching technique achieves performance similar to that of wormhole switching in the absence of faults, and reliability halfway between wormhole switching and PCS.

 Support for dynamic faults. Faults may occur at any time. When a fault interrupts a message in transit, the message cannot be delivered, and a fragment of the message may remain in the network forever, therefore producing deadlock. So, hardware support for dynamic faults has to perform two different actions: removing fragments of interrupted messages and notifying the source node so that the message is transmitted again. Adding support to remove fragments of interrupted messages is very convenient because it does not slow down normal operation significantly, and deadlocks produced by interrupted messages are avoided. However, notifying the source node produces an extra use of resources for every transmitted message, therefore degrading performance significantly even in the absence of faults. So, this additional support for reliable transmission should only be included when reliability is more important than performance.