Fat Trees, Toruses, and the Bisection Bandwidth Ceiling

A stencil code exchanges data with its geometric neighbours, and if the decomposition is mapped sensibly those neighbours are close in the network. A fast Fourier transform, a dense matrix transpose, and a global reduction do the opposite: every rank talks to ranks all over the machine. The second class of patterns is limited by a property of the wiring that no amount of per-link bandwidth fixes, because the traffic has to cross a cut that has only so many wires.

That property is bisection bandwidth: the total capacity of the links crossing a cut that divides the machine into two equal halves, minimized over all such cuts. It is the right figure of merit for any pattern in which half the ranks send to the other half, and it explains why the same application can scale well on one machine and poorly on another with identical nodes and identical per-port link rates.

The cut that bounds global traffic

Take any division of the ranks into two sets of equal size. Every byte that must travel from one set to the other crosses the cut, and the links crossing the cut have a fixed total capacity B. If a communication phase requires V bytes to cross, the phase cannot finish faster than V/B, regardless of how the endpoints are scheduled.

For an allreduce of n bytes per rank, every rank’s contribution must reach every other rank, so at least nP/2 bytes must cross the cut. The lower bound on time is therefore nP/(2B). Whether that bound is loose or tight depends on the algorithm and the topology, but it cannot be beaten. The same argument applies to an all-to-all exchange, where the volume crossing the cut is larger by another factor of the rank count, and to a transpose of a distributed matrix.

The bound is a statement about the wiring, not about the switches. A network with full bisection bandwidth has B proportional to P, so the per-rank share B/P is constant. A network with B growing more slowly than P has a per-rank share that falls as the machine grows, and the allreduce bound rises accordingly.

What a fat tree buys and what it costs

A fat tree arranges switches in levels and makes the links between levels progressively wider, so that no level is a bottleneck. The classical construction uses k-port switches in three levels: k pods, each containing k/2 edge switches connected to hosts and k/2 aggregation switches, with (k/2)^2 core switches joining the pods. Such a tree connects k^3/4 hosts. With 48-port switches that is 27,648 hosts, and every host can communicate with every other at the full link rate, because the core is provisioned for the worst case.

Full bisection is bought with links. The number of switches and cables grows faster than the number of hosts, and the root switches are the most expensive part of the fabric. Many installed clusters therefore build the tree with an oversubscription ratio: the links into the core carry less aggregate bandwidth than the links at the edge, typically by a factor of two or four. The machine still works, but a global pattern pays the oversubscription factor, and a job that ran at full speed on a non-oversubscribed partition will not do so on a larger oversubscribed one.

The tree also costs latency in hops. A packet from a host to a host in another pod traverses edge, aggregation, core, aggregation, edge, which is five switch hops. Each hop adds a store-and-forward or cut-through delay, and at high load the queues at the core add more. The topology minimizes the worst-case hop count at O(log P), which is the best a network of switches with bounded radix can do.

Why a torus is cheap and what it cannot do

A three-dimensional torus connects each node to its six axis neighbours, wrapping at the edges. Every node has the same small number of links, so the cabling cost per node is constant, and the network can be built from direct links between nodes without a separate switch layer. For a stencil code whose subdomains are mapped onto neighbouring nodes, almost all traffic stays on short local links, and the topology matches the communication pattern closely.

The bisection bandwidth does not keep up. A torus of L nodes per side has L^3 nodes, and a cut along one dimension crosses L^2 links in each direction, for 2L^2 links total. Per node, that is 2/L, which falls as the cube root of the machine size. At ten thousand nodes, L is about 21, so the per-node share of bisection bandwidth is roughly a tenth of a link. A global pattern can use only that share, however many links each node has.

The hop count is the other cost. Dimension-order routing sends a packet along one axis, then the next, then the next, so the worst-case distance is about 1.5 L hops, which grows as the cube root of the node count rather than as its logarithm. At a few thousand nodes the difference from a fat tree is small; at a hundred thousand it is not. Dimension-order routing is deadlock-free on a torus without virtual channels, which is part of why the topology is popular for machines that value simplicity and cost over worst-case global bandwidth.

#include <math.h>

/* Lower bound on allreduce time imposed by the bisection cut.
   n bytes per rank, p ranks, B bytes per second across the cut. */
double allreduce_bound(double n, long p, double b)
{
    return n * (double)p / (2.0 * b);
}

/* Bisection bandwidth in link units for two topologies. */
double bisect_torus(long nodes)      { return 2.0 * pow((double)nodes, 2.0 / 3.0); }
double bisect_fat_tree(long nodes)   { return (double)nodes; }  /* full bisection */

The two expressions differ by a factor of P^(1/3), and that factor is the entire argument for paying for a tree.

Dragonfly and the hierarchy compromise

The dragonfly topology sits between the two extremes. Nodes are grouped into groups of switches with high-radix ports; most traffic stays within a group, and a smaller number of global links connect groups. The hierarchy keeps the average hop count low, because a packet that leaves its group reaches any other group in one global hop, and it keeps the cost low, because the global links are a small fraction of the total.

The catch is that the global links are shared. A group with a switches and h global links per switch has a fixed capacity to the rest of the machine, and traffic that happens to concentrate on one group pair can saturate it. Dragonfly designs therefore depend on adaptive routing and on a traffic pattern that is spread across groups. A stencil code with a compact decomposition is a good fit, because its neighbours can be placed within a group; a global transpose is not, because it sends every group’s traffic to every other group at once.

The general principle across all three topologies is that cost scales with the worst-case traffic the network is designed to carry. A machine sized for local stencil traffic can be built cheaply from a torus. A machine sized for arbitrary global traffic needs a tree or a carefully provisioned dragonfly, and the difference in cost is a large multiple of the node cost.

Matching the pattern to the wiring

The topology is fixed at installation, but the mapping of ranks to nodes is not, and the mapping decides whether the application sees the local or the global side of the network.

For a block decomposition, ranks that exchange halos should be placed on nodes that are adjacent in the topology. The natural rank ordering from a row-major traversal of the process grid does not guarantee this, because the scheduler assigns ranks to nodes in the order the job requests them. A topology-aware placement maps the process grid onto the machine’s coordinates, which can turn a random pattern into a local one. The SPMD article notes that rank order carries no locality guarantee; this is where that matters.

For a global pattern, placement cannot help, and the only remedies are algorithmic. A reduction can be arranged as a sequence of local reductions followed by a smaller global one, so that most of the traffic stays within a group or a node. A transpose can be blocked so that the largest messages are contiguous and the number of hops per byte falls. These are the same ideas that communication-avoiding algorithms apply more aggressively, and they exist because the bisection bound is a property of the wiring that software can only work around.

The measurement consequence is that a scaling study on one partition does not transfer to another with a different oversubscription ratio or a different topology. The strong and weak scaling curve contains the network’s properties as much as the algorithm’s, and the only way to separate them is to know what the machine is wired to do.