Editing Fat tree

{{Short description|Universal network for provably efficient communication}}
{{More citations needed|date=August 2007}}
[[File:fat tree network.svg|thumb|A fat tree]]
[[File:Fat-tree.svg|thumb|A 2-level fat tree with 8-port switches]]

The '''fat tree network''' is a universal [[Network theory|network]] for provably efficient communication.<ref name="CL85">{{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 }}</ref> It was invented by [[Charles E. Leiserson]] of the [[Massachusetts Institute of Technology|MIT]] in 1985.<ref name="CL85" /> k-ary n-trees, the type of fat-trees commonly used in most high-performance networks, were initially formalized in 1997.<ref>{{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 }}</ref>

In a [[tree (data structure)|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 (computing)|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 link]]s; the varied thickness (bandwidth) of the data links allows for more efficient and technology-specific use.{{citation needed|date=March 2016}}

[[Mesh topology|Mesh]] and [[hypercube internetwork topology|hypercube]] topologies have communication requirements that follow a rigid algorithm, and cannot be tailored to specific packaging technologies.<ref>{{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}}</ref>

==Applications in supercomputers==
Supercomputers that use a fat tree network<ref>{{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}}</ref> include the two fastest as of late 2018,<ref>{{cite web|url=https://www.top500.org/lists/2018/11/|title=November 2018 TOP500|date=November 2018|access-date=2019-02-11|publisher=[[TOP500]]}}</ref> [[Summit (supercomputer)|Summit]]<ref>{{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]]}}</ref> and [[Sierra (supercomputer)|Sierra]],<ref>{{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]]}}</ref> as well as [[Tianhe-2]],<ref>{{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]]}}</ref> the [[Meiko Scientific]] CS-2, [[Yellowstone (supercomputer)|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 [[multicomputer]]s.{{citation needed|date=March 2016}} In this architecture, 2 to 360 compute nodes are arranged in a [[Circuit switching|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 [[Super Harvard Architecture Single-Chip Computer|SHARC]] [[digital signal processor]]s.{{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 scientist]]s at [[UCSD]] published a scalable design for network architecture<ref name="FaLouVah08">{{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 }}</ref> 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 ==
{{reflist}}

==Further reading==
* {{cite book |title=Advanced Computer Architectures: A Design Space Approach |url=https://archive.org/details/advancedcomputer0000sima |url-access=registration |last1=Sima |first1=D. |last2=Fountain |first2=T. |last3=Kacsuk |first3=P. |publisher=[[Addison-Wesley]] |date=1997 |isbn=978-0-201-42291-7 |oclc=36841473}}

{{Network topologies}}

{{DEFAULTSORT:Fat tree}}
[[Category:Network topology]]