Tightly Connected Hierarchical Interconnection Networks: Topology, Algorithms and Recursivity in an Asymptotically Optimal Class of Parallel Architectures

In this work we introduce a new method for constructing hierarchical interconnection networks. This approach uses a fully connected higher-level network to connect isomorphic cluster networks, motivated by the base observation that theoretically the clique graph (crossbar) is the best interconnect. The resulting concept is the Tightly Connected Hierarchical Interconnection network, or TCN. We discuss singly as well as multiply linked TCNs and show that single-level TCNs possess superior topological parameters and efficiently implement normal hypercube algorithms, including PRAM simulation. Especially efficient interconnection networks can be built by applying the TCN concept recursively. We prove that recursive TCN architectures exhibit sub-logarithmic topological parameters, reaching asymptotic optimum. The extension of the TCN method to the dynamic domain results in the Tightly Connected Multi-Stage Interconnection Network or TCMIN architecture. The TCMIN interconnect significantly improves the parameters of both the same-size non-hierarchical and hierarchical MINs, while it also has much better congestion and fault-tolerance characteristics than its traditional counterparts. Read more