On generalized fat trees

We introduce and analyze a new family of multiprocesser interconnection networks, called generalized fat trees, which include as special cases the fat trees used for the connection machine architecture CM-5, pruned butterflies, and various other fat trees proposed in the literature. The generalized fat trees provide a formal unifying concept to design and analyse a fat tree based architecture. The extended generalized fat tree network XGFT(h; m₁, ..., m_h; w₁, ..., w_h) of height h has Π_i=1 ^h m_i leaf processors and the inner nodes serve only as switches or routers. Each non-leaf node in level i has m_i children and each non-root has w_i+1 parent nodes. The generalized fat trees provide regularity, symmetry, recursive scalability, maximal fault-tolerance, logarithmic diameter bisection scalability, and permit simple algorithms for fault tolerant self-routing and broadcasting. These networks are also versatile, since they can efficiently embed rings, meshes and tori, trees, pyramids and hypercubes