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]

A fat tree.

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 and hypercube topologies have communication requirements that follow a rigid algorithm, and cannot be tailored to specific packaging technologies.[2]

Applications in supercomputers

Supercomputers that use a fat tree network[3] include the two fastest as of late 2018,[4] Summit[5] and Sierra,[6] as well as Tianhe-2,[7] 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[8] 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

1. Leiserson, Charles E (October 1985). "Fat-trees: universal networks for hardware-efficient supercomputing" (PDF). IEEE Transactions on Computers. 34 (10): 892–901. doi:10.1109/TC.1985.6312192.
2. Leiserson, Charles E.; Abuhamdeh, Zahi S.; Douglas, David C.; Feynman, Carl R.; Ganmukhi, Mahesh N.; Hill, Jeffrey V.; Daniel Hillis, W.; Kuszmaul, Bradley C.; St. Pierre, Margaret A.; Wells, David S.; Wong, Monica C.; Yang, Shaw-Wen; Zak, Robert (1992). "The Network Architecture of the Connection Machine CM-5". SPAA '92 Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures. ACM. pp. 272–285. doi:10.1145/140901.141883. ISBN 978-0-89791-483-3.
3. Yuefan Deng (2013). "3.2.1 Hardware systems: Network Interconnections: Topology". Applied Parallel Computing. World Scientific. p. 25. ISBN 978-981-4307-60-4.
4. "November 2018 TOP500". TOP500. November 2018. Retrieved 2019-02-11.
5. "Summit - Oak Ridge National Laboratory's next High Performance Supercomputer". Oak Ridge Leadership Computing Facility. Retrieved 2019-02-11.
6. Barney, Blaise (2019-01-18). "Using LC's Sierra Systems - Hardware - Mellanox EDR InfiniBand Network - Topology and LC Sierra Configuration". Lawrence Livermore National Laboratory. Retrieved 2019-02-11.
7. Dongarra, Jack (2013-06-03). "Visit to the National University for Defense Technology Changsha, China" (PDF). Netlib. Retrieved 2013-06-17.
8. Al-Fares, Mohammad; Loukissas, Alexander; Vahdat, Amin (2008). "A scalable, commodity data center network architecture" (PDF). Proceedings of the ACM SIGCOMM 2008 conference on Data communication. ACM. pp. 63–74. doi:10.1145/1402958.1402967. ISBN 978-1-60558-175-0.

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.