Butterfly-Kautz Networks: New Rearrangeable Nonblocking Multistage Interconnection Networks

摘要

In this paper we proposed a new rearrangeable nonblock-ing network, Butterfly-Kautz. The new network is a variant of Kautz networks based on degree two Kautz digraphs. For N x N Butterfly-Kautz networks, the nonblocking routing has a complexity of O(N log_2 N). Butterfly-Kautz networks use a modified looping algorithm found in Benes networks. Compare to Benes networks, Butterfly-Kautz networks utilize less cross-points.