Fat-Tree Routing for Transit

André DeHon


As an alternative to using a bidelta network topology for large Transit networks, I consider the requirements to extend the base Transit network into Leiserson's Fat-Tree configuration. Transit will be a high-speed, low-latency, fault-tolerant network interconnection for high performance multi-processor computers. The initial interconnect scheme planned for Transit will use a bidelta style network to support up to 256 processors. Scaling beyond 256 processors by simply extending that network topology will result in a uniform degradation of network latency across processors. A fat-tree network structure will allow the Transit network to be scaled arbitrarily while taking advantage of the locality and universality of fat-trees to minimize the impact of scaling upon network latency. I consider the topology and construction issues for integrating the Transit routing network component and technology into a fat-tree configuration. I also characterize the resulting network's size, locality, and performance and compare these characteristics with those of bidelta networks.

André DeHon <andre@mit.edu> MIT Transit Project MIT AI Lab