4. HIGH-RADIX TOPOLOGIES
of a Clos network can be combined or folded on top of one another creating a folded Clos or fat-
tree [ 44 ] network which can exploit traffic locality with the input/output ports co-located, as shown
in Figure 4.6 (b).
A Clos or folded Clos network, however, has a cost that is nearly double that of a butterfly
with equal capacity and has greater latency than a butterfly. The increased cost and latency both stem
from the need to route packets first to an arbitrary middle stage switch and then to their ultimate
destination. This doubles the number of long cables in the network, which approximately doubles
cost, and doubles the number of inter-router channels traversed, which drives up latency.
4.3.4 FLATTENED BUTTERFLY
To overcome the limitations of the folded-Clos topology, the flattened butterfly [ 41 ] removes in-
termediate stages and creates a direct network. As a result, the flattened butterfly is a topology that
exploits high-radix routers to realize lower cost than a Clos on load-balanced traffic, and provide
better performance and path diversity than a conventional butterfly. The flattened butterfly can be
derived by starting with a conventional butterfly ( k -ary n -fly) and combining or flattening the routers
in each row of the network into a single router. An example of flattened butterfly construction is
shown in Figure 4.7 . 4-ary 3-fly network is shown in Figure 4.7 (a) with the corresponding flattened
butterflies shown in Figure 4.7 (b). The routers R1, R2, and R3 from the first row of Figure 4.7 (a) are
combined into a single router R0 in the flattened butterfly of Figure 4.7 (b). As a row of routers is
combined, channels entirely local to the row, e.g., channel (R0,R1) in Figure 4.7 (a), are eliminated.
All other channels of the original butterfly remain in the flattened butterfly. Because channels in a
flattened butterfly are symmetrical, each line in Figures 4.7 (b) represents a bidirectional channel (i.e.,
two unidirectional channels), while each line in Figures 4.7 (a) represents a unidirectional channel.
A k -ary n -flat, the flattened butterfly derived from a k -ary n -fly, is composed of
1 routers where N is the size of the network. The routers are connected by channels
in n = n −
1 columns of inter-rank wiring in the butterfly.
In each dimension d ,from1to n , router i is connected to each router j given by
1 dimensions, corresponding to the n −
k d − 1 mod k k d − 1
for m from0to k − 1, where the connection from i to itself is omitted. For example, in Figure 4.7 (d),
R4 is connected to R5 in dimension 1, R6 in dimension 2, and R0 in dimension 3. With this
construction, it is easy to see that the flattened butterfly is equivalent to the generalized hypercube
topology [ 10 ], but with k -way concentration. With this concentration, the topology is better able
to exploit the properties of high-radix routers.
Although the flattened butterfly can cost-efficiently exploit high-radix routers, it is ultimately limited
by the physical constraints of a router radix and cost of scaling to large node count. For example, if