Fat tree
 | This article needs additional citations for verification. (August 2007) |
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]
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.[citation needed]
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 Tianhe-2,[4] 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 late August 2008, a team of computer scientists at UCSD published a scalable design for network architecture[5] 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
- ^ a b Charles E. Leiserson Fat-trees: universal networks for hardware-efficient supercomputing, IEEE Transactions on Computers, Vol. 34 , no. 10, Oct. 1985, pp. 892-901.
- ^ Charles E. Leiserson, Zahi S. Abuhamdeh, David C. Douglas, Carl R. Feynman, Mahesh N. Ganmukhi, Jeffrey V. Hill, W. Daniel Hillis, Bradley C. Kuszmaul, Margaret A. St. Pierre, David S. Wells, Monica C. Wong, Shaw-Wen Yang, and Robert Zak. The Network Architecture of the Connection Machine CM-5. Proceedings of the fourth annual ACM Symposium on Parallel Algorithms and Architectures. 1992.
- ^ Yuefan Deng include "Applied Parallel Computing". 2013. p. 25
- ^ Dongarra, Jack (2013-06-03). "Visit to the National University for Defense Technology Changsha, China" (PDF). Netlib. Retrieved 2013-06-17.
- ^ Al-Fares, Loukissas, Vahdat, A Scalable, Commodity Data Center Network Architecture, proceedings of SIGCOMM, 2008.
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.