Fat tree

{{Short description|Universal network for provably efficient communication}}

The fat tree network is a universal network for provably efficient communication.{{cite journal |author-link=Charles E. Leiserson |first=Charles E |last=Leiserson |title=Fat-trees: universal networks for hardware-efficient supercomputing |journal=IEEE Transactions on Computers |volume=34 |issue=10 |pages=892–901 |date=October 1985 |doi=10.1109/TC.1985.6312192 |s2cid=8927584 |url=http://courses.csail.mit.edu/6.896/spring04/handouts/papers/fat_trees.pdf }} It was invented by Charles E. Leiserson of the MIT in 1985. k-ary n-trees, the type of fat-trees commonly used in most high-performance networks, were initially formalized in 1997.{{Cite book |last=Petrini |first=Fabrizio |title=Proceedings 11th International Parallel Processing Symposium |chapter=K-ary n-trees: High performance networks for massively parallel architectures |date=1997 |chapter-url=https://ieeexplore.ieee.org/document/580853 |volume=doi: 10.1109/IPPS.1997.580853. |pages=87–93|doi=10.1109/IPPS.1997.580853 |isbn=0-8186-7793-7 |s2cid=6608892 }}

In a tree data structure, every branch has the same thickness (bandwidth), 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.{{citation needed|date=March 2016}}

Mesh and hypercube topologies have communication requirements that follow a rigid algorithm, and cannot be tailored to specific packaging technologies.{{cite book |first1=Charles E. |last1=Leiserson |first2=Zahi S. |last2=Abuhamdeh |first3=David C. |last3=Douglas |first4=Carl R. |last4=Feynman |first5=Mahesh N. |last5=Ganmukhi |first6=Jeffrey V. |last6=Hill |first7=W. |last7=Daniel Hillis |first8=Bradley C. |last8=Kuszmaul |first9=Margaret A. |last9=St. Pierre |first10=David S. |last10=Wells |first11=Monica C. |last11=Wong |first12=Shaw-Wen |last12=Yang |first13=Robert |last13=Zak |chapter=The Network Architecture of the Connection Machine CM-5 |title=SPAA '92 Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures |pages=272–285 |publisher=ACM |year=1992 |isbn=978-0-89791-483-3 |doi=10.1145/140901.141883 |s2cid=6307237 |chapter-url=https://dl.acm.org/citation.cfm?doid=140901.141883}}

Applications in supercomputers

Supercomputers that use a fat tree network{{cite book |author-link=Yuefan Deng |author=Yuefan Deng |title=Applied Parallel Computing |chapter=3.2.1 Hardware systems: Network Interconnections: Topology |chapter-url=https://books.google.com/books?id=YS9wvVeWrXgC&pg=PA25 |year=2013 |publisher=World Scientific |isbn=978-981-4307-60-4 |pages=25}} include the two fastest as of late 2018,{{cite web|url=https://www.top500.org/lists/2018/11/|title=November 2018 TOP500|date=November 2018|access-date=2019-02-11|publisher=TOP500}} Summit{{cite web|url=https://www.olcf.ornl.gov/olcf-resources/compute-systems/summit|title=Summit - Oak Ridge National Laboratory's next High Performance Supercomputer|access-date=2019-02-11|publisher=Oak Ridge Leadership Computing Facility}} and Sierra,{{cite web|url=https://computing.llnl.gov/tutorials/sierra/#Mellanox|title=Using LC's Sierra Systems - Hardware - Mellanox EDR InfiniBand Network - Topology and LC Sierra Configuration|date=2019-01-18|access-date=2019-02-11|last=Barney|first=Blaise|publisher=Lawrence Livermore National Laboratory}} as well as Tianhe-2,{{cite web|url=http://www.netlib.org/utk/people/JackDongarra/PAPERS/tianhe-2-dongarra-report.pdf|title=Visit to the National University for Defense Technology Changsha, China |date=2013-06-03 |access-date=2013-06-17 |last=Dongarra |first=Jack |publisher=Netlib}} the Meiko Scientific CS-2, Yellowstone, the Earth Simulator, the Cray X2, the Connection Machine CM-5, and various Altix supercomputers.{{citation needed|date=March 2016}}

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

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.{{citation needed|date=March 2016}}

Related topologies

In August 2008, a team of computer scientists at UCSD published a scalable design for network architecture{{cite book |first1=Mohammad |last1=Al-Fares |first2=Alexander |last2=Loukissas |first3=Amin |last3=Vahdat |chapter=A scalable, commodity data center network architecture |title=Proceedings of the ACM SIGCOMM 2008 conference on Data communication |isbn=978-1-60558-175-0 |pages=63–74 |year=2008 |doi=10.1145/1402958.1402967 |publisher=ACM |s2cid=65842 |chapter-url=http://www.cs.kent.edu/~javed/class-CXNET09S/papers-CXNET-2009/FaLV08-DataCenter-interconnect-p63-alfares.pdf }} 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.

Fat tree

Applications in supercomputers

Related topologies

References

Further reading