Minimum Switching Networks
Ricardo Ferreira, Michael Canesche, Kristtopher K. Coelho, José Augusto M. Nacif · 2018
Interconnection is a major challenge in parallel computer systems. In this paper, we introduce a novel scheme for designing interconnection multistage networks (MINs) with a reduced number of switches while retaining the networks' routability. We formalize the problem of multistage network design as a combinatorial search problem and we use Permutation Decision Diagrams (PiDD) to effectively explore the search space. Our method starts with a classical blocking multistage network (e.g., Shuffle-Exchange, Butterfly) and it explores all inter-stage permutation patterns and the minimum number of extra stages. We call the MINs produced by our scheme Minimum Switching Networks (MSNs), which are optimal with respect to the number of switches to build quasi and rearrangeable multistage networks. Empirical results on 8×8 permutation networks show the potential of our method.