Fat tree
Encyclopedia
Charles E. Leiserson
Charles Eric Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language...
of MIT, is a universal network
Network theory
Network theory is an area of computer science and network science and part of graph theory. It has application in many disciplines including statistical physics, particle physics, computer science, biology, economics, operations research, and sociology...
for provably efficient communication. Unlike an ordinary computer scientist
Computer scientist
A computer scientist is a scientist who has acquired knowledge of computer science, the study of the theoretical foundations of information and computation and their application in computer systems....
's notion of a tree
Tree (data structure)
In computer science, a tree is a widely-used data structure that emulates a hierarchical tree structure with a set of linked nodes.Mathematically, it is an ordered directed tree, more specifically an arborescence: an acyclic connected graph where each node has zero or more children nodes and at...
, which has "skinny" links all over, the links in a fat-tree become "fatter" as one moves up the tree towards the root. By judiciously choosing the fatness of links, the network can be tailored to efficiently use any bandwidth
Bandwidth (computing)
In computer networking and computer science, bandwidth, network bandwidth, data bandwidth, or digital bandwidth is a measure of available or consumed data communication resources expressed in bits/second or multiples of it .Note that in textbooks on wireless communications, modem data transmission,...
made available by packaging and communications technology. In contrast, other communications networks, such as hypercube
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, perpendicular to each other and of the same length.An...
s and meshes, have communication requirements that follow a prespecified mathematical law, and therefore cannot be tailored to specific packaging technologies.
Uses
The Connection MachineConnection Machine
The Connection Machine was a series of supercomputers that grew out of Danny Hillis' research in the early 1980s at MIT on alternatives to the traditional von Neumann architecture of computation...
Model CM5 supercomputer (circa 1990) used a fat tree interconnection network.
Mercury Computer Systems
Mercury Computer Systems
Mercury Computer Systems, Inc. provides high-performance embedded, real-time digital signal and image processing solutions.Mercury designs and builds embedded multicomputers, which may be considered to be either loosely coupled NUMA computers or tightly coupled clusters. Despite being marketed as...
used a hypertree network
Hypertree network
A hypertree network is a network topology that shares some traits with the binary tree network. It is a variation of the fat tree architecture....
, a variant of fat trees, in their multicomputer. From 2 to 360 compute nodes would reside in a circuit switched
Circuit switching
Circuit switching is a methodology of implementing a telecommunications network in which two network nodes establish a dedicated communications channel through the network before the nodes may communicate. The circuit guarantees the full bandwidth of the channel and remains connected for the...
fat tree network, with each node having local memory that could be mapped by any other node. Each node in this heterogeneous system could be an Intel i860
Intel i860
The Intel i860 was a RISC microprocessor from Intel, first released in 1989. The i860 was one of Intel's first attempts at an entirely new, high-end instruction set since the failed Intel i432 from the 1980s...
, a PowerPC
PowerPC
PowerPC is a RISC architecture created by the 1991 Apple–IBM–Motorola alliance, known as AIM...
, or a group of three SHARC
Super Harvard Architecture Single-Chip Computer
The Super Harvard Architecture Single-Chip Computer is a high performance floating-point and fixed-point DSP from Analog Devices,...
DSPs. The fat tree network was particularly well suited to the FFT, which customers used for signal processing
Signal processing
Signal processing is an area of systems engineering, electrical engineering and applied mathematics that deals with operations on or analysis of signals, in either discrete or continuous time...
tasks like radar
Radar
Radar is an object-detection system which uses radio waves to determine the range, altitude, direction, or speed of objects. It can be used to detect aircraft, ships, spacecraft, guided missiles, motor vehicles, weather formations, and terrain. The radar dish or antenna transmits pulses of radio...
, sonar
Sonar
Sonar is a technique that uses sound propagation to navigate, communicate with or detect other vessels...
, medical imaging
Medical imaging
Medical imaging is the technique and process used to create images of the human body for clinical purposes or medical science...
, and so on.
A fat tree network is now preferred for the Infiniband
InfiniBand
InfiniBand is a switched fabric communications link used in high-performance computing and enterprise data centers. Its features include high throughput, low latency, quality of service and failover, and it is designed to be scalable...
cluster architecture.
Related topologies
In late August 2008, a team of computer scientistComputer scientist
A computer scientist is a scientist who has acquired knowledge of computer science, the study of the theoretical foundations of information and computation and their application in computer systems....
s at UCSD published a scalable design for network architecture that uses a topology inspired by the fat tree topology (and misleadingly called a fat-tree in their paper) 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
Clos network
In the field of telecommunications, a Clos network is a kind of multistage circuit switching network, first formalized by Charles Clos in 1953, which represents a theoretical idealization of practical multi-stage telephone switching systems. Clos networks are required when the physical circuit...
, 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. Indeed it is not a tree at all in the graph-theoretic sense
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
, since it is not acyclic. However, many authors continue to use the term in this way.
Further reading
Advanced Computer Architectures: A Design Space Approach, D. Sima, T. Fountain and P. Kacsuk, Addison-Wesley, 1997.