Design of multistage interconnection networks

Abstract

Interconnection networks have extensive applications in switching and reconfigurable multiprocessor systems. A number of multistage networks which can achieve a limited number of permutations have been discussed in the literature [1]. On the other hand, rearrangeable networks [6] have the property that any idle input/output pair can be connected. In most parallel-processing applications, a specified set of input/output connection patterns are required. Often these patterns cannot be achieved by networks like shuffle exchange, cube, Omega and baseline. The chief objective of the paper is to present a methodology for multistage interconnection network design. This design generally requires less switching elements than the rearrangeable network. The paper relies on the formulation of a transmittance matrix for the network. The properties of this matrix are studied with particular focus on rearrangeable networks. A control algorithm which determines the switch states required to achieve a particular permutation is established. The switching algebraic approach is particularly well suited to address the network design problem, because the switch states are explicitly exhibited in the transmittance matrix.