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.

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