Fat tree

From HandWiki
Short description: Universal network for provably efficient communication
A fat tree
A 2-level fat tree with 8-port switches

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] 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.[citation needed]

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.[citation needed]

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

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]

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

  1. 1.0 1.1 Leiserson, Charles E (October 1985). "Fat-trees: universal networks for hardware-efficient supercomputing". IEEE Transactions on Computers 34 (10): 892–901. doi:10.1109/TC.1985.6312192. http://courses.csail.mit.edu/6.896/spring04/handouts/papers/fat_trees.pdf. 
  2. Petrini, Fabrizio (1997). "K-ary n-trees: High performance networks for massively parallel architectures". Proceedings 11th International Parallel Processing Symposium. doi: 10.1109/IPPS.1997.580853.. pp. 87–93. doi:10.1109/IPPS.1997.580853. ISBN 0-8186-7793-7. https://ieeexplore.ieee.org/document/580853. 
  3. Leiserson, Charles E.; Abuhamdeh, Zahi S.; Douglas, David C.; Feynman, Carl R.; Ganmukhi, Mahesh N.; Hill, Jeffrey V.; Daniel Hillis, W.; Kuszmaul, Bradley C. et al. (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. https://dl.acm.org/citation.cfm?doid=140901.141883. 
  4. Yuefan Deng (2013). "3.2.1 Hardware systems: Network Interconnections: Topology". Applied Parallel Computing. World Scientific. pp. 25. ISBN 978-981-4307-60-4. https://books.google.com/books?id=YS9wvVeWrXgC&pg=PA25. 
  5. "November 2018 TOP500". TOP500. November 2018. https://www.top500.org/lists/2018/11/. 
  6. "Summit - Oak Ridge National Laboratory's next High Performance Supercomputer". Oak Ridge Leadership Computing Facility. https://www.olcf.ornl.gov/olcf-resources/compute-systems/summit. 
  7. Barney, Blaise (2019-01-18). "Using LC's Sierra Systems - Hardware - Mellanox EDR InfiniBand Network - Topology and LC Sierra Configuration". Lawrence Livermore National Laboratory. https://computing.llnl.gov/tutorials/sierra/#Mellanox. 
  8. Dongarra, Jack (2013-06-03). "Visit to the National University for Defense Technology Changsha, China". Netlib. http://www.netlib.org/utk/people/JackDongarra/PAPERS/tianhe-2-dongarra-report.pdf. 
  9. Al-Fares, Mohammad; Loukissas, Alexander; Vahdat, Amin (2008). "A scalable, commodity data center network architecture". 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. http://www.cs.kent.edu/~javed/class-CXNET09S/papers-CXNET-2009/FaLV08-DataCenter-interconnect-p63-alfares.pdf. 

Further reading