2-dilated flattened butterfly: A nonblocking switching network

The flattened butterfly is known to be a cost efficient topology for high-radix networks. Because of its inherent path diversity, it is able to provide comparable cost/performance with the Clos network in adversarial traffic conditions. However, the flattened butterfly is a blocking network and this blocking behavior can degrade the performance of the network when all the I/O devices are transmitting and receiving data with full bandwidth. In this paper, we show that a 2-dilated flattened butterfly shows the nonblocking behavior which is a critical factor in deciding the quality of any high performance computing system network. We demonstrate the procedure to find static decentralized conflict-free routing schedule for this structure. We also compare the performance of a 2-dilated flattened butterfly with other switching networks. We also show that the 2-dilated flattened butterfly topology can be used to build high speed switching systems with reduced cost.