A recursively constructed low-cost interconnect

Interconnects play a critical role in various networking environments including data center networks, high performance computing systems, networks-on-chip, etc. An important design concern of interconnects is the hardware cost, especially when the scale increases. In order to achieve lower hardware cost, a lot of previous work leverages a tradeoff between the cost and the performance. In this paper, we alternatively propose a new type of recursively constructed multi-stage interconnect which is both cost efficient and performance guaranteed. The proposed interconnect can deliver the same communication pattern support and path availability as previous designs, yet at the same time achieves lower hardware complexity. We first design a prototype (or base case) for the new interconnect, which consists of three stages of switching modules. Then we use this prototype to decompose and replace the switching modules repeatedly and obtain the recursive case of our interconnect. The hardware cost of the recursively constructed interconnect can be significantly reduced, meanwhile the communication pattern support and path availability are perfectly preserved. For both the base case and the recursive case, we study the properties of the network topology, propose routing algorithms, give performance analysis and calculate cost. We show that the interconnect reduces the hardware cost from the previously best known result O(N3/2), where N is the number of input or output nodes of the interconnect, to O(N11/1-2δ log1.585N), where δ is a small value approaching zero when N increases.