Study of multistage SIMD interconnection networks

Four SIMD multistage networks - Feng's data manipulator, STARAN flip network, omega network, and indirect binary n-cube—are analyzed. Three parameters - topology, interchange box, and control structure—are defined. It is shown that the latter three networks use equivalent topologies and differences in their capabilities result from the other parameters. An augmented data manipulator network using a modified control structure to perform more single pass interconnections than the other networks is presented. Some problems may be solved more efficiently if the 2n processing elements of an SIMD machine can be partitioned into submachines of size 2r. Single and multiple control partitioning are defined. The capabilities of these multistage networks to perform in these partioned environments are discussed.