Fat tree

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] k-ary n-trees, the type of fat-trees commonly used in most high-performance networks, were initially formalized in 1997.^[2]

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.^{[citation needed]}

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

^ ^a ^b Leiserson, Charles E (October 1985). "Fat-trees: universal networks for hardware-efficient supercomputing" (PDF). IEEE Transactions on Computers. 34 (10): 892–901. doi:10.1109/TC.1985.6312192. S2CID 8927584.
^ Petrini, Fabrizio (1997). "K-ary n-trees: High performance networks for massively parallel architectures". Proceedings 11th International Parallel Processing Symposium. Vol. doi: 10.1109/IPPS.1997.580853. pp. 87–93. doi:10.1109/IPPS.1997.580853. ISBN 0-8186-7793-7. S2CID 6608892.
^ Leiserson, Charles E.; Abuhamdeh, Zahi S.; Douglas, David C.; Feynman, Carl R.; Ganmukhi, Mahesh N.; Hill, Jeffrey V.; Daniel Hillis, W.; Kuszmaul, Bradley C.; St. Pierre, Margaret A.; Wells, David S.; Wong, Monica C.; Yang, Shaw-Wen; Zak, Robert (1992). "The Network Architecture of the Connection Machine CM-5". SPAA '92 Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures. ACM. pp. 272–285. doi:10.1145/140901.141883. ISBN 978-0-89791-483-3. S2CID 6307237.

[CL85-1] Leiserson, Charles E (October 1985). "Fat-trees: universal networks for hardware-efficient supercomputing" (PDF). IEEE Transactions on Computers. 34 (10): 892–901. doi:10.1109/TC.1985.6312192. S2CID 8927584.

[2] Petrini, Fabrizio (1997). "K-ary n-trees: High performance networks for massively parallel architectures". Proceedings 11th International Parallel Processing Symposium. Vol. doi: 10.1109/IPPS.1997.580853. pp. 87–93. doi:10.1109/IPPS.1997.580853. ISBN 0-8186-7793-7. S2CID 6608892.

[3] Leiserson, Charles E.; Abuhamdeh, Zahi S.; Douglas, David C.; Feynman, Carl R.; Ganmukhi, Mahesh N.; Hill, Jeffrey V.; Daniel Hillis, W.; Kuszmaul, Bradley C.; St. Pierre, Margaret A.; Wells, David S.; Wong, Monica C.; Yang, Shaw-Wen; Zak, Robert (1992). "The Network Architecture of the Connection Machine CM-5". SPAA '92 Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures. ACM. pp. 272–285. doi:10.1145/140901.141883. ISBN 978-0-89791-483-3. S2CID 6307237.

[1]

[2]

[3]