Reference articles on history, science, culture and more
Encyclopedia

Fat tree

Universal network for provably efficient communication

Image credit is listed at the end of this article.

The fat tree network is a universal network for provably efficient communication. 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.

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.

Mesh and hypercube topologies have communication requirements that follow a rigid algorithm, and cannot be tailored to specific packaging technologies.

01Applications in supercomputers

Supercomputers that use a fat tree network include the two fastest as of late 2018, Summit and Sierra, as well as Tianhe-2, the Meiko Scientific CS-2, Yellowstone, the Earth Simulator, the Cray X2, the Connection Machine CM-5, and various Altix supercomputers.

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

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.

A 2-level fat tree with 8-port switches
A 2-level fat tree with 8-port switches
Watch videos about Fat treeExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article Fat tree, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Images, from Wikimedia Commons:

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.