Fat tree

A fat tree.

The fat tree network is a universal network for provably efficient communication.^[1] It was invented by Charles E. Leiserson of the Massachusetts Institute of Technology in 1985.^[1]

In a tree data structure, every branch has the same thickness, regardless of their place in the hierarchy—they are all "skinny" (skinny in this context means low-bandwidth). In a fat tree, branches nearer the top of the hierarchy are "fatter" (thicker) than branches further down the hierarchy. In a telecommunications network, the branches are data links; the varied thickness (bandwidth) of the data links allows for more efficient and technology-specific use.

Mesh topology and the "hypercube" topology of Connection Machines have communication requirements that follow a rigid algorithm, and cannot be tailored to specific packaging technologies.

Applications in supercomputers

Supercomputers that use a fat tree network^[2] include the Tianhe-2,^[3] the Meiko Scientific CS-2, Yellowstone, the Earth Simulator, the Cray X2, the Connection Machine CM-5, and various Altix supercomputers.

Mercury Computer Systems applied a variant of the fat tree topology—the hypertree network—to their multicomputers. In this architecture, 2 to 360 compute nodes are arranged in a circuit-switched fat tree network. Each node has local memory that can be mapped by any other node. Each node in this heterogeneous system could be an Intel i860, a PowerPC, or a group of three SHARC digital signal processors.

The fat tree network was particularly well suited to Fast Fourier transform computations, which customers used for such signal processing tasks as radar, sonar, and medical imaging.

Related topologies

In late August 2008, a team of computer scientists at UCSD published a scalable design for network architecture^[4] that uses a topology inspired by the fat tree topology to realize networks that scale better than those of previous hierarchical networks. The architecture uses commodity switches that are cheaper and more power-efficient than high-end modular data center switches.

This topology is actually a special instance of a Clos network, rather than a fat-tree as described above. That is because the edges near the root are emulated by many links to separate parents instead of a single high-capacity link to a single parent. However, many authors continue to use the term in this way.

References

Further reading

• Sima, D.; Fountain, T.; Kacsuk, P. (1997). Advanced Computer Architectures: A Design Space Approach. Addison-Wesley. ISBN 978-0-201-42291-7. OCLC 36841473.