Fat tree: Difference between revisions
No edit summary |
imported>Citation bot Removed URL that duplicated identifier. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 879/1032 |
||
| Line 4: | Line 4: | ||
[[File:Fat-tree.svg|thumb|A 2-level fat tree with 8-port switches]] | [[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 | 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 |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}} | 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}} | ||
| Line 11: | Line 11: | ||
==Applications in supercomputers== | ==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}} | 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]]}}{{Dead link|date=August 2025 |bot=InternetArchiveBot |fix-attempted=yes }}</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}} | [[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}} | ||
Latest revision as of 18:47, 25 August 2025
Template:Short description Script error: No such module "Unsubst".
The fat tree network is a universal network for provably efficient communication.[1] It was invented by Charles E. Leiserson of the MIT in 1985.[1] k-ary n-trees, the type of fat-trees commonly used in most high-performance networks, were initially formalized in 1997.[2]
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.Script error: No such module "Unsubst".
Mesh and hypercube topologies have communication requirements that follow a rigid algorithm, and cannot be tailored to specific packaging technologies.[3]
Applications in supercomputers
Supercomputers that use a fat tree network[4] include the two fastest as of late 2018,[5] Summit[6] and Sierra,[7] as well as Tianhe-2,[8] the Meiko Scientific CS-2, Yellowstone, the Earth Simulator, the Cray X2, the Connection Machine CM-5, and various Altix supercomputers.Script error: No such module "Unsubst".
Mercury Computer Systems applied a variant of the fat tree topology—the hypertree network—to their multicomputers.Script error: No such module "Unsubst". In this architecture, 2 to 360 compute nodes are arranged in a circuit-switched fat tree network.Script error: No such module "Unsubst". Each node has local memory that can be mapped by any other node.Script error: No such module "Unsubst". Each node in this heterogeneous system could be an Intel i860, a PowerPC, or a group of three SHARC digital signal processors.Script error: No such module "Unsubst".
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.Script error: No such module "Unsubst".
Related topologies
In August 2008, a team of computer scientists at UCSD published a scalable design for network architecture[9] 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
<templatestyles src="Reflist/styles.css" />
- ↑ a b Script error: No such module "Citation/CS1".
- ↑ Script error: No such module "citation/CS1".
- ↑ Script error: No such module "citation/CS1".
- ↑ Script error: No such module "citation/CS1".
- ↑ Script error: No such module "citation/CS1".
- ↑ Script error: No such module "citation/CS1".
- ↑ Script error: No such module "citation/CS1".Script error: No such module "Unsubst".
- ↑ Script error: No such module "citation/CS1".
- ↑ Script error: No such module "citation/CS1".
Script error: No such module "Check for unknown parameters".
Further reading
- Script error: No such module "citation/CS1".