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

MIT The Massachusetts Institute of Technology (MIT) is a private research university in Cambridge, Massachusetts, United States. Established in 1861, MIT has played a significant role in the development of many areas of modern technology and sc ...

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, e.g., including only woody plants with secondary growth, only ...

data structure In computer science, a data structure is a data organization 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 relationships amo ...

, 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 Bandwidth commonly refers to: * Bandwidth (signal processing) or ''analog bandwidth'', ''frequency bandwidth'', or ''radio bandwidth'', a measure of the width of a frequency range * Bandwidth (computing), the rate of data transfer, bit rate or thr ...

). 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 Node (networking), 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 ...

, the branches are

data link A data link is a means of telecommunications link, 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 t ...

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

Mesh Medical Subject Headings (MeSH) is a comprehensive controlled vocabulary for the purpose of indexing journal articles and books in the life sciences. It serves as a thesaurus of index terms that facilitates searching. Created and updated by th ...

and

hypercube In geometry, a hypercube is an ''n''-dimensional analogue of a square ( ) and a cube ( ); the special case for is known as a ''tesseract''. It is a closed, compact, convex figure whose 1- skeleton consists of groups of opposite parallel l ...

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

and Sierra, as well as

Tianhe-2 Tianhe-2 or TH-2 (, i.e. 'Milky Way 2') is a 33.86- petaflop 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 Meiko Scientific Ltd. was a British supercomputer company based in Bristol, founded by members of the design team working on the Inmos transputer microprocessor. History In 1985, when Inmos management suggested the release of the transputer be ...

CS-2,

Yellowstone Yellowstone National Park is a List of national parks of the United States, national park of the United States located in the northwest corner of Wyoming, with small portions extending into Montana and Idaho. It was established by the 42nd U ...

, the Earth Simulator, the Cray X2, the Connection Machine CM-5, and various

Altix Altix is a line of server computers and supercomputers produced by Silicon Graphics (and successor company Silicon Graphics International), based on Intel processors. It succeeded the MIPS/IRIX-based Origin 3000 servers. History The line was ...

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

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

, or a group of three SHARC

digital signal processor A digital signal processor (DSP) is a specialized microprocessor chip, with its architecture optimized for the operational needs of digital signal processing. DSPs are fabricated on metal–oxide–semiconductor (MOS) integrated circuit chips. ...

s. 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). A Fourier transform converts a signal from its original domain (often time or space) to a representation in ...

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 audio signal processing, sound, image processing, images, Scalar potential, potential fields, Seismic tomograph ...

tasks as

radar Radar is a system that uses radio waves to determine the distance ('' ranging''), direction ( azimuth and elevation angles), and radial velocity of objects relative to the site. It is a radiodetermination method used to detect and track ...

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

, and

medical imaging Medical imaging is the technique and process of imaging the interior of a body for clinical analysis and medical intervention, as well as visual representation of the function of some organs or tissues (physiology). Medical imaging seeks to revea ...

Related topologies

In August 2008, a team of

computer scientist A computer scientist is a scientist who specializes in the academic study of computer science. Computer scientists typically work on the theoretical side of computation. Although computer scientists can also focus their work and research on ...

s at

UCSD The University of California, San Diego (UC San Diego in communications material, formerly and colloquially UCSD) is a public land-grant research university in San Diego, California, United States. Established in 1960 near the pre-existing ...

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