Cornell University
School of Electrical and Computer Engineering
ECE 5970 Chip-Level Interconnection Networks
Spring 2010
Prof. Christopher Batten
207 Upson Hall • Tuesday and Thursday • 10:10–11:25am
home | details | schedule | projects
Fat-Tree Topology for Inter-Chip Networks
C.E. Leiserson. "Fat-Trees: Universal Networks for Hardware-Efficient Supercomputing." IEEE Transactions on Computers, C-34(10):892–901, October 1985.
- Discussion: February 11 shepherded by Allison Smyth
- Online Copy: leiserson-fat-trees-toc1985.pdf (link)
- Related Paper: leiserson-cm5-network-jpdc1996.pdf
This paper is one of the more theoretical papers we will be discussing this semester. The paper introduces a new tree topology, where the channel bandwidth increases as we move closer to the root. Variants of this topology are very popular in system-area networks for computer clusters. Students should have no trouble understanding Sections 1–2 and should spend time trying to interpret Figures 1–2 in light of the topology and router microarchitecture diagrams we have been discussing in class. The routing algorithm introduced in Section 2 is simple and interesting enough that all students should try and understand it. Consider what flow-control mechanism and channel bitwidth are assumed in Section 2. Students should feel free to move quickly through the proofs in Sections 3–6 and focus instead on the general conclusions. Most importantly, try and understand what Leiserson means by the "universality of fat-trees". Do students agree with the final conclusion of the paper expressed in the last paragraph? Students should carefully compare the fat-tree and Clos topologies, especially a "folded Clos" implementation where the input and output switches are co-located together and the middle switches resemble multiple root nodes in a fat-tree. Students might be interested in skimming the JPDC'96 paper which describes the details of the fat-tree network used in the Connection Machine CM-5 multiprocessor (particularly Figures 2–3).