The fat tree network is a universal

network Network, networking and networked may refer to: Science and technology * Network theory, the study of graphs as a representation of relations between discrete objects * Network science, an academic field that studies complex networks Mathematics ...

for provably efficient communication. It was invented by Charles E. Leiserson of the

Massachusetts Institute of Technology The Massachusetts Institute of Technology (MIT) is a Private university, private Land-grant university, land-grant research university in Cambridge, Massachusetts. Established in 1861, MIT has played a key role in the development of modern t ...

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 In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...

data structure In computer science, a data structure is a data organization, management, and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the rel ...

, 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 A telecommunications network is a group of nodes interconnected by telecommunications links that are used to exchange messages between the nodes. The links may use a variety of technologies based on the methodologies of circuit switching, mes ...

, the branches are

data link A data link is the means of connecting one location to another for the purpose of transmitting and receiving digital information ( data communication). It can also refer to a set of electronics assemblies, consisting of a transmitter and a rece ...

s; the varied thickness (bandwidth) of the data links allows for more efficient and technology-specific use.

Mesh A mesh is a barrier made of connected strands of metal, fiber, or other flexible or ductile materials. A mesh is similar to a web or a net in that it has many attached or woven strands. Types * A plastic mesh may be extruded, oriented, e ...

and

hypercube In geometry, a hypercube is an ''n''-dimensional analogue of a square () and a cube (). It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions ...

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

Applications in supercomputers

Supercomputers that use a fat tree network include the two fastest as of late 2018,

Summit A summit is a point on a surface that is higher in elevation than all points immediately adjacent to it. The topographic terms acme, apex, peak (mountain peak), and zenith are synonymous. The term (mountain top) is generally used only for a m ...

and

Sierra Sierra (Spanish for "mountain range" and "saw", from Latin '' serra'') may refer to the following: Places Mountains and mountain ranges * Sierra de Juárez, a mountain range in Baja California, Mexico * Sierra de las Nieves, a mountain range i ...

, as well as

Tianhe-2 Tianhe-2 or TH-2 (, i.e. 'Milky Way 2') is a 33.86-petaflops supercomputer located in the National Supercomputer Center in Guangzhou, China. It was developed by a team of 1,300 scientists and engineers. It was the world's fastest supercomputer ...

, the Meiko Scientific CS-2,

Yellowstone Yellowstone National Park is an American national park located in the western United States, largely in the northwest corner of Wyoming and extending into Montana and Idaho. It was established by the 42nd U.S. Congress with the Yellow ...

, the

Earth Simulator The is a series of supercomputers deployed at Japan Agency for Marine-Earth Science and Technology Yokohama Institute of Earth Sciences. Earth Simulator (first generation) The first generation of Earth Simulator, developed by the Japanese g ...

, the Cray X2, the Connection Machine CM-5, and various Altix supercomputers.

Mercury Computer Systems Mercury Systems, Inc. is a technology company serving the aerospace and defense industry. It designs, develops and manufactures open architecture computer hardware and software products, including secure embedded processing modules and subsystem ...

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 Circuit switching is a method of implementing a telecommunications network in which two network nodes establish a dedicated communications channel ( circuit) through the network before the nodes may communicate. The circuit guarantees the full b ...

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 The Intel i860 (also known as 80860) is a RISC microprocessor design introduced by Intel in 1989. It is one of Intel's first attempts at an entirely new, high-end instruction set architecture since the failed Intel iAPX 432 from the beginning o ...

, a

PowerPC PowerPC (with the backronym Performance Optimization With Enhanced RISC – Performance Computing, sometimes abbreviated as PPC) is a reduced instruction set computer (RISC) instruction set architecture (ISA) created by the 1991 Apple– IBM ...

, or a group of three SHARC digital signal processors. The fat tree network was particularly well suited to

fast Fourier transform A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in t ...

computations, which customers used for such

signal processing Signal processing is an electrical engineering subfield that focuses on analyzing, modifying and synthesizing '' signals'', such as sound, images, and scientific measurements. Signal processing techniques are used to optimize transmissions, ...

tasks as

radar Radar is a detection system that uses radio waves to determine the distance ('' ranging''), angle, and radial velocity of objects relative to the site. It can be used to detect aircraft, ships, spacecraft, guided missiles, motor vehicles, w ...

sonar Sonar (sound navigation and ranging or sonic navigation and ranging) is a technique that uses sound propagation (usually underwater, as in submarine navigation) to navigate, measure distances ( ranging), communicate with or detect objects on ...

, and medical imaging.

Related topologies

In August 2008, a team of

computer scientist A computer scientist is a person who is trained in the academic study of computer science. Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus ( ...

s at

UCSD The University of California, San Diego (UC San Diego or colloquially, UCSD) is a public land-grant research university in San Diego, California. Established in 1960 near the pre-existing Scripps Institution of Oceanography, UC San Diego is th ...

published a scalable design for network architecture 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 In the field of telecommunications, a Clos network is a kind of multistage circuit-switching network which represents a theoretical idealization of practical, multistage switching systems. It was invented by Edson Erwin in 1938 and first formalize ...

, 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.

Applications in supercomputers

Related topologies

References

Further reading